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 = 2*2*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 The factor of two is because if we compare two solutions, both
  22 of which may be off by ``ABS_TOL``, then the result could be off
  23 by ``2*ABS_TOL``. The factor of ``RANDOM_MAX`` allows for
  24 scaling a result (by ``RANDOM_MAX``) that may be off by
  25 ``ABS_TOL``. The final factor of two is to allow for the edge
  26 cases where we get an "unknown" result and need to lower the
  27 CVXOPT tolerance by a factor of two.
  28 """
  29
  30 # Tell pylint to shut up about the large number of methods.
  31 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
  32     """
  33     Tests for the SymmetricLinearGame and Solution classes.
  34     """
  35     def assert_within_tol(self, first, second):
  36         """
  37         Test that ``first`` and ``second`` are equal within a multiple of
  38         our default tolerances.
  39         """
  40         self.assertTrue(abs(first - second) < EPSILON)
  41
  42
  43     def assert_solution_exists(self, G):
  44         """
  45         Given  a SymmetricLinearGame, ensure that it has a solution.
  46         """
  47         soln = G.solution()
  48
  49         expected = inner_product(G._L*soln.player1_optimal(),
  50                                  soln.player2_optimal())
  51         self.assert_within_tol(soln.game_value(), expected)
  52
  53
  54
  55     def test_condition_lower_bound(self):
  56         """
  57         Ensure that the condition number of a game is greater than or
  58         equal to one.
  59
  60         It should be safe to compare these floats directly: we compute
  61         the condition number as the ratio of one nonnegative real number
  62         to a smaller nonnegative real number.
  63         """
  64         G = random_orthant_game()
  65         self.assertTrue(G.condition() >= 1.0)
  66         G = random_icecream_game()
  67         self.assertTrue(G.condition() >= 1.0)
  68
  69
  70     def test_solution_exists_orthant(self):
  71         """
  72         Every linear game has a solution, so we should be able to solve
  73         every symmetric linear game over the NonnegativeOrthant. Pick
  74         some parameters randomly and give it a shot. The resulting
  75         optimal solutions should give us the optimal game value when we
  76         apply the payoff operator to them.
  77         """
  78         G = random_orthant_game()
  79         self.assert_solution_exists(G)
  80
  81
  82     def test_solution_exists_icecream(self):
  83         """
  84         Like :meth:`test_solution_exists_nonnegative_orthant`, except
  85         over the ice cream cone.
  86         """
  87         G = random_icecream_game()
  88         self.assert_solution_exists(G)
  89
  90
  91     def test_negative_value_z_operator(self):
  92         """
  93         Test the example given in Gowda/Ravindran of a Z-matrix with
  94         negative game value on the nonnegative orthant.
  95         """
  96         K = NonnegativeOrthant(2)
  97         e1 = [1, 1]
  98         e2 = e1
  99         L = [[1, -2], [-2, 1]]
 100         G = SymmetricLinearGame(L, K, e1, e2)
 101         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 102
 103
 104     def assert_scaling_works(self, G):
 105         """
 106         Test that scaling ``L`` by a nonnegative number scales the value
 107         of the game by the same number.
 108         """
 109         (alpha, H) = random_nn_scaling(G)
 110         value1 = G.solution().game_value()
 111         value2 = H.solution().game_value()
 112         self.assert_within_tol(alpha*value1, value2)
 113
 114
 115     def test_scaling_orthant(self):
 116         """
 117         Test that scaling ``L`` by a nonnegative number scales the value
 118         of the game by the same number over the nonnegative orthant.
 119         """
 120         G = random_orthant_game()
 121         self.assert_scaling_works(G)
 122
 123
 124     def test_scaling_icecream(self):
 125         """
 126         The same test as :meth:`test_nonnegative_scaling_orthant`,
 127         except over the ice cream cone.
 128         """
 129         G = random_icecream_game()
 130         self.assert_scaling_works(G)
 131
 132
 133     def assert_translation_works(self, G):
 134         """
 135         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 136         the value of the associated game by alpha.
 137         """
 138         # We need to use ``L`` later, so make sure we transpose it
 139         # before passing it in as a column-indexed matrix.
 140         soln1 = G.solution()
 141         value1 = soln1.game_value()
 142         x_bar = soln1.player1_optimal()
 143         y_bar = soln1.player2_optimal()
 144
 145         # This is the "correct" representation of ``M``, but COLUMN
 146         # indexed...
 147         (alpha, H) = random_translation(G)
 148         value2 = H.solution().game_value()
 149
 150         self.assert_within_tol(value1 + alpha, value2)
 151
 152         # Make sure the same optimal pair works.
 153         self.assert_within_tol(value2, inner_product(H._L*x_bar, y_bar))
 154
 155
 156     def test_translation_orthant(self):
 157         """
 158         Test that translation works over the nonnegative orthant.
 159         """
 160         G = random_orthant_game()
 161         self.assert_translation_works(G)
 162
 163
 164     def test_translation_icecream(self):
 165         """
 166         The same as :meth:`test_translation_orthant`, except over the
 167         ice cream cone.
 168         """
 169         G = random_icecream_game()
 170         self.assert_translation_works(G)
 171
 172
 173     def assert_opposite_game_works(self, G):
 174         """
 175         Check the value of the "opposite" game that gives rise to a
 176         value that is the negation of the original game. Comes from
 177         some corollary.
 178         """
 179         # This is the "correct" representation of ``M``, but
 180         # COLUMN indexed...
 181         M = -G._L.trans()
 182
 183         # so we have to transpose it when we feed it to the constructor.
 184         # Note: the condition number of ``H`` should be comparable to ``G``.
 185         H = SymmetricLinearGame(M.trans(), G._K, G._e2, G._e1)
 186
 187         soln1 = G.solution()
 188         x_bar = soln1.player1_optimal()
 189         y_bar = soln1.player2_optimal()
 190         soln2 = H.solution()
 191
 192         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 193
 194         # Make sure the switched optimal pair works.
 195         self.assert_within_tol(soln2.game_value(),
 196                                inner_product(M*y_bar, x_bar))
 197
 198
 199     def test_opposite_game_orthant(self):
 200         """
 201         Test the value of the "opposite" game over the nonnegative
 202         orthant.
 203         """
 204         G = random_orthant_game()
 205         self.assert_opposite_game_works(G)
 206
 207
 208     def test_opposite_game_icecream(self):
 209         """
 210         Like :meth:`test_opposite_game_orthant`, except over the
 211         ice-cream cone.
 212         """
 213         G = random_icecream_game()
 214         self.assert_opposite_game_works(G)
 215
 216
 217     def assert_orthogonality(self, G):
 218         """
 219         Two orthogonality relations hold at an optimal solution, and we
 220         check them here.
 221         """
 222         soln = G.solution()
 223         x_bar = soln.player1_optimal()
 224         y_bar = soln.player2_optimal()
 225         value = soln.game_value()
 226
 227         ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1)
 228         self.assert_within_tol(ip1, 0)
 229
 230         ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar)
 231         self.assert_within_tol(ip2, 0)
 232
 233
 234     def test_orthogonality_orthant(self):
 235         """
 236         Check the orthgonality relationships that hold for a solution
 237         over the nonnegative orthant.
 238         """
 239         G = random_orthant_game()
 240         self.assert_orthogonality(G)
 241
 242
 243     def test_orthogonality_icecream(self):
 244         """
 245         Check the orthgonality relationships that hold for a solution
 246         over the ice-cream cone.
 247         """
 248         G = random_icecream_game()
 249         self.assert_orthogonality(G)
 250
 251
 252     def test_positive_operator_value(self):
 253         """
 254         Test that a positive operator on the nonnegative orthant gives
 255         rise to a a game with a nonnegative value.
 256
 257         This test theoretically applies to the ice-cream cone as well,
 258         but we don't know how to make positive operators on that cone.
 259         """
 260         G = random_positive_orthant_game()
 261         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 262
 263
 264     def assert_lyapunov_works(self, G):
 265         """
 266         Check that Lyapunov games act the way we expect.
 267         """
 268         soln = G.solution()
 269
 270         # We only check for positive/negative stability if the game
 271         # value is not basically zero. If the value is that close to
 272         # zero, we just won't check any assertions.
 273         #
 274         # See :meth:`assert_within_tol` for an explanation of the
 275         # fudge factors.
 276         eigs = eigenvalues_re(G._L)
 277
 278         if soln.game_value() > EPSILON:
 279             # L should be positive stable
 280             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 281             self.assertTrue(positive_stable)
 282         elif soln.game_value() < -EPSILON:
 283             # L should be negative stable
 284             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 285             self.assertTrue(negative_stable)
 286
 287         # The dual game's value should always equal the primal's.
 288         dualsoln = G.dual().solution()
 289         self.assert_within_tol(dualsoln.game_value(), soln.game_value())
 290
 291
 292     def test_lyapunov_orthant(self):
 293         """
 294         Test that a Lyapunov game on the nonnegative orthant works.
 295         """
 296         G = random_ll_orthant_game()
 297         self.assert_lyapunov_works(G)
 298
 299
 300     def test_lyapunov_icecream(self):
 301         """
 302         Test that a Lyapunov game on the ice-cream cone works.
 303         """
 304         G = random_ll_icecream_game()
 305         self.assert_lyapunov_works(G)