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
 535 def _random_skew_symmetric_matrix(dims):
 536     """
 537     Generate a random skew-symmetrix (``dims``-by-``dims``) matrix.
 538
 539     Examples
 540     --------
 541
 542        >>> A = _random_skew_symmetric_matrix(randint(1, 10))
 543        >>> norm(A + A.trans()) < options.ABS_TOL
 544        True
 545
 546     """
 547     strict_ut = [[uniform(-10, 10)*int(i < j) for i in range(dims)]
 548                  for j in range(dims)]
 549
 550     strict_ut = matrix(strict_ut, (dims, dims))
 551     return strict_ut - strict_ut.trans()
 552
 553
 554 def _random_lyapunov_like_icecream(dims):
 555     """
 556     Generate a random Lyapunov-like matrix over the ice-cream cone in
 557     ``dims`` dimensions.
 558     """
 559     a = matrix([uniform(-10, 10)], (1, 1))
 560     b = matrix([uniform(-10, 10) for idx in range(dims-1)], (dims-1, 1))
 561     D = _random_skew_symmetric_matrix(dims-1) + a*identity(dims-1)
 562     row1 = append_col(a, b.trans())
 563     row2 = append_col(b, D)
 564     return append_row(row1, row2)
 565
 566
 567 def _random_orthant_params():
 568     """
 569     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 570     random game over the nonnegative orthant. This is only used by
 571     the :class:`SymmetricLinearGameTest` class.
 572     """
 573     ambient_dim = randint(1, 10)
 574     K = NonnegativeOrthant(ambient_dim)
 575     e1 = [uniform(0.5, 10) for idx in range(K.dimension())]
 576     e2 = [uniform(0.5, 10) for idx in range(K.dimension())]
 577     L = _random_matrix(K.dimension())
 578     return (L, K, matrix(e1), matrix(e2))
 579
 580
 581 def _random_icecream_params():
 582     """
 583     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 584     random game over the ice cream cone. This is only used by
 585     the :class:`SymmetricLinearGameTest` class.
 586     """
 587     # Use a minimum dimension of two to avoid divide-by-zero in
 588     # the fudge factor we make up later.
 589     ambient_dim = randint(2, 10)
 590     K = IceCream(ambient_dim)
 591     e1 = [1] # Set the "height" of e1 to one
 592     e2 = [1] # And the same for e2
 593
 594     # If we choose the rest of the components of e1,e2 randomly
 595     # between 0 and 1, then the largest the squared norm of the
 596     # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
 597     # need to make it less than one (the height of the cone) so
 598     # that the whole thing is in the cone. The norm of the
 599     # non-height part is sqrt(dim(K) - 1), and we can divide by
 600     # twice that.
 601     fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0))
 602     e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 603     e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 604     L = _random_matrix(K.dimension())
 605
 606     return (L, K, matrix(e1), matrix(e2))
 607
 608
 609 class SymmetricLinearGameTest(TestCase):
 610     """
 611     Tests for the SymmetricLinearGame and Solution classes.
 612     """
 613     def assert_within_tol(self, first, second):
 614         """
 615         Test that ``first`` and ``second`` are equal within our default
 616         tolerance.
 617         """
 618         self.assertTrue(abs(first - second) < options.ABS_TOL)
 619
 620
 621     def assert_norm_within_tol(self, first, second):
 622         """
 623         Test that ``first`` and ``second`` vectors are equal in the
 624         sense that the norm of their difference is within our default
 625         tolerance.
 626         """
 627         self.assert_within_tol(norm(first - second), 0)
 628
 629
 630     def assert_solution_exists(self, L, K, e1, e2):
 631         """
 632         Given the parameters needed to construct a SymmetricLinearGame,
 633         ensure that that game has a solution.
 634         """
 635         # The matrix() constructor assumes that ``L`` is a list of
 636         # columns, so we transpose it to agree with what
 637         # SymmetricLinearGame() thinks.
 638         G = SymmetricLinearGame(L.trans(), K, e1, e2)
 639         soln = G.solution()
 640
 641         expected = inner_product(L*soln.player1_optimal(),
 642                                  soln.player2_optimal())
 643         self.assert_within_tol(soln.game_value(), expected)
 644
 645
 646     def test_solution_exists_orthant(self):
 647         """
 648         Every linear game has a solution, so we should be able to solve
 649         every symmetric linear game over the NonnegativeOrthant. Pick
 650         some parameters randomly and give it a shot. The resulting
 651         optimal solutions should give us the optimal game value when we
 652         apply the payoff operator to them.
 653         """
 654         (L, K, e1, e2) = _random_orthant_params()
 655         self.assert_solution_exists(L, K, e1, e2)
 656
 657
 658     def test_solution_exists_icecream(self):
 659         """
 660         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 661         over the ice cream cone.
 662         """
 663         (L, K, e1, e2) = _random_icecream_params()
 664         self.assert_solution_exists(L, K, e1, e2)
 665
 666
 667     def test_negative_value_z_operator(self):
 668         """
 669         Test the example given in Gowda/Ravindran of a Z-matrix with
 670         negative game value on the nonnegative orthant.
 671         """
 672         K = NonnegativeOrthant(2)
 673         e1 = [1, 1]
 674         e2 = e1
 675         L = [[1, -2], [-2, 1]]
 676         G = SymmetricLinearGame(L, K, e1, e2)
 677         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 678
 679
 680     def assert_scaling_works(self, L, K, e1, e2):
 681         """
 682         Test that scaling ``L`` by a nonnegative number scales the value
 683         of the game by the same number.
 684         """
 685         game1 = SymmetricLinearGame(L, K, e1, e2)
 686         value1 = game1.solution().game_value()
 687
 688         alpha = uniform(0.1, 10)
 689         game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
 690         value2 = game2.solution().game_value()
 691         self.assert_within_tol(alpha*value1, value2)
 692
 693
 694     def test_scaling_orthant(self):
 695         """
 696         Test that scaling ``L`` by a nonnegative number scales the value
 697         of the game by the same number over the nonnegative orthant.
 698         """
 699         (L, K, e1, e2) = _random_orthant_params()
 700         self.assert_scaling_works(L, K, e1, e2)
 701
 702
 703     def test_scaling_icecream(self):
 704         """
 705         The same test as :meth:`test_nonnegative_scaling_orthant`,
 706         except over the ice cream cone.
 707         """
 708         (L, K, e1, e2) = _random_icecream_params()
 709         self.assert_scaling_works(L, K, e1, e2)
 710
 711
 712     def assert_translation_works(self, L, K, e1, e2):
 713         """
 714         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 715         the value of the associated game by alpha.
 716         """
 717         # We need to use ``L`` later, so make sure we transpose it
 718         # before passing it in as a column-indexed matrix.
 719         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 720         soln1 = game1.solution()
 721         value1 = soln1.game_value()
 722         x_bar = soln1.player1_optimal()
 723         y_bar = soln1.player2_optimal()
 724
 725         alpha = uniform(-10, 10)
 726         tensor_prod = e1*e2.trans()
 727
 728         # This is the "correct" representation of ``M``, but COLUMN
 729         # indexed...
 730         M = L + alpha*tensor_prod
 731
 732         # so we have to transpose it when we feed it to the constructor.
 733         game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
 734         value2 = game2.solution().game_value()
 735
 736         self.assert_within_tol(value1 + alpha, value2)
 737
 738         # Make sure the same optimal pair works.
 739         self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
 740
 741
 742     def test_translation_orthant(self):
 743         """
 744         Test that translation works over the nonnegative orthant.
 745         """
 746         (L, K, e1, e2) = _random_orthant_params()
 747         self.assert_translation_works(L, K, e1, e2)
 748
 749
 750     def test_translation_icecream(self):
 751         """
 752         The same as :meth:`test_translation_orthant`, except over the
 753         ice cream cone.
 754         """
 755         (L, K, e1, e2) = _random_icecream_params()
 756         self.assert_translation_works(L, K, e1, e2)
 757
 758
 759     def assert_opposite_game_works(self, L, K, e1, e2):
 760         """
 761         Check the value of the "opposite" game that gives rise to a
 762         value that is the negation of the original game. Comes from
 763         some corollary.
 764         """
 765         # We need to use ``L`` later, so make sure we transpose it
 766         # before passing it in as a column-indexed matrix.
 767         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 768
 769         # This is the "correct" representation of ``M``, but
 770         # COLUMN indexed...
 771         M = -L.trans()
 772
 773         # so we have to transpose it when we feed it to the constructor.
 774         game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
 775
 776         soln1 = game1.solution()
 777         x_bar = soln1.player1_optimal()
 778         y_bar = soln1.player2_optimal()
 779         soln2 = game2.solution()
 780
 781         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 782
 783         # Make sure the switched optimal pair works.
 784         self.assert_within_tol(soln2.game_value(),
 785                                inner_product(M*y_bar, x_bar))
 786
 787
 788     def test_opposite_game_orthant(self):
 789         """
 790         Test the value of the "opposite" game over the nonnegative
 791         orthant.
 792         """
 793         (L, K, e1, e2) = _random_orthant_params()
 794         self.assert_opposite_game_works(L, K, e1, e2)
 795
 796
 797     def test_opposite_game_icecream(self):
 798         """
 799         Like :meth:`test_opposite_game_orthant`, except over the
 800         ice-cream cone.
 801         """
 802         (L, K, e1, e2) = _random_icecream_params()
 803         self.assert_opposite_game_works(L, K, e1, e2)
 804
 805
 806     def assert_orthogonality(self, L, K, e1, e2):
 807         """
 808         Two orthogonality relations hold at an optimal solution, and we
 809         check them here.
 810         """
 811         # We need to use ``L`` later, so make sure we transpose it
 812         # before passing it in as a column-indexed matrix.
 813         game = SymmetricLinearGame(L.trans(), K, e1, e2)
 814         soln = game.solution()
 815         x_bar = soln.player1_optimal()
 816         y_bar = soln.player2_optimal()
 817         value = soln.game_value()
 818
 819         ip1 = inner_product(y_bar, L*x_bar - value*e1)
 820         self.assert_within_tol(ip1, 0)
 821
 822         ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
 823         self.assert_within_tol(ip2, 0)
 824
 825
 826     def test_orthogonality_orthant(self):
 827         """
 828         Check the orthgonality relationships that hold for a solution
 829         over the nonnegative orthant.
 830         """
 831         (L, K, e1, e2) = _random_orthant_params()
 832         self.assert_orthogonality(L, K, e1, e2)
 833
 834
 835     def test_orthogonality_icecream(self):
 836         """
 837         Check the orthgonality relationships that hold for a solution
 838         over the ice-cream cone.
 839         """
 840         (L, K, e1, e2) = _random_icecream_params()
 841         self.assert_orthogonality(L, K, e1, e2)
 842
 843
 844     def test_positive_operator_value(self):
 845         """
 846         Test that a positive operator on the nonnegative orthant gives
 847         rise to a a game with a nonnegative value.
 848
 849         This test theoretically applies to the ice-cream cone as well,
 850         but we don't know how to make positive operators on that cone.
 851         """
 852         (K, e1, e2) = _random_orthant_params()[1:]
 853         L = _random_nonnegative_matrix(K.dimension())
 854
 855         game = SymmetricLinearGame(L, K, e1, e2)
 856         self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 857
 858
 859     def assert_lyapunov_works(self, L, K, e1, e2):
 860         """
 861         Check that Lyapunov games act the way we expect.
 862         """
 863         game = SymmetricLinearGame(L, K, e1, e2)
 864         soln = game.solution()
 865
 866         # We only check for positive/negative stability if the game
 867         # value is not basically zero. If the value is that close to
 868         # zero, we just won't check any assertions.
 869         eigs = eigenvalues_re(L)
 870         if soln.game_value() > options.ABS_TOL:
 871             # L should be positive stable
 872             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 873             self.assertTrue(positive_stable)
 874         elif soln.game_value() < -options.ABS_TOL:
 875             # L should be negative stable
 876             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 877             self.assertTrue(negative_stable)
 878
 879         # The dual game's value should always equal the primal's.
 880         dualsoln = game.dual().solution()
 881         self.assert_within_tol(dualsoln.game_value(), soln.game_value())
 882
 883
 884     def test_lyapunov_orthant(self):
 885         """
 886         Test that a Lyapunov game on the nonnegative orthant works.
 887         """
 888         (K, e1, e2) = _random_orthant_params()[1:]
 889         L = _random_diagonal_matrix(K.dimension())
 890
 891         self.assert_lyapunov_works(L, K, e1, e2)
 892
 893
 894     def test_lyapunov_icecream(self):
 895         """
 896         Test that a Lyapunov game on the ice-cream cone works.
 897         """
 898         (K, e1, e2) = _random_icecream_params()[1:]
 899         L = _random_lyapunov_like_icecream(K.dimension())
 900
 901         self.assert_lyapunov_works(L, K, e1, e2)