]>
gitweb.michael.orlitzky.com - dunshire.git/blob - games.py
80f5f8ae2a46d09f15e34546c511edeca286f4fa
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
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).
357 This example is computed in Gowda and Ravindran in the section
358 "The value of a Z-transformation"::
360 >>> from dunshire import *
361 >>> K = NonnegativeOrthant(3)
362 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
365 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
366 >>> print(SLG.solution())
367 Game value: -6.1724138
377 The value of the following game can be computed using the fact
378 that the identity is invertible::
380 >>> from dunshire import *
381 >>> K = NonnegativeOrthant(3)
382 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
385 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
386 >>> print(SLG.solution())
387 Game value: 0.0312500
398 # The cone "C" that appears in the statement of the CVXOPT
400 C
= CartesianProduct(self
._K
, self
._K
)
402 # The column vector "b" that appears on the right-hand side of
403 # Ax = b in the statement of the CVXOPT conelp program.
404 b
= matrix([1], tc
='d')
406 # A column of zeros that fits K.
407 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
409 # The column vector "h" that appears on the right-hand side of
410 # Gx + s = h in the statement of the CVXOPT conelp program.
411 h
= matrix([zero
, zero
])
413 # The column vector "c" that appears in the objective function
414 # value <c,x> in the statement of the CVXOPT conelp program.
415 c
= matrix([-1, zero
])
417 # The matrix "G" that appears on the left-hand side of Gx + s = h
418 # in the statement of the CVXOPT conelp program.
419 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
420 append_col(self
._e
1, -self
._L))
422 # The matrix "A" that appears on the right-hand side of Ax = b
423 # in the statement of the CVXOPT conelp program.
424 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
426 # Actually solve the thing and obtain a dictionary describing
428 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
430 # The optimal strategies are named ``p`` and ``q`` in the
431 # background documentation, and we need to extract them from
432 # the CVXOPT ``x`` and ``z`` variables. The objective values
433 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
434 # ``x`` and ``y`` variables; however, they're stored
435 # conveniently as separate entries in the solution dictionary.
436 p1_value
= -soln_dict
['primal objective']
437 p2_value
= -soln_dict
['dual objective']
438 p1_optimal
= soln_dict
['x'][1:]
439 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
441 # The "status" field contains "optimal" if everything went
442 # according to plan. Other possible values are "primal
443 # infeasible", "dual infeasible", "unknown", all of which mean
444 # we didn't get a solution. The "infeasible" ones are the
445 # worst, since they indicate that CVXOPT is convinced the
446 # problem is infeasible (and that cannot happen).
447 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
448 raise GameUnsolvableException(self
, soln_dict
)
449 elif soln_dict
['status'] == 'unknown':
450 # When we get a status of "unknown", we may still be able
451 # to salvage a solution out of the returned
452 # dictionary. Often this is the result of numerical
453 # difficulty and we can simply check that the primal/dual
454 # objectives match (within a tolerance) and that the
455 # primal/dual optimal solutions are within the cone (to a
456 # tolerance as well).
457 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
458 raise GameUnsolvableException(self
, soln_dict
)
459 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
460 raise GameUnsolvableException(self
, soln_dict
)
462 return Solution(p1_value
, p1_optimal
, p2_optimal
)
467 Return the dual game to this game.
469 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
470 then its dual is :math:`G^{*} =
471 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
472 is symmetric, :math:`K^{*} = K`.
477 >>> from dunshire import *
478 >>> K = NonnegativeOrthant(3)
479 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
482 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
483 >>> print(SLG.dual())
484 The linear game (L, K, e1, e2) where
488 K = Nonnegative orthant in the real 3-space,
497 # We pass ``self._L`` right back into the constructor, because
498 # it will be transposed there. And keep in mind that ``self._K``
500 return SymmetricLinearGame(self
._L,