]>
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 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
45 Game value: 10.0000000
54 tpl
= 'Game value: {:.7f}\n' \
55 'Player 1 optimal:{:s}\n' \
56 'Player 2 optimal:{:s}'
58 p1_str
= '\n{!s}'.format(self
.player1_optimal())
59 p1_str
= '\n '.join(p1_str
.splitlines())
60 p2_str
= '\n{!s}'.format(self
.player2_optimal())
61 p2_str
= '\n '.join(p2_str
.splitlines())
63 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
68 Return the game value for this solution.
70 return self
._game
_value
73 def player1_optimal(self
):
75 Return player one's optimal strategy in this solution.
77 return self
._player
1_optimal
80 def player2_optimal(self
):
82 Return player two's optimal strategy in this solution.
84 return self
._player
2_optimal
87 class SymmetricLinearGame
:
89 A representation of a symmetric linear game.
91 The data for a linear game are,
93 * A "payoff" operator ``L``.
95 * A point ``e`` in the interior of ``K``.
96 * A point ``f`` in the interior of the dual of ``K``.
98 In a symmetric game, the cone ``K`` is be self-dual. We therefore
99 name the two interior points ``e1`` and ``e2`` to indicate that
100 they come from the same cone but are "chosen" by players one and
103 The ambient space is assumed to be the span of ``K``.
105 def __init__(self
, L
, K
, e1
, e2
):
109 - ``L`` -- an n-by-b matrix represented as a list of lists
112 - ``K`` -- a SymmetricCone instance.
114 - ``e1`` -- the interior point of ``K`` belonging to player one,
117 - ``e2`` -- the interior point of ``K`` belonging to player two,
122 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
123 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
124 self
._L = matrix(L
, (K
.dimension(), K
.dimension()))
126 if not K
.contains_strict(self
._e
1):
127 raise ValueError('the point e1 must lie in the interior of K')
129 if not K
.contains_strict(self
._e
2):
130 raise ValueError('the point e2 must lie in the interior of K')
134 Return a string representatoin of this game.
138 >>> from cones import NonnegativeOrthant
139 >>> K = NonnegativeOrthant(3)
140 >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
143 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
145 The linear game (L, K, e1, e2) where
149 K = Nonnegative orthant in the real 3-space,
158 tpl
= 'The linear game (L, K, e1, e2) where\n' \
163 L_str
= '\n '.join(str(self
._L).splitlines())
164 e1_str
= '\n '.join(str(self
._e
1).splitlines())
165 e2_str
= '\n '.join(str(self
._e
2).splitlines())
166 return tpl
.format(L_str
, str(self
._K
), e1_str
, e2_str
)
171 Solve this linear game and return a Solution object.
175 If the cone program associated with this game could be
176 successfully solved, then a Solution object containing the
177 game's value and optimal strategies is returned. If the game
178 could *not* be solved -- which should never happen -- then a
179 GameUnsolvableException is raised. It can be printed to get the
180 raw output from CVXOPT.
184 This example is computed in Gowda and Ravindran in the section
185 "The value of a Z-transformation":
187 >>> from cones import NonnegativeOrthant
188 >>> K = NonnegativeOrthant(3)
189 >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
192 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
193 >>> print(SLG.solution())
194 Game value: -6.1724138
204 The value of the following game can be computed using the fact
205 that the identity is invertible:
207 >>> from cones import NonnegativeOrthant
208 >>> K = NonnegativeOrthant(3)
209 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
212 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
213 >>> print(SLG.solution())
214 Game value: 0.0312500
225 # The cone "C" that appears in the statement of the CVXOPT
227 C
= CartesianProduct(self
._K
, self
._K
)
229 # The column vector "b" that appears on the right-hand side of
230 # Ax = b in the statement of the CVXOPT conelp program.
231 b
= matrix([1], tc
='d')
233 # A column of zeros that fits K.
234 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
236 # The column vector "h" that appears on the right-hand side of
237 # Gx + s = h in the statement of the CVXOPT conelp program.
238 h
= matrix([zero
, zero
])
240 # The column vector "c" that appears in the objective function
241 # value <c,x> in the statement of the CVXOPT conelp program.
242 c
= matrix([-1, zero
])
244 # The matrix "G" that appears on the left-hand side of Gx + s = h
245 # in the statement of the CVXOPT conelp program.
246 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
247 append_col(self
._e
1, -self
._L))
249 # The matrix "A" that appears on the right-hand side of Ax = b
250 # in the statement of the CVXOPT conelp program.
251 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
253 # Actually solve the thing and obtain a dictionary describing
255 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
257 # The "status" field contains "optimal" if everything went
258 # according to plan. Other possible values are "primal
259 # infeasible", "dual infeasible", "unknown", all of which
260 # mean we didn't get a solution. That should never happen,
261 # because by construction our game has a solution, and thus
262 # the cone program should too.
263 if soln_dict
['status'] != 'optimal':
264 raise GameUnsolvableException(soln_dict
)
266 p1_value
= soln_dict
['x'][0]
267 p1_optimal
= soln_dict
['x'][1:]
268 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
270 return Solution(p1_value
, p1_optimal
, p2_optimal
)
274 Return the dual game to this game.
278 >>> from cones import NonnegativeOrthant
279 >>> K = NonnegativeOrthant(3)
280 >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
283 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
284 >>> print(SLG.dual())
285 The linear game (L, K, e1, e2) where
289 K = Nonnegative orthant in the real 3-space,
298 return SymmetricLinearGame(self
._L.trans(),
299 self
._K
, # Since "K" is symmetric.