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
, modifier
=1):
41 Test that ``first`` and ``second`` are equal within a multiple of
42 our default tolerances.
48 The first number to compare.
51 The second number to compare.
54 A scaling factor (default: 1) applied to the default
55 ``EPSILON`` for this comparison. If you have a poorly-
56 conditioned matrix, for example, you may want to set this
60 self
.assertTrue(abs(first
- second
) < EPSILON
*modifier
)
63 def assert_solution_exists(self
, G
):
65 Given a SymmetricLinearGame, ensure that it has a solution.
69 expected
= inner_product(G
._L*soln
.player1_optimal(),
70 soln
.player2_optimal())
71 self
.assert_within_tol(soln
.game_value(), expected
, G
.condition())
75 def test_condition_lower_bound(self
):
77 Ensure that the condition number of a game is greater than or
80 It should be safe to compare these floats directly: we compute
81 the condition number as the ratio of one nonnegative real number
82 to a smaller nonnegative real number.
84 G
= random_orthant_game()
85 self
.assertTrue(G
.condition() >= 1.0)
86 G
= random_icecream_game()
87 self
.assertTrue(G
.condition() >= 1.0)
90 def test_solution_exists_orthant(self
):
92 Every linear game has a solution, so we should be able to solve
93 every symmetric linear game over the NonnegativeOrthant. Pick
94 some parameters randomly and give it a shot. The resulting
95 optimal solutions should give us the optimal game value when we
96 apply the payoff operator to them.
98 G
= random_orthant_game()
99 self
.assert_solution_exists(G
)
102 def test_solution_exists_icecream(self
):
104 Like :meth:`test_solution_exists_nonnegative_orthant`, except
105 over the ice cream cone.
107 G
= random_icecream_game()
108 self
.assert_solution_exists(G
)
111 def test_negative_value_z_operator(self
):
113 Test the example given in Gowda/Ravindran of a Z-matrix with
114 negative game value on the nonnegative orthant.
116 K
= NonnegativeOrthant(2)
119 L
= [[1, -2], [-2, 1]]
120 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
121 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
124 def assert_scaling_works(self
, G
):
126 Test that scaling ``L`` by a nonnegative number scales the value
127 of the game by the same number.
129 (alpha
, H
) = random_nn_scaling(G
)
130 value1
= G
.solution().game_value()
131 value2
= H
.solution().game_value()
132 self
.assert_within_tol(alpha
*value1
, value2
, H
.condition())
135 def test_scaling_orthant(self
):
137 Test that scaling ``L`` by a nonnegative number scales the value
138 of the game by the same number over the nonnegative orthant.
140 G
= random_orthant_game()
141 self
.assert_scaling_works(G
)
144 def test_scaling_icecream(self
):
146 The same test as :meth:`test_nonnegative_scaling_orthant`,
147 except over the ice cream cone.
149 G
= random_icecream_game()
150 self
.assert_scaling_works(G
)
153 def assert_translation_works(self
, G
):
155 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
156 the value of the associated game by alpha.
158 # We need to use ``L`` later, so make sure we transpose it
159 # before passing it in as a column-indexed matrix.
161 value1
= soln1
.game_value()
162 x_bar
= soln1
.player1_optimal()
163 y_bar
= soln1
.player2_optimal()
165 # This is the "correct" representation of ``M``, but COLUMN
167 (alpha
, H
) = random_translation(G
)
168 value2
= H
.solution().game_value()
170 self
.assert_within_tol(value1
+ alpha
, value2
, H
.condition())
172 # Make sure the same optimal pair works.
173 self
.assert_within_tol(value2
,
174 inner_product(H
._L*x_bar
, y_bar
),
178 def test_translation_orthant(self
):
180 Test that translation works over the nonnegative orthant.
182 G
= random_orthant_game()
183 self
.assert_translation_works(G
)
186 def test_translation_icecream(self
):
188 The same as :meth:`test_translation_orthant`, except over the
191 G
= random_icecream_game()
192 self
.assert_translation_works(G
)
195 def assert_opposite_game_works(self
, G
):
197 Check the value of the "opposite" game that gives rise to a
198 value that is the negation of the original game. Comes from
201 # This is the "correct" representation of ``M``, but
205 # so we have to transpose it when we feed it to the constructor.
206 # Note: the condition number of ``H`` should be comparable to ``G``.
207 H
= SymmetricLinearGame(M
.trans(), G
._K
, G
._e
2, G
._e
1)
210 x_bar
= soln1
.player1_optimal()
211 y_bar
= soln1
.player2_optimal()
214 self
.assert_within_tol(-soln1
.game_value(),
218 # Make sure the switched optimal pair works.
219 self
.assert_within_tol(soln2
.game_value(),
220 inner_product(M
*y_bar
, x_bar
),
224 def test_opposite_game_orthant(self
):
226 Test the value of the "opposite" game over the nonnegative
229 G
= random_orthant_game()
230 self
.assert_opposite_game_works(G
)
233 def test_opposite_game_icecream(self
):
235 Like :meth:`test_opposite_game_orthant`, except over the
238 G
= random_icecream_game()
239 self
.assert_opposite_game_works(G
)
242 def assert_orthogonality(self
, G
):
244 Two orthogonality relations hold at an optimal solution, and we
248 x_bar
= soln
.player1_optimal()
249 y_bar
= soln
.player2_optimal()
250 value
= soln
.game_value()
252 ip1
= inner_product(y_bar
, G
._L*x_bar
- value
*G
._e
1)
253 self
.assert_within_tol(ip1
, 0, G
.condition())
255 ip2
= inner_product(value
*G
._e
2 - G
._L.trans()*y_bar
, x_bar
)
256 self
.assert_within_tol(ip2
, 0, G
.condition())
259 def test_orthogonality_orthant(self
):
261 Check the orthgonality relationships that hold for a solution
262 over the nonnegative orthant.
264 G
= random_orthant_game()
265 self
.assert_orthogonality(G
)
268 def test_orthogonality_icecream(self
):
270 Check the orthgonality relationships that hold for a solution
271 over the ice-cream cone.
273 G
= random_icecream_game()
274 self
.assert_orthogonality(G
)
277 def test_positive_operator_value(self
):
279 Test that a positive operator on the nonnegative orthant gives
280 rise to a a game with a nonnegative value.
282 This test theoretically applies to the ice-cream cone as well,
283 but we don't know how to make positive operators on that cone.
285 G
= random_positive_orthant_game()
286 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
289 def assert_lyapunov_works(self
, G
):
291 Check that Lyapunov games act the way we expect.
295 # We only check for positive/negative stability if the game
296 # value is not basically zero. If the value is that close to
297 # zero, we just won't check any assertions.
299 # See :meth:`assert_within_tol` for an explanation of the
301 eigs
= eigenvalues_re(G
._L)
303 if soln
.game_value() > EPSILON
:
304 # L should be positive stable
305 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
306 self
.assertTrue(positive_stable
)
307 elif soln
.game_value() < -EPSILON
:
308 # L should be negative stable
309 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
310 self
.assertTrue(negative_stable
)
312 # The dual game's value should always equal the primal's.
313 dualsoln
= G
.dual().solution()
314 self
.assert_within_tol(dualsoln
.game_value(),
319 def test_lyapunov_orthant(self
):
321 Test that a Lyapunov game on the nonnegative orthant works.
323 G
= random_ll_orthant_game()
324 self
.assert_lyapunov_works(G
)
327 def test_lyapunov_icecream(self
):
329 Test that a Lyapunov game on the ice-cream cone works.
331 G
= random_ll_icecream_game()
332 self
.assert_lyapunov_works(G
)