]>
gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/games.py
ff7fd18d32d5a959d739ff78574b023bf7b33ed1
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.
7 from cvxopt
import matrix
, printing
, solvers
8 from .cones
import CartesianProduct
9 from .errors
import GameUnsolvableException
, PoorScalingException
10 from .matrices
import (append_col
, append_row
, condition_number
, identity
,
11 inner_product
, norm
, specnorm
)
12 from .options
import ABS_TOL
, FLOAT_FORMAT
, DEBUG_FLOAT_FORMAT
14 printing
.options
['dformat'] = FLOAT_FORMAT
19 A representation of the solution of a linear game. It should contain
20 the value of the game, and both players' strategies.
25 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
35 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
37 Create a new Solution object from a game value and two optimal
38 strategies for the players.
40 self
._game
_value
= game_value
41 self
._player
1_optimal
= p1_optimal
42 self
._player
2_optimal
= p2_optimal
46 Return a string describing the solution of a linear game.
48 The three data that are described are,
50 * The value of the game.
51 * The optimal strategy of player one.
52 * The optimal strategy of player two.
54 The two optimal strategy vectors are indented by two spaces.
56 tpl
= 'Game value: {:.7f}\n' \
57 'Player 1 optimal:{:s}\n' \
58 'Player 2 optimal:{:s}'
60 p1_str
= '\n{!s}'.format(self
.player1_optimal())
61 p1_str
= '\n '.join(p1_str
.splitlines())
62 p2_str
= '\n{!s}'.format(self
.player2_optimal())
63 p2_str
= '\n '.join(p2_str
.splitlines())
65 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
70 Return the game value for this solution.
75 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
80 return self
._game
_value
83 def player1_optimal(self
):
85 Return player one's optimal strategy in this solution.
90 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
91 >>> print(s.player1_optimal())
97 return self
._player
1_optimal
100 def player2_optimal(self
):
102 Return player two's optimal strategy in this solution.
107 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
108 >>> print(s.player2_optimal())
114 return self
._player
2_optimal
117 class SymmetricLinearGame
:
119 A representation of a symmetric linear game.
121 The data for a symmetric linear game are,
123 * A "payoff" operator ``L``.
124 * A symmetric cone ``K``.
125 * Two points ``e1`` and ``e2`` in the interior of ``K``.
127 The ambient space is assumed to be the span of ``K``.
129 With those data understood, the game is played as follows. Players
130 one and two choose points :math:`x` and :math:`y` respectively, from
131 their respective strategy sets,
138 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
143 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
147 Afterwards, a "payout" is computed as :math:`\left\langle
148 L\left(x\right), y \right\rangle` and is paid to player one out of
149 player two's pocket. The game is therefore zero sum, and we suppose
150 that player one would like to guarantee himself the largest minimum
151 payout possible. That is, player one wishes to,
156 &\underset{y \in \Delta_{2}}{\min}\left(
157 \left\langle L\left(x\right), y \right\rangle
159 \text{subject to } & x \in \Delta_{1}.
162 Player two has the simultaneous goal to,
167 &\underset{x \in \Delta_{1}}{\max}\left(
168 \left\langle L\left(x\right), y \right\rangle
170 \text{subject to } & y \in \Delta_{2}.
173 These goals obviously conflict (the game is zero sum), but an
174 existence theorem guarantees at least one optimal min-max solution
175 from which neither player would like to deviate. This class is
176 able to find such a solution.
181 L : list of list of float
182 A matrix represented as a list of **rows**. This representation
183 agrees with (for example) `SageMath <https://www.sagemath.org/>`_
184 and `NumPy <https://www.numpy.org/>`_, but not with CVXOPT (whose
185 matrix constructor accepts a list of columns). In reality, ``L``
186 can be any iterable type of the correct length; however, you
187 should be extremely wary of the way we interpret anything other
190 K : dunshire.cones.SymmetricCone
191 The symmetric cone instance over which the game is played.
194 The interior point of ``K`` belonging to player one; it
195 can be of any iterable type having the correct length.
198 The interior point of ``K`` belonging to player two; it
199 can be of any enumerable type having the correct length.
205 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
210 >>> from dunshire import *
211 >>> K = NonnegativeOrthant(3)
212 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
215 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
217 The linear game (L, K, e1, e2) where
221 K = Nonnegative orthant in the real 3-space,
229 Lists can (and probably should) be used for every argument::
231 >>> from dunshire import *
232 >>> K = NonnegativeOrthant(2)
233 >>> L = [[1,0],[0,1]]
236 >>> G = SymmetricLinearGame(L, K, e1, e2)
238 The linear game (L, K, e1, e2) where
241 K = Nonnegative orthant in the real 2-space,
247 The points ``e1`` and ``e2`` can also be passed as some other
248 enumerable type (of the correct length) without much harm, since
249 there is no row/column ambiguity::
252 >>> from dunshire import *
253 >>> K = NonnegativeOrthant(2)
254 >>> L = [[1,0],[0,1]]
255 >>> e1 = cvxopt.matrix([1,1])
257 >>> G = SymmetricLinearGame(L, K, e1, e2)
259 The linear game (L, K, e1, e2) where
262 K = Nonnegative orthant in the real 2-space,
268 However, ``L`` will always be intepreted as a list of rows, even
269 if it is passed as a :class:`cvxopt.base.matrix` which is
270 otherwise indexed by columns::
273 >>> from dunshire import *
274 >>> K = NonnegativeOrthant(2)
275 >>> L = [[1,2],[3,4]]
278 >>> G = SymmetricLinearGame(L, K, e1, e2)
280 The linear game (L, K, e1, e2) where
283 K = Nonnegative orthant in the real 2-space,
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,
305 def __init__(self
, L
, K
, e1
, e2
):
307 Create a new SymmetricLinearGame object.
310 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
311 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
313 # Our input ``L`` is indexed by rows but CVXOPT matrices are
314 # indexed by columns, so we need to transpose the input before
315 # feeding it to CVXOPT.
316 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
318 if not self
._e
1 in K
:
319 raise ValueError('the point e1 must lie in the interior of K')
321 if not self
._e
2 in K
:
322 raise ValueError('the point e2 must lie in the interior of K')
324 # Initial value of cached method.
325 self
._L_specnorm
_value
= None
330 Return a string representation of this game.
332 tpl
= 'The linear game (L, K, e1, e2) where\n' \
337 indented_L
= '\n '.join(str(self
.L()).splitlines())
338 indented_e1
= '\n '.join(str(self
.e1()).splitlines())
339 indented_e2
= '\n '.join(str(self
.e2()).splitlines())
341 return tpl
.format(indented_L
,
349 Return the matrix ``L`` passed to the constructor.
355 The matrix that defines this game's :meth:`payoff` operator.
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)
378 Return the cone over which this game is played.
384 The :class:`SymmetricCone` over which this game is played.
389 >>> from dunshire import *
390 >>> K = NonnegativeOrthant(3)
391 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
394 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
396 Nonnegative orthant in the real 3-space
404 Return player one's interior point.
410 The point interior to :meth:`K` affiliated with player one.
415 >>> from dunshire import *
416 >>> K = NonnegativeOrthant(3)
417 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
420 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
433 Return player two's interior point.
439 The point interior to :meth:`K` affiliated with player one.
444 >>> from dunshire import *
445 >>> K = NonnegativeOrthant(3)
446 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
449 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
460 def payoff(self
, strategy1
, strategy2
):
462 Return the payoff associated with ``strategy1`` and ``strategy2``.
464 The payoff operator takes pairs of strategies to a real
465 number. For example, if player one's strategy is :math:`x` and
466 player two's strategy is :math:`y`, then the associated payoff
467 is :math:`\left\langle L\left(x\right),y \right\rangle \in
468 \mathbb{R}`. Here, :math:`L` denotes the same linear operator as
469 :meth:`L`. This method computes the payoff given the two
476 Player one's strategy.
479 Player two's strategy.
485 The payoff for the game when player one plays ``strategy1``
486 and player two plays ``strategy2``.
491 The value of the game should be the payoff at the optimal
494 >>> from dunshire import *
495 >>> K = NonnegativeOrthant(3)
496 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
499 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
500 >>> soln = SLG.solution()
501 >>> x_bar = soln.player1_optimal()
502 >>> y_bar = soln.player2_optimal()
503 >>> SLG.payoff(x_bar, y_bar) == soln.game_value()
507 return inner_product(self
.L()*strategy1
, strategy2
)
512 Return the dimension of this game.
514 The dimension of a game is not needed for the theory, but it is
515 useful for the implementation. We define the dimension of a game
516 to be the dimension of its underlying cone. Or what is the same,
517 the dimension of the space from which the strategies are chosen.
523 The dimension of the cone :meth:`K`, or of the space where
529 The dimension of a game over the nonnegative quadrant in the
530 plane should be two (the dimension of the plane)::
532 >>> from dunshire import *
533 >>> K = NonnegativeOrthant(2)
534 >>> L = [[1,-5],[-1,2]]
537 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
542 return self
.K().dimension()
547 Return a column of zeros that fits ``K``.
549 This is used in our CVXOPT construction.
553 It is not safe to cache any of the matrices passed to
554 CVXOPT, because it can clobber them.
560 A ``self.dimension()``-by-``1`` column vector of zeros.
565 >>> from dunshire import *
566 >>> K = NonnegativeOrthant(3)
570 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
571 >>> print(SLG._zero())
578 return matrix(0, (self
.dimension(), 1), tc
='d')
583 Return the matrix ``A`` used in our CVXOPT construction.
585 This matrix :math:`A` appears on the right-hand side of
586 :math:`Ax = b` in the `statement of the CVXOPT conelp program
587 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
591 It is not safe to cache any of the matrices passed to
592 CVXOPT, because it can clobber them.
598 A ``1``-by-``(1 + self.dimension())`` row vector. Its first
599 entry is zero, and the rest are the entries of :meth:`e2`.
604 >>> from dunshire import *
605 >>> K = NonnegativeOrthant(3)
606 >>> L = [[1,1,1],[1,1,1],[1,1,1]]
609 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
611 [0.0000000 1.0000000 2.0000000 3.0000000]
615 return matrix([0, self
.e2()], (1, self
.dimension() + 1), 'd')
621 Return the matrix ``G`` used in our CVXOPT construction.
623 Thus matrix :math:`G` appears on the left-hand side of :math:`Gx
624 + s = h` in the `statement of the CVXOPT conelp program
625 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
629 It is not safe to cache any of the matrices passed to
630 CVXOPT, because it can clobber them.
636 A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix.
641 >>> from dunshire import *
642 >>> K = NonnegativeOrthant(3)
643 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
646 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
648 [ 0.0000000 -1.0000000 0.0000000 0.0000000]
649 [ 0.0000000 0.0000000 -1.0000000 0.0000000]
650 [ 0.0000000 0.0000000 0.0000000 -1.0000000]
651 [ 1.0000000 -4.0000000 -5.0000000 -6.0000000]
652 [ 2.0000000 -7.0000000 -8.0000000 -9.0000000]
653 [ 3.0000000 -10.0000000 -11.0000000 -12.0000000]
657 identity_matrix
= identity(self
.dimension())
658 return append_row(append_col(self
._zero
(), -identity_matrix
),
659 append_col(self
.e1(), -self
.L()))
664 Return the vector ``c`` used in our CVXOPT construction.
666 The column vector :math:`c` appears in the objective function
667 value :math:`\left\langle c,x \right\rangle` in the `statement
668 of the CVXOPT conelp program
669 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
673 It is not safe to cache any of the matrices passed to
674 CVXOPT, because it can clobber them.
680 A :meth:`dimension`-by-``1`` column vector.
685 >>> from dunshire import *
686 >>> K = NonnegativeOrthant(3)
687 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
690 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
699 return matrix([-1, self
._zero
()])
704 Return the cone ``C`` used in our CVXOPT construction.
706 This is the cone over which the `CVXOPT conelp program
707 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_
714 The cartesian product of ``K`` with itself.
719 >>> from dunshire import *
720 >>> K = NonnegativeOrthant(3)
721 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
724 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
726 Cartesian product of dimension 6 with 2 factors:
727 * Nonnegative orthant in the real 3-space
728 * Nonnegative orthant in the real 3-space
731 return CartesianProduct(self
._K
, self
._K
)
735 Return the ``h`` vector used in our CVXOPT construction.
737 The :math:`h` vector appears on the right-hand side of :math:`Gx
738 + s = h` in the `statement of the CVXOPT conelp program
739 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
743 It is not safe to cache any of the matrices passed to
744 CVXOPT, because it can clobber them.
750 A ``2*self.dimension()``-by-``1`` column vector of zeros.
755 >>> from dunshire import *
756 >>> K = NonnegativeOrthant(3)
757 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
760 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
772 return matrix([self
._zero
(), self
._zero
()])
778 Return the ``b`` vector used in our CVXOPT construction.
780 The vector :math:`b` appears on the right-hand side of :math:`Ax
781 = b` in the `statement of the CVXOPT conelp program
782 <https://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
784 This method is static because the dimensions and entries of
785 ``b`` are known beforehand, and don't depend on any other
786 properties of the game.
790 It is not safe to cache any of the matrices passed to
791 CVXOPT, because it can clobber them.
797 A ``1``-by-``1`` matrix containing a single entry ``1``.
802 >>> from dunshire import *
803 >>> K = NonnegativeOrthant(3)
804 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
807 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
813 return matrix([1], tc
='d')
816 def player1_start(self
):
818 Return a feasible starting point for player one.
820 This starting point is for the CVXOPT formulation and not for
821 the original game. The basic premise is that if you scale
822 :meth:`e2` by the reciprocal of its squared norm, then you get a
823 point in :meth:`K` that makes a unit inner product with
824 :meth:`e2`. We then get to choose the primal objective function
825 value such that the constraint involving :meth:`L` is satisfied.
831 A dictionary with two keys, ``'x'`` and ``'s'``, which
832 contain the vectors of the same name in the CVXOPT primal
835 The vector ``x`` consists of the primal objective function
836 value concatenated with the strategy (for player one) that
837 achieves it. The vector ``s`` is essentially a dummy
838 variable, and is computed from the equality constraing in
839 the CVXOPT primal problem.
842 p
= self
.e2() / (norm(self
.e2()) ** 2)
843 dist
= self
.K().ball_radius(self
.e1())
844 nu
= - self
._L_specnorm
()/(dist
*norm(self
.e2()))
845 x
= matrix([nu
, p
], (self
.dimension() + 1, 1))
848 return {'x': x, 's': s}
851 def player2_start(self
):
853 Return a feasible starting point for player two.
855 This starting point is for the CVXOPT formulation and not for
856 the original game. The basic premise is that if you scale
857 :meth:`e1` by the reciprocal of its squared norm, then you get a
858 point in :meth:`K` that makes a unit inner product with
859 :meth:`e1`. We then get to choose the dual objective function
860 value such that the constraint involving :meth:`L` is satisfied.
866 A dictionary with two keys, ``'y'`` and ``'z'``, which
867 contain the vectors of the same name in the CVXOPT dual
870 The ``1``-by-``1`` vector ``y`` consists of the dual
871 objective function value. The last :meth:`dimension` entries
872 of the vector ``z`` contain the strategy (for player two)
873 that achieves it. The remaining entries of ``z`` are
874 essentially dummy variables, computed from the equality
875 constraint in the CVXOPT dual problem.
878 q
= self
.e1() / (norm(self
.e1()) ** 2)
879 dist
= self
.K().ball_radius(self
.e2())
880 omega
= self
._L_specnorm
()/(dist
*norm(self
.e1()))
883 z1
= y
*self
.e2() - self
.L().trans()*z2
884 z
= matrix([z1
, z2
], (self
.dimension()*2, 1))
886 return {'y': y, 'z': z}
889 def _L_specnorm(self
):
891 Compute the spectral norm of :meth:`L` and cache it.
893 The spectral norm of the matrix :meth:`L` is used in a few
894 places. Since it can be expensive to compute, we want to cache
895 its value. That is not possible in :func:`specnorm`, which lies
896 outside of a class, so this is the place to do it.
902 A nonnegative real number; the largest singular value of
903 the matrix :meth:`L`.
908 >>> from dunshire import *
909 >>> from dunshire.matrices import specnorm
910 >>> L = [[1,2],[3,4]]
911 >>> K = NonnegativeOrthant(2)
914 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
915 >>> specnorm(SLG.L()) == SLG._L_specnorm()
919 if self
._L_specnorm
_value
is None:
920 self
._L_specnorm
_value
= specnorm(self
.L())
921 return self
._L_specnorm
_value
924 def tolerance_scale(self
, solution
):
927 Return a scaling factor that should be applied to
928 :const:`dunshire.options.ABS_TOL` for this game.
930 When performing certain comparisons, the default tolerance
931 :const:`dunshire.options.ABS_TOL` may not be appropriate. For
932 example, if we expect ``x`` and ``y`` to be within
933 :const:`dunshire.options.ABS_TOL` of each other, than the inner
934 product of ``L*x`` and ``y`` can be as far apart as the spectral
935 norm of ``L`` times the sum of the norms of ``x`` and
936 ``y``. Such a comparison is made in :meth:`solution`, and in
937 many of our unit tests.
939 The returned scaling factor found from the inner product
944 \left\lVert L \right\rVert_{2}
945 \left( \left\lVert \bar{x} \right\rVert
946 + \left\lVert \bar{y} \right\rVert
949 where :math:`\bar{x}` and :math:`\bar{y}` are optimal solutions
950 for players one and two respectively. This scaling factor is not
951 formally justified, but attempting anything smaller leads to
956 Optimal solutions are not unique, so the scaling factor
957 obtained from ``solution`` may not work when comparing other
964 A solution of this game, used to obtain the norms of the
971 A scaling factor to be multiplied by
972 :const:`dunshire.options.ABS_TOL` when
973 making comparisons involving solutions of this game.
978 The spectral norm of ``L`` in this case is around ``5.464``, and
979 the optimal strategies both have norm one, so we expect the
980 tolerance scale to be somewhere around ``2 * 5.464``, or
983 >>> from dunshire import *
984 >>> L = [[1,2],[3,4]]
985 >>> K = NonnegativeOrthant(2)
988 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
989 >>> SLG.tolerance_scale(SLG.solution())
993 norm_p1_opt
= norm(solution
.player1_optimal())
994 norm_p2_opt
= norm(solution
.player2_optimal())
995 scale
= self
._L_specnorm
()*(norm_p1_opt
+ norm_p2_opt
)
997 # Don't return anything smaller than 1... we can't go below
998 # out "minimum tolerance."
1004 Solve this linear game and return a :class:`Solution`.
1010 A :class:`Solution` object describing the game's value and
1011 the optimal strategies of both players.
1015 GameUnsolvableException
1016 If the game could not be solved (if an optimal solution to its
1017 associated cone program was not found).
1019 PoorScalingException
1020 If the game could not be solved because CVXOPT crashed while
1021 trying to take the square root of a negative number.
1026 This example is computed in Gowda and Ravindran in the section
1027 "The value of a Z-transformation"::
1029 >>> from dunshire import *
1030 >>> K = NonnegativeOrthant(3)
1031 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1034 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1035 >>> print(SLG.solution())
1036 Game value: -6.172...
1046 The value of the following game can be computed using the fact
1047 that the identity is invertible::
1049 >>> from dunshire import *
1050 >>> K = NonnegativeOrthant(3)
1051 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
1054 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1055 >>> print(SLG.solution())
1056 Game value: 0.031...
1066 This is another Gowda/Ravindran example that is supposed to have
1067 a negative game value::
1069 >>> from dunshire import *
1070 >>> from dunshire.options import ABS_TOL
1071 >>> L = [[1, -2], [-2, 1]]
1072 >>> K = NonnegativeOrthant(2)
1075 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1076 >>> SLG.solution().game_value() < -ABS_TOL
1079 The following two games are problematic numerically, but we
1080 should be able to solve them::
1082 >>> from dunshire import *
1083 >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
1084 ... [ 1.30481749924621448500, 1.65278664543326403447]]
1085 >>> K = NonnegativeOrthant(2)
1086 >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
1087 >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
1088 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1089 >>> print(SLG.solution())
1090 Game value: 18.767...
1100 >>> from dunshire import *
1101 >>> L = [[1.54159395026049472754, 2.21344728574316684799],
1102 ... [1.33147433507846657541, 1.17913616272988108769]]
1103 >>> K = NonnegativeOrthant(2)
1104 >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
1105 >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
1106 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1107 >>> print(SLG.solution())
1108 Game value: 24.614...
1116 This is another one that was difficult numerically, and caused
1117 trouble even after we fixed the first two::
1119 >>> from dunshire import *
1120 >>> L = [[57.22233908627052301199, 41.70631373437460354126],
1121 ... [83.04512571985074487202, 57.82581810406928468637]]
1122 >>> K = NonnegativeOrthant(2)
1123 >>> e1 = [7.31887017043399268346, 0.89744171905822367474]
1124 >>> e2 = [0.11099824781179848388, 6.12564670639315345113]
1125 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
1126 >>> print(SLG.solution())
1127 Game value: 70.437...
1135 And finally, here's one that returns an "optimal" solution, but
1136 whose primal/dual objective function values are far apart::
1138 >>> from dunshire import *
1139 >>> L = [[ 6.49260076597376212248, -0.60528030227678542019],
1140 ... [ 2.59896077096751731972, -0.97685530240286766457]]
1142 >>> e1 = [1, 0.43749513972645248661]
1143 >>> e2 = [1, 0.46008379832200291260]
1144 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1145 >>> print(SLG.solution())
1146 Game value: 11.596...
1156 opts
= {'show_progress': False}
1157 soln_dict
= solvers
.conelp(self
.c(),
1160 self
.C().cvxopt_dims(),
1163 primalstart
=self
.player1_start(),
1164 dualstart
=self
.player2_start(),
1166 except ValueError as error
:
1167 if str(error
) == 'math domain error':
1168 # Oops, CVXOPT tried to take the square root of a
1169 # negative number. Report some details about the game
1170 # rather than just the underlying CVXOPT crash.
1171 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1172 raise PoorScalingException(self
)
1176 # The optimal strategies are named ``p`` and ``q`` in the
1177 # background documentation, and we need to extract them from
1178 # the CVXOPT ``x`` and ``z`` variables. The objective values
1179 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
1180 # ``x`` and ``y`` variables; however, they're stored
1181 # conveniently as separate entries in the solution dictionary.
1182 p1_value
= -soln_dict
['primal objective']
1183 p2_value
= -soln_dict
['dual objective']
1184 p1_optimal
= soln_dict
['x'][1:]
1185 p2_optimal
= soln_dict
['z'][self
.dimension():]
1187 # The "status" field contains "optimal" if everything went
1188 # according to plan. Other possible values are "primal
1189 # infeasible", "dual infeasible", "unknown", all of which mean
1190 # we didn't get a solution.
1192 # The "infeasible" ones are the worst, since they indicate
1193 # that CVXOPT is convinced the problem is infeasible (and that
1195 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
1196 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1197 raise GameUnsolvableException(self
, soln_dict
)
1199 # For the game value, we could use any of:
1203 # * (p1_value + p2_value)/2
1206 # We want the game value to be the payoff, however, so it
1207 # makes the most sense to just use that, even if it means we
1208 # can't test the fact that p1_value/p2_value are close to the
1210 payoff
= self
.payoff(p1_optimal
, p2_optimal
)
1211 soln
= Solution(payoff
, p1_optimal
, p2_optimal
)
1213 # The "optimal" and "unknown" results, we actually treat the
1214 # same. Even if CVXOPT bails out due to numerical difficulty,
1215 # it will have some candidate points in mind. If those
1216 # candidates are good enough, we take them. We do the same
1217 # check for "optimal" results.
1219 # First we check that the primal/dual objective values are
1220 # close enough because otherwise CVXOPT might return "unknown"
1221 # and give us two points in the cone that are nowhere near
1222 # optimal. And in fact, we need to ensure that they're close
1223 # for "optimal" results, too, because we need to know how
1224 # lenient to be in our testing.
1226 if abs(p1_value
- p2_value
) > self
.tolerance_scale(soln
)*ABS_TOL
:
1227 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1228 raise GameUnsolvableException(self
, soln_dict
)
1230 # And we also check that the points it gave us belong to the
1231 # cone, just in case...
1232 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
1233 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1234 raise GameUnsolvableException(self
, soln_dict
)
1239 def condition(self
):
1241 Return the condition number of this game.
1243 In the CVXOPT construction of this game, two matrices ``G`` and
1244 ``A`` appear. When those matrices are nasty, numerical problems
1245 can show up. We define the condition number of this game to be
1246 the average of the condition numbers of ``G`` and ``A`` in the
1247 CVXOPT construction. If the condition number of this game is
1248 high, you can problems like :class:`PoorScalingException`.
1250 Random testing shows that a condition number of around ``125``
1251 is about the best that we can solve reliably. However, the
1252 failures are intermittent, and you may get lucky with an
1253 ill-conditioned game.
1259 A real number greater than or equal to one that measures how
1260 bad this game is numerically.
1265 >>> from dunshire import *
1266 >>> K = NonnegativeOrthant(1)
1270 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1275 return (condition_number(self
.G()) + condition_number(self
.A()))/2
1280 Return the dual game to this game.
1282 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1283 then its dual is :math:`G^{*} =
1284 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1285 is symmetric, :math:`K^{*} = K`.
1290 >>> from dunshire import *
1291 >>> K = NonnegativeOrthant(3)
1292 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1295 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1296 >>> print(SLG.dual())
1297 The linear game (L, K, e1, e2) where
1301 K = Nonnegative orthant in the real 3-space,
1310 # We pass ``self.L()`` right back into the constructor, because
1311 # it will be transposed there. And keep in mind that ``self._K``
1313 return SymmetricLinearGame(self
.L(),