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