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
= G
.payoff(soln
.player1_optimal(), soln
.player2_optimal())
70 self
.assert_within_tol(soln
.game_value(), expected
, G
.condition())
74 def test_condition_lower_bound(self
):
76 Ensure that the condition number of a game is greater than or
79 It should be safe to compare these floats directly: we compute
80 the condition number as the ratio of one nonnegative real number
81 to a smaller nonnegative real number.
83 G
= random_orthant_game()
84 self
.assertTrue(G
.condition() >= 1.0)
85 G
= random_icecream_game()
86 self
.assertTrue(G
.condition() >= 1.0)
89 def test_solution_exists_orthant(self
):
91 Every linear game has a solution, so we should be able to solve
92 every symmetric linear game over the NonnegativeOrthant. Pick
93 some parameters randomly and give it a shot. The resulting
94 optimal solutions should give us the optimal game value when we
95 apply the payoff operator to them.
97 G
= random_orthant_game()
98 self
.assert_solution_exists(G
)
101 def test_solution_exists_icecream(self
):
103 Like :meth:`test_solution_exists_nonnegative_orthant`, except
104 over the ice cream cone.
106 G
= random_icecream_game()
107 self
.assert_solution_exists(G
)
110 def test_negative_value_z_operator(self
):
112 Test the example given in Gowda/Ravindran of a Z-matrix with
113 negative game value on the nonnegative orthant.
115 K
= NonnegativeOrthant(2)
118 L
= [[1, -2], [-2, 1]]
119 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
120 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
123 def assert_scaling_works(self
, G
):
125 Test that scaling ``L`` by a nonnegative number scales the value
126 of the game by the same number.
128 (alpha
, H
) = random_nn_scaling(G
)
129 value1
= G
.solution().game_value()
130 value2
= H
.solution().game_value()
131 self
.assert_within_tol(alpha
*value1
, value2
, H
.condition())
134 def test_scaling_orthant(self
):
136 Test that scaling ``L`` by a nonnegative number scales the value
137 of the game by the same number over the nonnegative orthant.
139 G
= random_orthant_game()
140 self
.assert_scaling_works(G
)
143 def test_scaling_icecream(self
):
145 The same test as :meth:`test_nonnegative_scaling_orthant`,
146 except over the ice cream cone.
148 G
= random_icecream_game()
149 self
.assert_scaling_works(G
)
152 def assert_translation_works(self
, G
):
154 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
155 the value of the associated game by alpha.
157 # We need to use ``L`` later, so make sure we transpose it
158 # before passing it in as a column-indexed matrix.
160 value1
= soln1
.game_value()
161 x_bar
= soln1
.player1_optimal()
162 y_bar
= soln1
.player2_optimal()
164 # This is the "correct" representation of ``M``, but COLUMN
166 (alpha
, H
) = random_translation(G
)
167 value2
= H
.solution().game_value()
169 self
.assert_within_tol(value1
+ alpha
, value2
, H
.condition())
171 # Make sure the same optimal pair works.
172 self
.assert_within_tol(value2
,
173 H
.payoff(x_bar
, y_bar
),
177 def test_translation_orthant(self
):
179 Test that translation works over the nonnegative orthant.
181 G
= random_orthant_game()
182 self
.assert_translation_works(G
)
185 def test_translation_icecream(self
):
187 The same as :meth:`test_translation_orthant`, except over the
190 G
= random_icecream_game()
191 self
.assert_translation_works(G
)
194 def assert_opposite_game_works(self
, G
):
196 Check the value of the "opposite" game that gives rise to a
197 value that is the negation of the original game. Comes from
200 # This is the "correct" representation of ``M``, but
204 # so we have to transpose it when we feed it to the constructor.
205 # Note: the condition number of ``H`` should be comparable to ``G``.
206 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e2(), G
.e1())
209 x_bar
= soln1
.player1_optimal()
210 y_bar
= soln1
.player2_optimal()
213 self
.assert_within_tol(-soln1
.game_value(),
217 # Make sure the switched optimal pair works.
218 self
.assert_within_tol(soln2
.game_value(),
219 H
.payoff(y_bar
, x_bar
),
223 def test_opposite_game_orthant(self
):
225 Test the value of the "opposite" game over the nonnegative
228 G
= random_orthant_game()
229 self
.assert_opposite_game_works(G
)
232 def test_opposite_game_icecream(self
):
234 Like :meth:`test_opposite_game_orthant`, except over the
237 G
= random_icecream_game()
238 self
.assert_opposite_game_works(G
)
241 def assert_orthogonality(self
, G
):
243 Two orthogonality relations hold at an optimal solution, and we
247 x_bar
= soln
.player1_optimal()
248 y_bar
= soln
.player2_optimal()
249 value
= soln
.game_value()
251 ip1
= inner_product(y_bar
, G
.L()*x_bar
- value
*G
.e1())
252 self
.assert_within_tol(ip1
, 0, G
.condition())
254 ip2
= inner_product(value
*G
.e2() - G
.L().trans()*y_bar
, x_bar
)
255 self
.assert_within_tol(ip2
, 0, G
.condition())
258 def test_orthogonality_orthant(self
):
260 Check the orthgonality relationships that hold for a solution
261 over the nonnegative orthant.
263 G
= random_orthant_game()
264 self
.assert_orthogonality(G
)
267 def test_orthogonality_icecream(self
):
269 Check the orthgonality relationships that hold for a solution
270 over the ice-cream cone.
272 G
= random_icecream_game()
273 self
.assert_orthogonality(G
)
276 def test_positive_operator_value(self
):
278 Test that a positive operator on the nonnegative orthant gives
279 rise to a a game with a nonnegative value.
281 This test theoretically applies to the ice-cream cone as well,
282 but we don't know how to make positive operators on that cone.
284 G
= random_positive_orthant_game()
285 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
288 def assert_lyapunov_works(self
, G
):
290 Check that Lyapunov games act the way we expect.
294 # We only check for positive/negative stability if the game
295 # value is not basically zero. If the value is that close to
296 # zero, we just won't check any assertions.
298 # See :meth:`assert_within_tol` for an explanation of the
300 eigs
= eigenvalues_re(G
.L())
302 if soln
.game_value() > EPSILON
:
303 # L should be positive stable
304 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
305 self
.assertTrue(positive_stable
)
306 elif soln
.game_value() < -EPSILON
:
307 # L should be negative stable
308 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
309 self
.assertTrue(negative_stable
)
311 # The dual game's value should always equal the primal's.
312 dualsoln
= G
.dual().solution()
313 self
.assert_within_tol(dualsoln
.game_value(),
318 def test_lyapunov_orthant(self
):
320 Test that a Lyapunov game on the nonnegative orthant works.
322 G
= random_ll_orthant_game()
323 self
.assert_lyapunov_works(G
)
326 def test_lyapunov_icecream(self
):
328 Test that a Lyapunov game on the ice-cream cone works.
330 G
= random_ll_icecream_game()
331 self
.assert_lyapunov_works(G
)