]>
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,
506 class SymmetricLinearGameTest(TestCase
):
508 Tests for the SymmetricLinearGame and Solution classes.
511 def random_square_matrix(self
, dims
):
513 Generate a random square (``dims``-by-``dims``) matrix,
514 represented as a list of rows.
516 return [[uniform(-10, 10) for i
in range(dims
)] for j
in range(dims
)]
519 def random_orthant_params(self
):
521 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
522 random game over the nonnegative orthant.
524 ambient_dim
= randint(1, 10)
525 K
= NonnegativeOrthant(ambient_dim
)
526 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
527 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
528 L
= self
.random_square_matrix(K
.dimension())
529 return (L
, K
, e1
, e2
)
532 def random_icecream_params(self
):
534 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
535 random game over the ice cream cone.
537 # Use a minimum dimension of two to avoid divide-by-zero in
538 # the fudge factor we make up later.
539 ambient_dim
= randint(2, 10)
540 K
= IceCream(ambient_dim
)
541 e1
= [1] # Set the "height" of e1 to one
542 e2
= [1] # And the same for e2
544 # If we choose the rest of the components of e1,e2 randomly
545 # between 0 and 1, then the largest the squared norm of the
546 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
547 # need to make it less than one (the height of the cone) so
548 # that the whole thing is in the cone. The norm of the
549 # non-height part is sqrt(dim(K) - 1), and we can divide by
551 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
552 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
553 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
554 L
= self
.random_square_matrix(K
.dimension())
556 return (L
, K
, e1
, e2
)
559 def assert_within_tol(self
, first
, second
):
561 Test that ``first`` and ``second`` are equal within our default
564 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
567 def assert_norm_within_tol(self
, first
, second
):
569 Test that ``first`` and ``second`` vectors are equal in the
570 sense that the norm of their difference is within our default
573 self
.assert_within_tol(norm(first
- second
), 0)
576 def assert_solution_exists(self
, L
, K
, e1
, e2
):
578 Given the parameters needed to construct a SymmetricLinearGame,
579 ensure that that game has a solution.
581 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
584 # The matrix() constructor assumes that ``L`` is a list of
585 # columns, so we transpose it to agree with what
586 # SymmetricLinearGame() thinks.
587 L_matrix
= matrix(L
).trans()
588 expected
= inner_product(L_matrix
*soln
.player1_optimal(),
589 soln
.player2_optimal())
590 self
.assert_within_tol(soln
.game_value(), expected
)
593 def test_solution_exists_nonnegative_orthant(self
):
595 Every linear game has a solution, so we should be able to solve
596 every symmetric linear game over the NonnegativeOrthant. Pick
597 some parameters randomly and give it a shot. The resulting
598 optimal solutions should give us the optimal game value when we
599 apply the payoff operator to them.
601 (L
, K
, e1
, e2
) = self
.random_orthant_params()
602 self
.assert_solution_exists(L
, K
, e1
, e2
)
605 def test_solution_exists_ice_cream(self
):
607 Like :meth:`test_solution_exists_nonnegative_orthant`, except
608 over the ice cream cone.
610 (L
, K
, e1
, e2
) = self
.random_icecream_params()
611 self
.assert_solution_exists(L
, K
, e1
, e2
)
614 def test_negative_value_Z_operator(self
):
616 Test the example given in Gowda/Ravindran of a Z-matrix with
617 negative game value on the nonnegative orthant.
619 K
= NonnegativeOrthant(2)
623 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
624 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
627 def test_nonnegative_scaling_orthant(self
):
629 Test that scaling ``L`` by a nonnegative number scales the value
630 of the game by the same number. Use the nonnegative orthant as
633 (L
, K
, e1
, e2
) = self
.random_orthant_params()
634 # Make ``L`` a matrix so that we can scale it by alpha. Its
635 # random, so who cares if it gets transposed.
637 G1
= SymmetricLinearGame(L
, K
, e1
, e2
)
638 value1
= G1
.solution().game_value()
640 alpha
= uniform(0.1, 10)
641 G2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
642 value2
= G2
.solution().game_value()
643 self
.assert_within_tol(alpha
*value1
, value2
)
646 def test_nonnegative_scaling_icecream(self
):
648 The same test as :meth:`test_nonnegative_scaling_orthant`,
649 except over the ice cream cone.
651 (L
, K
, e1
, e2
) = self
.random_icecream_params()
652 # Make ``L`` a matrix so that we can scale it by alpha. Its
653 # random, so who cares if it gets transposed.
655 G1
= SymmetricLinearGame(L
, K
, e1
, e2
)
656 value1
= G1
.solution().game_value()
658 alpha
= uniform(0.1, 10)
659 G2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
660 value2
= G2
.solution().game_value()
661 self
.assert_within_tol(alpha
*value1
, value2
)
664 def assert_translation_works(self
, L
, K
, e1
, e2
):
666 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
667 the value of the associated game by alpha.
669 e1
= matrix(e1
, (K
.dimension(), 1))
670 e2
= matrix(e2
, (K
.dimension(), 1))
671 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
672 G_soln
= G
.solution()
673 value_G
= G_soln
.game_value()
674 x_bar
= G_soln
.player1_optimal()
675 y_bar
= G_soln
.player2_optimal()
677 alpha
= uniform(-10, 10)
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 L
= matrix(L
).trans()
683 # Likewise, this is the "correct" representation of ``M``, but
687 # so we have to transpose it when we feed it to the constructor.
688 H
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
689 value_H
= H
.solution().game_value()
691 # Make sure the same optimal pair works.
692 H_payoff
= inner_product(M
*x_bar
, y_bar
)
694 self
.assert_within_tol(value_G
+ alpha
, value_H
)
695 self
.assert_within_tol(value_H
, H_payoff
)
698 def test_translation_orthant(self
):
700 Test that translation works over the nonnegative orthant.
702 (L
, K
, e1
, e2
) = self
.random_orthant_params()
703 self
.assert_translation_works(L
, K
, e1
, e2
)
706 def test_translation_icecream(self
):
708 The same as :meth:`test_translation_orthant`, except over the
711 (L
, K
, e1
, e2
) = self
.random_icecream_params()
712 self
.assert_translation_works(L
, K
, e1
, e2
)
715 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
716 e1
= matrix(e1
, (K
.dimension(), 1))
717 e2
= matrix(e2
, (K
.dimension(), 1))
718 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
720 # Make ``L`` a CVXOPT matrix so that we can do math with
721 # it. Note that this gives us the "correct" representation of
722 # ``L`` (in agreement with what G has), but COLUMN indexed.
723 L
= matrix(L
).trans()
725 # Likewise, this is the "correct" representation of ``M``, but
729 # so we have to transpose it when we feed it to the constructor.
730 H
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
732 G_soln
= G
.solution()
733 x_bar
= G_soln
.player1_optimal()
734 y_bar
= G_soln
.player2_optimal()
735 H_soln
= H
.solution()
737 # Make sure the switched optimal pair works.
738 H_payoff
= inner_product(M
*y_bar
, x_bar
)
740 self
.assert_within_tol(-G_soln
.game_value(), H_soln
.game_value())
741 self
.assert_within_tol(H_soln
.game_value(), H_payoff
)
744 def test_opposite_game_orthant(self
):
746 Check the value of the "opposite" game that gives rise to a
747 value that is the negation of the original game. Comes from
750 (L
, K
, e1
, e2
) = self
.random_orthant_params()
751 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
754 def test_opposite_game_icecream(self
):
756 Like :meth:`test_opposite_game_orthant`, except over the
759 (L
, K
, e1
, e2
) = self
.random_icecream_params()
760 self
.assert_opposite_game_works(L
, K
, e1
, e2
)