]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/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.
8 # These few are used only for tests.
10 from random
import randint
, uniform
11 from unittest
import TestCase
13 # These are mostly actually needed.
14 from cvxopt
import matrix
, printing
, solvers
15 from cones
import CartesianProduct
, IceCream
, NonnegativeOrthant
16 from errors
import GameUnsolvableException
17 from matrices
import append_col
, append_row
, identity
, inner_product
, norm
20 printing
.options
['dformat'] = options
.FLOAT_FORMAT
21 solvers
.options
['show_progress'] = options
.VERBOSE
26 A representation of the solution of a linear game. It should contain
27 the value of the game, and both players' strategies.
32 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
33 Game value: 10.0000000
42 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
44 Create a new Solution object from a game value and two optimal
45 strategies for the players.
47 self
._game
_value
= game_value
48 self
._player
1_optimal
= p1_optimal
49 self
._player
2_optimal
= p2_optimal
53 Return a string describing the solution of a linear game.
55 The three data that are described are,
57 * The value of the game.
58 * The optimal strategy of player one.
59 * The optimal strategy of player two.
61 The two optimal strategy vectors are indented by two spaces.
63 tpl
= 'Game value: {:.7f}\n' \
64 'Player 1 optimal:{:s}\n' \
65 'Player 2 optimal:{:s}'
67 p1_str
= '\n{!s}'.format(self
.player1_optimal())
68 p1_str
= '\n '.join(p1_str
.splitlines())
69 p2_str
= '\n{!s}'.format(self
.player2_optimal())
70 p2_str
= '\n '.join(p2_str
.splitlines())
72 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
77 Return the game value for this solution.
82 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
87 return self
._game
_value
90 def player1_optimal(self
):
92 Return player one's optimal strategy in this solution.
97 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
98 >>> print(s.player1_optimal())
104 return self
._player
1_optimal
107 def player2_optimal(self
):
109 Return player two's optimal strategy in this solution.
114 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
115 >>> print(s.player2_optimal())
121 return self
._player
2_optimal
124 class SymmetricLinearGame
:
126 A representation of a symmetric linear game.
128 The data for a symmetric linear game are,
130 * A "payoff" operator ``L``.
131 * A symmetric cone ``K``.
132 * Two points ``e1`` and ``e2`` in the interior of ``K``.
134 The ambient space is assumed to be the span of ``K``.
136 With those data understood, the game is played as follows. Players
137 one and two choose points :math:`x` and :math:`y` respectively, from
138 their respective strategy sets,
145 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
150 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
154 Afterwards, a "payout" is computed as :math:`\left\langle
155 L\left(x\right), y \right\rangle` and is paid to player one out of
156 player two's pocket. The game is therefore zero sum, and we suppose
157 that player one would like to guarantee himself the largest minimum
158 payout possible. That is, player one wishes to,
163 &\underset{y \in \Delta_{2}}{\min}\left(
164 \left\langle L\left(x\right), y \right\rangle
166 \text{subject to } & x \in \Delta_{1}.
169 Player two has the simultaneous goal to,
174 &\underset{x \in \Delta_{1}}{\max}\left(
175 \left\langle L\left(x\right), y \right\rangle
177 \text{subject to } & y \in \Delta_{2}.
180 These goals obviously conflict (the game is zero sum), but an
181 existence theorem guarantees at least one optimal min-max solution
182 from which neither player would like to deviate. This class is
183 able to find such a solution.
188 L : list of list of float
189 A matrix represented as a list of ROWS. This representation
190 agrees with (for example) SageMath and NumPy, but not with CVXOPT
191 (whose matrix constructor accepts a list of columns).
193 K : :class:`SymmetricCone`
194 The symmetric cone instance over which the game is played.
197 The interior point of ``K`` belonging to player one; it
198 can be of any iterable type having the correct length.
201 The interior point of ``K`` belonging to player two; it
202 can be of any enumerable type having the correct length.
208 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
213 >>> from cones import NonnegativeOrthant
214 >>> K = NonnegativeOrthant(3)
215 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
218 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
220 The linear game (L, K, e1, e2) where
224 K = Nonnegative orthant in the real 3-space,
232 Lists can (and probably should) be used for every argument::
234 >>> from cones import NonnegativeOrthant
235 >>> K = NonnegativeOrthant(2)
236 >>> L = [[1,0],[0,1]]
239 >>> G = SymmetricLinearGame(L, K, e1, e2)
241 The linear game (L, K, e1, e2) where
244 K = Nonnegative orthant in the real 2-space,
250 The points ``e1`` and ``e2`` can also be passed as some other
251 enumerable type (of the correct length) without much harm, since
252 there is no row/column ambiguity::
256 >>> from cones import NonnegativeOrthant
257 >>> K = NonnegativeOrthant(2)
258 >>> L = [[1,0],[0,1]]
259 >>> e1 = cvxopt.matrix([1,1])
260 >>> e2 = numpy.matrix([1,1])
261 >>> G = SymmetricLinearGame(L, K, e1, e2)
263 The linear game (L, K, e1, e2) where
266 K = Nonnegative orthant in the real 2-space,
272 However, ``L`` will always be intepreted as a list of rows, even
273 if it is passed as a :class:`cvxopt.base.matrix` which is
274 otherwise indexed by columns::
277 >>> from cones import NonnegativeOrthant
278 >>> K = NonnegativeOrthant(2)
279 >>> L = [[1,2],[3,4]]
282 >>> G = SymmetricLinearGame(L, K, e1, e2)
284 The linear game (L, K, e1, e2) where
287 K = Nonnegative orthant in the real 2-space,
292 >>> L = cvxopt.matrix(L)
297 >>> G = SymmetricLinearGame(L, K, e1, e2)
299 The linear game (L, K, e1, e2) where
302 K = Nonnegative orthant in the real 2-space,
309 def __init__(self
, L
, K
, e1
, e2
):
311 Create a new SymmetricLinearGame object.
314 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
315 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
317 # Our input ``L`` is indexed by rows but CVXOPT matrices are
318 # indexed by columns, so we need to transpose the input before
319 # feeding it to CVXOPT.
320 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
322 if not self
._e
1 in K
:
323 raise ValueError('the point e1 must lie in the interior of K')
325 if not self
._e
2 in K
:
326 raise ValueError('the point e2 must lie in the interior of K')
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
._e
1).splitlines())
339 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
340 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
345 Solve this linear game and return a :class:`Solution`.
351 A :class:`Solution` object describing the game's value and
352 the optimal strategies of both players.
356 GameUnsolvableException
357 If the game could not be solved (if an optimal solution to its
358 associated cone program was not found).
363 This example is computed in Gowda and Ravindran in the section
364 "The value of a Z-transformation"::
366 >>> from cones import NonnegativeOrthant
367 >>> K = NonnegativeOrthant(3)
368 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
371 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
372 >>> print(SLG.solution())
373 Game value: -6.1724138
383 The value of the following game can be computed using the fact
384 that the identity is invertible::
386 >>> from cones import NonnegativeOrthant
387 >>> K = NonnegativeOrthant(3)
388 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
391 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
392 >>> print(SLG.solution())
393 Game value: 0.0312500
404 # The cone "C" that appears in the statement of the CVXOPT
406 C
= CartesianProduct(self
._K
, self
._K
)
408 # The column vector "b" that appears on the right-hand side of
409 # Ax = b in the statement of the CVXOPT conelp program.
410 b
= matrix([1], tc
='d')
412 # A column of zeros that fits K.
413 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
415 # The column vector "h" that appears on the right-hand side of
416 # Gx + s = h in the statement of the CVXOPT conelp program.
417 h
= matrix([zero
, zero
])
419 # The column vector "c" that appears in the objective function
420 # value <c,x> in the statement of the CVXOPT conelp program.
421 c
= matrix([-1, zero
])
423 # The matrix "G" that appears on the left-hand side of Gx + s = h
424 # in the statement of the CVXOPT conelp program.
425 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
426 append_col(self
._e
1, -self
._L))
428 # The matrix "A" that appears on the right-hand side of Ax = b
429 # in the statement of the CVXOPT conelp program.
430 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
432 # Actually solve the thing and obtain a dictionary describing
434 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
436 p1_value
= -soln_dict
['primal objective']
437 p2_value
= -soln_dict
['dual objective']
438 p1_optimal
= soln_dict
['x'][1:]
439 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
441 # The "status" field contains "optimal" if everything went
442 # according to plan. Other possible values are "primal
443 # infeasible", "dual infeasible", "unknown", all of which mean
444 # we didn't get a solution. The "infeasible" ones are the
445 # worst, since they indicate that CVXOPT is convinced the
446 # problem is infeasible (and that cannot happen).
447 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
448 raise GameUnsolvableException(soln_dict
)
449 elif soln_dict
['status'] == 'unknown':
450 # When we get a status of "unknown", we may still be able
451 # to salvage a solution out of the returned
452 # dictionary. Often this is the result of numerical
453 # difficulty and we can simply check that the primal/dual
454 # objectives match (within a tolerance) and that the
455 # primal/dual optimal solutions are within the cone (to a
456 # tolerance as well).
457 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
458 raise GameUnsolvableException(soln_dict
)
459 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
460 raise GameUnsolvableException(soln_dict
)
462 return Solution(p1_value
, p1_optimal
, p2_optimal
)
467 Return the dual game to this game.
469 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
470 then its dual is :math:`G^{*} =
471 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
472 is symmetric, :math:`K^{*} = K`.
477 >>> from cones import NonnegativeOrthant
478 >>> K = NonnegativeOrthant(3)
479 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
482 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
483 >>> print(SLG.dual())
484 The linear game (L, K, e1, e2) where
488 K = Nonnegative orthant in the real 3-space,
497 # We pass ``self._L`` right back into the constructor, because
498 # it will be transposed there. And keep in mind that ``self._K``
500 return SymmetricLinearGame(self
._L,
507 def _random_matrix(dims
):
509 Generate a random square (``dims``-by-``dims``) matrix,
510 represented as a list of rows. This is used only by the
511 :class:`SymmetricLinearGameTest` class.
513 return [[uniform(-10, 10) for i
in range(dims
)] for j
in range(dims
)]
515 def _random_nonnegative_matrix(dims
):
517 Generate a random square (``dims``-by-``dims``) matrix with
518 nonnegative entries, represented as a list of rows. This is used
519 only by the :class:`SymmetricLinearGameTest` class.
521 L
= _random_matrix(dims
)
522 return [[abs(entry
) for entry
in row
] for row
in L
]
524 def _random_diagonal_matrix(dims
):
526 Generate a random square (``dims``-by-``dims``) matrix with nonzero
527 entries only on the diagonal, represented as a list of rows. This is
528 used only by the :class:`SymmetricLinearGameTest` class.
530 return [[uniform(-10, 10)*int(i
== j
) for i
in range(dims
)]
531 for j
in range(dims
)]
533 def _random_orthant_params():
535 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
536 random game over the nonnegative orthant. This is only used by
537 the :class:`SymmetricLinearGameTest` class.
539 ambient_dim
= randint(1, 10)
540 K
= NonnegativeOrthant(ambient_dim
)
541 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
542 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
543 L
= _random_matrix(K
.dimension())
544 return (L
, K
, e1
, e2
)
547 def _random_icecream_params():
549 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
550 random game over the ice cream cone. This is only used by
551 the :class:`SymmetricLinearGameTest` class.
553 # Use a minimum dimension of two to avoid divide-by-zero in
554 # the fudge factor we make up later.
555 ambient_dim
= randint(2, 10)
556 K
= IceCream(ambient_dim
)
557 e1
= [1] # Set the "height" of e1 to one
558 e2
= [1] # And the same for e2
560 # If we choose the rest of the components of e1,e2 randomly
561 # between 0 and 1, then the largest the squared norm of the
562 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
563 # need to make it less than one (the height of the cone) so
564 # that the whole thing is in the cone. The norm of the
565 # non-height part is sqrt(dim(K) - 1), and we can divide by
567 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
568 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
569 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
570 L
= _random_matrix(K
.dimension())
572 return (L
, K
, e1
, e2
)
575 class SymmetricLinearGameTest(TestCase
):
577 Tests for the SymmetricLinearGame and Solution classes.
579 def assert_within_tol(self
, first
, second
):
581 Test that ``first`` and ``second`` are equal within our default
584 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
587 def assert_norm_within_tol(self
, first
, second
):
589 Test that ``first`` and ``second`` vectors are equal in the
590 sense that the norm of their difference is within our default
593 self
.assert_within_tol(norm(first
- second
), 0)
596 def assert_solution_exists(self
, L
, K
, e1
, e2
):
598 Given the parameters needed to construct a SymmetricLinearGame,
599 ensure that that game has a solution.
601 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
604 # The matrix() constructor assumes that ``L`` is a list of
605 # columns, so we transpose it to agree with what
606 # SymmetricLinearGame() thinks.
607 L_matrix
= matrix(L
).trans()
608 expected
= inner_product(L_matrix
*soln
.player1_optimal(),
609 soln
.player2_optimal())
610 self
.assert_within_tol(soln
.game_value(), expected
)
613 def test_solution_exists_orthant(self
):
615 Every linear game has a solution, so we should be able to solve
616 every symmetric linear game over the NonnegativeOrthant. Pick
617 some parameters randomly and give it a shot. The resulting
618 optimal solutions should give us the optimal game value when we
619 apply the payoff operator to them.
621 (L
, K
, e1
, e2
) = _random_orthant_params()
622 self
.assert_solution_exists(L
, K
, e1
, e2
)
625 def test_solution_exists_icecream(self
):
627 Like :meth:`test_solution_exists_nonnegative_orthant`, except
628 over the ice cream cone.
630 (L
, K
, e1
, e2
) = _random_icecream_params()
631 self
.assert_solution_exists(L
, K
, e1
, e2
)
634 def test_negative_value_z_operator(self
):
636 Test the example given in Gowda/Ravindran of a Z-matrix with
637 negative game value on the nonnegative orthant.
639 K
= NonnegativeOrthant(2)
642 L
= [[1, -2], [-2, 1]]
643 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
644 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
647 def assert_scaling_works(self
, L
, K
, e1
, e2
):
649 Test that scaling ``L`` by a nonnegative number scales the value
650 of the game by the same number.
652 # Make ``L`` a matrix so that we can scale it by alpha. Its
653 # random, so who cares if it gets transposed.
655 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
656 value1
= game1
.solution().game_value()
658 alpha
= uniform(0.1, 10)
659 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
660 value2
= game2
.solution().game_value()
661 self
.assert_within_tol(alpha
*value1
, value2
)
664 def test_scaling_orthant(self
):
666 Test that scaling ``L`` by a nonnegative number scales the value
667 of the game by the same number over the nonnegative orthant.
669 (L
, K
, e1
, e2
) = _random_orthant_params()
670 self
.assert_scaling_works(L
, K
, e1
, e2
)
673 def test_scaling_icecream(self
):
675 The same test as :meth:`test_nonnegative_scaling_orthant`,
676 except over the ice cream cone.
678 (L
, K
, e1
, e2
) = _random_icecream_params()
679 self
.assert_scaling_works(L
, K
, e1
, e2
)
682 def assert_translation_works(self
, L
, K
, e1
, e2
):
684 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
685 the value of the associated game by alpha.
687 e1
= matrix(e1
, (K
.dimension(), 1))
688 e2
= matrix(e2
, (K
.dimension(), 1))
689 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
690 soln1
= game1
.solution()
691 value1
= soln1
.game_value()
692 x_bar
= soln1
.player1_optimal()
693 y_bar
= soln1
.player2_optimal()
695 # Make ``L`` a CVXOPT matrix so that we can do math with
696 # it. Note that this gives us the "correct" representation of
697 # ``L`` (in agreement with what G has), but COLUMN indexed.
698 alpha
= uniform(-10, 10)
699 L
= matrix(L
).trans()
700 tensor_prod
= e1
*e2
.trans()
702 # Likewise, this is the "correct" representation of ``M``, but
704 M
= L
+ alpha
*tensor_prod
706 # so we have to transpose it when we feed it to the constructor.
707 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
708 value2
= game2
.solution().game_value()
710 self
.assert_within_tol(value1
+ alpha
, value2
)
712 # Make sure the same optimal pair works.
713 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
716 def test_translation_orthant(self
):
718 Test that translation works over the nonnegative orthant.
720 (L
, K
, e1
, e2
) = _random_orthant_params()
721 self
.assert_translation_works(L
, K
, e1
, e2
)
724 def test_translation_icecream(self
):
726 The same as :meth:`test_translation_orthant`, except over the
729 (L
, K
, e1
, e2
) = _random_icecream_params()
730 self
.assert_translation_works(L
, K
, e1
, e2
)
733 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
735 Check the value of the "opposite" game that gives rise to a
736 value that is the negation of the original game. Comes from
739 e1
= matrix(e1
, (K
.dimension(), 1))
740 e2
= matrix(e2
, (K
.dimension(), 1))
741 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
743 # Make ``L`` a CVXOPT matrix so that we can do math with
744 # it. Note that this gives us the "correct" representation of
745 # ``L`` (in agreement with what G has), but COLUMN indexed.
746 L
= matrix(L
).trans()
748 # Likewise, this is the "correct" representation of ``M``, but
752 # so we have to transpose it when we feed it to the constructor.
753 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
755 soln1
= game1
.solution()
756 x_bar
= soln1
.player1_optimal()
757 y_bar
= soln1
.player2_optimal()
758 soln2
= game2
.solution()
760 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
762 # Make sure the switched optimal pair works.
763 self
.assert_within_tol(soln2
.game_value(),
764 inner_product(M
*y_bar
, x_bar
))
767 def test_opposite_game_orthant(self
):
769 Test the value of the "opposite" game over the nonnegative
772 (L
, K
, e1
, e2
) = _random_orthant_params()
773 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
776 def test_opposite_game_icecream(self
):
778 Like :meth:`test_opposite_game_orthant`, except over the
781 (L
, K
, e1
, e2
) = _random_icecream_params()
782 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
785 def assert_orthogonality(self
, L
, K
, e1
, e2
):
787 Two orthogonality relations hold at an optimal solution, and we
790 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
791 soln
= game
.solution()
792 x_bar
= soln
.player1_optimal()
793 y_bar
= soln
.player2_optimal()
794 value
= soln
.game_value()
796 # Make these matrices so that we can compute with them.
797 L
= matrix(L
).trans()
798 e1
= matrix(e1
, (K
.dimension(), 1))
799 e2
= matrix(e2
, (K
.dimension(), 1))
801 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
802 self
.assert_within_tol(ip1
, 0)
804 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
805 self
.assert_within_tol(ip2
, 0)
808 def test_orthogonality_orthant(self
):
810 Check the orthgonality relationships that hold for a solution
811 over the nonnegative orthant.
813 (L
, K
, e1
, e2
) = _random_orthant_params()
814 self
.assert_orthogonality(L
, K
, e1
, e2
)
817 def test_orthogonality_icecream(self
):
819 Check the orthgonality relationships that hold for a solution
820 over the ice-cream cone.
822 (L
, K
, e1
, e2
) = _random_icecream_params()
823 self
.assert_orthogonality(L
, K
, e1
, e2
)
826 def test_positive_operator_value(self
):
828 Test that a positive operator on the nonnegative orthant gives
829 rise to a a game with a nonnegative value.
831 This test theoretically applies to the ice-cream cone as well,
832 but we don't know how to make positive operators on that cone.
834 (_
, K
, e1
, e2
) = _random_orthant_params()
836 # Ignore that L, we need a nonnegative one.
837 L
= _random_nonnegative_matrix(K
.dimension())
839 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
840 self
.assertTrue(game
.solution().game_value() >= -options
.ABS_TOL
)