2 Unit tests for the :class:`SymmetricLinearGame` class.
5 from unittest
import TestCase
7 from dunshire
.cones
import NonnegativeOrthant
8 from dunshire
.games
import SymmetricLinearGame
9 from dunshire
.matrices
import eigenvalues_re
, inner_product
10 from dunshire
import options
11 from .randomgen
import (RANDOM_MAX
, random_icecream_game
,
12 random_ll_icecream_game
, random_ll_orthant_game
,
13 random_nn_scaling
, random_orthant_game
,
14 random_positive_orthant_game
, random_translation
)
16 EPSILON
= (1 + RANDOM_MAX
)*options
.ABS_TOL
18 This is the tolerance constant including fudge factors that we use to
19 determine whether or not two numbers are equal in tests.
21 Often we will want to compare two solutions, say for games that are
22 equivalent. If the first game value is low by ``ABS_TOL`` and the second
23 is high by ``ABS_TOL``, then the total could be off by ``2*ABS_TOL``. We
24 also subject solutions to translations and scalings, which adds to or
25 scales their error. If the first game is low by ``ABS_TOL`` and the
26 second is high by ``ABS_TOL`` before scaling, then after scaling, the
27 second could be high by ``RANDOM_MAX*ABS_TOL``. That is the rationale
28 for the factor of ``1 + RANDOM_MAX`` in ``EPSILON``. Since ``1 +
29 RANDOM_MAX`` is greater than ``2*ABS_TOL``, we don't need to handle the
30 first issue mentioned (both solutions off by the same amount in opposite
34 # Tell pylint to shut up about the large number of methods.
35 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
37 Tests for the SymmetricLinearGame and Solution classes.
39 def assert_within_tol(self
, first
, second
):
41 Test that ``first`` and ``second`` are equal within a multiple of
42 our default tolerances.
44 self
.assertTrue(abs(first
- second
) < EPSILON
)
47 def assert_solution_exists(self
, G
):
49 Given a SymmetricLinearGame, ensure that it has a solution.
53 expected
= inner_product(G
._L*soln
.player1_optimal(),
54 soln
.player2_optimal())
55 self
.assert_within_tol(soln
.game_value(), expected
)
59 def test_condition_lower_bound(self
):
61 Ensure that the condition number of a game is greater than or
64 It should be safe to compare these floats directly: we compute
65 the condition number as the ratio of one nonnegative real number
66 to a smaller nonnegative real number.
68 G
= random_orthant_game()
69 self
.assertTrue(G
.condition() >= 1.0)
70 G
= random_icecream_game()
71 self
.assertTrue(G
.condition() >= 1.0)
74 def test_solution_exists_orthant(self
):
76 Every linear game has a solution, so we should be able to solve
77 every symmetric linear game over the NonnegativeOrthant. Pick
78 some parameters randomly and give it a shot. The resulting
79 optimal solutions should give us the optimal game value when we
80 apply the payoff operator to them.
82 G
= random_orthant_game()
83 self
.assert_solution_exists(G
)
86 def test_solution_exists_icecream(self
):
88 Like :meth:`test_solution_exists_nonnegative_orthant`, except
89 over the ice cream cone.
91 G
= random_icecream_game()
92 self
.assert_solution_exists(G
)
95 def test_negative_value_z_operator(self
):
97 Test the example given in Gowda/Ravindran of a Z-matrix with
98 negative game value on the nonnegative orthant.
100 K
= NonnegativeOrthant(2)
103 L
= [[1, -2], [-2, 1]]
104 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
105 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
108 def assert_scaling_works(self
, G
):
110 Test that scaling ``L`` by a nonnegative number scales the value
111 of the game by the same number.
113 (alpha
, H
) = random_nn_scaling(G
)
114 value1
= G
.solution().game_value()
115 value2
= H
.solution().game_value()
116 self
.assert_within_tol(alpha
*value1
, value2
)
119 def test_scaling_orthant(self
):
121 Test that scaling ``L`` by a nonnegative number scales the value
122 of the game by the same number over the nonnegative orthant.
124 G
= random_orthant_game()
125 self
.assert_scaling_works(G
)
128 def test_scaling_icecream(self
):
130 The same test as :meth:`test_nonnegative_scaling_orthant`,
131 except over the ice cream cone.
133 G
= random_icecream_game()
134 self
.assert_scaling_works(G
)
137 def assert_translation_works(self
, G
):
139 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
140 the value of the associated game by alpha.
142 # We need to use ``L`` later, so make sure we transpose it
143 # before passing it in as a column-indexed matrix.
145 value1
= soln1
.game_value()
146 x_bar
= soln1
.player1_optimal()
147 y_bar
= soln1
.player2_optimal()
149 # This is the "correct" representation of ``M``, but COLUMN
151 (alpha
, H
) = random_translation(G
)
152 value2
= H
.solution().game_value()
154 self
.assert_within_tol(value1
+ alpha
, value2
)
156 # Make sure the same optimal pair works.
157 self
.assert_within_tol(value2
, inner_product(H
._L*x_bar
, y_bar
))
160 def test_translation_orthant(self
):
162 Test that translation works over the nonnegative orthant.
164 G
= random_orthant_game()
165 self
.assert_translation_works(G
)
168 def test_translation_icecream(self
):
170 The same as :meth:`test_translation_orthant`, except over the
173 G
= random_icecream_game()
174 self
.assert_translation_works(G
)
177 def assert_opposite_game_works(self
, G
):
179 Check the value of the "opposite" game that gives rise to a
180 value that is the negation of the original game. Comes from
183 # This is the "correct" representation of ``M``, but
187 # so we have to transpose it when we feed it to the constructor.
188 # Note: the condition number of ``H`` should be comparable to ``G``.
189 H
= SymmetricLinearGame(M
.trans(), G
._K
, G
._e
2, G
._e
1)
192 x_bar
= soln1
.player1_optimal()
193 y_bar
= soln1
.player2_optimal()
196 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
198 # Make sure the switched optimal pair works.
199 self
.assert_within_tol(soln2
.game_value(),
200 inner_product(M
*y_bar
, x_bar
))
203 def test_opposite_game_orthant(self
):
205 Test the value of the "opposite" game over the nonnegative
208 G
= random_orthant_game()
209 self
.assert_opposite_game_works(G
)
212 def test_opposite_game_icecream(self
):
214 Like :meth:`test_opposite_game_orthant`, except over the
217 G
= random_icecream_game()
218 self
.assert_opposite_game_works(G
)
221 def assert_orthogonality(self
, G
):
223 Two orthogonality relations hold at an optimal solution, and we
227 x_bar
= soln
.player1_optimal()
228 y_bar
= soln
.player2_optimal()
229 value
= soln
.game_value()
231 ip1
= inner_product(y_bar
, G
._L*x_bar
- value
*G
._e
1)
232 self
.assert_within_tol(ip1
, 0)
234 ip2
= inner_product(value
*G
._e
2 - G
._L.trans()*y_bar
, x_bar
)
235 self
.assert_within_tol(ip2
, 0)
238 def test_orthogonality_orthant(self
):
240 Check the orthgonality relationships that hold for a solution
241 over the nonnegative orthant.
243 G
= random_orthant_game()
244 self
.assert_orthogonality(G
)
247 def test_orthogonality_icecream(self
):
249 Check the orthgonality relationships that hold for a solution
250 over the ice-cream cone.
252 G
= random_icecream_game()
253 self
.assert_orthogonality(G
)
256 def test_positive_operator_value(self
):
258 Test that a positive operator on the nonnegative orthant gives
259 rise to a a game with a nonnegative value.
261 This test theoretically applies to the ice-cream cone as well,
262 but we don't know how to make positive operators on that cone.
264 G
= random_positive_orthant_game()
265 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
268 def assert_lyapunov_works(self
, G
):
270 Check that Lyapunov games act the way we expect.
274 # We only check for positive/negative stability if the game
275 # value is not basically zero. If the value is that close to
276 # zero, we just won't check any assertions.
278 # See :meth:`assert_within_tol` for an explanation of the
280 eigs
= eigenvalues_re(G
._L)
282 if soln
.game_value() > EPSILON
:
283 # L should be positive stable
284 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
285 self
.assertTrue(positive_stable
)
286 elif soln
.game_value() < -EPSILON
:
287 # L should be negative stable
288 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
289 self
.assertTrue(negative_stable
)
291 # The dual game's value should always equal the primal's.
292 dualsoln
= G
.dual().solution()
293 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
296 def test_lyapunov_orthant(self
):
298 Test that a Lyapunov game on the nonnegative orthant works.
300 G
= random_ll_orthant_game()
301 self
.assert_lyapunov_works(G
)
304 def test_lyapunov_icecream(self
):
306 Test that a Lyapunov game on the ice-cream cone works.
308 G
= random_ll_icecream_game()
309 self
.assert_lyapunov_works(G
)