]>
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,
224 Condition((L, K, e1, e2)) = 31.834...
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,
243 Condition((L, K, e1, e2)) = 1.707...
245 The points ``e1`` and ``e2`` can also be passed as some other
246 enumerable type (of the correct length) without much harm, since
247 there is no row/column ambiguity::
251 >>> from dunshire import *
252 >>> K = NonnegativeOrthant(2)
253 >>> L = [[1,0],[0,1]]
254 >>> e1 = cvxopt.matrix([1,1])
255 >>> e2 = numpy.matrix([1,1])
256 >>> G = SymmetricLinearGame(L, K, e1, e2)
258 The linear game (L, K, e1, e2) where
261 K = Nonnegative orthant in the real 2-space,
266 Condition((L, K, e1, e2)) = 1.707...
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 Condition((L, K, e1, e2)) = 6.073...
289 >>> L = cvxopt.matrix(L)
294 >>> G = SymmetricLinearGame(L, K, e1, e2)
296 The linear game (L, K, e1, e2) where
299 K = Nonnegative orthant in the real 2-space,
304 Condition((L, K, e1, e2)) = 6.073...
307 def __init__(self
, L
, K
, e1
, e2
):
309 Create a new SymmetricLinearGame object.
312 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
313 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
315 # Our input ``L`` is indexed by rows but CVXOPT matrices are
316 # indexed by columns, so we need to transpose the input before
317 # feeding it to CVXOPT.
318 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
320 if not self
._e
1 in K
:
321 raise ValueError('the point e1 must lie in the interior of K')
323 if not self
._e
2 in K
:
324 raise ValueError('the point e2 must lie in the interior of K')
326 # Initial value of cached method.
327 self
._L_specnorm
_value
= None
332 Return a string representation of this game.
334 tpl
= 'The linear game (L, K, e1, e2) where\n' \
339 ' Condition((L, K, e1, e2)) = {:f}.'
340 indented_L
= '\n '.join(str(self
.L()).splitlines())
341 indented_e1
= '\n '.join(str(self
.e1()).splitlines())
342 indented_e2
= '\n '.join(str(self
.e2()).splitlines())
344 return tpl
.format(indented_L
,
353 Return the matrix ``L`` passed to the constructor.
359 The matrix that defines this game's :meth:`payoff` operator.
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)
382 Return the cone over which this game is played.
388 The :class:`SymmetricCone` over which this game is played.
393 >>> from dunshire import *
394 >>> K = NonnegativeOrthant(3)
395 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
398 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
400 Nonnegative orthant in the real 3-space
408 Return player one's interior point.
414 The point interior to :meth:`K` affiliated with player one.
419 >>> from dunshire import *
420 >>> K = NonnegativeOrthant(3)
421 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
424 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
437 Return player two's interior point.
443 The point interior to :meth:`K` affiliated with player one.
448 >>> from dunshire import *
449 >>> K = NonnegativeOrthant(3)
450 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
453 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
464 def payoff(self
, strategy1
, strategy2
):
466 Return the payoff associated with ``strategy1`` and ``strategy2``.
468 The payoff operator takes pairs of strategies to a real
469 number. For example, if player one's strategy is :math:`x` and
470 player two's strategy is :math:`y`, then the associated payoff
471 is :math:`\left\langle L\left(x\right),y \right\rangle` \in
472 \mathbb{R}. Here, :math:`L` denotes the same linear operator as
473 :meth:`L`. This method computes the payoff given the two
480 Player one's strategy.
483 Player two's strategy.
489 The payoff for the game when player one plays ``strategy1``
490 and player two plays ``strategy2``.
495 The value of the game should be the payoff at the optimal
498 >>> from dunshire import *
499 >>> from dunshire.options import ABS_TOL
500 >>> K = NonnegativeOrthant(3)
501 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
504 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
505 >>> soln = SLG.solution()
506 >>> x_bar = soln.player1_optimal()
507 >>> y_bar = soln.player2_optimal()
508 >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL
512 return inner_product(self
.L()*strategy1
, strategy2
)
517 Return the dimension of this game.
519 The dimension of a game is not needed for the theory, but it is
520 useful for the implementation. We define the dimension of a game
521 to be the dimension of its underlying cone. Or what is the same,
522 the dimension of the space from which the strategies are chosen.
528 The dimension of the cone :meth:`K`, or of the space where
534 The dimension of a game over the nonnegative quadrant in the
535 plane should be two (the dimension of the plane)::
537 >>> from dunshire import *
538 >>> K = NonnegativeOrthant(2)
539 >>> L = [[1,-5],[-1,2]]
542 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
547 return self
.K().dimension()
552 Return a column of zeros that fits ``K``.
554 This is used in our CVXOPT construction.
558 It is not safe to cache any of the matrices passed to
559 CVXOPT, because it can clobber them.
565 A ``self.dimension()``-by-``1`` column vector of zeros.
570 >>> from dunshire import *
571 >>> K = NonnegativeOrthant(3)
575 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
576 >>> print(SLG._zero())
583 return matrix(0, (self
.dimension(), 1), tc
='d')
588 Return the matrix ``A`` used in our CVXOPT construction.
590 This matrix ``A`` appears on the right-hand side of ``Ax = b``
591 in the statement of the CVXOPT conelp program.
595 It is not safe to cache any of the matrices passed to
596 CVXOPT, because it can clobber them.
602 A ``1``-by-``(1 + self.dimension())`` row vector. Its first
603 entry is zero, and the rest are the entries of ``e2``.
608 >>> from dunshire import *
609 >>> K = NonnegativeOrthant(3)
610 >>> L = [[1,1,1],[1,1,1],[1,1,1]]
613 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
615 [0.0000000 1.0000000 2.0000000 3.0000000]
619 return matrix([0, self
.e2()], (1, self
.dimension() + 1), 'd')
625 Return the matrix ``G`` used in our CVXOPT construction.
627 Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
628 in the statement of the CVXOPT conelp program.
632 It is not safe to cache any of the matrices passed to
633 CVXOPT, because it can clobber them.
639 A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix.
644 >>> from dunshire import *
645 >>> K = NonnegativeOrthant(3)
646 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
649 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
651 [ 0.0000000 -1.0000000 0.0000000 0.0000000]
652 [ 0.0000000 0.0000000 -1.0000000 0.0000000]
653 [ 0.0000000 0.0000000 0.0000000 -1.0000000]
654 [ 1.0000000 -4.0000000 -5.0000000 -6.0000000]
655 [ 2.0000000 -7.0000000 -8.0000000 -9.0000000]
656 [ 3.0000000 -10.0000000 -11.0000000 -12.0000000]
660 identity_matrix
= identity(self
.dimension())
661 return append_row(append_col(self
._zero
(), -identity_matrix
),
662 append_col(self
.e1(), -self
.L()))
667 Return the vector ``c`` used in our CVXOPT construction.
669 The column vector ``c`` appears in the objective function
670 value ``<c,x>`` in the statement of the CVXOPT conelp program.
674 It is not safe to cache any of the matrices passed to
675 CVXOPT, because it can clobber them.
681 A ``self.dimension()``-by-``1`` column vector.
686 >>> from dunshire import *
687 >>> K = NonnegativeOrthant(3)
688 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
691 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
700 return matrix([-1, self
._zero
()])
705 Return the cone ``C`` used in our CVXOPT construction.
707 The cone ``C`` is the cone over which the conelp program takes
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 ``h`` vector appears on the right-hand side of :math:`Gx + s
738 = h` in the statement of the CVXOPT conelp program.
742 It is not safe to cache any of the matrices passed to
743 CVXOPT, because it can clobber them.
749 A ``2*self.dimension()``-by-``1`` column vector of zeros.
754 >>> from dunshire import *
755 >>> K = NonnegativeOrthant(3)
756 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
759 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
771 return matrix([self
._zero
(), self
._zero
()])
777 Return the ``b`` vector used in our CVXOPT construction.
779 The vector ``b`` appears on the right-hand side of :math:`Ax =
780 b` in the statement of the CVXOPT conelp program.
782 This method is static because the dimensions and entries of
783 ``b`` are known beforehand, and don't depend on any other
784 properties of the game.
788 It is not safe to cache any of the matrices passed to
789 CVXOPT, because it can clobber them.
795 A ``1``-by-``1`` matrix containing a single entry ``1``.
800 >>> from dunshire import *
801 >>> K = NonnegativeOrthant(3)
802 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
805 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
811 return matrix([1], tc
='d')
814 def player1_start(self
):
816 Return a feasible starting point for player one.
818 This starting point is for the CVXOPT formulation and not for
819 the original game. The basic premise is that if you normalize
820 :meth:`e2`, then you get a point in :meth:`K` that makes a unit
821 inner product with :meth:`e2`. We then get to choose the primal
822 objective function value such that the constraint involving
823 :meth:`L` is satisfied.
825 p
= self
.e2() / (norm(self
.e2()) ** 2)
826 dist
= self
.K().ball_radius(self
.e1())
827 nu
= - self
._L_specnorm
()/(dist
*norm(self
.e2()))
828 x
= matrix([nu
, p
], (self
.dimension() + 1, 1))
831 return {'x': x, 's': s}
834 def player2_start(self
):
836 Return a feasible starting point for player two.
838 q
= self
.e1() / (norm(self
.e1()) ** 2)
839 dist
= self
.K().ball_radius(self
.e2())
840 omega
= self
._L_specnorm
()/(dist
*norm(self
.e1()))
843 z1
= y
*self
.e2() - self
.L().trans()*z2
844 z
= matrix([z1
, z2
], (self
.dimension()*2, 1))
846 return {'y': y, 'z': z}
849 def _L_specnorm(self
):
851 Compute the spectral norm of :meth:`L` and cache it.
853 The spectral norm of the matrix :meth:`L` is used in a few
854 places. Since it can be expensive to compute, we want to cache
855 its value. That is not possible in :func:`specnorm`, which lies
856 outside of a class, so this is the place to do it.
862 A nonnegative real number; the largest singular value of
863 the matrix :meth:`L`.
866 if self
._L_specnorm
_value
is None:
867 self
._L_specnorm
_value
= specnorm(self
.L())
868 return self
._L_specnorm
_value
871 def tolerance_scale(self
, solution
):
873 Return a scaling factor that should be applied to ``ABS_TOL``
876 When performing certain comparisons, the default tolernace
877 ``ABS_TOL`` may not be appropriate. For example, if we expect
878 ``x`` and ``y`` to be within ``ABS_TOL`` of each other, than the
879 inner product of ``L*x`` and ``y`` can be as far apart as the
880 spectral norm of ``L`` times the sum of the norms of ``x`` and
881 ``y``. Such a comparison is made in :meth:`solution`, and in
882 many of our unit tests.
884 The returned scaling factor found from the inner product mentioned
889 \left\lVert L \right\rVert_{2}
890 \left( \left\lVert \bar{x} \right\rVert
891 + \left\lVert \bar{y} \right\rVert
894 where :math:`\bar{x}` and :math:`\bar{y}` are optimal solutions
895 for players one and two respectively. This scaling factor is not
896 formally justified, but attempting anything smaller leads to
901 Optimal solutions are not unique, so the scaling factor
902 obtained from ``solution`` may not work when comparing other
909 A solution of this game, used to obtain the norms of the
916 A scaling factor to be multiplied by ``ABS_TOL`` when
917 making comparisons involving solutions of this game.
920 norm_p1_opt
= norm(solution
.player1_optimal())
921 norm_p2_opt
= norm(solution
.player2_optimal())
922 scale
= self
._L_specnorm
()*(norm_p1_opt
+ norm_p2_opt
)
924 # Don't return anything smaller than 1... we can't go below
925 # out "minimum tolerance."
931 Solve this linear game and return a :class:`Solution`.
937 A :class:`Solution` object describing the game's value and
938 the optimal strategies of both players.
942 GameUnsolvableException
943 If the game could not be solved (if an optimal solution to its
944 associated cone program was not found).
947 If the game could not be solved because CVXOPT crashed while
948 trying to take the square root of a negative number.
953 This example is computed in Gowda and Ravindran in the section
954 "The value of a Z-transformation"::
956 >>> from dunshire import *
957 >>> K = NonnegativeOrthant(3)
958 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
961 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
962 >>> print(SLG.solution())
963 Game value: -6.172...
973 The value of the following game can be computed using the fact
974 that the identity is invertible::
976 >>> from dunshire import *
977 >>> K = NonnegativeOrthant(3)
978 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
981 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
982 >>> print(SLG.solution())
993 This is another Gowda/Ravindran example that is supposed to have
994 a negative game value::
996 >>> from dunshire import *
997 >>> from dunshire.options import ABS_TOL
998 >>> L = [[1, -2], [-2, 1]]
999 >>> K = NonnegativeOrthant(2)
1002 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1003 >>> SLG.solution().game_value() < -ABS_TOL
1006 The following two games are problematic numerically, but we
1007 should be able to solve them::
1009 >>> from dunshire import *
1010 >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
1011 ... [ 1.30481749924621448500, 1.65278664543326403447]]
1012 >>> K = NonnegativeOrthant(2)
1013 >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
1014 >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
1015 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1016 >>> print(SLG.solution())
1017 Game value: 18.767...
1027 >>> from dunshire import *
1028 >>> L = [[1.54159395026049472754, 2.21344728574316684799],
1029 ... [1.33147433507846657541, 1.17913616272988108769]]
1030 >>> K = NonnegativeOrthant(2)
1031 >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
1032 >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
1033 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1034 >>> print(SLG.solution())
1035 Game value: 24.614...
1043 This is another one that was difficult numerically, and caused
1044 trouble even after we fixed the first two::
1046 >>> from dunshire import *
1047 >>> L = [[57.22233908627052301199, 41.70631373437460354126],
1048 ... [83.04512571985074487202, 57.82581810406928468637]]
1049 >>> K = NonnegativeOrthant(2)
1050 >>> e1 = [7.31887017043399268346, 0.89744171905822367474]
1051 >>> e2 = [0.11099824781179848388, 6.12564670639315345113]
1052 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
1053 >>> print(SLG.solution())
1054 Game value: 70.437...
1062 And finally, here's one that returns an "optimal" solution, but
1063 whose primal/dual objective function values are far apart::
1065 >>> from dunshire import *
1066 >>> L = [[ 6.49260076597376212248, -0.60528030227678542019],
1067 ... [ 2.59896077096751731972, -0.97685530240286766457]]
1069 >>> e1 = [1, 0.43749513972645248661]
1070 >>> e2 = [1, 0.46008379832200291260]
1071 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1072 >>> print(SLG.solution())
1073 Game value: 11.596...
1083 opts
= {'show_progress': False}
1084 soln_dict
= solvers
.conelp(self
._c
(),
1087 self
.C().cvxopt_dims(),
1090 primalstart
=self
.player1_start(),
1091 dualstart
=self
.player2_start(),
1093 except ValueError as error
:
1094 if str(error
) == 'math domain error':
1095 # Oops, CVXOPT tried to take the square root of a
1096 # negative number. Report some details about the game
1097 # rather than just the underlying CVXOPT crash.
1098 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1099 raise PoorScalingException(self
)
1103 # The optimal strategies are named ``p`` and ``q`` in the
1104 # background documentation, and we need to extract them from
1105 # the CVXOPT ``x`` and ``z`` variables. The objective values
1106 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
1107 # ``x`` and ``y`` variables; however, they're stored
1108 # conveniently as separate entries in the solution dictionary.
1109 p1_value
= -soln_dict
['primal objective']
1110 p2_value
= -soln_dict
['dual objective']
1111 p1_optimal
= soln_dict
['x'][1:]
1112 p2_optimal
= soln_dict
['z'][self
.dimension():]
1114 # The "status" field contains "optimal" if everything went
1115 # according to plan. Other possible values are "primal
1116 # infeasible", "dual infeasible", "unknown", all of which mean
1117 # we didn't get a solution.
1119 # The "infeasible" ones are the worst, since they indicate
1120 # that CVXOPT is convinced the problem is infeasible (and that
1122 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
1123 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1124 raise GameUnsolvableException(self
, soln_dict
)
1126 # For the game value, we could use any of:
1130 # * (p1_value + p2_value)/2
1133 # We want the game value to be the payoff, however, so it
1134 # makes the most sense to just use that, even if it means we
1135 # can't test the fact that p1_value/p2_value are close to the
1137 payoff
= self
.payoff(p1_optimal
, p2_optimal
)
1138 soln
= Solution(payoff
, p1_optimal
, p2_optimal
)
1140 # The "optimal" and "unknown" results, we actually treat the
1141 # same. Even if CVXOPT bails out due to numerical difficulty,
1142 # it will have some candidate points in mind. If those
1143 # candidates are good enough, we take them. We do the same
1144 # check (perhaps pointlessly so) for "optimal" results.
1146 # First we check that the primal/dual objective values are
1147 # close enough (one could be low by ABS_TOL, the other high by
1148 # it) because otherwise CVXOPT might return "unknown" and give
1149 # us two points in the cone that are nowhere near optimal.
1151 if abs(p1_value
- p2_value
) > self
.tolerance_scale(soln
)*ABS_TOL
:
1152 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1153 raise GameUnsolvableException(self
, soln_dict
)
1155 # And we also check that the points it gave us belong to the
1156 # cone, just in case...
1157 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
1158 printing
.options
['dformat'] = DEBUG_FLOAT_FORMAT
1159 raise GameUnsolvableException(self
, soln_dict
)
1164 def condition(self
):
1166 Return the condition number of this game.
1168 In the CVXOPT construction of this game, two matrices ``G`` and
1169 ``A`` appear. When those matrices are nasty, numerical problems
1170 can show up. We define the condition number of this game to be
1171 the average of the condition numbers of ``G`` and ``A`` in the
1172 CVXOPT construction. If the condition number of this game is
1173 high, then you can expect numerical difficulty (such as
1174 :class:`PoorScalingException`).
1180 A real number greater than or equal to one that measures how
1181 bad this game is numerically.
1186 >>> from dunshire import *
1187 >>> K = NonnegativeOrthant(1)
1191 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1196 return (condition_number(self
._G
()) + condition_number(self
.A()))/2
1201 Return the dual game to this game.
1203 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1204 then its dual is :math:`G^{*} =
1205 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1206 is symmetric, :math:`K^{*} = K`.
1211 >>> from dunshire import *
1212 >>> K = NonnegativeOrthant(3)
1213 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1216 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1217 >>> print(SLG.dual())
1218 The linear game (L, K, e1, e2) where
1222 K = Nonnegative orthant in the real 3-space,
1229 Condition((L, K, e1, e2)) = 44.476...
1232 # We pass ``self.L()`` right back into the constructor, because
1233 # it will be transposed there. And keep in mind that ``self._K``
1235 return SymmetricLinearGame(self
.L(),