test/symmetric_linear_game_test.py

   1 """
   2 Unit tests for the :class:`SymmetricLinearGame` class.
   3 """
   4
   5 from unittest import TestCase
   6
   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)
  15
  16 EPSILON = (1 + RANDOM_MAX)*options.ABS_TOL
  17 """
  18 This is the tolerance constant including fudge factors that we use to
  19 determine whether or not two numbers are equal in tests.
  20
  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
  31 directions).
  32 """
  33
  34 # Tell pylint to shut up about the large number of methods.
  35 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
  36     """
  37     Tests for the SymmetricLinearGame and Solution classes.
  38     """
  39     def assert_within_tol(self, first, second, modifier=1):
  40         """
  41         Test that ``first`` and ``second`` are equal within a multiple of
  42         our default tolerances.
  43
  44         Parameters
  45         ----------
  46
  47         first : float
  48             The first number to compare.
  49
  50         second : float
  51             The second number to compare.
  52
  53         modifier : float
  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
  57             greater than one.
  58
  59         """
  60         self.assertTrue(abs(first - second) < EPSILON*modifier)
  61
  62
  63     def assert_solution_exists(self, G):
  64         """
  65         Given  a SymmetricLinearGame, ensure that it has a solution.
  66         """
  67         soln = G.solution()
  68
  69         expected = inner_product(G._L*soln.player1_optimal(),
  70                                  soln.player2_optimal())
  71         self.assert_within_tol(soln.game_value(), expected, G.condition())
  72
  73
  74
  75     def test_condition_lower_bound(self):
  76         """
  77         Ensure that the condition number of a game is greater than or
  78         equal to one.
  79
  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.
  83         """
  84         G = random_orthant_game()
  85         self.assertTrue(G.condition() >= 1.0)
  86         G = random_icecream_game()
  87         self.assertTrue(G.condition() >= 1.0)
  88
  89
  90     def test_solution_exists_orthant(self):
  91         """
  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.
  97         """
  98         G = random_orthant_game()
  99         self.assert_solution_exists(G)
 100
 101
 102     def test_solution_exists_icecream(self):
 103         """
 104         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 105         over the ice cream cone.
 106         """
 107         G = random_icecream_game()
 108         self.assert_solution_exists(G)
 109
 110
 111     def test_negative_value_z_operator(self):
 112         """
 113         Test the example given in Gowda/Ravindran of a Z-matrix with
 114         negative game value on the nonnegative orthant.
 115         """
 116         K = NonnegativeOrthant(2)
 117         e1 = [1, 1]
 118         e2 = e1
 119         L = [[1, -2], [-2, 1]]
 120         G = SymmetricLinearGame(L, K, e1, e2)
 121         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 122
 123
 124     def assert_scaling_works(self, G):
 125         """
 126         Test that scaling ``L`` by a nonnegative number scales the value
 127         of the game by the same number.
 128         """
 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())
 133
 134
 135     def test_scaling_orthant(self):
 136         """
 137         Test that scaling ``L`` by a nonnegative number scales the value
 138         of the game by the same number over the nonnegative orthant.
 139         """
 140         G = random_orthant_game()
 141         self.assert_scaling_works(G)
 142
 143
 144     def test_scaling_icecream(self):
 145         """
 146         The same test as :meth:`test_nonnegative_scaling_orthant`,
 147         except over the ice cream cone.
 148         """
 149         G = random_icecream_game()
 150         self.assert_scaling_works(G)
 151
 152
 153     def assert_translation_works(self, G):
 154         """
 155         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 156         the value of the associated game by alpha.
 157         """
 158         # We need to use ``L`` later, so make sure we transpose it
 159         # before passing it in as a column-indexed matrix.
 160         soln1 = G.solution()
 161         value1 = soln1.game_value()
 162         x_bar = soln1.player1_optimal()
 163         y_bar = soln1.player2_optimal()
 164
 165         # This is the "correct" representation of ``M``, but COLUMN
 166         # indexed...
 167         (alpha, H) = random_translation(G)
 168         value2 = H.solution().game_value()
 169
 170         self.assert_within_tol(value1 + alpha, value2, H.condition())
 171
 172         # Make sure the same optimal pair works.
 173         self.assert_within_tol(value2,
 174                                inner_product(H._L*x_bar, y_bar),
 175                                H.condition())
 176
 177
 178     def test_translation_orthant(self):
 179         """
 180         Test that translation works over the nonnegative orthant.
 181         """
 182         G = random_orthant_game()
 183         self.assert_translation_works(G)
 184
 185
 186     def test_translation_icecream(self):
 187         """
 188         The same as :meth:`test_translation_orthant`, except over the
 189         ice cream cone.
 190         """
 191         G = random_icecream_game()
 192         self.assert_translation_works(G)
 193
 194
 195     def assert_opposite_game_works(self, G):
 196         """
 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
 199         some corollary.
 200         """
 201         # This is the "correct" representation of ``M``, but
 202         # COLUMN indexed...
 203         M = -G._L.trans()
 204
 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._e2, G._e1)
 208
 209         soln1 = G.solution()
 210         x_bar = soln1.player1_optimal()
 211         y_bar = soln1.player2_optimal()
 212         soln2 = H.solution()
 213
 214         self.assert_within_tol(-soln1.game_value(),
 215                                soln2.game_value(),
 216                                H.condition())
 217
 218         # Make sure the switched optimal pair works.
 219         self.assert_within_tol(soln2.game_value(),
 220                                inner_product(M*y_bar, x_bar),
 221                                H.condition())
 222
 223
 224     def test_opposite_game_orthant(self):
 225         """
 226         Test the value of the "opposite" game over the nonnegative
 227         orthant.
 228         """
 229         G = random_orthant_game()
 230         self.assert_opposite_game_works(G)
 231
 232
 233     def test_opposite_game_icecream(self):
 234         """
 235         Like :meth:`test_opposite_game_orthant`, except over the
 236         ice-cream cone.
 237         """
 238         G = random_icecream_game()
 239         self.assert_opposite_game_works(G)
 240
 241
 242     def assert_orthogonality(self, G):
 243         """
 244         Two orthogonality relations hold at an optimal solution, and we
 245         check them here.
 246         """
 247         soln = G.solution()
 248         x_bar = soln.player1_optimal()
 249         y_bar = soln.player2_optimal()
 250         value = soln.game_value()
 251
 252         ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1)
 253         self.assert_within_tol(ip1, 0, G.condition())
 254
 255         ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar)
 256         self.assert_within_tol(ip2, 0, G.condition())
 257
 258
 259     def test_orthogonality_orthant(self):
 260         """
 261         Check the orthgonality relationships that hold for a solution
 262         over the nonnegative orthant.
 263         """
 264         G = random_orthant_game()
 265         self.assert_orthogonality(G)
 266
 267
 268     def test_orthogonality_icecream(self):
 269         """
 270         Check the orthgonality relationships that hold for a solution
 271         over the ice-cream cone.
 272         """
 273         G = random_icecream_game()
 274         self.assert_orthogonality(G)
 275
 276
 277     def test_positive_operator_value(self):
 278         """
 279         Test that a positive operator on the nonnegative orthant gives
 280         rise to a a game with a nonnegative value.
 281
 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.
 284         """
 285         G = random_positive_orthant_game()
 286         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 287
 288
 289     def assert_lyapunov_works(self, G):
 290         """
 291         Check that Lyapunov games act the way we expect.
 292         """
 293         soln = G.solution()
 294
 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.
 298         #
 299         # See :meth:`assert_within_tol` for an explanation of the
 300         # fudge factors.
 301         eigs = eigenvalues_re(G._L)
 302
 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)
 311
 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(),
 315                                soln.game_value(),
 316                                G.condition())
 317
 318
 319     def test_lyapunov_orthant(self):
 320         """
 321         Test that a Lyapunov game on the nonnegative orthant works.
 322         """
 323         G = random_ll_orthant_game()
 324         self.assert_lyapunov_works(G)
 325
 326
 327     def test_lyapunov_icecream(self):
 328         """
 329         Test that a Lyapunov game on the ice-cream cone works.
 330         """
 331         G = random_ll_icecream_game()
 332         self.assert_lyapunov_works(G)