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 = G.payoff(soln.player1_optimal(), soln.player2_optimal())
  70         self.assert_within_tol(soln.game_value(), expected, G.condition())
  71
  72
  73
  74     def test_condition_lower_bound(self):
  75         """
  76         Ensure that the condition number of a game is greater than or
  77         equal to one.
  78
  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.
  82         """
  83         G = random_orthant_game()
  84         self.assertTrue(G.condition() >= 1.0)
  85         G = random_icecream_game()
  86         self.assertTrue(G.condition() >= 1.0)
  87
  88
  89     def test_solution_exists_orthant(self):
  90         """
  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.
  96         """
  97         G = random_orthant_game()
  98         self.assert_solution_exists(G)
  99
 100
 101     def test_solution_exists_icecream(self):
 102         """
 103         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 104         over the ice cream cone.
 105         """
 106         G = random_icecream_game()
 107         self.assert_solution_exists(G)
 108
 109
 110     def test_negative_value_z_operator(self):
 111         """
 112         Test the example given in Gowda/Ravindran of a Z-matrix with
 113         negative game value on the nonnegative orthant.
 114         """
 115         K = NonnegativeOrthant(2)
 116         e1 = [1, 1]
 117         e2 = e1
 118         L = [[1, -2], [-2, 1]]
 119         G = SymmetricLinearGame(L, K, e1, e2)
 120         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 121
 122
 123     def assert_scaling_works(self, G):
 124         """
 125         Test that scaling ``L`` by a nonnegative number scales the value
 126         of the game by the same number.
 127         """
 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())
 132
 133
 134     def test_scaling_orthant(self):
 135         """
 136         Test that scaling ``L`` by a nonnegative number scales the value
 137         of the game by the same number over the nonnegative orthant.
 138         """
 139         G = random_orthant_game()
 140         self.assert_scaling_works(G)
 141
 142
 143     def test_scaling_icecream(self):
 144         """
 145         The same test as :meth:`test_nonnegative_scaling_orthant`,
 146         except over the ice cream cone.
 147         """
 148         G = random_icecream_game()
 149         self.assert_scaling_works(G)
 150
 151
 152     def assert_translation_works(self, G):
 153         """
 154         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 155         the value of the associated game by alpha.
 156         """
 157         # We need to use ``L`` later, so make sure we transpose it
 158         # before passing it in as a column-indexed matrix.
 159         soln1 = G.solution()
 160         value1 = soln1.game_value()
 161         x_bar = soln1.player1_optimal()
 162         y_bar = soln1.player2_optimal()
 163
 164         # This is the "correct" representation of ``M``, but COLUMN
 165         # indexed...
 166         (alpha, H) = random_translation(G)
 167         value2 = H.solution().game_value()
 168
 169         self.assert_within_tol(value1 + alpha, value2, H.condition())
 170
 171         # Make sure the same optimal pair works.
 172         self.assert_within_tol(value2,
 173                                H.payoff(x_bar, y_bar),
 174                                H.condition())
 175
 176
 177     def test_translation_orthant(self):
 178         """
 179         Test that translation works over the nonnegative orthant.
 180         """
 181         G = random_orthant_game()
 182         self.assert_translation_works(G)
 183
 184
 185     def test_translation_icecream(self):
 186         """
 187         The same as :meth:`test_translation_orthant`, except over the
 188         ice cream cone.
 189         """
 190         G = random_icecream_game()
 191         self.assert_translation_works(G)
 192
 193
 194     def assert_opposite_game_works(self, G):
 195         """
 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
 198         some corollary.
 199         """
 200         # This is the "correct" representation of ``M``, but
 201         # COLUMN indexed...
 202         M = -G.L().trans()
 203
 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())
 207
 208         soln1 = G.solution()
 209         x_bar = soln1.player1_optimal()
 210         y_bar = soln1.player2_optimal()
 211         soln2 = H.solution()
 212
 213         self.assert_within_tol(-soln1.game_value(),
 214                                soln2.game_value(),
 215                                H.condition())
 216
 217         # Make sure the switched optimal pair works.
 218         self.assert_within_tol(soln2.game_value(),
 219                                H.payoff(y_bar, x_bar),
 220                                H.condition())
 221
 222
 223     def test_opposite_game_orthant(self):
 224         """
 225         Test the value of the "opposite" game over the nonnegative
 226         orthant.
 227         """
 228         G = random_orthant_game()
 229         self.assert_opposite_game_works(G)
 230
 231
 232     def test_opposite_game_icecream(self):
 233         """
 234         Like :meth:`test_opposite_game_orthant`, except over the
 235         ice-cream cone.
 236         """
 237         G = random_icecream_game()
 238         self.assert_opposite_game_works(G)
 239
 240
 241     def assert_orthogonality(self, G):
 242         """
 243         Two orthogonality relations hold at an optimal solution, and we
 244         check them here.
 245         """
 246         soln = G.solution()
 247         x_bar = soln.player1_optimal()
 248         y_bar = soln.player2_optimal()
 249         value = soln.game_value()
 250
 251         ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1())
 252         self.assert_within_tol(ip1, 0, G.condition())
 253
 254         ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar)
 255         self.assert_within_tol(ip2, 0, G.condition())
 256
 257
 258     def test_orthogonality_orthant(self):
 259         """
 260         Check the orthgonality relationships that hold for a solution
 261         over the nonnegative orthant.
 262         """
 263         G = random_orthant_game()
 264         self.assert_orthogonality(G)
 265
 266
 267     def test_orthogonality_icecream(self):
 268         """
 269         Check the orthgonality relationships that hold for a solution
 270         over the ice-cream cone.
 271         """
 272         G = random_icecream_game()
 273         self.assert_orthogonality(G)
 274
 275
 276     def test_positive_operator_value(self):
 277         """
 278         Test that a positive operator on the nonnegative orthant gives
 279         rise to a a game with a nonnegative value.
 280
 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.
 283         """
 284         G = random_positive_orthant_game()
 285         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 286
 287
 288     def assert_lyapunov_works(self, G):
 289         """
 290         Check that Lyapunov games act the way we expect.
 291         """
 292         soln = G.solution()
 293
 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.
 297         #
 298         # See :meth:`assert_within_tol` for an explanation of the
 299         # fudge factors.
 300         eigs = eigenvalues_re(G.L())
 301
 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)
 310
 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(),
 314                                soln.game_value(),
 315                                G.condition())
 316
 317
 318     def test_lyapunov_orthant(self):
 319         """
 320         Test that a Lyapunov game on the nonnegative orthant works.
 321         """
 322         G = random_ll_orthant_game()
 323         self.assert_lyapunov_works(G)
 324
 325
 326     def test_lyapunov_icecream(self):
 327         """
 328         Test that a Lyapunov game on the ice-cream cone works.
 329         """
 330         G = random_ll_icecream_game()
 331         self.assert_lyapunov_works(G)