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,
 511     represented as a list of rows. This is used only by the
 512     :class:`SymmetricLinearGameTest` class.
 513     """
 514     return [[uniform(-10, 10) for i in range(dims)] 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, represented as a list of rows. This is used
 520     only by the :class:`SymmetricLinearGameTest` class.
 521     """
 522     L = _random_matrix(dims)
 523     return [[abs(entry) for entry in row] for row in L]
 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, represented as a list of rows. This is
 529     used only by the :class:`SymmetricLinearGameTest` class.
 530     """
 531     return [[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, e1, 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, e1, 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         G = SymmetricLinearGame(L, K, e1, e2)
 603         soln = G.solution()
 604
 605         # The matrix() constructor assumes that ``L`` is a list of
 606         # columns, so we transpose it to agree with what
 607         # SymmetricLinearGame() thinks.
 608         L_matrix = matrix(L).trans()
 609         expected = inner_product(L_matrix*soln.player1_optimal(),
 610                                  soln.player2_optimal())
 611         self.assert_within_tol(soln.game_value(), expected)
 612
 613
 614     def test_solution_exists_orthant(self):
 615         """
 616         Every linear game has a solution, so we should be able to solve
 617         every symmetric linear game over the NonnegativeOrthant. Pick
 618         some parameters randomly and give it a shot. The resulting
 619         optimal solutions should give us the optimal game value when we
 620         apply the payoff operator to them.
 621         """
 622         (L, K, e1, e2) = _random_orthant_params()
 623         self.assert_solution_exists(L, K, e1, e2)
 624
 625
 626     def test_solution_exists_icecream(self):
 627         """
 628         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 629         over the ice cream cone.
 630         """
 631         (L, K, e1, e2) = _random_icecream_params()
 632         self.assert_solution_exists(L, K, e1, e2)
 633
 634
 635     def test_negative_value_z_operator(self):
 636         """
 637         Test the example given in Gowda/Ravindran of a Z-matrix with
 638         negative game value on the nonnegative orthant.
 639         """
 640         K = NonnegativeOrthant(2)
 641         e1 = [1, 1]
 642         e2 = e1
 643         L = [[1, -2], [-2, 1]]
 644         G = SymmetricLinearGame(L, K, e1, e2)
 645         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 646
 647
 648     def assert_scaling_works(self, L, K, e1, e2):
 649         """
 650         Test that scaling ``L`` by a nonnegative number scales the value
 651         of the game by the same number.
 652         """
 653         # Make ``L`` a matrix so that we can scale it by alpha. Its
 654         # random, so who cares if it gets transposed.
 655         L = matrix(L)
 656         game1 = SymmetricLinearGame(L, K, e1, e2)
 657         value1 = game1.solution().game_value()
 658
 659         alpha = uniform(0.1, 10)
 660         game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
 661         value2 = game2.solution().game_value()
 662         self.assert_within_tol(alpha*value1, value2)
 663
 664
 665     def test_scaling_orthant(self):
 666         """
 667         Test that scaling ``L`` by a nonnegative number scales the value
 668         of the game by the same number over the nonnegative orthant.
 669         """
 670         (L, K, e1, e2) = _random_orthant_params()
 671         self.assert_scaling_works(L, K, e1, e2)
 672
 673
 674     def test_scaling_icecream(self):
 675         """
 676         The same test as :meth:`test_nonnegative_scaling_orthant`,
 677         except over the ice cream cone.
 678         """
 679         (L, K, e1, e2) = _random_icecream_params()
 680         self.assert_scaling_works(L, K, e1, e2)
 681
 682
 683     def assert_translation_works(self, L, K, e1, e2):
 684         """
 685         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 686         the value of the associated game by alpha.
 687         """
 688         e1 = matrix(e1, (K.dimension(), 1))
 689         e2 = matrix(e2, (K.dimension(), 1))
 690         game1 = SymmetricLinearGame(L, K, e1, e2)
 691         soln1 = game1.solution()
 692         value1 = soln1.game_value()
 693         x_bar = soln1.player1_optimal()
 694         y_bar = soln1.player2_optimal()
 695
 696         # Make ``L`` a CVXOPT matrix so that we can do math with
 697         # it. Note that this gives us the "correct" representation of
 698         # ``L`` (in agreement with what G has), but COLUMN indexed.
 699         alpha = uniform(-10, 10)
 700         L = matrix(L).trans()
 701         tensor_prod = e1*e2.trans()
 702
 703         # Likewise, this is the "correct" representation of ``M``, but
 704         # COLUMN indexed...
 705         M = L + alpha*tensor_prod
 706
 707         # so we have to transpose it when we feed it to the constructor.
 708         game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
 709         value2 = game2.solution().game_value()
 710
 711         self.assert_within_tol(value1 + alpha, value2)
 712
 713         # Make sure the same optimal pair works.
 714         self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
 715
 716
 717     def test_translation_orthant(self):
 718         """
 719         Test that translation works over the nonnegative orthant.
 720         """
 721         (L, K, e1, e2) = _random_orthant_params()
 722         self.assert_translation_works(L, K, e1, e2)
 723
 724
 725     def test_translation_icecream(self):
 726         """
 727         The same as :meth:`test_translation_orthant`, except over the
 728         ice cream cone.
 729         """
 730         (L, K, e1, e2) = _random_icecream_params()
 731         self.assert_translation_works(L, K, e1, e2)
 732
 733
 734     def assert_opposite_game_works(self, L, K, e1, e2):
 735         """
 736         Check the value of the "opposite" game that gives rise to a
 737         value that is the negation of the original game. Comes from
 738         some corollary.
 739         """
 740         e1 = matrix(e1, (K.dimension(), 1))
 741         e2 = matrix(e2, (K.dimension(), 1))
 742         game1 = SymmetricLinearGame(L, K, e1, e2)
 743
 744         # Make ``L`` a CVXOPT matrix so that we can do math with
 745         # it. Note that this gives us the "correct" representation of
 746         # ``L`` (in agreement with what G has), but COLUMN indexed.
 747         L = matrix(L).trans()
 748
 749         # Likewise, this is the "correct" representation of ``M``, but
 750         # COLUMN indexed...
 751         M = -L.trans()
 752
 753         # so we have to transpose it when we feed it to the constructor.
 754         game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
 755
 756         soln1 = game1.solution()
 757         x_bar = soln1.player1_optimal()
 758         y_bar = soln1.player2_optimal()
 759         soln2 = game2.solution()
 760
 761         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 762
 763         # Make sure the switched optimal pair works.
 764         self.assert_within_tol(soln2.game_value(),
 765                                inner_product(M*y_bar, x_bar))
 766
 767
 768     def test_opposite_game_orthant(self):
 769         """
 770         Test the value of the "opposite" game over the nonnegative
 771         orthant.
 772         """
 773         (L, K, e1, e2) = _random_orthant_params()
 774         self.assert_opposite_game_works(L, K, e1, e2)
 775
 776
 777     def test_opposite_game_icecream(self):
 778         """
 779         Like :meth:`test_opposite_game_orthant`, except over the
 780         ice-cream cone.
 781         """
 782         (L, K, e1, e2) = _random_icecream_params()
 783         self.assert_opposite_game_works(L, K, e1, e2)
 784
 785
 786     def assert_orthogonality(self, L, K, e1, e2):
 787         """
 788         Two orthogonality relations hold at an optimal solution, and we
 789         check them here.
 790         """
 791         game = SymmetricLinearGame(L, K, e1, e2)
 792         soln = game.solution()
 793         x_bar = soln.player1_optimal()
 794         y_bar = soln.player2_optimal()
 795         value = soln.game_value()
 796
 797         # Make these matrices so that we can compute with them.
 798         L = matrix(L).trans()
 799         e1 = matrix(e1, (K.dimension(), 1))
 800         e2 = matrix(e2, (K.dimension(), 1))
 801
 802         ip1 = inner_product(y_bar, L*x_bar - value*e1)
 803         self.assert_within_tol(ip1, 0)
 804
 805         ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
 806         self.assert_within_tol(ip2, 0)
 807
 808
 809     def test_orthogonality_orthant(self):
 810         """
 811         Check the orthgonality relationships that hold for a solution
 812         over the nonnegative orthant.
 813         """
 814         (L, K, e1, e2) = _random_orthant_params()
 815         self.assert_orthogonality(L, K, e1, e2)
 816
 817
 818     def test_orthogonality_icecream(self):
 819         """
 820         Check the orthgonality relationships that hold for a solution
 821         over the ice-cream cone.
 822         """
 823         (L, K, e1, e2) = _random_icecream_params()
 824         self.assert_orthogonality(L, K, e1, e2)
 825
 826
 827     def test_positive_operator_value(self):
 828         """
 829         Test that a positive operator on the nonnegative orthant gives
 830         rise to a a game with a nonnegative value.
 831
 832         This test theoretically applies to the ice-cream cone as well,
 833         but we don't know how to make positive operators on that cone.
 834         """
 835         (_, K, e1, e2) = _random_orthant_params()
 836
 837         # Ignore that L, we need a nonnegative one.
 838         L = _random_nonnegative_matrix(K.dimension())
 839
 840         game = SymmetricLinearGame(L, K, e1, e2)
 841         self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 842
 843     def test_lyapunov_orthant(self):
 844         """
 845         Test that a Lyapunov game on the nonnegative orthant works.
 846         """
 847         (_, K, e1, e2) = _random_orthant_params()
 848
 849         # Ignore that L, we need a diagonal (Lyapunov-like) one.
 850         L = _random_diagonal_matrix(K.dimension())
 851         game = SymmetricLinearGame(L, K, e1, e2)
 852         soln = game.solution()
 853
 854         # We only check for positive/negative stability if the game
 855         # value is not basically zero. If the value is that close to
 856         # zero, we just won't check any assertions.
 857         L = matrix(L).trans()
 858         if soln.game_value() > options.ABS_TOL:
 859             # L should be positive stable
 860             ps = all([eig > -options.ABS_TOL for eig in  eigenvalues_re(L)])
 861             self.assertTrue(ps)
 862         elif soln.game_value() < -options.ABS_TOL:
 863             # L should be negative stable
 864             ns = all([eig < options.ABS_TOL for eig in  eigenvalues_re(L)])
 865             self.assertTrue(ns)
 866
 867         # The dual game's value should always equal the primal's.
 868         dualsoln = game.dual().solution()
 869         self.assert_within_tol(dualsoln.game_value(), soln.game_value())