]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/games.py
76fbf7deedfec733bf4213bec000bdf449087e75
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_square_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
)]
516 def _random_orthant_params():
518 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
519 random game over the nonnegative orthant. This is only used by
520 the :class:`SymmetricLinearGameTest` class.
522 ambient_dim
= randint(1, 10)
523 K
= NonnegativeOrthant(ambient_dim
)
524 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
525 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
526 L
= _random_square_matrix(K
.dimension())
527 return (L
, K
, e1
, e2
)
530 def _random_icecream_params():
532 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
533 random game over the ice cream cone. This is only used by
534 the :class:`SymmetricLinearGameTest` class.
536 # Use a minimum dimension of two to avoid divide-by-zero in
537 # the fudge factor we make up later.
538 ambient_dim
= randint(2, 10)
539 K
= IceCream(ambient_dim
)
540 e1
= [1] # Set the "height" of e1 to one
541 e2
= [1] # And the same for e2
543 # If we choose the rest of the components of e1,e2 randomly
544 # between 0 and 1, then the largest the squared norm of the
545 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
546 # need to make it less than one (the height of the cone) so
547 # that the whole thing is in the cone. The norm of the
548 # non-height part is sqrt(dim(K) - 1), and we can divide by
550 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
551 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
552 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
553 L
= _random_square_matrix(K
.dimension())
555 return (L
, K
, e1
, e2
)
558 class SymmetricLinearGameTest(TestCase
):
560 Tests for the SymmetricLinearGame and Solution classes.
562 def assert_within_tol(self
, first
, second
):
564 Test that ``first`` and ``second`` are equal within our default
567 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
570 def assert_norm_within_tol(self
, first
, second
):
572 Test that ``first`` and ``second`` vectors are equal in the
573 sense that the norm of their difference is within our default
576 self
.assert_within_tol(norm(first
- second
), 0)
579 def assert_solution_exists(self
, L
, K
, e1
, e2
):
581 Given the parameters needed to construct a SymmetricLinearGame,
582 ensure that that game has a solution.
584 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
587 # The matrix() constructor assumes that ``L`` is a list of
588 # columns, so we transpose it to agree with what
589 # SymmetricLinearGame() thinks.
590 L_matrix
= matrix(L
).trans()
591 expected
= inner_product(L_matrix
*soln
.player1_optimal(),
592 soln
.player2_optimal())
593 self
.assert_within_tol(soln
.game_value(), expected
)
596 def test_solution_exists_orthant(self
):
598 Every linear game has a solution, so we should be able to solve
599 every symmetric linear game over the NonnegativeOrthant. Pick
600 some parameters randomly and give it a shot. The resulting
601 optimal solutions should give us the optimal game value when we
602 apply the payoff operator to them.
604 (L
, K
, e1
, e2
) = _random_orthant_params()
605 self
.assert_solution_exists(L
, K
, e1
, e2
)
608 def test_solution_exists_icecream(self
):
610 Like :meth:`test_solution_exists_nonnegative_orthant`, except
611 over the ice cream cone.
613 (L
, K
, e1
, e2
) = _random_icecream_params()
614 self
.assert_solution_exists(L
, K
, e1
, e2
)
617 def test_negative_value_z_operator(self
):
619 Test the example given in Gowda/Ravindran of a Z-matrix with
620 negative game value on the nonnegative orthant.
622 K
= NonnegativeOrthant(2)
625 L
= [[1, -2], [-2, 1]]
626 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
627 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
630 def assert_scaling_works(self
, L
, K
, e1
, e2
):
632 Test that scaling ``L`` by a nonnegative number scales the value
633 of the game by the same number.
635 # Make ``L`` a matrix so that we can scale it by alpha. Its
636 # random, so who cares if it gets transposed.
638 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
639 value1
= game1
.solution().game_value()
641 alpha
= uniform(0.1, 10)
642 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
643 value2
= game2
.solution().game_value()
644 self
.assert_within_tol(alpha
*value1
, value2
)
647 def test_scaling_orthant(self
):
649 Test that scaling ``L`` by a nonnegative number scales the value
650 of the game by the same number over the nonnegative orthant.
652 (L
, K
, e1
, e2
) = _random_orthant_params()
653 self
.assert_scaling_works(L
, K
, e1
, e2
)
656 def test_scaling_icecream(self
):
658 The same test as :meth:`test_nonnegative_scaling_orthant`,
659 except over the ice cream cone.
661 (L
, K
, e1
, e2
) = _random_icecream_params()
662 self
.assert_scaling_works(L
, K
, e1
, e2
)
665 def assert_translation_works(self
, L
, K
, e1
, e2
):
667 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
668 the value of the associated game by alpha.
670 e1
= matrix(e1
, (K
.dimension(), 1))
671 e2
= matrix(e2
, (K
.dimension(), 1))
672 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
673 soln1
= game1
.solution()
674 value1
= soln1
.game_value()
675 x_bar
= soln1
.player1_optimal()
676 y_bar
= soln1
.player2_optimal()
678 # Make ``L`` a CVXOPT matrix so that we can do math with
679 # it. Note that this gives us the "correct" representation of
680 # ``L`` (in agreement with what G has), but COLUMN indexed.
681 alpha
= uniform(-10, 10)
682 L
= matrix(L
).trans()
683 tensor_prod
= e1
*e2
.trans()
685 # Likewise, this is the "correct" representation of ``M``, but
687 M
= L
+ alpha
*tensor_prod
689 # so we have to transpose it when we feed it to the constructor.
690 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
691 value2
= game2
.solution().game_value()
693 self
.assert_within_tol(value1
+ alpha
, value2
)
695 # Make sure the same optimal pair works.
696 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
699 def test_translation_orthant(self
):
701 Test that translation works over the nonnegative orthant.
703 (L
, K
, e1
, e2
) = _random_orthant_params()
704 self
.assert_translation_works(L
, K
, e1
, e2
)
707 def test_translation_icecream(self
):
709 The same as :meth:`test_translation_orthant`, except over the
712 (L
, K
, e1
, e2
) = _random_icecream_params()
713 self
.assert_translation_works(L
, K
, e1
, e2
)
716 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
718 Check the value of the "opposite" game that gives rise to a
719 value that is the negation of the original game. Comes from
722 e1
= matrix(e1
, (K
.dimension(), 1))
723 e2
= matrix(e2
, (K
.dimension(), 1))
724 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
726 # Make ``L`` a CVXOPT matrix so that we can do math with
727 # it. Note that this gives us the "correct" representation of
728 # ``L`` (in agreement with what G has), but COLUMN indexed.
729 L
= matrix(L
).trans()
731 # Likewise, this is the "correct" representation of ``M``, but
735 # so we have to transpose it when we feed it to the constructor.
736 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
738 soln1
= game1
.solution()
739 x_bar
= soln1
.player1_optimal()
740 y_bar
= soln1
.player2_optimal()
741 soln2
= game2
.solution()
743 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
745 # Make sure the switched optimal pair works.
746 self
.assert_within_tol(soln2
.game_value(),
747 inner_product(M
*y_bar
, x_bar
))
750 def test_opposite_game_orthant(self
):
752 Test the value of the "opposite" game over the nonnegative
755 (L
, K
, e1
, e2
) = _random_orthant_params()
756 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
759 def test_opposite_game_icecream(self
):
761 Like :meth:`test_opposite_game_orthant`, except over the
764 (L
, K
, e1
, e2
) = _random_icecream_params()
765 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
768 def assert_orthogonality(self
, L
, K
, e1
, e2
):
770 Two orthogonality relations hold at an optimal solution, and we
773 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
774 soln
= game
.solution()
775 x_bar
= soln
.player1_optimal()
776 y_bar
= soln
.player2_optimal()
777 value
= soln
.game_value()
779 # Make these matrices so that we can compute with them.
780 L
= matrix(L
).trans()
781 e1
= matrix(e1
, (K
.dimension(), 1))
782 e2
= matrix(e2
, (K
.dimension(), 1))
784 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
785 self
.assert_within_tol(ip1
, 0)
787 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
788 self
.assert_within_tol(ip2
, 0)
791 def test_orthogonality_orthant(self
):
793 Check the orthgonality relationships that hold for a solution
794 over the nonnegative orthant.
796 (L
, K
, e1
, e2
) = _random_orthant_params()
797 self
.assert_orthogonality(L
, K
, e1
, e2
)
800 def test_orthogonality_icecream(self
):
802 Check the orthgonality relationships that hold for a solution
803 over the ice-cream cone.
805 (L
, K
, e1
, e2
) = _random_icecream_params()
806 self
.assert_orthogonality(L
, K
, e1
, e2
)