src/dunshire/symmetric_linear_game.py

   1 """
   2 Symmetric linear games and their solutions.
   3
   4 This module contains the main SymmetricLinearGame class that knows how
   5 to solve a linear game.
   6 """
   7
   8 from cvxopt import matrix, printing, solvers
   9
  10 from cones import CartesianProduct
  11 from errors import GameUnsolvableException
  12 from matrices import append_col, append_row, identity
  13
  14 printing.options['dformat'] = '%.7f'
  15 solvers.options['show_progress'] = False
  16
  17
  18 class Solution:
  19     """
  20     A representation of the solution of a linear game. It should contain
  21     the value of the game, and both players' strategies.
  22     """
  23     def __init__(self, game_value, p1_optimal, p2_optimal):
  24         """
  25         Create a new Solution object from a game value and two optimal
  26         strategies for the players.
  27         """
  28         self._game_value = game_value
  29         self._player1_optimal = p1_optimal
  30         self._player2_optimal = p2_optimal
  31
  32     def __str__(self):
  33         """
  34         Return a string describing the solution of a linear game.
  35
  36         The three data that are described are,
  37
  38           * The value of the game.
  39           * The optimal strategy of player one.
  40           * The optimal strategy of player two.
  41
  42         """
  43
  44         tpl = 'Game value: {:.7f}\n' \
  45               'Player 1 optimal:{:s}\n' \
  46               'Player 2 optimal:{:s}\n'
  47
  48         p1_str = '\n{!s}'.format(self.player1_optimal())
  49         p1_str = '\n  '.join(p1_str.splitlines())
  50         p2_str = '\n{!s}'.format(self.player2_optimal())
  51         p2_str = '\n  '.join(p2_str.splitlines())
  52
  53         return tpl.format(self.game_value(), p1_str, p2_str)
  54
  55
  56     def game_value(self):
  57         """
  58         Return the game value for this solution.
  59         """
  60         return self._game_value
  61
  62
  63     def player1_optimal(self):
  64         """
  65         Return player one's optimal strategy in this solution.
  66         """
  67         return self._player1_optimal
  68
  69
  70     def player2_optimal(self):
  71         """
  72         Return player two's optimal strategy in this solution.
  73         """
  74         return self._player2_optimal
  75
  76
  77 class SymmetricLinearGame:
  78     """
  79     A representation of a symmetric linear game.
  80
  81     The data for a linear game are,
  82
  83       * A "payoff" operator ``L``.
  84       * A cone ``K``.
  85       * A point ``e`` in the interior of ``K``.
  86       * A point ``f`` in the interior of the dual of ``K``.
  87
  88     In a symmetric game, the cone ``K`` is be self-dual. We therefore
  89     name the two interior points ``e1`` and ``e2`` to indicate that
  90     they come from the same cone but are "chosen" by players one and
  91     two respectively.
  92
  93     The ambient space is assumed to be the span of ``K``.
  94     """
  95     def __init__(self, L, K, e1, e2):
  96         """
  97         INPUT:
  98
  99           - ``L`` -- an n-by-b matrix represented as a list of lists
 100              of real numbers.
 101
 102           - ``K`` -- a SymmetricCone instance.
 103
 104           - ``e1`` -- the interior point of ``K`` belonging to player one,
 105                       as a column vector.
 106
 107           - ``e2`` -- the interior point of ``K`` belonging to player two,
 108                       as a column vector.
 109
 110         """
 111         self._K = K
 112         self._e1 = matrix(e1, (K.dimension(), 1))
 113         self._e2 = matrix(e2, (K.dimension(), 1))
 114         self._L = matrix(L, (K.dimension(), K.dimension()))
 115
 116         if not K.contains_strict(self._e1):
 117             raise ValueError('the point e1 must lie in the interior of K')
 118
 119         if not K.contains_strict(self._e2):
 120             raise ValueError('the point e2 must lie in the interior of K')
 121
 122     def __str__(self):
 123         """
 124         Return a string representatoin of this game.
 125         """
 126         return "a game"
 127
 128     def solution(self):
 129         """
 130         Solve this linear game and return a Solution object.
 131
 132         OUTPUT:
 133
 134         If the cone program associated with this game could be
 135         successfully solved, then a Solution object containing the
 136         game's value and optimal strategies is returned. If the game
 137         could *not* be solved -- which should never happen -- then a
 138         GameUnsolvableException is raised. It can be printed to get the
 139         raw output from CVXOPT.
 140         """
 141         # The cone "C" that appears in the statement of the CVXOPT
 142         # conelp program.
 143         C = CartesianProduct(self._K, self._K)
 144
 145         # The column vector "b" that appears on the right-hand side of
 146         # Ax = b in the statement of the CVXOPT conelp program.
 147         b = matrix([1], tc='d')
 148
 149         # A column of zeros that fits K.
 150         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 151
 152         # The column vector "h" that appears on the right-hand side of
 153         # Gx + s = h in the statement of the CVXOPT conelp program.
 154         h = matrix([zero, zero])
 155
 156         # The column vector "c" that appears in the objective function
 157         # value <c,x> in the statement of the CVXOPT conelp program.
 158         c = matrix([-1, zero])
 159
 160         # The matrix "G" that appears on the left-hand side of Gx + s = h
 161         # in the statement of the CVXOPT conelp program.
 162         G = append_row(append_col(zero, -identity(self._K.dimension())),
 163                        append_col(self._e1, -self._L))
 164
 165         # The matrix "A" that appears on the right-hand side of Ax = b
 166         # in the statement of the CVXOPT conelp program.
 167         A = matrix([0, self._e1], (1, self._K.dimension() + 1), 'd')
 168
 169         # Actually solve the thing and obtain a dictionary describing
 170         # what happened.
 171         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 172
 173         # The "status" field contains "optimal" if everything went
 174         # according to plan. Other possible values are "primal
 175         # infeasible", "dual infeasible", "unknown", all of which
 176         # mean we didn't get a solution. That should never happen,
 177         # because by construction our game has a solution, and thus
 178         # the cone program should too.
 179         if soln_dict['status'] != 'optimal':
 180             raise GameUnsolvableException(soln_dict)
 181
 182         p1_value = soln_dict['x'][0]
 183         p1_optimal = soln_dict['x'][1:]
 184         p2_optimal = soln_dict['z'][self._K.dimension():]
 185
 186         return Solution(p1_value, p1_optimal, p2_optimal)
 187
 188     def dual(self):
 189         """
 190         Return the dual game to this game.
 191         """
 192         return SymmetricLinearGame(self._L.trans(),
 193                                    self._K, # Since "K" is symmetric.
 194                                    self._e2,
 195                                    self._e1)