]>
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
, eigenvalues_re
, identity
,
21 printing
.options
['dformat'] = options
.FLOAT_FORMAT
22 solvers
.options
['show_progress'] = options
.VERBOSE
27 A representation of the solution of a linear game. It should contain
28 the value of the game, and both players' strategies.
33 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
34 Game value: 10.0000000
43 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
45 Create a new Solution object from a game value and two optimal
46 strategies for the players.
48 self
._game
_value
= game_value
49 self
._player
1_optimal
= p1_optimal
50 self
._player
2_optimal
= p2_optimal
54 Return a string describing the solution of a linear game.
56 The three data that are described are,
58 * The value of the game.
59 * The optimal strategy of player one.
60 * The optimal strategy of player two.
62 The two optimal strategy vectors are indented by two spaces.
64 tpl
= 'Game value: {:.7f}\n' \
65 'Player 1 optimal:{:s}\n' \
66 'Player 2 optimal:{:s}'
68 p1_str
= '\n{!s}'.format(self
.player1_optimal())
69 p1_str
= '\n '.join(p1_str
.splitlines())
70 p2_str
= '\n{!s}'.format(self
.player2_optimal())
71 p2_str
= '\n '.join(p2_str
.splitlines())
73 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
78 Return the game value for this solution.
83 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
88 return self
._game
_value
91 def player1_optimal(self
):
93 Return player one's optimal strategy in this solution.
98 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
99 >>> print(s.player1_optimal())
105 return self
._player
1_optimal
108 def player2_optimal(self
):
110 Return player two's optimal strategy in this solution.
115 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
116 >>> print(s.player2_optimal())
122 return self
._player
2_optimal
125 class SymmetricLinearGame
:
127 A representation of a symmetric linear game.
129 The data for a symmetric linear game are,
131 * A "payoff" operator ``L``.
132 * A symmetric cone ``K``.
133 * Two points ``e1`` and ``e2`` in the interior of ``K``.
135 The ambient space is assumed to be the span of ``K``.
137 With those data understood, the game is played as follows. Players
138 one and two choose points :math:`x` and :math:`y` respectively, from
139 their respective strategy sets,
146 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
151 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
155 Afterwards, a "payout" is computed as :math:`\left\langle
156 L\left(x\right), y \right\rangle` and is paid to player one out of
157 player two's pocket. The game is therefore zero sum, and we suppose
158 that player one would like to guarantee himself the largest minimum
159 payout possible. That is, player one wishes to,
164 &\underset{y \in \Delta_{2}}{\min}\left(
165 \left\langle L\left(x\right), y \right\rangle
167 \text{subject to } & x \in \Delta_{1}.
170 Player two has the simultaneous goal to,
175 &\underset{x \in \Delta_{1}}{\max}\left(
176 \left\langle L\left(x\right), y \right\rangle
178 \text{subject to } & y \in \Delta_{2}.
181 These goals obviously conflict (the game is zero sum), but an
182 existence theorem guarantees at least one optimal min-max solution
183 from which neither player would like to deviate. This class is
184 able to find such a solution.
189 L : list of list of float
190 A matrix represented as a list of ROWS. This representation
191 agrees with (for example) SageMath and NumPy, but not with CVXOPT
192 (whose matrix constructor accepts a list of columns).
194 K : :class:`SymmetricCone`
195 The symmetric cone instance over which the game is played.
198 The interior point of ``K`` belonging to player one; it
199 can be of any iterable type having the correct length.
202 The interior point of ``K`` belonging to player two; it
203 can be of any enumerable type having the correct length.
209 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
214 >>> from cones import NonnegativeOrthant
215 >>> K = NonnegativeOrthant(3)
216 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
219 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
221 The linear game (L, K, e1, e2) where
225 K = Nonnegative orthant in the real 3-space,
233 Lists can (and probably should) be used for every argument::
235 >>> from cones import NonnegativeOrthant
236 >>> K = NonnegativeOrthant(2)
237 >>> L = [[1,0],[0,1]]
240 >>> G = SymmetricLinearGame(L, K, e1, e2)
242 The linear game (L, K, e1, e2) where
245 K = Nonnegative orthant in the real 2-space,
251 The points ``e1`` and ``e2`` can also be passed as some other
252 enumerable type (of the correct length) without much harm, since
253 there is no row/column ambiguity::
257 >>> from cones import NonnegativeOrthant
258 >>> K = NonnegativeOrthant(2)
259 >>> L = [[1,0],[0,1]]
260 >>> e1 = cvxopt.matrix([1,1])
261 >>> e2 = numpy.matrix([1,1])
262 >>> G = SymmetricLinearGame(L, K, e1, e2)
264 The linear game (L, K, e1, e2) where
267 K = Nonnegative orthant in the real 2-space,
273 However, ``L`` will always be intepreted as a list of rows, even
274 if it is passed as a :class:`cvxopt.base.matrix` which is
275 otherwise indexed by columns::
278 >>> from cones import NonnegativeOrthant
279 >>> K = NonnegativeOrthant(2)
280 >>> L = [[1,2],[3,4]]
283 >>> G = SymmetricLinearGame(L, K, e1, e2)
285 The linear game (L, K, e1, e2) where
288 K = Nonnegative orthant in the real 2-space,
293 >>> L = cvxopt.matrix(L)
298 >>> G = SymmetricLinearGame(L, K, e1, e2)
300 The linear game (L, K, e1, e2) where
303 K = Nonnegative orthant in the real 2-space,
310 def __init__(self
, L
, K
, e1
, e2
):
312 Create a new SymmetricLinearGame object.
315 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
316 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
318 # Our input ``L`` is indexed by rows but CVXOPT matrices are
319 # indexed by columns, so we need to transpose the input before
320 # feeding it to CVXOPT.
321 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
323 if not self
._e
1 in K
:
324 raise ValueError('the point e1 must lie in the interior of K')
326 if not self
._e
2 in K
:
327 raise ValueError('the point e2 must lie in the interior of K')
331 Return a string representation of this game.
333 tpl
= 'The linear game (L, K, e1, e2) where\n' \
338 indented_L
= '\n '.join(str(self
._L).splitlines())
339 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
340 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
341 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
346 Solve this linear game and return a :class:`Solution`.
352 A :class:`Solution` object describing the game's value and
353 the optimal strategies of both players.
357 GameUnsolvableException
358 If the game could not be solved (if an optimal solution to its
359 associated cone program was not found).
364 This example is computed in Gowda and Ravindran in the section
365 "The value of a Z-transformation"::
367 >>> from cones import NonnegativeOrthant
368 >>> K = NonnegativeOrthant(3)
369 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
372 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
373 >>> print(SLG.solution())
374 Game value: -6.1724138
384 The value of the following game can be computed using the fact
385 that the identity is invertible::
387 >>> from cones import NonnegativeOrthant
388 >>> K = NonnegativeOrthant(3)
389 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
392 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
393 >>> print(SLG.solution())
394 Game value: 0.0312500
405 # The cone "C" that appears in the statement of the CVXOPT
407 C
= CartesianProduct(self
._K
, self
._K
)
409 # The column vector "b" that appears on the right-hand side of
410 # Ax = b in the statement of the CVXOPT conelp program.
411 b
= matrix([1], tc
='d')
413 # A column of zeros that fits K.
414 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
416 # The column vector "h" that appears on the right-hand side of
417 # Gx + s = h in the statement of the CVXOPT conelp program.
418 h
= matrix([zero
, zero
])
420 # The column vector "c" that appears in the objective function
421 # value <c,x> in the statement of the CVXOPT conelp program.
422 c
= matrix([-1, zero
])
424 # The matrix "G" that appears on the left-hand side of Gx + s = h
425 # in the statement of the CVXOPT conelp program.
426 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
427 append_col(self
._e
1, -self
._L))
429 # The matrix "A" that appears on the right-hand side of Ax = b
430 # in the statement of the CVXOPT conelp program.
431 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
433 # Actually solve the thing and obtain a dictionary describing
435 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
437 p1_value
= -soln_dict
['primal objective']
438 p2_value
= -soln_dict
['dual objective']
439 p1_optimal
= soln_dict
['x'][1:]
440 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
442 # The "status" field contains "optimal" if everything went
443 # according to plan. Other possible values are "primal
444 # infeasible", "dual infeasible", "unknown", all of which mean
445 # we didn't get a solution. The "infeasible" ones are the
446 # worst, since they indicate that CVXOPT is convinced the
447 # problem is infeasible (and that cannot happen).
448 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
449 raise GameUnsolvableException(soln_dict
)
450 elif soln_dict
['status'] == 'unknown':
451 # When we get a status of "unknown", we may still be able
452 # to salvage a solution out of the returned
453 # dictionary. Often this is the result of numerical
454 # difficulty and we can simply check that the primal/dual
455 # objectives match (within a tolerance) and that the
456 # primal/dual optimal solutions are within the cone (to a
457 # tolerance as well).
458 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
459 raise GameUnsolvableException(soln_dict
)
460 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
461 raise GameUnsolvableException(soln_dict
)
463 return Solution(p1_value
, p1_optimal
, p2_optimal
)
468 Return the dual game to this game.
470 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
471 then its dual is :math:`G^{*} =
472 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
473 is symmetric, :math:`K^{*} = K`.
478 >>> from cones import NonnegativeOrthant
479 >>> K = NonnegativeOrthant(3)
480 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
483 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
484 >>> print(SLG.dual())
485 The linear game (L, K, e1, e2) where
489 K = Nonnegative orthant in the real 3-space,
498 # We pass ``self._L`` right back into the constructor, because
499 # it will be transposed there. And keep in mind that ``self._K``
501 return SymmetricLinearGame(self
._L,
508 def _random_matrix(dims
):
510 Generate a random square (``dims``-by-``dims``) matrix. This is used
511 only by the :class:`SymmetricLinearGameTest` class.
513 return matrix([[uniform(-10, 10) for i
in range(dims
)]
514 for j
in range(dims
)])
516 def _random_nonnegative_matrix(dims
):
518 Generate a random square (``dims``-by-``dims``) matrix with
519 nonnegative entries. This is used only by the
520 :class:`SymmetricLinearGameTest` class.
522 L
= _random_matrix(dims
)
523 return matrix([abs(entry
) for entry
in L
], (dims
, dims
))
525 def _random_diagonal_matrix(dims
):
527 Generate a random square (``dims``-by-``dims``) matrix with nonzero
528 entries only on the diagonal. This is used only by the
529 :class:`SymmetricLinearGameTest` class.
531 return matrix([[uniform(-10, 10)*int(i
== j
) for i
in range(dims
)]
532 for j
in range(dims
)])
535 def _random_skew_symmetric_matrix(dims
):
537 Generate a random skew-symmetrix (``dims``-by-``dims``) matrix.
542 >>> A = _random_skew_symmetric_matrix(randint(1, 10))
543 >>> norm(A + A.trans()) < options.ABS_TOL
547 strict_ut
= [[uniform(-10, 10)*int(i
< j
) for i
in range(dims
)]
548 for j
in range(dims
)]
550 strict_ut
= matrix(strict_ut
, (dims
, dims
))
551 return strict_ut
- strict_ut
.trans()
554 def _random_lyapunov_like_icecream(dims
):
556 Generate a random Lyapunov-like matrix over the ice-cream cone in
559 a
= matrix([uniform(-10, 10)], (1, 1))
560 b
= matrix([uniform(-10, 10) for idx
in range(dims
-1)], (dims
-1, 1))
561 D
= _random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
562 row1
= append_col(a
, b
.trans())
563 row2
= append_col(b
, D
)
564 return append_row(row1
, row2
)
567 def _random_orthant_params():
569 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
570 random game over the nonnegative orthant. This is only used by
571 the :class:`SymmetricLinearGameTest` class.
573 ambient_dim
= randint(1, 10)
574 K
= NonnegativeOrthant(ambient_dim
)
575 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
576 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
577 L
= _random_matrix(K
.dimension())
578 return (L
, K
, matrix(e1
), matrix(e2
))
581 def _random_icecream_params():
583 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
584 random game over the ice cream cone. This is only used by
585 the :class:`SymmetricLinearGameTest` class.
587 # Use a minimum dimension of two to avoid divide-by-zero in
588 # the fudge factor we make up later.
589 ambient_dim
= randint(2, 10)
590 K
= IceCream(ambient_dim
)
591 e1
= [1] # Set the "height" of e1 to one
592 e2
= [1] # And the same for e2
594 # If we choose the rest of the components of e1,e2 randomly
595 # between 0 and 1, then the largest the squared norm of the
596 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
597 # need to make it less than one (the height of the cone) so
598 # that the whole thing is in the cone. The norm of the
599 # non-height part is sqrt(dim(K) - 1), and we can divide by
601 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
602 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
603 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
604 L
= _random_matrix(K
.dimension())
606 return (L
, K
, matrix(e1
), matrix(e2
))
609 class SymmetricLinearGameTest(TestCase
):
611 Tests for the SymmetricLinearGame and Solution classes.
613 def assert_within_tol(self
, first
, second
):
615 Test that ``first`` and ``second`` are equal within our default
618 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
621 def assert_norm_within_tol(self
, first
, second
):
623 Test that ``first`` and ``second`` vectors are equal in the
624 sense that the norm of their difference is within our default
627 self
.assert_within_tol(norm(first
- second
), 0)
630 def assert_solution_exists(self
, L
, K
, e1
, e2
):
632 Given the parameters needed to construct a SymmetricLinearGame,
633 ensure that that game has a solution.
635 # The matrix() constructor assumes that ``L`` is a list of
636 # columns, so we transpose it to agree with what
637 # SymmetricLinearGame() thinks.
638 G
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
641 expected
= inner_product(L
*soln
.player1_optimal(),
642 soln
.player2_optimal())
643 self
.assert_within_tol(soln
.game_value(), expected
)
646 def test_solution_exists_orthant(self
):
648 Every linear game has a solution, so we should be able to solve
649 every symmetric linear game over the NonnegativeOrthant. Pick
650 some parameters randomly and give it a shot. The resulting
651 optimal solutions should give us the optimal game value when we
652 apply the payoff operator to them.
654 (L
, K
, e1
, e2
) = _random_orthant_params()
655 self
.assert_solution_exists(L
, K
, e1
, e2
)
658 def test_solution_exists_icecream(self
):
660 Like :meth:`test_solution_exists_nonnegative_orthant`, except
661 over the ice cream cone.
663 (L
, K
, e1
, e2
) = _random_icecream_params()
664 self
.assert_solution_exists(L
, K
, e1
, e2
)
667 def test_negative_value_z_operator(self
):
669 Test the example given in Gowda/Ravindran of a Z-matrix with
670 negative game value on the nonnegative orthant.
672 K
= NonnegativeOrthant(2)
675 L
= [[1, -2], [-2, 1]]
676 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
677 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
680 def assert_scaling_works(self
, L
, K
, e1
, e2
):
682 Test that scaling ``L`` by a nonnegative number scales the value
683 of the game by the same number.
685 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
686 value1
= game1
.solution().game_value()
688 alpha
= uniform(0.1, 10)
689 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
690 value2
= game2
.solution().game_value()
691 self
.assert_within_tol(alpha
*value1
, value2
)
694 def test_scaling_orthant(self
):
696 Test that scaling ``L`` by a nonnegative number scales the value
697 of the game by the same number over the nonnegative orthant.
699 (L
, K
, e1
, e2
) = _random_orthant_params()
700 self
.assert_scaling_works(L
, K
, e1
, e2
)
703 def test_scaling_icecream(self
):
705 The same test as :meth:`test_nonnegative_scaling_orthant`,
706 except over the ice cream cone.
708 (L
, K
, e1
, e2
) = _random_icecream_params()
709 self
.assert_scaling_works(L
, K
, e1
, e2
)
712 def assert_translation_works(self
, L
, K
, e1
, e2
):
714 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
715 the value of the associated game by alpha.
717 # We need to use ``L`` later, so make sure we transpose it
718 # before passing it in as a column-indexed matrix.
719 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
720 soln1
= game1
.solution()
721 value1
= soln1
.game_value()
722 x_bar
= soln1
.player1_optimal()
723 y_bar
= soln1
.player2_optimal()
725 alpha
= uniform(-10, 10)
726 tensor_prod
= e1
*e2
.trans()
728 # This is the "correct" representation of ``M``, but COLUMN
730 M
= L
+ alpha
*tensor_prod
732 # so we have to transpose it when we feed it to the constructor.
733 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
734 value2
= game2
.solution().game_value()
736 self
.assert_within_tol(value1
+ alpha
, value2
)
738 # Make sure the same optimal pair works.
739 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
742 def test_translation_orthant(self
):
744 Test that translation works over the nonnegative orthant.
746 (L
, K
, e1
, e2
) = _random_orthant_params()
747 self
.assert_translation_works(L
, K
, e1
, e2
)
750 def test_translation_icecream(self
):
752 The same as :meth:`test_translation_orthant`, except over the
755 (L
, K
, e1
, e2
) = _random_icecream_params()
756 self
.assert_translation_works(L
, K
, e1
, e2
)
759 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
761 Check the value of the "opposite" game that gives rise to a
762 value that is the negation of the original game. Comes from
765 # We need to use ``L`` later, so make sure we transpose it
766 # before passing it in as a column-indexed matrix.
767 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
769 # This is the "correct" representation of ``M``, but
773 # so we have to transpose it when we feed it to the constructor.
774 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
776 soln1
= game1
.solution()
777 x_bar
= soln1
.player1_optimal()
778 y_bar
= soln1
.player2_optimal()
779 soln2
= game2
.solution()
781 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
783 # Make sure the switched optimal pair works.
784 self
.assert_within_tol(soln2
.game_value(),
785 inner_product(M
*y_bar
, x_bar
))
788 def test_opposite_game_orthant(self
):
790 Test the value of the "opposite" game over the nonnegative
793 (L
, K
, e1
, e2
) = _random_orthant_params()
794 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
797 def test_opposite_game_icecream(self
):
799 Like :meth:`test_opposite_game_orthant`, except over the
802 (L
, K
, e1
, e2
) = _random_icecream_params()
803 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
806 def assert_orthogonality(self
, L
, K
, e1
, e2
):
808 Two orthogonality relations hold at an optimal solution, and we
811 # We need to use ``L`` later, so make sure we transpose it
812 # before passing it in as a column-indexed matrix.
813 game
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
814 soln
= game
.solution()
815 x_bar
= soln
.player1_optimal()
816 y_bar
= soln
.player2_optimal()
817 value
= soln
.game_value()
819 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
820 self
.assert_within_tol(ip1
, 0)
822 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
823 self
.assert_within_tol(ip2
, 0)
826 def test_orthogonality_orthant(self
):
828 Check the orthgonality relationships that hold for a solution
829 over the nonnegative orthant.
831 (L
, K
, e1
, e2
) = _random_orthant_params()
832 self
.assert_orthogonality(L
, K
, e1
, e2
)
835 def test_orthogonality_icecream(self
):
837 Check the orthgonality relationships that hold for a solution
838 over the ice-cream cone.
840 (L
, K
, e1
, e2
) = _random_icecream_params()
841 self
.assert_orthogonality(L
, K
, e1
, e2
)
844 def test_positive_operator_value(self
):
846 Test that a positive operator on the nonnegative orthant gives
847 rise to a a game with a nonnegative value.
849 This test theoretically applies to the ice-cream cone as well,
850 but we don't know how to make positive operators on that cone.
852 (_
, K
, e1
, e2
) = _random_orthant_params()
854 # Ignore that L, we need a nonnegative one.
855 L
= _random_nonnegative_matrix(K
.dimension())
857 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
858 self
.assertTrue(game
.solution().game_value() >= -options
.ABS_TOL
)
861 def assert_lyapunov_works(self
, L
, K
, e1
, e2
):
863 Check that Lyapunov games act the way we expect.
865 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
866 soln
= game
.solution()
868 # We only check for positive/negative stability if the game
869 # value is not basically zero. If the value is that close to
870 # zero, we just won't check any assertions.
871 eigs
= eigenvalues_re(L
)
872 if soln
.game_value() > options
.ABS_TOL
:
873 # L should be positive stable
874 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
875 self
.assertTrue(positive_stable
)
876 elif soln
.game_value() < -options
.ABS_TOL
:
877 # L should be negative stable
878 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
879 self
.assertTrue(negative_stable
)
881 # The dual game's value should always equal the primal's.
882 dualsoln
= game
.dual().solution()
883 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
886 def test_lyapunov_orthant(self
):
888 Test that a Lyapunov game on the nonnegative orthant works.
890 (L
, K
, e1
, e2
) = _random_orthant_params()
892 # Ignore that L, we need a diagonal (Lyapunov-like) one.
893 # (And we don't need to transpose those.)
894 L
= _random_diagonal_matrix(K
.dimension())
896 self
.assert_lyapunov_works(L
, K
, e1
, e2
)
899 def test_lyapunov_icecream(self
):
901 Test that a Lyapunov game on the ice-cream cone works.
903 (L
, K
, e1
, e2
) = _random_icecream_params()
905 # Ignore that L, we need a diagonal (Lyapunov-like) one.
906 # (And we don't need to transpose those.)
907 L
= _random_lyapunov_like_icecream(K
.dimension())
909 self
.assert_lyapunov_works(L
, K
, e1
, e2
)