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):
  40         """
  41         Test that ``first`` and ``second`` are equal within a multiple of
  42         our default tolerances.
  43         """
  44         self.assertTrue(abs(first - second) < EPSILON)
  45
  46
  47     def assert_solution_exists(self, G):
  48         """
  49         Given  a SymmetricLinearGame, ensure that it has a solution.
  50         """
  51         soln = G.solution()
  52
  53         expected = inner_product(G._L*soln.player1_optimal(),
  54                                  soln.player2_optimal())
  55         self.assert_within_tol(soln.game_value(), expected)
  56
  57
  58
  59     def test_condition_lower_bound(self):
  60         """
  61         Ensure that the condition number of a game is greater than or
  62         equal to one.
  63
  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.
  67         """
  68         G = random_orthant_game()
  69         self.assertTrue(G.condition() >= 1.0)
  70         G = random_icecream_game()
  71         self.assertTrue(G.condition() >= 1.0)
  72
  73
  74     def test_solution_exists_orthant(self):
  75         """
  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.
  81         """
  82         G = random_orthant_game()
  83         self.assert_solution_exists(G)
  84
  85
  86     def test_solution_exists_icecream(self):
  87         """
  88         Like :meth:`test_solution_exists_nonnegative_orthant`, except
  89         over the ice cream cone.
  90         """
  91         G = random_icecream_game()
  92         self.assert_solution_exists(G)
  93
  94
  95     def test_negative_value_z_operator(self):
  96         """
  97         Test the example given in Gowda/Ravindran of a Z-matrix with
  98         negative game value on the nonnegative orthant.
  99         """
 100         K = NonnegativeOrthant(2)
 101         e1 = [1, 1]
 102         e2 = e1
 103         L = [[1, -2], [-2, 1]]
 104         G = SymmetricLinearGame(L, K, e1, e2)
 105         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 106
 107
 108     def assert_scaling_works(self, G):
 109         """
 110         Test that scaling ``L`` by a nonnegative number scales the value
 111         of the game by the same number.
 112         """
 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)
 117
 118
 119     def test_scaling_orthant(self):
 120         """
 121         Test that scaling ``L`` by a nonnegative number scales the value
 122         of the game by the same number over the nonnegative orthant.
 123         """
 124         G = random_orthant_game()
 125         self.assert_scaling_works(G)
 126
 127
 128     def test_scaling_icecream(self):
 129         """
 130         The same test as :meth:`test_nonnegative_scaling_orthant`,
 131         except over the ice cream cone.
 132         """
 133         G = random_icecream_game()
 134         self.assert_scaling_works(G)
 135
 136
 137     def assert_translation_works(self, G):
 138         """
 139         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 140         the value of the associated game by alpha.
 141         """
 142         # We need to use ``L`` later, so make sure we transpose it
 143         # before passing it in as a column-indexed matrix.
 144         soln1 = G.solution()
 145         value1 = soln1.game_value()
 146         x_bar = soln1.player1_optimal()
 147         y_bar = soln1.player2_optimal()
 148
 149         # This is the "correct" representation of ``M``, but COLUMN
 150         # indexed...
 151         (alpha, H) = random_translation(G)
 152         value2 = H.solution().game_value()
 153
 154         self.assert_within_tol(value1 + alpha, value2)
 155
 156         # Make sure the same optimal pair works.
 157         self.assert_within_tol(value2, inner_product(H._L*x_bar, y_bar))
 158
 159
 160     def test_translation_orthant(self):
 161         """
 162         Test that translation works over the nonnegative orthant.
 163         """
 164         G = random_orthant_game()
 165         self.assert_translation_works(G)
 166
 167
 168     def test_translation_icecream(self):
 169         """
 170         The same as :meth:`test_translation_orthant`, except over the
 171         ice cream cone.
 172         """
 173         G = random_icecream_game()
 174         self.assert_translation_works(G)
 175
 176
 177     def assert_opposite_game_works(self, G):
 178         """
 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
 181         some corollary.
 182         """
 183         # This is the "correct" representation of ``M``, but
 184         # COLUMN indexed...
 185         M = -G._L.trans()
 186
 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._e2, G._e1)
 190
 191         soln1 = G.solution()
 192         x_bar = soln1.player1_optimal()
 193         y_bar = soln1.player2_optimal()
 194         soln2 = H.solution()
 195
 196         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 197
 198         # Make sure the switched optimal pair works.
 199         self.assert_within_tol(soln2.game_value(),
 200                                inner_product(M*y_bar, x_bar))
 201
 202
 203     def test_opposite_game_orthant(self):
 204         """
 205         Test the value of the "opposite" game over the nonnegative
 206         orthant.
 207         """
 208         G = random_orthant_game()
 209         self.assert_opposite_game_works(G)
 210
 211
 212     def test_opposite_game_icecream(self):
 213         """
 214         Like :meth:`test_opposite_game_orthant`, except over the
 215         ice-cream cone.
 216         """
 217         G = random_icecream_game()
 218         self.assert_opposite_game_works(G)
 219
 220
 221     def assert_orthogonality(self, G):
 222         """
 223         Two orthogonality relations hold at an optimal solution, and we
 224         check them here.
 225         """
 226         soln = G.solution()
 227         x_bar = soln.player1_optimal()
 228         y_bar = soln.player2_optimal()
 229         value = soln.game_value()
 230
 231         ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1)
 232         self.assert_within_tol(ip1, 0)
 233
 234         ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar)
 235         self.assert_within_tol(ip2, 0)
 236
 237
 238     def test_orthogonality_orthant(self):
 239         """
 240         Check the orthgonality relationships that hold for a solution
 241         over the nonnegative orthant.
 242         """
 243         G = random_orthant_game()
 244         self.assert_orthogonality(G)
 245
 246
 247     def test_orthogonality_icecream(self):
 248         """
 249         Check the orthgonality relationships that hold for a solution
 250         over the ice-cream cone.
 251         """
 252         G = random_icecream_game()
 253         self.assert_orthogonality(G)
 254
 255
 256     def test_positive_operator_value(self):
 257         """
 258         Test that a positive operator on the nonnegative orthant gives
 259         rise to a a game with a nonnegative value.
 260
 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.
 263         """
 264         G = random_positive_orthant_game()
 265         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 266
 267
 268     def assert_lyapunov_works(self, G):
 269         """
 270         Check that Lyapunov games act the way we expect.
 271         """
 272         soln = G.solution()
 273
 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.
 277         #
 278         # See :meth:`assert_within_tol` for an explanation of the
 279         # fudge factors.
 280         eigs = eigenvalues_re(G._L)
 281
 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)
 290
 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())
 294
 295
 296     def test_lyapunov_orthant(self):
 297         """
 298         Test that a Lyapunov game on the nonnegative orthant works.
 299         """
 300         G = random_ll_orthant_game()
 301         self.assert_lyapunov_works(G)
 302
 303
 304     def test_lyapunov_icecream(self):
 305         """
 306         Test that a Lyapunov game on the ice-cream cone works.
 307         """
 308         G = random_ll_icecream_game()
 309         self.assert_lyapunov_works(G)