]>
gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/games.py
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 and NumPy, but not with CVXOPT
184 (whose matrix constructor accepts a list of columns).
186 K : :class:`SymmetricCone`
187 The symmetric cone instance over which the game is played.
190 The interior point of ``K`` belonging to player one; it
191 can be of any iterable type having the correct length.
194 The interior point of ``K`` belonging to player two; it
195 can be of any enumerable type having the correct length.
201 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
206 >>> from dunshire import *
207 >>> K = NonnegativeOrthant(3)
208 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
211 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
213 The linear game (L, K, e1, e2) where
217 K = Nonnegative orthant in the real 3-space,
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,
243 The points ``e1`` and ``e2`` can also be passed as some other
244 enumerable type (of the correct length) without much harm, since
245 there is no row/column ambiguity::
249 >>> from dunshire import *
250 >>> K = NonnegativeOrthant(2)
251 >>> L = [[1,0],[0,1]]
252 >>> e1 = cvxopt.matrix([1,1])
253 >>> e2 = numpy.matrix([1,1])
254 >>> G = SymmetricLinearGame(L, K, e1, e2)
256 The linear game (L, K, e1, e2) where
259 K = Nonnegative orthant in the real 2-space,
265 However, ``L`` will always be intepreted as a list of rows, even
266 if it is passed as a :class:`cvxopt.base.matrix` which is
267 otherwise indexed by columns::
270 >>> from dunshire import *
271 >>> K = NonnegativeOrthant(2)
272 >>> L = [[1,2],[3,4]]
275 >>> G = SymmetricLinearGame(L, K, e1, e2)
277 The linear game (L, K, e1, e2) where
280 K = Nonnegative orthant in the real 2-space,
285 >>> L = cvxopt.matrix(L)
290 >>> G = SymmetricLinearGame(L, K, e1, e2)
292 The linear game (L, K, e1, e2) where
295 K = Nonnegative orthant in the real 2-space,
302 def __init__(self
, L
, K
, e1
, e2
):
304 Create a new SymmetricLinearGame object.
307 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
308 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
310 # Our input ``L`` is indexed by rows but CVXOPT matrices are
311 # indexed by columns, so we need to transpose the input before
312 # feeding it to CVXOPT.
313 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
315 if not self
._e
1 in K
:
316 raise ValueError('the point e1 must lie in the interior of K')
318 if not self
._e
2 in K
:
319 raise ValueError('the point e2 must lie in the interior of K')
321 # Initial value of cached method.
322 self
._L_specnorm
_value
= None
327 Return a string representation of this game.
329 tpl
= 'The linear game (L, K, e1, e2) where\n' \
334 indented_L
= '\n '.join(str(self
.L()).splitlines())
335 indented_e1
= '\n '.join(str(self
.e1()).splitlines())
336 indented_e2
= '\n '.join(str(self
.e2()).splitlines())
338 return tpl
.format(indented_L
,
346 Return the matrix ``L`` passed to the constructor.
352 The matrix that defines this game's :meth:`payoff` operator.
357 >>> from dunshire import *
358 >>> K = NonnegativeOrthant(3)
359 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
362 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
375 Return the cone over which this game is played.
381 The :class:`SymmetricCone` over which this game is played.
386 >>> from dunshire import *
387 >>> K = NonnegativeOrthant(3)
388 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
391 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
393 Nonnegative orthant in the real 3-space
401 Return player one's interior point.
407 The point interior to :meth:`K` affiliated with player one.
412 >>> from dunshire import *
413 >>> K = NonnegativeOrthant(3)
414 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
417 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
430 Return player two's interior point.
436 The point interior to :meth:`K` affiliated with player one.
441 >>> from dunshire import *
442 >>> K = NonnegativeOrthant(3)
443 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
446 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
457 def payoff(self
, strategy1
, strategy2
):
459 Return the payoff associated with ``strategy1`` and ``strategy2``.
461 The payoff operator takes pairs of strategies to a real
462 number. For example, if player one's strategy is :math:`x` and
463 player two's strategy is :math:`y`, then the associated payoff
464 is :math:`\left\langle L\left(x\right),y \right\rangle` \in
465 \mathbb{R}. Here, :math:`L` denotes the same linear operator as
466 :meth:`L`. This method computes the payoff given the two
473 Player one's strategy.
476 Player two's strategy.
482 The payoff for the game when player one plays ``strategy1``
483 and player two plays ``strategy2``.
488 The value of the game should be the payoff at the optimal
491 >>> from dunshire import *
492 >>> from dunshire.options import ABS_TOL
493 >>> K = NonnegativeOrthant(3)
494 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
497 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
498 >>> soln = SLG.solution()
499 >>> x_bar = soln.player1_optimal()
500 >>> y_bar = soln.player2_optimal()
501 >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL
505 return inner_product(self
.L()*strategy1
, strategy2
)
510 Return the dimension of this game.
512 The dimension of a game is not needed for the theory, but it is
513 useful for the implementation. We define the dimension of a game
514 to be the dimension of its underlying cone. Or what is the same,
515 the dimension of the space from which the strategies are chosen.
521 The dimension of the cone :meth:`K`, or of the space where
527 The dimension of a game over the nonnegative quadrant in the
528 plane should be two (the dimension of the plane)::
530 >>> from dunshire import *
531 >>> K = NonnegativeOrthant(2)
532 >>> L = [[1,-5],[-1,2]]
535 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
540 return self
.K().dimension()
545 Return a column of zeros that fits ``K``.
547 This is used in our CVXOPT construction.
551 It is not safe to cache any of the matrices passed to
552 CVXOPT, because it can clobber them.
558 A ``self.dimension()``-by-``1`` column vector of zeros.
563 >>> from dunshire import *
564 >>> K = NonnegativeOrthant(3)
568 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
569 >>> print(SLG._zero())
576 return matrix(0, (self
.dimension(), 1), tc
='d')
581 Return the matrix ``A`` used in our CVXOPT construction.
583 This matrix :math`A` appears on the right-hand side of :math:`Ax
584 = b` in the statement of the CVXOPT conelp program.
588 It is not safe to cache any of the matrices passed to
589 CVXOPT, because it can clobber them.
595 A ``1``-by-``(1 + self.dimension())`` row vector. Its first
596 entry is zero, and the rest are the entries of ``e2``.
601 >>> from dunshire import *
602 >>> K = NonnegativeOrthant(3)
603 >>> L = [[1,1,1],[1,1,1],[1,1,1]]
606 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
608 [0.0000000 1.0000000 2.0000000 3.0000000]
612 return matrix([0, self
.e2()], (1, self
.dimension() + 1), 'd')
618 Return the matrix ``G`` used in our CVXOPT construction.
620 Thus matrix :math:`G` appears on the left-hand side of :math:`Gx
621 + s = h` in the statement of the CVXOPT conelp program.
625 It is not safe to cache any of the matrices passed to
626 CVXOPT, because it can clobber them.
632 A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix.
637 >>> from dunshire import *
638 >>> K = NonnegativeOrthant(3)
639 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
642 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
644 [ 0.0000000 -1.0000000 0.0000000 0.0000000]
645 [ 0.0000000 0.0000000 -1.0000000 0.0000000]
646 [ 0.0000000 0.0000000 0.0000000 -1.0000000]
647 [ 1.0000000 -4.0000000 -5.0000000 -6.0000000]
648 [ 2.0000000 -7.0000000 -8.0000000 -9.0000000]
649 [ 3.0000000 -10.0000000 -11.0000000 -12.0000000]
653 identity_matrix
= identity(self
.dimension())
654 return append_row(append_col(self
._zero
(), -identity_matrix
),
655 append_col(self
.e1(), -self
.L()))
660 Return the vector ``c`` used in our CVXOPT construction.
662 The column vector :math:`c` appears in the objective function
663 value :math:`\left\langle c,x \right\rangle` in the statement of
664 the CVXOPT conelp program.
668 It is not safe to cache any of the matrices passed to
669 CVXOPT, because it can clobber them.
675 A ``self.dimension()``-by-``1`` column vector.
680 >>> from dunshire import *
681 >>> K = NonnegativeOrthant(3)
682 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
685 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
694 return matrix([-1, self
._zero
()])
699 Return the cone ``C`` used in our CVXOPT construction.
701 This is the cone over which the conelp program takes place.
707 The cartesian product of ``K`` with itself.
712 >>> from dunshire import *
713 >>> K = NonnegativeOrthant(3)
714 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
717 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
719 Cartesian product of dimension 6 with 2 factors:
720 * Nonnegative orthant in the real 3-space
721 * Nonnegative orthant in the real 3-space
724 return CartesianProduct(self
._K
, self
._K
)
728 Return the ``h`` vector used in our CVXOPT construction.
730 The :math:`h` vector appears on the right-hand side of :math:`Gx + s
731 = h` in the statement of the CVXOPT conelp program.
735 It is not safe to cache any of the matrices passed to
736 CVXOPT, because it can clobber them.
742 A ``2*self.dimension()``-by-``1`` column vector of zeros.
747 >>> from dunshire import *
748 >>> K = NonnegativeOrthant(3)
749 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
752 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
764 return matrix([self
._zero
(), self
._zero
()])
770 Return the ``b`` vector used in our CVXOPT construction.
772 The vector ``b`` appears on the right-hand side of :math:`Ax =
773 b` in the statement of the CVXOPT conelp program.
775 This method is static because the dimensions and entries of
776 ``b`` are known beforehand, and don't depend on any other
777 properties of the game.
781 It is not safe to cache any of the matrices passed to
782 CVXOPT, because it can clobber them.
788 A ``1``-by-``1`` matrix containing a single entry ``1``.
793 >>> from dunshire import *
794 >>> K = NonnegativeOrthant(3)
795 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
798 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
804 return matrix([1], tc
='d')
807 def player1_start(self
):
809 Return a feasible starting point for player one.
811 This starting point is for the CVXOPT formulation and not for
812 the original game. The basic premise is that if you scale
813 :meth:`e2` by the reciprocal of its squared norm, then you get a
814 point in :meth:`K` that makes a unit inner product with
815 :meth:`e2`. We then get to choose the primal objective function
816 value such that the constraint involving :meth:`L` is satisfied.
822 A dictionary with two keys, 'x' and 's', which contain the
823 vectors of the same name in the CVXOPT primal problem
826 The vector ``x`` consists of the primal objective function
827 value concatenated with the strategy (for player one) that
828 achieves it. The vector ``s`` is essentially a dummy
829 variable, and is computed from the equality constraing in
830 the CVXOPT primal problem.
833 p
= self
.e2() / (norm(self
.e2()) ** 2)
834 dist
= self
.K().ball_radius(self
.e1())
835 nu
= - self
._L_specnorm
()/(dist
*norm(self
.e2()))
836 x
= matrix([nu
, p
], (self
.dimension() + 1, 1))
839 return {'x': x, 's': s}
842 def player2_start(self
):
844 Return a feasible starting point for player two.
846 This starting point is for the CVXOPT formulation and not for
847 the original game. The basic premise is that if you scale
848 :meth:`e1` by the reciprocal of its squared norm, then you get a
849 point in :meth:`K` that makes a unit inner product with
850 :meth:`e1`. We then get to choose the dual objective function
851 value such that the constraint involving :meth:`L` is satisfied.
857 A dictionary with two keys, 'y' and 'z', which contain the
858 vectors of the same name in the CVXOPT dual problem
861 The ``1``-by-``1`` vector ``y`` consists of the dual
862 objective function value. The last :meth:`dimension` entries
863 of the vector ``z`` contain the strategy (for player two)
864 that achieves it. The remaining entries of ``z`` are
865 essentially dummy variables, computed from the equality
866 constraint in the CVXOPT dual problem.
869 q
= self
.e1() / (norm(self
.e1()) ** 2)
870 dist
= self
.K().ball_radius(self
.e2())
871 omega
= self
._L_specnorm
()/(dist
*norm(self
.e1()))
874 z1
= y
*self
.e2() - self
.L().trans()*z2
875 z
= matrix([z1
, z2
], (self
.dimension()*2, 1))
877 return {'y': y, 'z': z}
880 def _L_specnorm(self
):
882 Compute the spectral norm of :meth:`L` and cache it.
884 The spectral norm of the matrix :meth:`L` is used in a few
885 places. Since it can be expensive to compute, we want to cache
886 its value. That is not possible in :func:`specnorm`, which lies
887 outside of a class, so this is the place to do it.
893 A nonnegative real number; the largest singular value of
894 the matrix :meth:`L`.
899 >>> from dunshire import *
900 >>> from dunshire.matrices import specnorm
901 >>> L = [[1,2],[3,4]]
902 >>> K = NonnegativeOrthant(2)
905 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
906 >>> specnorm(SLG.L()) == SLG._L_specnorm()
910 if self
._L_specnorm
_value
is None:
911 self
._L_specnorm
_value
= specnorm(self
.L())
912 return self
._L_specnorm
_value
915 def tolerance_scale(self
, solution
):
917 Return a scaling factor that should be applied to ``ABS_TOL``
920 When performing certain comparisons, the default tolernace
921 ``ABS_TOL`` may not be appropriate. For example, if we expect
922 ``x`` and ``y`` to be within ``ABS_TOL`` of each other, than the
923 inner product of ``L*x`` and ``y`` can be as far apart as the
924 spectral norm of ``L`` times the sum of the norms of ``x`` and
925 ``y``. Such a comparison is made in :meth:`solution`, and in
926 many of our unit tests.
928 The returned scaling factor found from the inner product mentioned
933 \left\lVert L \right\rVert_{2}
934 \left( \left\lVert \bar{x} \right\rVert
935 + \left\lVert \bar{y} \right\rVert
938 where :math:`\bar{x}` and :math:`\bar{y}` are optimal solutions
939 for players one and two respectively. This scaling factor is not
940 formally justified, but attempting anything smaller leads to
945 Optimal solutions are not unique, so the scaling factor
946 obtained from ``solution`` may not work when comparing other
953 A solution of this game, used to obtain the norms of the
960 A scaling factor to be multiplied by ``ABS_TOL`` when
961 making comparisons involving solutions of this game.
966 The spectral norm of ``L`` in this case is around ``5.464``, and
967 the optimal strategies both have norm one, so we expect the
968 tolerance scale to be somewhere around ``2 * 5.464``, or
971 >>> from dunshire import *
972 >>> L = [[1,2],[3,4]]
973 >>> K = NonnegativeOrthant(2)
976 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
977 >>> SLG.tolerance_scale(SLG.solution())
981 norm_p1_opt
= norm(solution
.player1_optimal())
982 norm_p2_opt
= norm(solution
.player2_optimal())
983 scale
= self
._L_specnorm
()*(norm_p1_opt
+ norm_p2_opt
)
985 # Don't return anything smaller than 1... we can't go below
986 # out "minimum tolerance."
992 Solve this linear game and return a :class:`Solution`.
998 A :class:`Solution` object describing the game's value and
999 the optimal strategies of both players.
1003 GameUnsolvableException
1004 If the game could not be solved (if an optimal solution to its
1005 associated cone program was not found).
1007 PoorScalingException
1008 If the game could not be solved because CVXOPT crashed while
1009 trying to take the square root of a negative number.
1014 This example is computed in Gowda and Ravindran in the section
1015 "The value of a Z-transformation"::
1017 >>> from dunshire import *
1018 >>> K = NonnegativeOrthant(3)
1019 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1022 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1023 >>> print(SLG.solution())
1024 Game value: -6.172...
1034 The value of the following game can be computed using the fact
1035 that the identity is invertible::
1037 >>> from dunshire import *
1038 >>> K = NonnegativeOrthant(3)
1039 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
1042 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1043 >>> print(SLG.solution())
1044 Game value: 0.031...
1054 This is another Gowda/Ravindran example that is supposed to have
1055 a negative game value::
1057 >>> from dunshire import *
1058 >>> from dunshire.options import ABS_TOL
1059 >>> L = [[1, -2], [-2, 1]]
1060 >>> K = NonnegativeOrthant(2)
1063 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1064 >>> SLG.solution().game_value() < -ABS_TOL
1067 The following two games are problematic numerically, but we
1068 should be able to solve them::
1070 >>> from dunshire import *
1071 >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
1072 ... [ 1.30481749924621448500, 1.65278664543326403447]]
1073 >>> K = NonnegativeOrthant(2)
1074 >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
1075 >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
1076 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1077 >>> print(SLG.solution())
1078 Game value: 18.767...
1088 >>> from dunshire import *
1089 >>> L = [[1.54159395026049472754, 2.21344728574316684799],
1090 ... [1.33147433507846657541, 1.17913616272988108769]]
1091 >>> K = NonnegativeOrthant(2)
1092 >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
1093 >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
1094 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1095 >>> print(SLG.solution())
1096 Game value: 24.614...
1104 This is another one that was difficult numerically, and caused
1105 trouble even after we fixed the first two::
1107 >>> from dunshire import *
1108 >>> L = [[57.22233908627052301199, 41.70631373437460354126],
1109 ... [83.04512571985074487202, 57.82581810406928468637]]
1110 >>> K = NonnegativeOrthant(2)
1111 >>> e1 = [7.31887017043399268346, 0.89744171905822367474]
1112 >>> e2 = [0.11099824781179848388, 6.12564670639315345113]
1113 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
1114 >>> print(SLG.solution())
1115 Game value: 70.437...
1123 And finally, here's one that returns an "optimal" solution, but
1124 whose primal/dual objective function values are far apart::
1126 >>> from dunshire import *
1127 >>> L = [[ 6.49260076597376212248, -0.60528030227678542019],
1128 ... [ 2.59896077096751731972, -0.97685530240286766457]]
1130 >>> e1 = [1, 0.43749513972645248661]
1131 >>> e2 = [1, 0.46008379832200291260]
1132 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1133 >>> print(SLG.solution())
1134 Game value: 11.596...
1144 opts
= {'show_progress': False}
1145 soln_dict
= solvers
.conelp(self
.c(),
1148 self
.C().cvxopt_dims(),
1151 primalstart
=self
.player1_start(),
1152 dualstart
=self
.player2_start(),
1154 except ValueError as error
:
1155 if str(error
) == 'math domain error':
1156 # Oops, CVXOPT tried to take the square root of a
1157 # negative number. Report some details about the game
1158 # rather than just the underlying CVXOPT crash.
1159 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1160 raise PoorScalingException(self
)
1164 # The optimal strategies are named ``p`` and ``q`` in the
1165 # background documentation, and we need to extract them from
1166 # the CVXOPT ``x`` and ``z`` variables. The objective values
1167 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
1168 # ``x`` and ``y`` variables; however, they're stored
1169 # conveniently as separate entries in the solution dictionary.
1170 p1_value
= -soln_dict
['primal objective']
1171 p2_value
= -soln_dict
['dual objective']
1172 p1_optimal
= soln_dict
['x'][1:]
1173 p2_optimal
= soln_dict
['z'][self
.dimension():]
1175 # The "status" field contains "optimal" if everything went
1176 # according to plan. Other possible values are "primal
1177 # infeasible", "dual infeasible", "unknown", all of which mean
1178 # we didn't get a solution.
1180 # The "infeasible" ones are the worst, since they indicate
1181 # that CVXOPT is convinced the problem is infeasible (and that
1183 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
1184 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1185 raise GameUnsolvableException(self
, soln_dict
)
1187 # For the game value, we could use any of:
1191 # * (p1_value + p2_value)/2
1194 # We want the game value to be the payoff, however, so it
1195 # makes the most sense to just use that, even if it means we
1196 # can't test the fact that p1_value/p2_value are close to the
1198 payoff
= self
.payoff(p1_optimal
, p2_optimal
)
1199 soln
= Solution(payoff
, p1_optimal
, p2_optimal
)
1201 # The "optimal" and "unknown" results, we actually treat the
1202 # same. Even if CVXOPT bails out due to numerical difficulty,
1203 # it will have some candidate points in mind. If those
1204 # candidates are good enough, we take them. We do the same
1205 # check for "optimal" results.
1207 # First we check that the primal/dual objective values are
1208 # close enough because otherwise CVXOPT might return "unknown"
1209 # and give us two points in the cone that are nowhere near
1210 # optimal. And in fact, we need to ensure that they're close
1211 # for "optimal" results, too, because we need to know how
1212 # lenient to be in our testing.
1214 if abs(p1_value
- p2_value
) > self
.tolerance_scale(soln
)*ABS_TOL
:
1215 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1216 raise GameUnsolvableException(self
, soln_dict
)
1218 # And we also check that the points it gave us belong to the
1219 # cone, just in case...
1220 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
1221 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1222 raise GameUnsolvableException(self
, soln_dict
)
1227 def condition(self
):
1229 Return the condition number of this game.
1231 In the CVXOPT construction of this game, two matrices ``G`` and
1232 ``A`` appear. When those matrices are nasty, numerical problems
1233 can show up. We define the condition number of this game to be
1234 the average of the condition numbers of ``G`` and ``A`` in the
1235 CVXOPT construction. If the condition number of this game is
1236 high, then you can expect numerical difficulty (such as
1237 :class:`PoorScalingException`).
1243 A real number greater than or equal to one that measures how
1244 bad this game is numerically.
1249 >>> from dunshire import *
1250 >>> K = NonnegativeOrthant(1)
1254 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1259 return (condition_number(self
.G()) + condition_number(self
.A()))/2
1264 Return the dual game to this game.
1266 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1267 then its dual is :math:`G^{*} =
1268 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1269 is symmetric, :math:`K^{*} = K`.
1274 >>> from dunshire import *
1275 >>> K = NonnegativeOrthant(3)
1276 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1279 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1280 >>> print(SLG.dual())
1281 The linear game (L, K, e1, e2) where
1285 K = Nonnegative orthant in the real 3-space,
1294 # We pass ``self.L()`` right back into the constructor, because
1295 # it will be transposed there. And keep in mind that ``self._K``
1297 return SymmetricLinearGame(self
.L(),