]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/symmetric_linear_game.py
2 Symmetric linear games and their solutions.
4 This module contains the main SymmetricLinearGame class that knows how
5 to solve a linear game.
8 from cvxopt
import matrix
, printing
, solvers
10 from cones
import CartesianProduct
11 from errors
import GameUnsolvableException
12 from matrices
import append_col
, append_row
, identity
14 printing
.options
['dformat'] = '%.7f'
15 solvers
.options
['show_progress'] = False
20 A representation of the solution of a linear game. It should contain
21 the value of the game, and both players' strategies.
23 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
25 Create a new Solution object from a game value and two optimal
26 strategies for the players.
28 self
._game
_value
= game_value
29 self
._player
1_optimal
= p1_optimal
30 self
._player
2_optimal
= p2_optimal
34 Return a string describing the solution of a linear game.
36 The three data that are described are,
38 * The value of the game.
39 * The optimal strategy of player one.
40 * The optimal strategy of player two.
44 tpl
= 'Game value: {:.7f}\n' \
45 'Player 1 optimal:{:s}\n' \
46 'Player 2 optimal:{:s}\n'
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())
53 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
58 Return the game value for this solution.
60 return self
._game
_value
63 def player1_optimal(self
):
65 Return player one's optimal strategy in this solution.
67 return self
._player
1_optimal
70 def player2_optimal(self
):
72 Return player two's optimal strategy in this solution.
74 return self
._player
2_optimal
77 class SymmetricLinearGame
:
79 A representation of a symmetric linear game.
81 The data for a linear game are,
83 * A "payoff" operator ``L``.
85 * A point ``e`` in the interior of ``K``.
86 * A point ``f`` in the interior of the dual of ``K``.
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
93 The ambient space is assumed to be the span of ``K``.
95 def __init__(self
, L
, K
, e1
, e2
):
99 - ``L`` -- an n-by-b matrix represented as a list of lists
102 - ``K`` -- a SymmetricCone instance.
104 - ``e1`` -- the interior point of ``K`` belonging to player one,
107 - ``e2`` -- the interior point of ``K`` belonging to player two,
112 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
113 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
114 self
._L = matrix(L
, (K
.dimension(), K
.dimension()))
116 if not K
.contains_strict(self
._e
1):
117 raise ValueError('the point e1 must lie in the interior of K')
119 if not K
.contains_strict(self
._e
2):
120 raise ValueError('the point e2 must lie in the interior of K')
124 Return a string representatoin of this game.
130 Solve this linear game and return a Solution object.
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.
141 # The cone "C" that appears in the statement of the CVXOPT
143 C
= CartesianProduct(self
._K
, self
._K
)
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')
149 # A column of zeros that fits K.
150 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
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
])
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
])
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
._e
1, -self
._L))
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
._e
1], (1, self
._K
.dimension() + 1), 'd')
169 # Actually solve the thing and obtain a dictionary describing
171 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
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
)
182 p1_value
= soln_dict
['x'][0]
183 p1_optimal
= soln_dict
['x'][1:]
184 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
186 return Solution(p1_value
, p1_optimal
, p2_optimal
)
190 Return the dual game to this game.
192 return SymmetricLinearGame(self
._L.trans(),
193 self
._K
, # Since "K" is symmetric.