src/dunshire/games.py

   1 """
   2 Symmetric linear games and their solutions.
   3
   4 This module contains the main :class:`SymmetricLinearGame` class that
   5 knows how to solve a linear game.
   6 """
   7
   8 # These few are used only for tests.
   9 from math import sqrt
  10 from random import randint, uniform
  11 from unittest import TestCase
  12
  13 # These are mostly actually needed.
  14 from cvxopt import matrix, printing, solvers
  15 from cones import CartesianProduct, IceCream, NonnegativeOrthant
  16 from errors import GameUnsolvableException
  17 from matrices import (append_col, append_row, eigenvalues_re, identity,
  18                       inner_product, norm)
  19 import options
  20
  21 printing.options['dformat'] = options.FLOAT_FORMAT
  22 solvers.options['show_progress'] = options.VERBOSE
  23
  24
  25 class Solution:
  26     """
  27     A representation of the solution of a linear game. It should contain
  28     the value of the game, and both players' strategies.
  29
  30     Examples
  31     --------
  32
  33         >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
  34         Game value: 10.0000000
  35         Player 1 optimal:
  36           [ 1]
  37           [ 2]
  38         Player 2 optimal:
  39           [ 3]
  40           [ 4]
  41
  42     """
  43     def __init__(self, game_value, p1_optimal, p2_optimal):
  44         """
  45         Create a new Solution object from a game value and two optimal
  46         strategies for the players.
  47         """
  48         self._game_value = game_value
  49         self._player1_optimal = p1_optimal
  50         self._player2_optimal = p2_optimal
  51
  52     def __str__(self):
  53         """
  54         Return a string describing the solution of a linear game.
  55
  56         The three data that are described are,
  57
  58           * The value of the game.
  59           * The optimal strategy of player one.
  60           * The optimal strategy of player two.
  61
  62         The two optimal strategy vectors are indented by two spaces.
  63         """
  64         tpl = 'Game value: {:.7f}\n' \
  65               'Player 1 optimal:{:s}\n' \
  66               'Player 2 optimal:{:s}'
  67
  68         p1_str = '\n{!s}'.format(self.player1_optimal())
  69         p1_str = '\n  '.join(p1_str.splitlines())
  70         p2_str = '\n{!s}'.format(self.player2_optimal())
  71         p2_str = '\n  '.join(p2_str.splitlines())
  72
  73         return tpl.format(self.game_value(), p1_str, p2_str)
  74
  75
  76     def game_value(self):
  77         """
  78         Return the game value for this solution.
  79
  80         Examples
  81         --------
  82
  83             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
  84             >>> s.game_value()
  85             10
  86
  87         """
  88         return self._game_value
  89
  90
  91     def player1_optimal(self):
  92         """
  93         Return player one's optimal strategy in this solution.
  94
  95         Examples
  96         --------
  97
  98             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
  99             >>> print(s.player1_optimal())
 100             [ 1]
 101             [ 2]
 102             <BLANKLINE>
 103
 104         """
 105         return self._player1_optimal
 106
 107
 108     def player2_optimal(self):
 109         """
 110         Return player two's optimal strategy in this solution.
 111
 112         Examples
 113         --------
 114
 115             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
 116             >>> print(s.player2_optimal())
 117             [ 3]
 118             [ 4]
 119             <BLANKLINE>
 120
 121         """
 122         return self._player2_optimal
 123
 124
 125 class SymmetricLinearGame:
 126     r"""
 127     A representation of a symmetric linear game.
 128
 129     The data for a symmetric linear game are,
 130
 131       * A "payoff" operator ``L``.
 132       * A symmetric cone ``K``.
 133       * Two points ``e1`` and ``e2`` in the interior of ``K``.
 134
 135     The ambient space is assumed to be the span of ``K``.
 136
 137     With those data understood, the game is played as follows. Players
 138     one and two choose points :math:`x` and :math:`y` respectively, from
 139     their respective strategy sets,
 140
 141     .. math::
 142         \begin{aligned}
 143             \Delta_{1}
 144             &=
 145             \left\{
 146               x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
 147             \right\}\\
 148             \Delta_{2}
 149             &=
 150             \left\{
 151               y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
 152             \right\}.
 153         \end{aligned}
 154
 155     Afterwards, a "payout" is computed as :math:`\left\langle
 156     L\left(x\right), y \right\rangle` and is paid to player one out of
 157     player two's pocket. The game is therefore zero sum, and we suppose
 158     that player one would like to guarantee himself the largest minimum
 159     payout possible. That is, player one wishes to,
 160
 161     .. math::
 162         \begin{aligned}
 163             \text{maximize }
 164               &\underset{y \in \Delta_{2}}{\min}\left(
 165                 \left\langle L\left(x\right), y \right\rangle
 166               \right)\\
 167             \text{subject to } & x \in \Delta_{1}.
 168         \end{aligned}
 169
 170     Player two has the simultaneous goal to,
 171
 172     .. math::
 173         \begin{aligned}
 174             \text{minimize }
 175               &\underset{x \in \Delta_{1}}{\max}\left(
 176                 \left\langle L\left(x\right), y \right\rangle
 177               \right)\\
 178             \text{subject to } & y \in \Delta_{2}.
 179         \end{aligned}
 180
 181     These goals obviously conflict (the game is zero sum), but an
 182     existence theorem guarantees at least one optimal min-max solution
 183     from which neither player would like to deviate. This class is
 184     able to find such a solution.
 185
 186     Parameters
 187     ----------
 188
 189     L : list of list of float
 190         A matrix represented as a list of ROWS. This representation
 191         agrees with (for example) SageMath and NumPy, but not with CVXOPT
 192         (whose matrix constructor accepts a list of columns).
 193
 194     K : :class:`SymmetricCone`
 195         The symmetric cone instance over which the game is played.
 196
 197     e1 : iterable float
 198         The interior point of ``K`` belonging to player one; it
 199         can be of any iterable type having the correct length.
 200
 201     e2 : iterable float
 202         The interior point of ``K`` belonging to player two; it
 203         can be of any enumerable type having the correct length.
 204
 205     Raises
 206     ------
 207
 208     ValueError
 209         If either ``e1`` or ``e2`` lie outside of the cone ``K``.
 210
 211     Examples
 212     --------
 213
 214         >>> from cones import NonnegativeOrthant
 215         >>> K = NonnegativeOrthant(3)
 216         >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 217         >>> e1 = [1,1,1]
 218         >>> e2 = [1,2,3]
 219         >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 220         >>> print(SLG)
 221         The linear game (L, K, e1, e2) where
 222           L = [  1  -5 -15]
 223               [ -1   2  -3]
 224               [-12 -15   1],
 225           K = Nonnegative orthant in the real 3-space,
 226           e1 = [ 1]
 227                [ 1]
 228                [ 1],
 229           e2 = [ 1]
 230                [ 2]
 231                [ 3].
 232
 233     Lists can (and probably should) be used for every argument::
 234
 235         >>> from cones import NonnegativeOrthant
 236         >>> K = NonnegativeOrthant(2)
 237         >>> L = [[1,0],[0,1]]
 238         >>> e1 = [1,1]
 239         >>> e2 = [1,1]
 240         >>> G = SymmetricLinearGame(L, K, e1, e2)
 241         >>> print(G)
 242         The linear game (L, K, e1, e2) where
 243           L = [ 1  0]
 244               [ 0  1],
 245           K = Nonnegative orthant in the real 2-space,
 246           e1 = [ 1]
 247                [ 1],
 248           e2 = [ 1]
 249                [ 1].
 250
 251     The points ``e1`` and ``e2`` can also be passed as some other
 252     enumerable type (of the correct length) without much harm, since
 253     there is no row/column ambiguity::
 254
 255         >>> import cvxopt
 256         >>> import numpy
 257         >>> from cones import NonnegativeOrthant
 258         >>> K = NonnegativeOrthant(2)
 259         >>> L = [[1,0],[0,1]]
 260         >>> e1 = cvxopt.matrix([1,1])
 261         >>> e2 = numpy.matrix([1,1])
 262         >>> G = SymmetricLinearGame(L, K, e1, e2)
 263         >>> print(G)
 264         The linear game (L, K, e1, e2) where
 265           L = [ 1  0]
 266               [ 0  1],
 267           K = Nonnegative orthant in the real 2-space,
 268           e1 = [ 1]
 269                [ 1],
 270           e2 = [ 1]
 271                [ 1].
 272
 273     However, ``L`` will always be intepreted as a list of rows, even
 274     if it is passed as a :class:`cvxopt.base.matrix` which is
 275     otherwise indexed by columns::
 276
 277         >>> import cvxopt
 278         >>> from cones import NonnegativeOrthant
 279         >>> K = NonnegativeOrthant(2)
 280         >>> L = [[1,2],[3,4]]
 281         >>> e1 = [1,1]
 282         >>> e2 = e1
 283         >>> G = SymmetricLinearGame(L, K, e1, e2)
 284         >>> print(G)
 285         The linear game (L, K, e1, e2) where
 286           L = [ 1  2]
 287               [ 3  4],
 288           K = Nonnegative orthant in the real 2-space,
 289           e1 = [ 1]
 290                [ 1],
 291           e2 = [ 1]
 292                [ 1].
 293         >>> L = cvxopt.matrix(L)
 294         >>> print(L)
 295         [ 1  3]
 296         [ 2  4]
 297         <BLANKLINE>
 298         >>> G = SymmetricLinearGame(L, K, e1, e2)
 299         >>> print(G)
 300         The linear game (L, K, e1, e2) where
 301           L = [ 1  2]
 302               [ 3  4],
 303           K = Nonnegative orthant in the real 2-space,
 304           e1 = [ 1]
 305                [ 1],
 306           e2 = [ 1]
 307                [ 1].
 308
 309     """
 310     def __init__(self, L, K, e1, e2):
 311         """
 312         Create a new SymmetricLinearGame object.
 313         """
 314         self._K = K
 315         self._e1 = matrix(e1, (K.dimension(), 1))
 316         self._e2 = matrix(e2, (K.dimension(), 1))
 317
 318         # Our input ``L`` is indexed by rows but CVXOPT matrices are
 319         # indexed by columns, so we need to transpose the input before
 320         # feeding it to CVXOPT.
 321         self._L = matrix(L, (K.dimension(), K.dimension())).trans()
 322
 323         if not self._e1 in K:
 324             raise ValueError('the point e1 must lie in the interior of K')
 325
 326         if not self._e2 in K:
 327             raise ValueError('the point e2 must lie in the interior of K')
 328
 329     def __str__(self):
 330         """
 331         Return a string representation of this game.
 332         """
 333         tpl = 'The linear game (L, K, e1, e2) where\n' \
 334               '  L = {:s},\n' \
 335               '  K = {!s},\n' \
 336               '  e1 = {:s},\n' \
 337               '  e2 = {:s}.'
 338         indented_L = '\n      '.join(str(self._L).splitlines())
 339         indented_e1 = '\n       '.join(str(self._e1).splitlines())
 340         indented_e2 = '\n       '.join(str(self._e2).splitlines())
 341         return tpl.format(indented_L, str(self._K), indented_e1, indented_e2)
 342
 343
 344     def solution(self):
 345         """
 346         Solve this linear game and return a :class:`Solution`.
 347
 348         Returns
 349         -------
 350
 351         :class:`Solution`
 352             A :class:`Solution` object describing the game's value and
 353             the optimal strategies of both players.
 354
 355         Raises
 356         ------
 357         GameUnsolvableException
 358             If the game could not be solved (if an optimal solution to its
 359             associated cone program was not found).
 360
 361         Examples
 362         --------
 363
 364         This example is computed in Gowda and Ravindran in the section
 365         "The value of a Z-transformation"::
 366
 367             >>> from cones import NonnegativeOrthant
 368             >>> K = NonnegativeOrthant(3)
 369             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 370             >>> e1 = [1,1,1]
 371             >>> e2 = [1,1,1]
 372             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 373             >>> print(SLG.solution())
 374             Game value: -6.1724138
 375             Player 1 optimal:
 376               [ 0.5517241]
 377               [-0.0000000]
 378               [ 0.4482759]
 379             Player 2 optimal:
 380               [0.4482759]
 381               [0.0000000]
 382               [0.5517241]
 383
 384         The value of the following game can be computed using the fact
 385         that the identity is invertible::
 386
 387             >>> from cones import NonnegativeOrthant
 388             >>> K = NonnegativeOrthant(3)
 389             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 390             >>> e1 = [1,2,3]
 391             >>> e2 = [4,5,6]
 392             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 393             >>> print(SLG.solution())
 394             Game value: 0.0312500
 395             Player 1 optimal:
 396               [0.0312500]
 397               [0.0625000]
 398               [0.0937500]
 399             Player 2 optimal:
 400               [0.1250000]
 401               [0.1562500]
 402               [0.1875000]
 403
 404         """
 405         # The cone "C" that appears in the statement of the CVXOPT
 406         # conelp program.
 407         C = CartesianProduct(self._K, self._K)
 408
 409         # The column vector "b" that appears on the right-hand side of
 410         # Ax = b in the statement of the CVXOPT conelp program.
 411         b = matrix([1], tc='d')
 412
 413         # A column of zeros that fits K.
 414         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 415
 416         # The column vector "h" that appears on the right-hand side of
 417         # Gx + s = h in the statement of the CVXOPT conelp program.
 418         h = matrix([zero, zero])
 419
 420         # The column vector "c" that appears in the objective function
 421         # value <c,x> in the statement of the CVXOPT conelp program.
 422         c = matrix([-1, zero])
 423
 424         # The matrix "G" that appears on the left-hand side of Gx + s = h
 425         # in the statement of the CVXOPT conelp program.
 426         G = append_row(append_col(zero, -identity(self._K.dimension())),
 427                        append_col(self._e1, -self._L))
 428
 429         # The matrix "A" that appears on the right-hand side of Ax = b
 430         # in the statement of the CVXOPT conelp program.
 431         A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
 432
 433         # Actually solve the thing and obtain a dictionary describing
 434         # what happened.
 435         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 436
 437         p1_value = -soln_dict['primal objective']
 438         p2_value = -soln_dict['dual objective']
 439         p1_optimal = soln_dict['x'][1:]
 440         p2_optimal = soln_dict['z'][self._K.dimension():]
 441
 442         # The "status" field contains "optimal" if everything went
 443         # according to plan. Other possible values are "primal
 444         # infeasible", "dual infeasible", "unknown", all of which mean
 445         # we didn't get a solution. The "infeasible" ones are the
 446         # worst, since they indicate that CVXOPT is convinced the
 447         # problem is infeasible (and that cannot happen).
 448         if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
 449             raise GameUnsolvableException(soln_dict)
 450         elif soln_dict['status'] == 'unknown':
 451             # When we get a status of "unknown", we may still be able
 452             # to salvage a solution out of the returned
 453             # dictionary. Often this is the result of numerical
 454             # difficulty and we can simply check that the primal/dual
 455             # objectives match (within a tolerance) and that the
 456             # primal/dual optimal solutions are within the cone (to a
 457             # tolerance as well).
 458             if abs(p1_value - p2_value) > options.ABS_TOL:
 459                 raise GameUnsolvableException(soln_dict)
 460             if (p1_optimal not in self._K) or (p2_optimal not in self._K):
 461                 raise GameUnsolvableException(soln_dict)
 462
 463         return Solution(p1_value, p1_optimal, p2_optimal)
 464
 465
 466     def dual(self):
 467         r"""
 468         Return the dual game to this game.
 469
 470         If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
 471         then its dual is :math:`G^{*} =
 472         \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
 473         is symmetric, :math:`K^{*} = K`.
 474
 475         Examples
 476         --------
 477
 478             >>> from cones import NonnegativeOrthant
 479             >>> K = NonnegativeOrthant(3)
 480             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 481             >>> e1 = [1,1,1]
 482             >>> e2 = [1,2,3]
 483             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 484             >>> print(SLG.dual())
 485             The linear game (L, K, e1, e2) where
 486               L = [  1  -1 -12]
 487                   [ -5   2 -15]
 488                   [-15  -3   1],
 489               K = Nonnegative orthant in the real 3-space,
 490               e1 = [ 1]
 491                    [ 2]
 492                    [ 3],
 493               e2 = [ 1]
 494                    [ 1]
 495                    [ 1].
 496
 497         """
 498         # We pass ``self._L`` right back into the constructor, because
 499         # it will be transposed there. And keep in mind that ``self._K``
 500         # is its own dual.
 501         return SymmetricLinearGame(self._L,
 502                                    self._K,
 503                                    self._e2,
 504                                    self._e1)
 505
 506
 507
 508 def _random_matrix(dims):
 509     """
 510     Generate a random square (``dims``-by-``dims``) matrix. This is used
 511     only by the :class:`SymmetricLinearGameTest` class.
 512     """
 513     return matrix([[uniform(-10, 10) for i in range(dims)]
 514                    for j in range(dims)])
 515
 516 def _random_nonnegative_matrix(dims):
 517     """
 518     Generate a random square (``dims``-by-``dims``) matrix with
 519     nonnegative entries. This is used only by the
 520     :class:`SymmetricLinearGameTest` class.
 521     """
 522     L = _random_matrix(dims)
 523     return matrix([abs(entry) for entry in L], (dims, dims))
 524
 525 def _random_diagonal_matrix(dims):
 526     """
 527     Generate a random square (``dims``-by-``dims``) matrix with nonzero
 528     entries only on the diagonal. This is used only by the
 529     :class:`SymmetricLinearGameTest` class.
 530     """
 531     return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)]
 532                    for j in range(dims)])
 533
 534 def _random_orthant_params():
 535     """
 536     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 537     random game over the nonnegative orthant. This is only used by
 538     the :class:`SymmetricLinearGameTest` class.
 539     """
 540     ambient_dim = randint(1, 10)
 541     K = NonnegativeOrthant(ambient_dim)
 542     e1 = [uniform(0.5, 10) for idx in range(K.dimension())]
 543     e2 = [uniform(0.5, 10) for idx in range(K.dimension())]
 544     L = _random_matrix(K.dimension())
 545     return (L, K, matrix(e1), matrix(e2))
 546
 547
 548 def _random_icecream_params():
 549     """
 550     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 551     random game over the ice cream cone. This is only used by
 552     the :class:`SymmetricLinearGameTest` class.
 553     """
 554     # Use a minimum dimension of two to avoid divide-by-zero in
 555     # the fudge factor we make up later.
 556     ambient_dim = randint(2, 10)
 557     K = IceCream(ambient_dim)
 558     e1 = [1] # Set the "height" of e1 to one
 559     e2 = [1] # And the same for e2
 560
 561     # If we choose the rest of the components of e1,e2 randomly
 562     # between 0 and 1, then the largest the squared norm of the
 563     # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
 564     # need to make it less than one (the height of the cone) so
 565     # that the whole thing is in the cone. The norm of the
 566     # non-height part is sqrt(dim(K) - 1), and we can divide by
 567     # twice that.
 568     fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0))
 569     e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 570     e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 571     L = _random_matrix(K.dimension())
 572
 573     return (L, K, matrix(e1), matrix(e2))
 574
 575
 576 class SymmetricLinearGameTest(TestCase):
 577     """
 578     Tests for the SymmetricLinearGame and Solution classes.
 579     """
 580     def assert_within_tol(self, first, second):
 581         """
 582         Test that ``first`` and ``second`` are equal within our default
 583         tolerance.
 584         """
 585         self.assertTrue(abs(first - second) < options.ABS_TOL)
 586
 587
 588     def assert_norm_within_tol(self, first, second):
 589         """
 590         Test that ``first`` and ``second`` vectors are equal in the
 591         sense that the norm of their difference is within our default
 592         tolerance.
 593         """
 594         self.assert_within_tol(norm(first - second), 0)
 595
 596
 597     def assert_solution_exists(self, L, K, e1, e2):
 598         """
 599         Given the parameters needed to construct a SymmetricLinearGame,
 600         ensure that that game has a solution.
 601         """
 602         # The matrix() constructor assumes that ``L`` is a list of
 603         # columns, so we transpose it to agree with what
 604         # SymmetricLinearGame() thinks.
 605         G = SymmetricLinearGame(L.trans(), K, e1, e2)
 606         soln = G.solution()
 607
 608         expected = inner_product(L*soln.player1_optimal(),
 609                                  soln.player2_optimal())
 610         self.assert_within_tol(soln.game_value(), expected)
 611
 612
 613     def test_solution_exists_orthant(self):
 614         """
 615         Every linear game has a solution, so we should be able to solve
 616         every symmetric linear game over the NonnegativeOrthant. Pick
 617         some parameters randomly and give it a shot. The resulting
 618         optimal solutions should give us the optimal game value when we
 619         apply the payoff operator to them.
 620         """
 621         (L, K, e1, e2) = _random_orthant_params()
 622         self.assert_solution_exists(L, K, e1, e2)
 623
 624
 625     def test_solution_exists_icecream(self):
 626         """
 627         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 628         over the ice cream cone.
 629         """
 630         (L, K, e1, e2) = _random_icecream_params()
 631         self.assert_solution_exists(L, K, e1, e2)
 632
 633
 634     def test_negative_value_z_operator(self):
 635         """
 636         Test the example given in Gowda/Ravindran of a Z-matrix with
 637         negative game value on the nonnegative orthant.
 638         """
 639         K = NonnegativeOrthant(2)
 640         e1 = [1, 1]
 641         e2 = e1
 642         L = [[1, -2], [-2, 1]]
 643         G = SymmetricLinearGame(L, K, e1, e2)
 644         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 645
 646
 647     def assert_scaling_works(self, L, K, e1, e2):
 648         """
 649         Test that scaling ``L`` by a nonnegative number scales the value
 650         of the game by the same number.
 651         """
 652         game1 = SymmetricLinearGame(L, K, e1, e2)
 653         value1 = game1.solution().game_value()
 654
 655         alpha = uniform(0.1, 10)
 656         game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
 657         value2 = game2.solution().game_value()
 658         self.assert_within_tol(alpha*value1, value2)
 659
 660
 661     def test_scaling_orthant(self):
 662         """
 663         Test that scaling ``L`` by a nonnegative number scales the value
 664         of the game by the same number over the nonnegative orthant.
 665         """
 666         (L, K, e1, e2) = _random_orthant_params()
 667         self.assert_scaling_works(L, K, e1, e2)
 668
 669
 670     def test_scaling_icecream(self):
 671         """
 672         The same test as :meth:`test_nonnegative_scaling_orthant`,
 673         except over the ice cream cone.
 674         """
 675         (L, K, e1, e2) = _random_icecream_params()
 676         self.assert_scaling_works(L, K, e1, e2)
 677
 678
 679     def assert_translation_works(self, L, K, e1, e2):
 680         """
 681         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 682         the value of the associated game by alpha.
 683         """
 684         # We need to use ``L`` later, so make sure we transpose it
 685         # before passing it in as a column-indexed matrix.
 686         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 687         soln1 = game1.solution()
 688         value1 = soln1.game_value()
 689         x_bar = soln1.player1_optimal()
 690         y_bar = soln1.player2_optimal()
 691
 692         alpha = uniform(-10, 10)
 693         tensor_prod = e1*e2.trans()
 694
 695         # This is the "correct" representation of ``M``, but COLUMN
 696         # indexed...
 697         M = L + alpha*tensor_prod
 698
 699         # so we have to transpose it when we feed it to the constructor.
 700         game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
 701         value2 = game2.solution().game_value()
 702
 703         self.assert_within_tol(value1 + alpha, value2)
 704
 705         # Make sure the same optimal pair works.
 706         self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
 707
 708
 709     def test_translation_orthant(self):
 710         """
 711         Test that translation works over the nonnegative orthant.
 712         """
 713         (L, K, e1, e2) = _random_orthant_params()
 714         self.assert_translation_works(L, K, e1, e2)
 715
 716
 717     def test_translation_icecream(self):
 718         """
 719         The same as :meth:`test_translation_orthant`, except over the
 720         ice cream cone.
 721         """
 722         (L, K, e1, e2) = _random_icecream_params()
 723         self.assert_translation_works(L, K, e1, e2)
 724
 725
 726     def assert_opposite_game_works(self, L, K, e1, e2):
 727         """
 728         Check the value of the "opposite" game that gives rise to a
 729         value that is the negation of the original game. Comes from
 730         some corollary.
 731         """
 732         # We need to use ``L`` later, so make sure we transpose it
 733         # before passing it in as a column-indexed matrix.
 734         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 735
 736         # This is the "correct" representation of ``M``, but
 737         # COLUMN indexed...
 738         M = -L.trans()
 739
 740         # so we have to transpose it when we feed it to the constructor.
 741         game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
 742
 743         soln1 = game1.solution()
 744         x_bar = soln1.player1_optimal()
 745         y_bar = soln1.player2_optimal()
 746         soln2 = game2.solution()
 747
 748         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 749
 750         # Make sure the switched optimal pair works.
 751         self.assert_within_tol(soln2.game_value(),
 752                                inner_product(M*y_bar, x_bar))
 753
 754
 755     def test_opposite_game_orthant(self):
 756         """
 757         Test the value of the "opposite" game over the nonnegative
 758         orthant.
 759         """
 760         (L, K, e1, e2) = _random_orthant_params()
 761         self.assert_opposite_game_works(L, K, e1, e2)
 762
 763
 764     def test_opposite_game_icecream(self):
 765         """
 766         Like :meth:`test_opposite_game_orthant`, except over the
 767         ice-cream cone.
 768         """
 769         (L, K, e1, e2) = _random_icecream_params()
 770         self.assert_opposite_game_works(L, K, e1, e2)
 771
 772
 773     def assert_orthogonality(self, L, K, e1, e2):
 774         """
 775         Two orthogonality relations hold at an optimal solution, and we
 776         check them here.
 777         """
 778         # We need to use ``L`` later, so make sure we transpose it
 779         # before passing it in as a column-indexed matrix.
 780         game = SymmetricLinearGame(L.trans(), K, e1, e2)
 781         soln = game.solution()
 782         x_bar = soln.player1_optimal()
 783         y_bar = soln.player2_optimal()
 784         value = soln.game_value()
 785
 786         ip1 = inner_product(y_bar, L*x_bar - value*e1)
 787         self.assert_within_tol(ip1, 0)
 788
 789         ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
 790         self.assert_within_tol(ip2, 0)
 791
 792
 793     def test_orthogonality_orthant(self):
 794         """
 795         Check the orthgonality relationships that hold for a solution
 796         over the nonnegative orthant.
 797         """
 798         (L, K, e1, e2) = _random_orthant_params()
 799         self.assert_orthogonality(L, K, e1, e2)
 800
 801
 802     def test_orthogonality_icecream(self):
 803         """
 804         Check the orthgonality relationships that hold for a solution
 805         over the ice-cream cone.
 806         """
 807         (L, K, e1, e2) = _random_icecream_params()
 808         self.assert_orthogonality(L, K, e1, e2)
 809
 810
 811     def test_positive_operator_value(self):
 812         """
 813         Test that a positive operator on the nonnegative orthant gives
 814         rise to a a game with a nonnegative value.
 815
 816         This test theoretically applies to the ice-cream cone as well,
 817         but we don't know how to make positive operators on that cone.
 818         """
 819         (_, K, e1, e2) = _random_orthant_params()
 820
 821         # Ignore that L, we need a nonnegative one.
 822         L = _random_nonnegative_matrix(K.dimension())
 823
 824         game = SymmetricLinearGame(L, K, e1, e2)
 825         self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 826
 827
 828     def test_lyapunov_orthant(self):
 829         """
 830         Test that a Lyapunov game on the nonnegative orthant works.
 831         """
 832         (L, K, e1, e2) = _random_orthant_params()
 833
 834         # Ignore that L, we need a diagonal (Lyapunov-like) one.
 835         # (And we don't need to transpose those.)
 836         L = _random_diagonal_matrix(K.dimension())
 837         game = SymmetricLinearGame(L, K, e1, e2)
 838         soln = game.solution()
 839
 840         # We only check for positive/negative stability if the game
 841         # value is not basically zero. If the value is that close to
 842         # zero, we just won't check any assertions.
 843         if soln.game_value() > options.ABS_TOL:
 844             # L should be positive stable
 845             ps = all([eig > -options.ABS_TOL for eig in  eigenvalues_re(L)])
 846             self.assertTrue(ps)
 847         elif soln.game_value() < -options.ABS_TOL:
 848             # L should be negative stable
 849             ns = all([eig < options.ABS_TOL for eig in  eigenvalues_re(L)])
 850             self.assertTrue(ns)
 851
 852         # The dual game's value should always equal the primal's.
 853         dualsoln = game.dual().solution()
 854         self.assert_within_tol(dualsoln.game_value(), soln.game_value())