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.games import SymmetricLinearGame
   8 from dunshire.matrices import eigenvalues_re, inner_product, norm
   9 from dunshire import options
  10 from .randomgen import (random_icecream_game, random_ll_icecream_game,
  11                         random_ll_orthant_game, random_nn_scaling,
  12                         random_orthant_game, random_positive_orthant_game,
  13                         random_translation)
  14
  15
  16 # Tell pylint to shut up about the large number of methods.
  17 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
  18     """
  19     Tests for the SymmetricLinearGame and Solution classes.
  20     """
  21     def assert_within_tol(self, first, second, modifier=1):
  22         """
  23         Test that ``first`` and ``second`` are equal within a multiple of
  24         our default tolerances.
  25
  26         Parameters
  27         ----------
  28
  29         first : float
  30             The first number to compare.
  31
  32         second : float
  33             The second number to compare.
  34
  35         modifier : float
  36             A scaling factor (default: 1) applied to the default
  37             tolerance for this comparison. If you have a poorly-
  38             conditioned matrix, for example, you may want to set this
  39             greater than one.
  40
  41         """
  42         self.assertTrue(abs(first - second) < options.ABS_TOL*modifier)
  43
  44
  45     def test_solutions_dont_change_orthant(self):
  46         G = random_orthant_game()
  47         self.assert_solutions_dont_change(G)
  48
  49     def test_solutions_dont_change_icecream(self):
  50         G = random_icecream_game()
  51         self.assert_solutions_dont_change(G)
  52
  53     def assert_solutions_dont_change(self, G):
  54         """
  55         If we solve the same problem twice, we should get
  56         the same answer both times.
  57         """
  58         soln1 = G.solution()
  59         soln2 = G.solution()
  60         p1_diff = norm(soln1.player1_optimal() - soln2.player1_optimal())
  61         p2_diff = norm(soln1.player2_optimal() - soln2.player2_optimal())
  62         gv_diff = abs(soln1.game_value() - soln2.game_value())
  63
  64         p1_close = p1_diff < options.ABS_TOL
  65         p2_close = p2_diff < options.ABS_TOL
  66         gv_close = gv_diff < options.ABS_TOL
  67
  68         self.assertTrue(p1_close and p2_close and gv_close)
  69
  70
  71     def assert_player1_start_valid(self, G):
  72         x = G.player1_start()['x']
  73         s = G.player1_start()['s']
  74         s1 = s[0:G.dimension()]
  75         s2 = s[G.dimension():]
  76         self.assert_within_tol(norm(G.A()*x - G.b()), 0)
  77         self.assertTrue((s1, s2) in G.C())
  78
  79
  80     def test_player1_start_valid_orthant(self):
  81         """
  82         Ensure that player one's starting point is in the orthant.
  83         """
  84         G = random_orthant_game()
  85         self.assert_player1_start_valid(G)
  86
  87
  88     def test_player1_start_valid_icecream(self):
  89         """
  90         Ensure that player one's starting point is in the ice-cream cone.
  91         """
  92         G = random_icecream_game()
  93         self.assert_player1_start_valid(G)
  94
  95
  96     def assert_player2_start_valid(self, G):
  97         z = G.player2_start()['z']
  98         z1 = z[0:G.dimension()]
  99         z2 = z[G.dimension():]
 100         self.assertTrue((z1, z2) in G.C())
 101
 102
 103     def test_player2_start_valid_orthant(self):
 104         """
 105         Ensure that player two's starting point is in the orthant.
 106         """
 107         G = random_orthant_game()
 108         self.assert_player2_start_valid(G)
 109
 110
 111     def test_player2_start_valid_icecream(self):
 112         """
 113         Ensure that player two's starting point is in the ice-cream cone.
 114         """
 115         G = random_icecream_game()
 116         self.assert_player2_start_valid(G)
 117
 118
 119     def test_condition_lower_bound(self):
 120         """
 121         Ensure that the condition number of a game is greater than or
 122         equal to one.
 123
 124         It should be safe to compare these floats directly: we compute
 125         the condition number as the ratio of one nonnegative real number
 126         to a smaller nonnegative real number.
 127         """
 128         G = random_orthant_game()
 129         self.assertTrue(G.condition() >= 1.0)
 130         G = random_icecream_game()
 131         self.assertTrue(G.condition() >= 1.0)
 132
 133
 134     def assert_scaling_works(self, G):
 135         """
 136         Test that scaling ``L`` by a nonnegative number scales the value
 137         of the game by the same number.
 138         """
 139         (alpha, H) = random_nn_scaling(G)
 140         soln1 = G.solution()
 141         soln2 = H.solution()
 142         value1 = soln1.game_value()
 143         value2 = soln2.game_value()
 144         modifier1 = G.epsilon_scale(soln1)
 145         modifier2 = H.epsilon_scale(soln2)
 146         modifier = max(modifier1, modifier2)
 147         self.assert_within_tol(alpha*value1, value2, modifier)
 148
 149
 150     def test_scaling_orthant(self):
 151         """
 152         Test that scaling ``L`` by a nonnegative number scales the value
 153         of the game by the same number over the nonnegative orthant.
 154         """
 155         G = random_orthant_game()
 156         self.assert_scaling_works(G)
 157
 158
 159     def test_scaling_icecream(self):
 160         """
 161         The same test as :meth:`test_nonnegative_scaling_orthant`,
 162         except over the ice cream cone.
 163         """
 164         G = random_icecream_game()
 165         self.assert_scaling_works(G)
 166
 167
 168     def assert_translation_works(self, G):
 169         """
 170         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 171         the value of the associated game by alpha.
 172         """
 173         # We need to use ``L`` later, so make sure we transpose it
 174         # before passing it in as a column-indexed matrix.
 175         soln1 = G.solution()
 176         value1 = soln1.game_value()
 177         x_bar = soln1.player1_optimal()
 178         y_bar = soln1.player2_optimal()
 179
 180         # This is the "correct" representation of ``M``, but COLUMN
 181         # indexed...
 182         (alpha, H) = random_translation(G)
 183         value2 = H.solution().game_value()
 184
 185         modifier = G.epsilon_scale(soln1)
 186         self.assert_within_tol(value1 + alpha, value2, modifier)
 187
 188         # Make sure the same optimal pair works.
 189         self.assert_within_tol(value2, H.payoff(x_bar, y_bar), modifier)
 190
 191
 192     def test_translation_orthant(self):
 193         """
 194         Test that translation works over the nonnegative orthant.
 195         """
 196         G = random_orthant_game()
 197         self.assert_translation_works(G)
 198
 199
 200     def test_translation_icecream(self):
 201         """
 202         The same as :meth:`test_translation_orthant`, except over the
 203         ice cream cone.
 204         """
 205         G = random_icecream_game()
 206         self.assert_translation_works(G)
 207
 208
 209     def assert_opposite_game_works(self, G):
 210         """
 211         Check the value of the "opposite" game that gives rise to a
 212         value that is the negation of the original game. Comes from
 213         some corollary.
 214         """
 215         # This is the "correct" representation of ``M``, but
 216         # COLUMN indexed...
 217         M = -G.L().trans()
 218
 219         # so we have to transpose it when we feed it to the constructor.
 220         # Note: the condition number of ``H`` should be comparable to ``G``.
 221         H = SymmetricLinearGame(M.trans(), G.K(), G.e2(), G.e1())
 222
 223         soln1 = G.solution()
 224         x_bar = soln1.player1_optimal()
 225         y_bar = soln1.player2_optimal()
 226         soln2 = H.solution()
 227
 228         mod = G.epsilon_scale(soln1)
 229         self.assert_within_tol(-soln1.game_value(), soln2.game_value(), mod)
 230
 231         # Make sure the switched optimal pair works. Since x_bar and
 232         # y_bar come from G, we use the same modifier.
 233         self.assert_within_tol(soln2.game_value(), H.payoff(y_bar, x_bar), mod)
 234
 235
 236
 237     def test_opposite_game_orthant(self):
 238         """
 239         Test the value of the "opposite" game over the nonnegative
 240         orthant.
 241         """
 242         G = random_orthant_game()
 243         self.assert_opposite_game_works(G)
 244
 245
 246     def test_opposite_game_icecream(self):
 247         """
 248         Like :meth:`test_opposite_game_orthant`, except over the
 249         ice-cream cone.
 250         """
 251         G = random_icecream_game()
 252         self.assert_opposite_game_works(G)
 253
 254
 255     def assert_orthogonality(self, G):
 256         """
 257         Two orthogonality relations hold at an optimal solution, and we
 258         check them here.
 259         """
 260         soln = G.solution()
 261         x_bar = soln.player1_optimal()
 262         y_bar = soln.player2_optimal()
 263         value = soln.game_value()
 264
 265         ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1())
 266         ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar)
 267
 268         modifier = G.epsilon_scale(soln)
 269         self.assert_within_tol(ip1, 0, modifier)
 270         self.assert_within_tol(ip2, 0, modifier)
 271
 272
 273     def test_orthogonality_orthant(self):
 274         """
 275         Check the orthgonality relationships that hold for a solution
 276         over the nonnegative orthant.
 277         """
 278         G = random_orthant_game()
 279         self.assert_orthogonality(G)
 280
 281
 282     def test_orthogonality_icecream(self):
 283         """
 284         Check the orthgonality relationships that hold for a solution
 285         over the ice-cream cone.
 286         """
 287         G = random_icecream_game()
 288         self.assert_orthogonality(G)
 289
 290
 291     def test_positive_operator_value(self):
 292         """
 293         Test that a positive operator on the nonnegative orthant gives
 294         rise to a a game with a nonnegative value.
 295
 296         This test theoretically applies to the ice-cream cone as well,
 297         but we don't know how to make positive operators on that cone.
 298         """
 299         G = random_positive_orthant_game()
 300         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 301
 302
 303     def assert_lyapunov_works(self, G):
 304         """
 305         Check that Lyapunov games act the way we expect.
 306         """
 307         soln = G.solution()
 308
 309         # We only check for positive/negative stability if the game
 310         # value is not basically zero. If the value is that close to
 311         # zero, we just won't check any assertions.
 312         #
 313         # See :meth:`assert_within_tol` for an explanation of the
 314         # fudge factors.
 315         eigs = eigenvalues_re(G.L())
 316
 317         if soln.game_value() > options.ABS_TOL:
 318             # L should be positive stable
 319             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 320             self.assertTrue(positive_stable)
 321         elif soln.game_value() < -options.ABS_TOL:
 322             # L should be negative stable
 323             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 324             self.assertTrue(negative_stable)
 325
 326         dualsoln = G.dual().solution()
 327         mod = G.epsilon_scale(soln)
 328         self.assert_within_tol(dualsoln.game_value(), soln.game_value(), mod)
 329
 330
 331     def test_lyapunov_orthant(self):
 332         """
 333         Test that a Lyapunov game on the nonnegative orthant works.
 334         """
 335         G = random_ll_orthant_game()
 336         self.assert_lyapunov_works(G)
 337
 338
 339     def test_lyapunov_icecream(self):
 340         """
 341         Test that a Lyapunov game on the ice-cream cone works.
 342         """
 343         G = random_ll_icecream_game()
 344         self.assert_lyapunov_works(G)