]> gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/games.py
Update the project URL.
[dunshire.git] / dunshire / games.py
1 """
2 Symmetric linear games and their solutions.
3
4 This module contains the main :class:`SymmetricLinearGame` class that
5 knows how to solve a linear game.
6 """
7
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,
12 inner_product)
13 from . import options
14
15 printing.options['dformat'] = options.FLOAT_FORMAT
16
17 class Solution:
18 """
19 A representation of the solution of a linear game. It should contain
20 the value of the game, and both players' strategies.
21
22 Examples
23 --------
24
25 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
26 Game value: 10.0000000
27 Player 1 optimal:
28 [ 1]
29 [ 2]
30 Player 2 optimal:
31 [ 3]
32 [ 4]
33
34 """
35 def __init__(self, game_value, p1_optimal, p2_optimal):
36 """
37 Create a new Solution object from a game value and two optimal
38 strategies for the players.
39 """
40 self._game_value = game_value
41 self._player1_optimal = p1_optimal
42 self._player2_optimal = p2_optimal
43
44 def __str__(self):
45 """
46 Return a string describing the solution of a linear game.
47
48 The three data that are described are,
49
50 * The value of the game.
51 * The optimal strategy of player one.
52 * The optimal strategy of player two.
53
54 The two optimal strategy vectors are indented by two spaces.
55 """
56 tpl = 'Game value: {:.7f}\n' \
57 'Player 1 optimal:{:s}\n' \
58 'Player 2 optimal:{:s}'
59
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())
64
65 return tpl.format(self.game_value(), p1_str, p2_str)
66
67
68 def game_value(self):
69 """
70 Return the game value for this solution.
71
72 Examples
73 --------
74
75 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
76 >>> s.game_value()
77 10
78
79 """
80 return self._game_value
81
82
83 def player1_optimal(self):
84 """
85 Return player one's optimal strategy in this solution.
86
87 Examples
88 --------
89
90 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
91 >>> print(s.player1_optimal())
92 [ 1]
93 [ 2]
94 <BLANKLINE>
95
96 """
97 return self._player1_optimal
98
99
100 def player2_optimal(self):
101 """
102 Return player two's optimal strategy in this solution.
103
104 Examples
105 --------
106
107 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
108 >>> print(s.player2_optimal())
109 [ 3]
110 [ 4]
111 <BLANKLINE>
112
113 """
114 return self._player2_optimal
115
116
117 class SymmetricLinearGame:
118 r"""
119 A representation of a symmetric linear game.
120
121 The data for a symmetric linear game are,
122
123 * A "payoff" operator ``L``.
124 * A symmetric cone ``K``.
125 * Two points ``e1`` and ``e2`` in the interior of ``K``.
126
127 The ambient space is assumed to be the span of ``K``.
128
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,
132
133 .. math::
134 \begin{aligned}
135 \Delta_{1}
136 &=
137 \left\{
138 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
139 \right\}\\
140 \Delta_{2}
141 &=
142 \left\{
143 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
144 \right\}.
145 \end{aligned}
146
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,
152
153 .. math::
154 \begin{aligned}
155 \text{maximize }
156 &\underset{y \in \Delta_{2}}{\min}\left(
157 \left\langle L\left(x\right), y \right\rangle
158 \right)\\
159 \text{subject to } & x \in \Delta_{1}.
160 \end{aligned}
161
162 Player two has the simultaneous goal to,
163
164 .. math::
165 \begin{aligned}
166 \text{minimize }
167 &\underset{x \in \Delta_{1}}{\max}\left(
168 \left\langle L\left(x\right), y \right\rangle
169 \right)\\
170 \text{subject to } & y \in \Delta_{2}.
171 \end{aligned}
172
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.
177
178 Parameters
179 ----------
180
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).
185
186 K : :class:`SymmetricCone`
187 The symmetric cone instance over which the game is played.
188
189 e1 : iterable float
190 The interior point of ``K`` belonging to player one; it
191 can be of any iterable type having the correct length.
192
193 e2 : iterable float
194 The interior point of ``K`` belonging to player two; it
195 can be of any enumerable type having the correct length.
196
197 Raises
198 ------
199
200 ValueError
201 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
202
203 Examples
204 --------
205
206 >>> from dunshire import *
207 >>> K = NonnegativeOrthant(3)
208 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
209 >>> e1 = [1,1,1]
210 >>> e2 = [1,2,3]
211 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
212 >>> print(SLG)
213 The linear game (L, K, e1, e2) where
214 L = [ 1 -5 -15]
215 [ -1 2 -3]
216 [-12 -15 1],
217 K = Nonnegative orthant in the real 3-space,
218 e1 = [ 1]
219 [ 1]
220 [ 1],
221 e2 = [ 1]
222 [ 2]
223 [ 3],
224 Condition((L, K, e1, e2)) = 31.834...
225
226 Lists can (and probably should) be used for every argument::
227
228 >>> from dunshire import *
229 >>> K = NonnegativeOrthant(2)
230 >>> L = [[1,0],[0,1]]
231 >>> e1 = [1,1]
232 >>> e2 = [1,1]
233 >>> G = SymmetricLinearGame(L, K, e1, e2)
234 >>> print(G)
235 The linear game (L, K, e1, e2) where
236 L = [ 1 0]
237 [ 0 1],
238 K = Nonnegative orthant in the real 2-space,
239 e1 = [ 1]
240 [ 1],
241 e2 = [ 1]
242 [ 1],
243 Condition((L, K, e1, e2)) = 1.707...
244
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::
248
249 >>> import cvxopt
250 >>> import numpy
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)
257 >>> print(G)
258 The linear game (L, K, e1, e2) where
259 L = [ 1 0]
260 [ 0 1],
261 K = Nonnegative orthant in the real 2-space,
262 e1 = [ 1]
263 [ 1],
264 e2 = [ 1]
265 [ 1],
266 Condition((L, K, e1, e2)) = 1.707...
267
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::
271
272 >>> import cvxopt
273 >>> from dunshire import *
274 >>> K = NonnegativeOrthant(2)
275 >>> L = [[1,2],[3,4]]
276 >>> e1 = [1,1]
277 >>> e2 = e1
278 >>> G = SymmetricLinearGame(L, K, e1, e2)
279 >>> print(G)
280 The linear game (L, K, e1, e2) where
281 L = [ 1 2]
282 [ 3 4],
283 K = Nonnegative orthant in the real 2-space,
284 e1 = [ 1]
285 [ 1],
286 e2 = [ 1]
287 [ 1],
288 Condition((L, K, e1, e2)) = 6.073...
289 >>> L = cvxopt.matrix(L)
290 >>> print(L)
291 [ 1 3]
292 [ 2 4]
293 <BLANKLINE>
294 >>> G = SymmetricLinearGame(L, K, e1, e2)
295 >>> print(G)
296 The linear game (L, K, e1, e2) where
297 L = [ 1 2]
298 [ 3 4],
299 K = Nonnegative orthant in the real 2-space,
300 e1 = [ 1]
301 [ 1],
302 e2 = [ 1]
303 [ 1],
304 Condition((L, K, e1, e2)) = 6.073...
305
306 """
307 def __init__(self, L, K, e1, e2):
308 """
309 Create a new SymmetricLinearGame object.
310 """
311 self._K = K
312 self._e1 = matrix(e1, (K.dimension(), 1))
313 self._e2 = matrix(e2, (K.dimension(), 1))
314
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()
319
320 if not self._e1 in K:
321 raise ValueError('the point e1 must lie in the interior of K')
322
323 if not self._e2 in K:
324 raise ValueError('the point e2 must lie in the interior of K')
325
326
327
328 def __str__(self):
329 """
330 Return a string representation of this game.
331 """
332 tpl = 'The linear game (L, K, e1, e2) where\n' \
333 ' L = {:s},\n' \
334 ' K = {!s},\n' \
335 ' e1 = {:s},\n' \
336 ' e2 = {:s},\n' \
337 ' Condition((L, K, e1, e2)) = {:f}.'
338 indented_L = '\n '.join(str(self._L).splitlines())
339 indented_e1 = '\n '.join(str(self._e1).splitlines())
340 indented_e2 = '\n '.join(str(self._e2).splitlines())
341
342 return tpl.format(indented_L,
343 str(self._K),
344 indented_e1,
345 indented_e2,
346 self.condition())
347
348
349 def L(self):
350 """
351 Return the matrix ``L`` passed to the constructor.
352
353 Returns
354 -------
355
356 matrix
357 The matrix that defines this game's :meth:`payoff` operator.
358
359 Examples
360 --------
361
362 >>> from dunshire import *
363 >>> K = NonnegativeOrthant(3)
364 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
365 >>> e1 = [1,1,1]
366 >>> e2 = [1,2,3]
367 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
368 >>> print(SLG.L())
369 [ 1 -5 -15]
370 [ -1 2 -3]
371 [-12 -15 1]
372 <BLANKLINE>
373
374 """
375 return self._L
376
377
378 def K(self):
379 """
380 Return the cone over which this game is played.
381
382 Returns
383 -------
384
385 SymmetricCone
386 The :class:`SymmetricCone` over which this game is played.
387
388 Examples
389 --------
390
391 >>> from dunshire import *
392 >>> K = NonnegativeOrthant(3)
393 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
394 >>> e1 = [1,1,1]
395 >>> e2 = [1,2,3]
396 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
397 >>> print(SLG.K())
398 Nonnegative orthant in the real 3-space
399
400 """
401 return self._K
402
403
404 def e1(self):
405 """
406 Return player one's interior point.
407
408 Returns
409 -------
410
411 matrix
412 The point interior to :meth:`K` affiliated with player one.
413
414 Examples
415 --------
416
417 >>> from dunshire import *
418 >>> K = NonnegativeOrthant(3)
419 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
420 >>> e1 = [1,1,1]
421 >>> e2 = [1,2,3]
422 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
423 >>> print(SLG.e1())
424 [ 1]
425 [ 1]
426 [ 1]
427 <BLANKLINE>
428
429 """
430 return self._e1
431
432
433 def e2(self):
434 """
435 Return player two's interior point.
436
437 Returns
438 -------
439
440 matrix
441 The point interior to :meth:`K` affiliated with player one.
442
443 Examples
444 --------
445
446 >>> from dunshire import *
447 >>> K = NonnegativeOrthant(3)
448 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
449 >>> e1 = [1,1,1]
450 >>> e2 = [1,2,3]
451 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
452 >>> print(SLG.e2())
453 [ 1]
454 [ 2]
455 [ 3]
456 <BLANKLINE>
457
458 """
459 return self._e2
460
461
462 def payoff(self, strategy1, strategy2):
463 r"""
464 Return the payoff associated with ``strategy1`` and ``strategy2``.
465
466 The payoff operator takes pairs of strategies to a real
467 number. For example, if player one's strategy is :math:`x` and
468 player two's strategy is :math:`y`, then the associated payoff
469 is :math:`\left\langle L\left(x\right),y \right\rangle` \in
470 \mathbb{R}. Here, :math:`L` denotes the same linear operator as
471 :meth:`L`. This method computes the payoff given the two
472 players' strategies.
473
474 Parameters
475 ----------
476
477 strategy1 : matrix
478 Player one's strategy.
479
480 strategy2 : matrix
481 Player two's strategy.
482
483 Returns
484 -------
485
486 float
487 The payoff for the game when player one plays ``strategy1``
488 and player two plays ``strategy2``.
489
490 Examples
491 --------
492
493 The value of the game should be the payoff at the optimal
494 strategies::
495
496 >>> from dunshire import *
497 >>> from dunshire.options import ABS_TOL
498 >>> K = NonnegativeOrthant(3)
499 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
500 >>> e1 = [1,1,1]
501 >>> e2 = [1,1,1]
502 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
503 >>> soln = SLG.solution()
504 >>> x_bar = soln.player1_optimal()
505 >>> y_bar = soln.player2_optimal()
506 >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL
507 True
508
509 """
510 return inner_product(self.L()*strategy1, strategy2)
511
512
513 def dimension(self):
514 """
515 Return the dimension of this game.
516
517 The dimension of a game is not needed for the theory, but it is
518 useful for the implementation. We define the dimension of a game
519 to be the dimension of its underlying cone. Or what is the same,
520 the dimension of the space from which the strategies are chosen.
521
522 Returns
523 -------
524
525 int
526 The dimension of the cone :meth:`K`, or of the space where
527 this game is played.
528
529 Examples
530 --------
531
532 The dimension of a game over the nonnegative quadrant in the
533 plane should be two (the dimension of the plane)::
534
535 >>> from dunshire import *
536 >>> K = NonnegativeOrthant(2)
537 >>> L = [[1,-5],[-1,2]]
538 >>> e1 = [1,1]
539 >>> e2 = [1,4]
540 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
541 >>> SLG.dimension()
542 2
543
544 """
545 return self.K().dimension()
546
547
548 def _zero(self):
549 """
550 Return a column of zeros that fits ``K``.
551
552 This is used in our CVXOPT construction.
553
554 .. warning::
555
556 It is not safe to cache any of the matrices passed to
557 CVXOPT, because it can clobber them.
558
559 Returns
560 -------
561
562 matrix
563 A ``self.dimension()``-by-``1`` column vector of zeros.
564
565 Examples
566 --------
567
568 >>> from dunshire import *
569 >>> K = NonnegativeOrthant(3)
570 >>> L = identity(3)
571 >>> e1 = [1,1,1]
572 >>> e2 = e1
573 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
574 >>> print(SLG._zero())
575 [0.0000000]
576 [0.0000000]
577 [0.0000000]
578 <BLANKLINE>
579
580 """
581 return matrix(0, (self.dimension(), 1), tc='d')
582
583
584 def _A(self):
585 """
586 Return the matrix ``A`` used in our CVXOPT construction.
587
588 This matrix ``A`` appears on the right-hand side of ``Ax = b``
589 in the statement of the CVXOPT conelp program.
590
591 .. warning::
592
593 It is not safe to cache any of the matrices passed to
594 CVXOPT, because it can clobber them.
595
596 Returns
597 -------
598
599 matrix
600 A ``1``-by-``(1 + self.dimension())`` row vector. Its first
601 entry is zero, and the rest are the entries of ``e2``.
602
603 Examples
604 --------
605
606 >>> from dunshire import *
607 >>> K = NonnegativeOrthant(3)
608 >>> L = [[1,1,1],[1,1,1],[1,1,1]]
609 >>> e1 = [1,1,1]
610 >>> e2 = [1,2,3]
611 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
612 >>> print(SLG._A())
613 [0.0000000 1.0000000 2.0000000 3.0000000]
614 <BLANKLINE>
615
616 """
617 return matrix([0, self._e2], (1, self.dimension() + 1), 'd')
618
619
620
621 def _G(self):
622 r"""
623 Return the matrix ``G`` used in our CVXOPT construction.
624
625 Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
626 in the statement of the CVXOPT conelp program.
627
628 .. warning::
629
630 It is not safe to cache any of the matrices passed to
631 CVXOPT, because it can clobber them.
632
633 Returns
634 -------
635
636 matrix
637 A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix.
638
639 Examples
640 --------
641
642 >>> from dunshire import *
643 >>> K = NonnegativeOrthant(3)
644 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
645 >>> e1 = [1,2,3]
646 >>> e2 = [1,1,1]
647 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
648 >>> print(SLG._G())
649 [ 0.0000000 -1.0000000 0.0000000 0.0000000]
650 [ 0.0000000 0.0000000 -1.0000000 0.0000000]
651 [ 0.0000000 0.0000000 0.0000000 -1.0000000]
652 [ 1.0000000 -4.0000000 -5.0000000 -6.0000000]
653 [ 2.0000000 -7.0000000 -8.0000000 -9.0000000]
654 [ 3.0000000 -10.0000000 -11.0000000 -12.0000000]
655 <BLANKLINE>
656
657 """
658 identity_matrix = identity(self.dimension())
659 return append_row(append_col(self._zero(), -identity_matrix),
660 append_col(self._e1, -self._L))
661
662
663 def _c(self):
664 """
665 Return the vector ``c`` used in our CVXOPT construction.
666
667 The column vector ``c`` appears in the objective function
668 value ``<c,x>`` in the statement of the CVXOPT conelp program.
669
670 .. warning::
671
672 It is not safe to cache any of the matrices passed to
673 CVXOPT, because it can clobber them.
674
675 Returns
676 -------
677
678 matrix
679 A ``self.dimension()``-by-``1`` column vector.
680
681 Examples
682 --------
683
684 >>> from dunshire import *
685 >>> K = NonnegativeOrthant(3)
686 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
687 >>> e1 = [1,2,3]
688 >>> e2 = [1,1,1]
689 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
690 >>> print(SLG._c())
691 [-1.0000000]
692 [ 0.0000000]
693 [ 0.0000000]
694 [ 0.0000000]
695 <BLANKLINE>
696
697 """
698 return matrix([-1, self._zero()])
699
700
701 def _C(self):
702 """
703 Return the cone ``C`` used in our CVXOPT construction.
704
705 The cone ``C`` is the cone over which the conelp program takes
706 place.
707
708 Returns
709 -------
710
711 CartesianProduct
712 The cartesian product of ``K`` with itself.
713
714 Examples
715 --------
716
717 >>> from dunshire import *
718 >>> K = NonnegativeOrthant(3)
719 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
720 >>> e1 = [1,2,3]
721 >>> e2 = [1,1,1]
722 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
723 >>> print(SLG._C())
724 Cartesian product of dimension 6 with 2 factors:
725 * Nonnegative orthant in the real 3-space
726 * Nonnegative orthant in the real 3-space
727
728 """
729 return CartesianProduct(self._K, self._K)
730
731 def _h(self):
732 """
733 Return the ``h`` vector used in our CVXOPT construction.
734
735 The ``h`` vector appears on the right-hand side of :math:`Gx + s
736 = h` in the statement of the CVXOPT conelp program.
737
738 .. warning::
739
740 It is not safe to cache any of the matrices passed to
741 CVXOPT, because it can clobber them.
742
743 Returns
744 -------
745
746 matrix
747 A ``2*self.dimension()``-by-``1`` column vector of zeros.
748
749 Examples
750 --------
751
752 >>> from dunshire import *
753 >>> K = NonnegativeOrthant(3)
754 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
755 >>> e1 = [1,2,3]
756 >>> e2 = [1,1,1]
757 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
758 >>> print(SLG._h())
759 [0.0000000]
760 [0.0000000]
761 [0.0000000]
762 [0.0000000]
763 [0.0000000]
764 [0.0000000]
765 <BLANKLINE>
766
767 """
768
769 return matrix([self._zero(), self._zero()])
770
771
772 @staticmethod
773 def _b():
774 """
775 Return the ``b`` vector used in our CVXOPT construction.
776
777 The vector ``b`` appears on the right-hand side of :math:`Ax =
778 b` in the statement of the CVXOPT conelp program.
779
780 This method is static because the dimensions and entries of
781 ``b`` are known beforehand, and don't depend on any other
782 properties of the game.
783
784 .. warning::
785
786 It is not safe to cache any of the matrices passed to
787 CVXOPT, because it can clobber them.
788
789 Returns
790 -------
791
792 matrix
793 A ``1``-by-``1`` matrix containing a single entry ``1``.
794
795 Examples
796 --------
797
798 >>> from dunshire import *
799 >>> K = NonnegativeOrthant(3)
800 >>> L = [[4,5,6],[7,8,9],[10,11,12]]
801 >>> e1 = [1,2,3]
802 >>> e2 = [1,1,1]
803 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
804 >>> print(SLG._b())
805 [1.0000000]
806 <BLANKLINE>
807
808 """
809 return matrix([1], tc='d')
810
811
812 def _try_solution(self, tolerance):
813 """
814 Solve this linear game within ``tolerance``, if possible.
815
816 This private function is the one that does all of the actual
817 work for :meth:`solution`. This method accepts a ``tolerance``,
818 and what :meth:`solution` does is call this method twice with
819 two different tolerances. First it tries a strict tolerance, and
820 then it tries a looser one.
821
822 .. warning::
823
824 If you try to be smart and precompute the matrices used by
825 this function (the ones passed to ``conelp``), then you're
826 going to shoot yourself in the foot. CVXOPT can and will
827 clobber some (but not all) of its input matrices. This isn't
828 performance sensitive, so play it safe.
829
830 Parameters
831 ----------
832
833 tolerance : float
834 The absolute tolerance to pass to the CVXOPT solver.
835
836 Returns
837 -------
838
839 :class:`Solution`
840 A :class:`Solution` object describing the game's value and
841 the optimal strategies of both players.
842
843 Raises
844 ------
845 GameUnsolvableException
846 If the game could not be solved (if an optimal solution to its
847 associated cone program was not found).
848
849 PoorScalingException
850 If the game could not be solved because CVXOPT crashed while
851 trying to take the square root of a negative number.
852
853 Examples
854 --------
855
856 This game can be solved easily, so the first attempt in
857 :meth:`solution` should succeed::
858
859 >>> from dunshire import *
860 >>> from dunshire.matrices import norm
861 >>> from dunshire.options import ABS_TOL
862 >>> K = NonnegativeOrthant(3)
863 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
864 >>> e1 = [1,1,1]
865 >>> e2 = [1,1,1]
866 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
867 >>> s1 = SLG.solution()
868 >>> s2 = SLG._try_solution(options.ABS_TOL)
869 >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL
870 True
871 >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL
872 True
873 >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL
874 True
875
876 This game cannot be solved with the default tolerance, but it
877 can be solved with a weaker one::
878
879 >>> from dunshire import *
880 >>> from dunshire.options import ABS_TOL
881 >>> L = [[ 0.58538005706658102767, 1.53764301129883040886],
882 ... [-1.34901059721452210027, 1.50121179114155500756]]
883 >>> K = NonnegativeOrthant(2)
884 >>> e1 = [1.04537193228494995623, 1.39699624965841895374]
885 >>> e2 = [0.35326554172108337593, 0.11795703527854853321]
886 >>> SLG = SymmetricLinearGame(L,K,e1,e2)
887 >>> print(SLG._try_solution(ABS_TOL / 10))
888 Traceback (most recent call last):
889 ...
890 dunshire.errors.GameUnsolvableException: Solution failed...
891 >>> print(SLG._try_solution(ABS_TOL))
892 Game value: 9.1100945
893 Player 1 optimal:
894 [-0.0000000]
895 [ 8.4776631]
896 Player 2 optimal:
897 [0.0000000]
898 [0.7158216]
899
900 """
901 try:
902 opts = {'show_progress': options.VERBOSE, 'abstol': tolerance}
903 soln_dict = solvers.conelp(self._c(),
904 self._G(),
905 self._h(),
906 self._C().cvxopt_dims(),
907 self._A(),
908 self._b(),
909 options=opts)
910 except ValueError as error:
911 if str(error) == 'math domain error':
912 # Oops, CVXOPT tried to take the square root of a
913 # negative number. Report some details about the game
914 # rather than just the underlying CVXOPT crash.
915 raise PoorScalingException(self)
916 else:
917 raise error
918
919 # The optimal strategies are named ``p`` and ``q`` in the
920 # background documentation, and we need to extract them from
921 # the CVXOPT ``x`` and ``z`` variables. The objective values
922 # :math:`nu` and :math:`omega` can also be found in the CVXOPT
923 # ``x`` and ``y`` variables; however, they're stored
924 # conveniently as separate entries in the solution dictionary.
925 p1_value = -soln_dict['primal objective']
926 p2_value = -soln_dict['dual objective']
927 p1_optimal = soln_dict['x'][1:]
928 p2_optimal = soln_dict['z'][self.dimension():]
929
930 # The "status" field contains "optimal" if everything went
931 # according to plan. Other possible values are "primal
932 # infeasible", "dual infeasible", "unknown", all of which mean
933 # we didn't get a solution. The "infeasible" ones are the
934 # worst, since they indicate that CVXOPT is convinced the
935 # problem is infeasible (and that cannot happen).
936 if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
937 raise GameUnsolvableException(self, soln_dict)
938 elif soln_dict['status'] == 'unknown':
939 # When we get a status of "unknown", we may still be able
940 # to salvage a solution out of the returned
941 # dictionary. Often this is the result of numerical
942 # difficulty and we can simply check that the primal/dual
943 # objectives match (within a tolerance) and that the
944 # primal/dual optimal solutions are within the cone (to a
945 # tolerance as well).
946 #
947 # The fudge factor of two is basically unjustified, but
948 # makes intuitive sense when you imagine that the primal
949 # value could be under the true optimal by ``ABS_TOL``
950 # and the dual value could be over by the same amount.
951 #
952 if abs(p1_value - p2_value) > tolerance:
953 raise GameUnsolvableException(self, soln_dict)
954 if (p1_optimal not in self._K) or (p2_optimal not in self._K):
955 raise GameUnsolvableException(self, soln_dict)
956
957 return Solution(p1_value, p1_optimal, p2_optimal)
958
959
960 def solution(self):
961 """
962 Solve this linear game and return a :class:`Solution`.
963
964 Returns
965 -------
966
967 :class:`Solution`
968 A :class:`Solution` object describing the game's value and
969 the optimal strategies of both players.
970
971 Raises
972 ------
973 GameUnsolvableException
974 If the game could not be solved (if an optimal solution to its
975 associated cone program was not found).
976
977 PoorScalingException
978 If the game could not be solved because CVXOPT crashed while
979 trying to take the square root of a negative number.
980
981 Examples
982 --------
983
984 This example is computed in Gowda and Ravindran in the section
985 "The value of a Z-transformation"::
986
987 >>> from dunshire import *
988 >>> K = NonnegativeOrthant(3)
989 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
990 >>> e1 = [1,1,1]
991 >>> e2 = [1,1,1]
992 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
993 >>> print(SLG.solution())
994 Game value: -6.1724138
995 Player 1 optimal:
996 [ 0.551...]
997 [-0.000...]
998 [ 0.448...]
999 Player 2 optimal:
1000 [0.448...]
1001 [0.000...]
1002 [0.551...]
1003
1004 The value of the following game can be computed using the fact
1005 that the identity is invertible::
1006
1007 >>> from dunshire import *
1008 >>> K = NonnegativeOrthant(3)
1009 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
1010 >>> e1 = [1,2,3]
1011 >>> e2 = [4,5,6]
1012 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1013 >>> print(SLG.solution())
1014 Game value: 0.0312500
1015 Player 1 optimal:
1016 [0.031...]
1017 [0.062...]
1018 [0.093...]
1019 Player 2 optimal:
1020 [0.125...]
1021 [0.156...]
1022 [0.187...]
1023
1024 """
1025 try:
1026 # First try with a stricter tolerance. Who knows, it might
1027 # work. If it does, we prefer that solution.
1028 return self._try_solution(options.ABS_TOL / 10)
1029
1030 except (PoorScalingException, GameUnsolvableException):
1031 # Ok, that didn't work. Let's try it with the default tolerance..
1032 try:
1033 return self._try_solution(options.ABS_TOL / 10)
1034 except (PoorScalingException, GameUnsolvableException) as error:
1035 # Well, that didn't work either. Let's verbosify the matrix
1036 # output format before we allow the exception to be raised.
1037 printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
1038 raise error
1039
1040
1041 def condition(self):
1042 r"""
1043 Return the condition number of this game.
1044
1045 In the CVXOPT construction of this game, two matrices ``G`` and
1046 ``A`` appear. When those matrices are nasty, numerical problems
1047 can show up. We define the condition number of this game to be
1048 the average of the condition numbers of ``G`` and ``A`` in the
1049 CVXOPT construction. If the condition number of this game is
1050 high, then you can expect numerical difficulty (such as
1051 :class:`PoorScalingException`).
1052
1053 Returns
1054 -------
1055
1056 float
1057 A real number greater than or equal to one that measures how
1058 bad this game is numerically.
1059
1060 Examples
1061 --------
1062
1063 >>> from dunshire import *
1064 >>> K = NonnegativeOrthant(1)
1065 >>> L = [[1]]
1066 >>> e1 = [1]
1067 >>> e2 = e1
1068 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1069 >>> actual = SLG.condition()
1070 >>> expected = 1.8090169943749477
1071 >>> abs(actual - expected) < options.ABS_TOL
1072 True
1073
1074 """
1075 return (condition_number(self._G()) + condition_number(self._A()))/2
1076
1077
1078 def dual(self):
1079 r"""
1080 Return the dual game to this game.
1081
1082 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1083 then its dual is :math:`G^{*} =
1084 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1085 is symmetric, :math:`K^{*} = K`.
1086
1087 Examples
1088 --------
1089
1090 >>> from dunshire import *
1091 >>> K = NonnegativeOrthant(3)
1092 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1093 >>> e1 = [1,1,1]
1094 >>> e2 = [1,2,3]
1095 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1096 >>> print(SLG.dual())
1097 The linear game (L, K, e1, e2) where
1098 L = [ 1 -1 -12]
1099 [ -5 2 -15]
1100 [-15 -3 1],
1101 K = Nonnegative orthant in the real 3-space,
1102 e1 = [ 1]
1103 [ 2]
1104 [ 3],
1105 e2 = [ 1]
1106 [ 1]
1107 [ 1],
1108 Condition((L, K, e1, e2)) = 44.476...
1109
1110 """
1111 # We pass ``self._L`` right back into the constructor, because
1112 # it will be transposed there. And keep in mind that ``self._K``
1113 # is its own dual.
1114 return SymmetricLinearGame(self._L,
1115 self._K,
1116 self._e2,
1117 self._e1)