]>
gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/games.py
9610802e4ffd4108d2c244b2c36a9e44084427cd
2 Symmetric linear games and their solutions.
4 This module contains the main :class:`SymmetricLinearGame` class that
5 knows how to solve a linear game.
8 from cvxopt
import matrix
, printing
, solvers
9 from .cones
import CartesianProduct
10 from .errors
import GameUnsolvableException
, PoorScalingException
11 from .matrices
import append_col
, append_row
, identity
14 printing
.options
['dformat'] = options
.FLOAT_FORMAT
15 solvers
.options
['show_progress'] = options
.VERBOSE
20 A representation of the solution of a linear game. It should contain
21 the value of the game, and both players' strategies.
26 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
27 Game value: 10.0000000
36 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
38 Create a new Solution object from a game value and two optimal
39 strategies for the players.
41 self
._game
_value
= game_value
42 self
._player
1_optimal
= p1_optimal
43 self
._player
2_optimal
= p2_optimal
47 Return a string describing the solution of a linear game.
49 The three data that are described are,
51 * The value of the game.
52 * The optimal strategy of player one.
53 * The optimal strategy of player two.
55 The two optimal strategy vectors are indented by two spaces.
57 tpl
= 'Game value: {:.7f}\n' \
58 'Player 1 optimal:{:s}\n' \
59 'Player 2 optimal:{:s}'
61 p1_str
= '\n{!s}'.format(self
.player1_optimal())
62 p1_str
= '\n '.join(p1_str
.splitlines())
63 p2_str
= '\n{!s}'.format(self
.player2_optimal())
64 p2_str
= '\n '.join(p2_str
.splitlines())
66 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
71 Return the game value for this solution.
76 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
81 return self
._game
_value
84 def player1_optimal(self
):
86 Return player one's optimal strategy in this solution.
91 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
92 >>> print(s.player1_optimal())
98 return self
._player
1_optimal
101 def player2_optimal(self
):
103 Return player two's optimal strategy in this solution.
108 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
109 >>> print(s.player2_optimal())
115 return self
._player
2_optimal
118 class SymmetricLinearGame
:
120 A representation of a symmetric linear game.
122 The data for a symmetric linear game are,
124 * A "payoff" operator ``L``.
125 * A symmetric cone ``K``.
126 * Two points ``e1`` and ``e2`` in the interior of ``K``.
128 The ambient space is assumed to be the span of ``K``.
130 With those data understood, the game is played as follows. Players
131 one and two choose points :math:`x` and :math:`y` respectively, from
132 their respective strategy sets,
139 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
144 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
148 Afterwards, a "payout" is computed as :math:`\left\langle
149 L\left(x\right), y \right\rangle` and is paid to player one out of
150 player two's pocket. The game is therefore zero sum, and we suppose
151 that player one would like to guarantee himself the largest minimum
152 payout possible. That is, player one wishes to,
157 &\underset{y \in \Delta_{2}}{\min}\left(
158 \left\langle L\left(x\right), y \right\rangle
160 \text{subject to } & x \in \Delta_{1}.
163 Player two has the simultaneous goal to,
168 &\underset{x \in \Delta_{1}}{\max}\left(
169 \left\langle L\left(x\right), y \right\rangle
171 \text{subject to } & y \in \Delta_{2}.
174 These goals obviously conflict (the game is zero sum), but an
175 existence theorem guarantees at least one optimal min-max solution
176 from which neither player would like to deviate. This class is
177 able to find such a solution.
182 L : list of list of float
183 A matrix represented as a list of ROWS. This representation
184 agrees with (for example) SageMath and NumPy, but not with CVXOPT
185 (whose matrix constructor accepts a list of columns).
187 K : :class:`SymmetricCone`
188 The symmetric cone instance over which the game is played.
191 The interior point of ``K`` belonging to player one; it
192 can be of any iterable type having the correct length.
195 The interior point of ``K`` belonging to player two; it
196 can be of any enumerable type having the correct length.
202 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
207 >>> from dunshire import *
208 >>> K = NonnegativeOrthant(3)
209 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
212 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
214 The linear game (L, K, e1, e2) where
218 K = Nonnegative orthant in the real 3-space,
226 Lists can (and probably should) be used for every argument::
228 >>> from dunshire import *
229 >>> K = NonnegativeOrthant(2)
230 >>> L = [[1,0],[0,1]]
233 >>> G = SymmetricLinearGame(L, K, e1, e2)
235 The linear game (L, K, e1, e2) where
238 K = Nonnegative orthant in the real 2-space,
244 The points ``e1`` and ``e2`` can also be passed as some other
245 enumerable type (of the correct length) without much harm, since
246 there is no row/column ambiguity::
250 >>> from dunshire import *
251 >>> K = NonnegativeOrthant(2)
252 >>> L = [[1,0],[0,1]]
253 >>> e1 = cvxopt.matrix([1,1])
254 >>> e2 = numpy.matrix([1,1])
255 >>> G = SymmetricLinearGame(L, K, e1, e2)
257 The linear game (L, K, e1, e2) where
260 K = Nonnegative orthant in the real 2-space,
266 However, ``L`` will always be intepreted as a list of rows, even
267 if it is passed as a :class:`cvxopt.base.matrix` which is
268 otherwise indexed by columns::
271 >>> from dunshire import *
272 >>> K = NonnegativeOrthant(2)
273 >>> L = [[1,2],[3,4]]
276 >>> G = SymmetricLinearGame(L, K, e1, e2)
278 The linear game (L, K, e1, e2) where
281 K = Nonnegative orthant in the real 2-space,
286 >>> L = cvxopt.matrix(L)
291 >>> G = SymmetricLinearGame(L, K, e1, e2)
293 The linear game (L, K, e1, e2) where
296 K = Nonnegative orthant in the real 2-space,
303 def __init__(self
, L
, K
, e1
, e2
):
305 Create a new SymmetricLinearGame object.
308 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
309 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
311 # Our input ``L`` is indexed by rows but CVXOPT matrices are
312 # indexed by columns, so we need to transpose the input before
313 # feeding it to CVXOPT.
314 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
316 if not self
._e
1 in K
:
317 raise ValueError('the point e1 must lie in the interior of K')
319 if not self
._e
2 in K
:
320 raise ValueError('the point e2 must lie in the interior of K')
324 Return a string representation of this game.
326 tpl
= 'The linear game (L, K, e1, e2) where\n' \
331 indented_L
= '\n '.join(str(self
._L).splitlines())
332 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
333 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
334 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
339 Solve this linear game and return a :class:`Solution`.
345 A :class:`Solution` object describing the game's value and
346 the optimal strategies of both players.
350 GameUnsolvableException
351 If the game could not be solved (if an optimal solution to its
352 associated cone program was not found).
355 If the game could not be solved because CVXOPT crashed while
356 trying to take the square root of a negative number.
361 This example is computed in Gowda and Ravindran in the section
362 "The value of a Z-transformation"::
364 >>> from dunshire import *
365 >>> K = NonnegativeOrthant(3)
366 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
369 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
370 >>> print(SLG.solution())
371 Game value: -6.1724138
381 The value of the following game can be computed using the fact
382 that the identity is invertible::
384 >>> from dunshire import *
385 >>> K = NonnegativeOrthant(3)
386 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
389 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
390 >>> print(SLG.solution())
391 Game value: 0.0312500
402 # The cone "C" that appears in the statement of the CVXOPT
404 C
= CartesianProduct(self
._K
, self
._K
)
406 # The column vector "b" that appears on the right-hand side of
407 # Ax = b in the statement of the CVXOPT conelp program.
408 b
= matrix([1], tc
='d')
410 # A column of zeros that fits K.
411 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
413 # The column vector "h" that appears on the right-hand side of
414 # Gx + s = h in the statement of the CVXOPT conelp program.
415 h
= matrix([zero
, zero
])
417 # The column vector "c" that appears in the objective function
418 # value <c,x> in the statement of the CVXOPT conelp program.
419 c
= matrix([-1, zero
])
421 # The matrix "G" that appears on the left-hand side of Gx + s = h
422 # in the statement of the CVXOPT conelp program.
423 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
424 append_col(self
._e
1, -self
._L))
426 # The matrix "A" that appears on the right-hand side of Ax = b
427 # in the statement of the CVXOPT conelp program.
428 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
430 # Actually solve the thing and obtain a dictionary describing
433 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
434 except ValueError as e
:
435 if str(e
) == 'math domain error':
436 # Oops, CVXOPT tried to take the square root of a
437 # negative number. Report some details about the game
438 # rather than just the underlying CVXOPT crash.
439 raise PoorScalingException(self
)
443 # The optimal strategies are named ``p`` and ``q`` in the
444 # background documentation, and we need to extract them from
445 # the CVXOPT ``x`` and ``z`` variables. The objective values
446 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
447 # ``x`` and ``y`` variables; however, they're stored
448 # conveniently as separate entries in the solution dictionary.
449 p1_value
= -soln_dict
['primal objective']
450 p2_value
= -soln_dict
['dual objective']
451 p1_optimal
= soln_dict
['x'][1:]
452 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
454 # The "status" field contains "optimal" if everything went
455 # according to plan. Other possible values are "primal
456 # infeasible", "dual infeasible", "unknown", all of which mean
457 # we didn't get a solution. The "infeasible" ones are the
458 # worst, since they indicate that CVXOPT is convinced the
459 # problem is infeasible (and that cannot happen).
460 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
461 raise GameUnsolvableException(self
, soln_dict
)
462 elif soln_dict
['status'] == 'unknown':
463 # When we get a status of "unknown", we may still be able
464 # to salvage a solution out of the returned
465 # dictionary. Often this is the result of numerical
466 # difficulty and we can simply check that the primal/dual
467 # objectives match (within a tolerance) and that the
468 # primal/dual optimal solutions are within the cone (to a
469 # tolerance as well).
470 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
471 raise GameUnsolvableException(self
, soln_dict
)
472 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
473 raise GameUnsolvableException(self
, soln_dict
)
475 return Solution(p1_value
, p1_optimal
, p2_optimal
)
480 Return the dual game to this game.
482 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
483 then its dual is :math:`G^{*} =
484 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
485 is symmetric, :math:`K^{*} = K`.
490 >>> from dunshire import *
491 >>> K = NonnegativeOrthant(3)
492 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
495 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
496 >>> print(SLG.dual())
497 The linear game (L, K, e1, e2) where
501 K = Nonnegative orthant in the real 3-space,
510 # We pass ``self._L`` right back into the constructor, because
511 # it will be transposed there. And keep in mind that ``self._K``
513 return SymmetricLinearGame(self
._L,