]>
gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/games.py
1f3a15a0b261c723f7f5c65d66d255fd2b9fdc99
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
, condition_number
, identity
14 printing
.options
['dformat'] = options
.FLOAT_FORMAT
18 A representation of the solution of a linear game. It should contain
19 the value of the game, and both players' strategies.
24 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
25 Game value: 10.0000000
34 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
36 Create a new Solution object from a game value and two optimal
37 strategies for the players.
39 self
._game
_value
= game_value
40 self
._player
1_optimal
= p1_optimal
41 self
._player
2_optimal
= p2_optimal
45 Return a string describing the solution of a linear game.
47 The three data that are described are,
49 * The value of the game.
50 * The optimal strategy of player one.
51 * The optimal strategy of player two.
53 The two optimal strategy vectors are indented by two spaces.
55 tpl
= 'Game value: {:.7f}\n' \
56 'Player 1 optimal:{:s}\n' \
57 'Player 2 optimal:{:s}'
59 p1_str
= '\n{!s}'.format(self
.player1_optimal())
60 p1_str
= '\n '.join(p1_str
.splitlines())
61 p2_str
= '\n{!s}'.format(self
.player2_optimal())
62 p2_str
= '\n '.join(p2_str
.splitlines())
64 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
69 Return the game value for this solution.
74 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
79 return self
._game
_value
82 def player1_optimal(self
):
84 Return player one's optimal strategy in this solution.
89 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
90 >>> print(s.player1_optimal())
96 return self
._player
1_optimal
99 def player2_optimal(self
):
101 Return player two's optimal strategy in this solution.
106 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
107 >>> print(s.player2_optimal())
113 return self
._player
2_optimal
116 class SymmetricLinearGame
:
118 A representation of a symmetric linear game.
120 The data for a symmetric linear game are,
122 * A "payoff" operator ``L``.
123 * A symmetric cone ``K``.
124 * Two points ``e1`` and ``e2`` in the interior of ``K``.
126 The ambient space is assumed to be the span of ``K``.
128 With those data understood, the game is played as follows. Players
129 one and two choose points :math:`x` and :math:`y` respectively, from
130 their respective strategy sets,
137 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
142 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
146 Afterwards, a "payout" is computed as :math:`\left\langle
147 L\left(x\right), y \right\rangle` and is paid to player one out of
148 player two's pocket. The game is therefore zero sum, and we suppose
149 that player one would like to guarantee himself the largest minimum
150 payout possible. That is, player one wishes to,
155 &\underset{y \in \Delta_{2}}{\min}\left(
156 \left\langle L\left(x\right), y \right\rangle
158 \text{subject to } & x \in \Delta_{1}.
161 Player two has the simultaneous goal to,
166 &\underset{x \in \Delta_{1}}{\max}\left(
167 \left\langle L\left(x\right), y \right\rangle
169 \text{subject to } & y \in \Delta_{2}.
172 These goals obviously conflict (the game is zero sum), but an
173 existence theorem guarantees at least one optimal min-max solution
174 from which neither player would like to deviate. This class is
175 able to find such a solution.
180 L : list of list of float
181 A matrix represented as a list of ROWS. This representation
182 agrees with (for example) SageMath and NumPy, but not with CVXOPT
183 (whose matrix constructor accepts a list of columns).
185 K : :class:`SymmetricCone`
186 The symmetric cone instance over which the game is played.
189 The interior point of ``K`` belonging to player one; it
190 can be of any iterable type having the correct length.
193 The interior point of ``K`` belonging to player two; it
194 can be of any enumerable type having the correct length.
200 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
205 >>> from dunshire import *
206 >>> K = NonnegativeOrthant(3)
207 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
210 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
212 The linear game (L, K, e1, e2) where
216 K = Nonnegative orthant in the real 3-space,
223 Condition((L, K, e1, e2)) = 31.834...
225 Lists can (and probably should) be used for every argument::
227 >>> from dunshire import *
228 >>> K = NonnegativeOrthant(2)
229 >>> L = [[1,0],[0,1]]
232 >>> G = SymmetricLinearGame(L, K, e1, e2)
234 The linear game (L, K, e1, e2) where
237 K = Nonnegative orthant in the real 2-space,
242 Condition((L, K, e1, e2)) = 1.707...
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,
265 Condition((L, K, e1, e2)) = 1.707...
267 However, ``L`` will always be intepreted as a list of rows, even
268 if it is passed as a :class:`cvxopt.base.matrix` which is
269 otherwise indexed by columns::
272 >>> from dunshire import *
273 >>> K = NonnegativeOrthant(2)
274 >>> L = [[1,2],[3,4]]
277 >>> G = SymmetricLinearGame(L, K, e1, e2)
279 The linear game (L, K, e1, e2) where
282 K = Nonnegative orthant in the real 2-space,
287 Condition((L, K, e1, e2)) = 6.073...
288 >>> L = cvxopt.matrix(L)
293 >>> G = SymmetricLinearGame(L, K, e1, e2)
295 The linear game (L, K, e1, e2) where
298 K = Nonnegative orthant in the real 2-space,
303 Condition((L, K, e1, e2)) = 6.073...
306 def __init__(self
, L
, K
, e1
, e2
):
308 Create a new SymmetricLinearGame object.
311 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
312 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
314 # Our input ``L`` is indexed by rows but CVXOPT matrices are
315 # indexed by columns, so we need to transpose the input before
316 # feeding it to CVXOPT.
317 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
319 if not self
._e
1 in K
:
320 raise ValueError('the point e1 must lie in the interior of K')
322 if not self
._e
2 in K
:
323 raise ValueError('the point e2 must lie in the interior of K')
329 Return a string representation of this game.
331 tpl
= 'The linear game (L, K, e1, e2) where\n' \
336 ' Condition((L, K, e1, e2)) = {:f}.'
337 indented_L
= '\n '.join(str(self
._L).splitlines())
338 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
339 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
341 return tpl
.format(indented_L
,
350 Return a column of zeros that fits ``K``.
352 This is used in our CVXOPT construction.
356 It is not safe to cache any of the matrices passed to
357 CVXOPT, because it can clobber them.
363 A ``K.dimension()``-by-``1`` column vector of zeros.
368 >>> from dunshire import *
369 >>> K = NonnegativeOrthant(3)
373 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
374 >>> print(SLG._zero())
381 return matrix(0, (self
._K
.dimension(), 1), tc
='d')
386 Return the matrix ``A`` used in our CVXOPT construction.
388 This matrix ``A`` appears on the right-hand side of ``Ax = b``
389 in the statement of the CVXOPT conelp program.
393 It is not safe to cache any of the matrices passed to
394 CVXOPT, because it can clobber them.
400 A ``1``-by-``(1 + K.dimension())`` row vector. Its first
401 entry is zero, and the rest are the entries of ``e2``.
406 >>> from dunshire import *
407 >>> K = NonnegativeOrthant(3)
408 >>> L = [[1,1,1],[1,1,1],[1,1,1]]
411 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
413 [0.0000000 1.0000000 2.0000000 3.0000000]
417 return matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
423 Return the matrix ``G`` used in our CVXOPT construction.
425 Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
426 in the statement of the CVXOPT conelp program.
430 It is not safe to cache any of the matrices passed to
431 CVXOPT, because it can clobber them.
437 A ``2*K.dimension()``-by-``1 + K.dimension()`` matrix.
442 >>> from dunshire import *
443 >>> K = NonnegativeOrthant(3)
444 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
447 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
449 [ 0.0000000 -1.0000000 0.0000000 0.0000000]
450 [ 0.0000000 0.0000000 -1.0000000 0.0000000]
451 [ 0.0000000 0.0000000 0.0000000 -1.0000000]
452 [ 1.0000000 -4.0000000 -5.0000000 -6.0000000]
453 [ 2.0000000 -7.0000000 -8.0000000 -9.0000000]
454 [ 3.0000000 -10.0000000 -11.0000000 -12.0000000]
458 I
= identity(self
._K
.dimension())
459 return append_row(append_col(self
._zero
(), -I
),
460 append_col(self
._e
1, -self
._L))
465 Return the vector ``c`` used in our CVXOPT construction.
467 The column vector ``c`` appears in the objective function
468 value ``<c,x>`` in the statement of the CVXOPT conelp program.
472 It is not safe to cache any of the matrices passed to
473 CVXOPT, because it can clobber them.
479 A ``K.dimension()``-by-``1`` column vector.
484 >>> from dunshire import *
485 >>> K = NonnegativeOrthant(3)
486 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
489 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
498 return matrix([-1, self
._zero
()])
503 Return the cone ``C`` used in our CVXOPT construction.
505 The cone ``C`` is the cone over which the conelp program takes
512 The cartesian product of ``K`` with itself.
517 >>> from dunshire import *
518 >>> K = NonnegativeOrthant(3)
519 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
522 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
524 Cartesian product of dimension 6 with 2 factors:
525 * Nonnegative orthant in the real 3-space
526 * Nonnegative orthant in the real 3-space
529 return CartesianProduct(self
._K
, self
._K
)
533 Return the ``h`` vector used in our CVXOPT construction.
535 The ``h`` vector appears on the right-hand side of :math:`Gx + s
536 = h` in the statement of the CVXOPT conelp program.
540 It is not safe to cache any of the matrices passed to
541 CVXOPT, because it can clobber them.
547 A ``2*K.dimension()``-by-``1`` column vector of zeros.
552 >>> from dunshire import *
553 >>> K = NonnegativeOrthant(3)
554 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
557 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
569 return matrix([self
._zero
(), self
._zero
()])
573 Return the ``b`` vector used in our CVXOPT construction.
575 The vector ``b`` appears on the right-hand side of :math:`Ax =
576 b` in the statement of the CVXOPT conelp program.
580 It is not safe to cache any of the matrices passed to
581 CVXOPT, because it can clobber them.
587 A ``1``-by-``1`` matrix containing a single entry ``1``.
592 >>> from dunshire import *
593 >>> K = NonnegativeOrthant(3)
594 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
597 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
603 return matrix([1], tc
='d')
606 def _try_solution(self
, tolerance
):
608 Solve this linear game within ``tolerance``, if possible.
610 This private function is the one that does all of the actual
611 work for :meth:`solution`. This method accepts a ``tolerance``,
612 and what :meth:`solution` does is call this method twice with
613 two different tolerances. First it tries a strict tolerance, and
614 then it tries a looser one.
618 If you try to be smart and precompute the matrices used by
619 this function (the ones passed to ``conelp``), then you're
620 going to shoot yourself in the foot. CVXOPT can and will
621 clobber some (but not all) of its input matrices. This isn't
622 performance sensitive, so play it safe.
628 The absolute tolerance to pass to the CVXOPT solver.
634 A :class:`Solution` object describing the game's value and
635 the optimal strategies of both players.
639 GameUnsolvableException
640 If the game could not be solved (if an optimal solution to its
641 associated cone program was not found).
644 If the game could not be solved because CVXOPT crashed while
645 trying to take the square root of a negative number.
650 This game can be solved easily, so the first attempt in
651 :meth:`solution` should succeed::
653 >>> from dunshire import *
654 >>> from dunshire.matrices import norm
655 >>> from dunshire.options import ABS_TOL
656 >>> K = NonnegativeOrthant(3)
657 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
660 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
661 >>> s1 = SLG.solution()
662 >>> s2 = SLG._try_solution(options.ABS_TOL)
663 >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL
665 >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL
667 >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL
672 solvers
.options
['show_progress'] = options
.VERBOSE
673 solvers
.options
['abs_tol'] = tolerance
674 soln_dict
= solvers
.conelp(self
._c
(),
677 self
._C
().cvxopt_dims(),
680 except ValueError as e
:
681 if str(e
) == 'math domain error':
682 # Oops, CVXOPT tried to take the square root of a
683 # negative number. Report some details about the game
684 # rather than just the underlying CVXOPT crash.
685 raise PoorScalingException(self
)
689 # The optimal strategies are named ``p`` and ``q`` in the
690 # background documentation, and we need to extract them from
691 # the CVXOPT ``x`` and ``z`` variables. The objective values
692 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
693 # ``x`` and ``y`` variables; however, they're stored
694 # conveniently as separate entries in the solution dictionary.
695 p1_value
= -soln_dict
['primal objective']
696 p2_value
= -soln_dict
['dual objective']
697 p1_optimal
= soln_dict
['x'][1:]
698 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
700 # The "status" field contains "optimal" if everything went
701 # according to plan. Other possible values are "primal
702 # infeasible", "dual infeasible", "unknown", all of which mean
703 # we didn't get a solution. The "infeasible" ones are the
704 # worst, since they indicate that CVXOPT is convinced the
705 # problem is infeasible (and that cannot happen).
706 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
707 raise GameUnsolvableException(self
, soln_dict
)
708 elif soln_dict
['status'] == 'unknown':
709 # When we get a status of "unknown", we may still be able
710 # to salvage a solution out of the returned
711 # dictionary. Often this is the result of numerical
712 # difficulty and we can simply check that the primal/dual
713 # objectives match (within a tolerance) and that the
714 # primal/dual optimal solutions are within the cone (to a
715 # tolerance as well).
717 # The fudge factor of two is basically unjustified, but
718 # makes intuitive sense when you imagine that the primal
719 # value could be under the true optimal by ``ABS_TOL``
720 # and the dual value could be over by the same amount.
722 if abs(p1_value
- p2_value
) > tolerance
:
723 raise GameUnsolvableException(self
, soln_dict
)
724 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
725 raise GameUnsolvableException(self
, soln_dict
)
727 return Solution(p1_value
, p1_optimal
, p2_optimal
)
732 Solve this linear game and return a :class:`Solution`.
738 A :class:`Solution` object describing the game's value and
739 the optimal strategies of both players.
743 GameUnsolvableException
744 If the game could not be solved (if an optimal solution to its
745 associated cone program was not found).
748 If the game could not be solved because CVXOPT crashed while
749 trying to take the square root of a negative number.
754 This example is computed in Gowda and Ravindran in the section
755 "The value of a Z-transformation"::
757 >>> from dunshire import *
758 >>> K = NonnegativeOrthant(3)
759 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
762 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
763 >>> print(SLG.solution())
764 Game value: -6.1724138
774 The value of the following game can be computed using the fact
775 that the identity is invertible::
777 >>> from dunshire import *
778 >>> K = NonnegativeOrthant(3)
779 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
782 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
783 >>> print(SLG.solution())
784 Game value: 0.0312500
796 # First try with a stricter tolerance. Who knows, it might
797 # work. If it does, we prefer that solution.
798 return self
._try
_solution
(options
.ABS_TOL
/ 10)
800 except (PoorScalingException
, GameUnsolvableException
):
801 # Ok, that didn't work. Let's try it with the default
802 # tolerance, and whatever happens, happens.
803 return self
._try
_solution
(options
.ABS_TOL
)
808 Return the condition number of this game.
810 In the CVXOPT construction of this game, two matrices ``G`` and
811 ``A`` appear. When those matrices are nasty, numerical problems
812 can show up. We define the condition number of this game to be
813 the average of the condition numbers of ``G`` and ``A`` in the
814 CVXOPT construction. If the condition number of this game is
815 high, then you can expect numerical difficulty (such as
816 :class:`PoorScalingException`).
822 A real number greater than or equal to one that measures how
823 bad this game is numerically.
828 >>> from dunshire import *
829 >>> K = NonnegativeOrthant(1)
833 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
834 >>> actual = SLG.condition()
835 >>> expected = 1.8090169943749477
836 >>> abs(actual - expected) < options.ABS_TOL
840 return (condition_number(self
._G
()) + condition_number(self
._A
()))/2
845 Return the dual game to this game.
847 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
848 then its dual is :math:`G^{*} =
849 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
850 is symmetric, :math:`K^{*} = K`.
855 >>> from dunshire import *
856 >>> K = NonnegativeOrthant(3)
857 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
860 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
861 >>> print(SLG.dual())
862 The linear game (L, K, e1, e2) where
866 K = Nonnegative orthant in the real 3-space,
873 Condition((L, K, e1, e2)) = 44.476...
876 # We pass ``self._L`` right back into the constructor, because
877 # it will be transposed there. And keep in mind that ``self._K``
879 return SymmetricLinearGame(self
._L,