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 from cvxopt import matrix, printing, solvers
   9 from .cones import CartesianProduct
  10 from .errors import GameUnsolvableException, PoorScalingException
  11 from .matrices import append_col, append_row, condition_number, identity
  12 from . import options
  13
  14 printing.options['dformat'] = options.FLOAT_FORMAT
  15
  16 class Solution:
  17     """
  18     A representation of the solution of a linear game. It should contain
  19     the value of the game, and both players' strategies.
  20
  21     Examples
  22     --------
  23
  24         >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
  25         Game value: 10.0000000
  26         Player 1 optimal:
  27           [ 1]
  28           [ 2]
  29         Player 2 optimal:
  30           [ 3]
  31           [ 4]
  32
  33     """
  34     def __init__(self, game_value, p1_optimal, p2_optimal):
  35         """
  36         Create a new Solution object from a game value and two optimal
  37         strategies for the players.
  38         """
  39         self._game_value = game_value
  40         self._player1_optimal = p1_optimal
  41         self._player2_optimal = p2_optimal
  42
  43     def __str__(self):
  44         """
  45         Return a string describing the solution of a linear game.
  46
  47         The three data that are described are,
  48
  49           * The value of the game.
  50           * The optimal strategy of player one.
  51           * The optimal strategy of player two.
  52
  53         The two optimal strategy vectors are indented by two spaces.
  54         """
  55         tpl = 'Game value: {:.7f}\n' \
  56               'Player 1 optimal:{:s}\n' \
  57               'Player 2 optimal:{:s}'
  58
  59         p1_str = '\n{!s}'.format(self.player1_optimal())
  60         p1_str = '\n  '.join(p1_str.splitlines())
  61         p2_str = '\n{!s}'.format(self.player2_optimal())
  62         p2_str = '\n  '.join(p2_str.splitlines())
  63
  64         return tpl.format(self.game_value(), p1_str, p2_str)
  65
  66
  67     def game_value(self):
  68         """
  69         Return the game value for this solution.
  70
  71         Examples
  72         --------
  73
  74             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
  75             >>> s.game_value()
  76             10
  77
  78         """
  79         return self._game_value
  80
  81
  82     def player1_optimal(self):
  83         """
  84         Return player one's optimal strategy in this solution.
  85
  86         Examples
  87         --------
  88
  89             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
  90             >>> print(s.player1_optimal())
  91             [ 1]
  92             [ 2]
  93             <BLANKLINE>
  94
  95         """
  96         return self._player1_optimal
  97
  98
  99     def player2_optimal(self):
 100         """
 101         Return player two's optimal strategy in this solution.
 102
 103         Examples
 104         --------
 105
 106             >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
 107             >>> print(s.player2_optimal())
 108             [ 3]
 109             [ 4]
 110             <BLANKLINE>
 111
 112         """
 113         return self._player2_optimal
 114
 115
 116 class SymmetricLinearGame:
 117     r"""
 118     A representation of a symmetric linear game.
 119
 120     The data for a symmetric linear game are,
 121
 122       * A "payoff" operator ``L``.
 123       * A symmetric cone ``K``.
 124       * Two points ``e1`` and ``e2`` in the interior of ``K``.
 125
 126     The ambient space is assumed to be the span of ``K``.
 127
 128     With those data understood, the game is played as follows. Players
 129     one and two choose points :math:`x` and :math:`y` respectively, from
 130     their respective strategy sets,
 131
 132     .. math::
 133         \begin{aligned}
 134             \Delta_{1}
 135             &=
 136             \left\{
 137               x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
 138             \right\}\\
 139             \Delta_{2}
 140             &=
 141             \left\{
 142               y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
 143             \right\}.
 144         \end{aligned}
 145
 146     Afterwards, a "payout" is computed as :math:`\left\langle
 147     L\left(x\right), y \right\rangle` and is paid to player one out of
 148     player two's pocket. The game is therefore zero sum, and we suppose
 149     that player one would like to guarantee himself the largest minimum
 150     payout possible. That is, player one wishes to,
 151
 152     .. math::
 153         \begin{aligned}
 154             \text{maximize }
 155               &\underset{y \in \Delta_{2}}{\min}\left(
 156                 \left\langle L\left(x\right), y \right\rangle
 157               \right)\\
 158             \text{subject to } & x \in \Delta_{1}.
 159         \end{aligned}
 160
 161     Player two has the simultaneous goal to,
 162
 163     .. math::
 164         \begin{aligned}
 165             \text{minimize }
 166               &\underset{x \in \Delta_{1}}{\max}\left(
 167                 \left\langle L\left(x\right), y \right\rangle
 168               \right)\\
 169             \text{subject to } & y \in \Delta_{2}.
 170         \end{aligned}
 171
 172     These goals obviously conflict (the game is zero sum), but an
 173     existence theorem guarantees at least one optimal min-max solution
 174     from which neither player would like to deviate. This class is
 175     able to find such a solution.
 176
 177     Parameters
 178     ----------
 179
 180     L : list of list of float
 181         A matrix represented as a list of ROWS. This representation
 182         agrees with (for example) SageMath and NumPy, but not with CVXOPT
 183         (whose matrix constructor accepts a list of columns).
 184
 185     K : :class:`SymmetricCone`
 186         The symmetric cone instance over which the game is played.
 187
 188     e1 : iterable float
 189         The interior point of ``K`` belonging to player one; it
 190         can be of any iterable type having the correct length.
 191
 192     e2 : iterable float
 193         The interior point of ``K`` belonging to player two; it
 194         can be of any enumerable type having the correct length.
 195
 196     Raises
 197     ------
 198
 199     ValueError
 200         If either ``e1`` or ``e2`` lie outside of the cone ``K``.
 201
 202     Examples
 203     --------
 204
 205         >>> from dunshire import *
 206         >>> K = NonnegativeOrthant(3)
 207         >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 208         >>> e1 = [1,1,1]
 209         >>> e2 = [1,2,3]
 210         >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 211         >>> print(SLG)
 212         The linear game (L, K, e1, e2) where
 213           L = [  1  -5 -15]
 214               [ -1   2  -3]
 215               [-12 -15   1],
 216           K = Nonnegative orthant in the real 3-space,
 217           e1 = [ 1]
 218                [ 1]
 219                [ 1],
 220           e2 = [ 1]
 221                [ 2]
 222                [ 3],
 223           Condition((L, K, e1, e2)) = 31.834...
 224
 225     Lists can (and probably should) be used for every argument::
 226
 227         >>> from dunshire import *
 228         >>> K = NonnegativeOrthant(2)
 229         >>> L = [[1,0],[0,1]]
 230         >>> e1 = [1,1]
 231         >>> e2 = [1,1]
 232         >>> G = SymmetricLinearGame(L, K, e1, e2)
 233         >>> print(G)
 234         The linear game (L, K, e1, e2) where
 235           L = [ 1  0]
 236               [ 0  1],
 237           K = Nonnegative orthant in the real 2-space,
 238           e1 = [ 1]
 239                [ 1],
 240           e2 = [ 1]
 241                [ 1],
 242           Condition((L, K, e1, e2)) = 1.707...
 243
 244     The points ``e1`` and ``e2`` can also be passed as some other
 245     enumerable type (of the correct length) without much harm, since
 246     there is no row/column ambiguity::
 247
 248         >>> import cvxopt
 249         >>> import numpy
 250         >>> from dunshire import *
 251         >>> K = NonnegativeOrthant(2)
 252         >>> L = [[1,0],[0,1]]
 253         >>> e1 = cvxopt.matrix([1,1])
 254         >>> e2 = numpy.matrix([1,1])
 255         >>> G = SymmetricLinearGame(L, K, e1, e2)
 256         >>> print(G)
 257         The linear game (L, K, e1, e2) where
 258           L = [ 1  0]
 259               [ 0  1],
 260           K = Nonnegative orthant in the real 2-space,
 261           e1 = [ 1]
 262                [ 1],
 263           e2 = [ 1]
 264                [ 1],
 265           Condition((L, K, e1, e2)) = 1.707...
 266
 267     However, ``L`` will always be intepreted as a list of rows, even
 268     if it is passed as a :class:`cvxopt.base.matrix` which is
 269     otherwise indexed by columns::
 270
 271         >>> import cvxopt
 272         >>> from dunshire import *
 273         >>> K = NonnegativeOrthant(2)
 274         >>> L = [[1,2],[3,4]]
 275         >>> e1 = [1,1]
 276         >>> e2 = e1
 277         >>> G = SymmetricLinearGame(L, K, e1, e2)
 278         >>> print(G)
 279         The linear game (L, K, e1, e2) where
 280           L = [ 1  2]
 281               [ 3  4],
 282           K = Nonnegative orthant in the real 2-space,
 283           e1 = [ 1]
 284                [ 1],
 285           e2 = [ 1]
 286                [ 1],
 287           Condition((L, K, e1, e2)) = 6.073...
 288         >>> L = cvxopt.matrix(L)
 289         >>> print(L)
 290         [ 1  3]
 291         [ 2  4]
 292         <BLANKLINE>
 293         >>> G = SymmetricLinearGame(L, K, e1, e2)
 294         >>> print(G)
 295         The linear game (L, K, e1, e2) where
 296           L = [ 1  2]
 297               [ 3  4],
 298           K = Nonnegative orthant in the real 2-space,
 299           e1 = [ 1]
 300                [ 1],
 301           e2 = [ 1]
 302                [ 1],
 303           Condition((L, K, e1, e2)) = 6.073...
 304
 305     """
 306     def __init__(self, L, K, e1, e2):
 307         """
 308         Create a new SymmetricLinearGame object.
 309         """
 310         self._K = K
 311         self._e1 = matrix(e1, (K.dimension(), 1))
 312         self._e2 = matrix(e2, (K.dimension(), 1))
 313
 314         # Our input ``L`` is indexed by rows but CVXOPT matrices are
 315         # indexed by columns, so we need to transpose the input before
 316         # feeding it to CVXOPT.
 317         self._L = matrix(L, (K.dimension(), K.dimension())).trans()
 318
 319         if not self._e1 in K:
 320             raise ValueError('the point e1 must lie in the interior of K')
 321
 322         if not self._e2 in K:
 323             raise ValueError('the point e2 must lie in the interior of K')
 324
 325
 326
 327     def __str__(self):
 328         """
 329         Return a string representation of this game.
 330         """
 331         tpl = 'The linear game (L, K, e1, e2) where\n' \
 332               '  L = {:s},\n' \
 333               '  K = {!s},\n' \
 334               '  e1 = {:s},\n' \
 335               '  e2 = {:s},\n' \
 336               '  Condition((L, K, e1, e2)) = {:f}.'
 337         indented_L = '\n      '.join(str(self._L).splitlines())
 338         indented_e1 = '\n       '.join(str(self._e1).splitlines())
 339         indented_e2 = '\n       '.join(str(self._e2).splitlines())
 340
 341         return tpl.format(indented_L,
 342                           str(self._K),
 343                           indented_e1,
 344                           indented_e2,
 345                           self.condition())
 346
 347
 348     def _zero(self):
 349         """
 350         Return a column of zeros that fits ``K``.
 351
 352         This is used in our CVXOPT construction.
 353
 354         .. warning::
 355
 356             It is not safe to cache any of the matrices passed to
 357             CVXOPT, because it can clobber them.
 358
 359         Returns
 360         -------
 361
 362         matrix
 363             A ``K.dimension()``-by-``1`` column vector of zeros.
 364
 365         Examples
 366         --------
 367
 368             >>> from dunshire import *
 369             >>> K = NonnegativeOrthant(3)
 370             >>> L = identity(3)
 371             >>> e1 = [1,1,1]
 372             >>> e2 = e1
 373             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 374             >>> print(SLG._zero())
 375             [0.0000000]
 376             [0.0000000]
 377             [0.0000000]
 378             <BLANKLINE>
 379
 380         """
 381         return matrix(0, (self._K.dimension(), 1), tc='d')
 382
 383
 384     def _A(self):
 385         """
 386         Return the matrix ``A`` used in our CVXOPT construction.
 387
 388         This matrix ``A``  appears on the right-hand side of ``Ax = b``
 389         in the statement of the CVXOPT conelp program.
 390
 391         .. warning::
 392
 393             It is not safe to cache any of the matrices passed to
 394             CVXOPT, because it can clobber them.
 395
 396         Returns
 397         -------
 398
 399         matrix
 400             A ``1``-by-``(1 + K.dimension())`` row vector. Its first
 401             entry is zero, and the rest are the entries of ``e2``.
 402
 403         Examples
 404         --------
 405
 406             >>> from dunshire import *
 407             >>> K = NonnegativeOrthant(3)
 408             >>> L = [[1,1,1],[1,1,1],[1,1,1]]
 409             >>> e1 = [1,1,1]
 410             >>> e2 = [1,2,3]
 411             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 412             >>> print(SLG._A())
 413             [0.0000000 1.0000000 2.0000000 3.0000000]
 414             <BLANKLINE>
 415
 416         """
 417         return matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
 418
 419
 420
 421     def _G(self):
 422         r"""
 423         Return the matrix ``G`` used in our CVXOPT construction.
 424
 425         Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
 426         in the statement of the CVXOPT conelp program.
 427
 428         .. warning::
 429
 430             It is not safe to cache any of the matrices passed to
 431             CVXOPT, because it can clobber them.
 432
 433         Returns
 434         -------
 435
 436         matrix
 437             A ``2*K.dimension()``-by-``1 + K.dimension()`` matrix.
 438
 439         Examples
 440         --------
 441
 442             >>> from dunshire import *
 443             >>> K = NonnegativeOrthant(3)
 444             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 445             >>> e1 = [1,2,3]
 446             >>> e2 = [1,1,1]
 447             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 448             >>> print(SLG._G())
 449             [  0.0000000  -1.0000000   0.0000000   0.0000000]
 450             [  0.0000000   0.0000000  -1.0000000   0.0000000]
 451             [  0.0000000   0.0000000   0.0000000  -1.0000000]
 452             [  1.0000000  -4.0000000  -5.0000000  -6.0000000]
 453             [  2.0000000  -7.0000000  -8.0000000  -9.0000000]
 454             [  3.0000000 -10.0000000 -11.0000000 -12.0000000]
 455             <BLANKLINE>
 456
 457         """
 458         I = identity(self._K.dimension())
 459         return append_row(append_col(self._zero(), -I),
 460                           append_col(self._e1, -self._L))
 461
 462
 463     def _c(self):
 464         """
 465         Return the vector ``c`` used in our CVXOPT construction.
 466
 467         The column vector ``c``  appears in the objective function
 468         value ``<c,x>`` in the statement of the CVXOPT conelp program.
 469
 470         .. warning::
 471
 472             It is not safe to cache any of the matrices passed to
 473             CVXOPT, because it can clobber them.
 474
 475         Returns
 476         -------
 477
 478         matrix
 479             A ``K.dimension()``-by-``1`` column vector.
 480
 481         Examples
 482         --------
 483
 484             >>> from dunshire import *
 485             >>> K = NonnegativeOrthant(3)
 486             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 487             >>> e1 = [1,2,3]
 488             >>> e2 = [1,1,1]
 489             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 490             >>> print(SLG._c())
 491             [-1.0000000]
 492             [ 0.0000000]
 493             [ 0.0000000]
 494             [ 0.0000000]
 495             <BLANKLINE>
 496
 497         """
 498         return matrix([-1, self._zero()])
 499
 500
 501     def _C(self):
 502         """
 503         Return the cone ``C`` used in our CVXOPT construction.
 504
 505         The cone ``C`` is the cone over which the conelp program takes
 506         place.
 507
 508         Returns
 509         -------
 510
 511         CartesianProduct
 512             The cartesian product of ``K`` with itself.
 513
 514         Examples
 515         --------
 516
 517             >>> from dunshire import *
 518             >>> K = NonnegativeOrthant(3)
 519             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 520             >>> e1 = [1,2,3]
 521             >>> e2 = [1,1,1]
 522             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 523             >>> print(SLG._C())
 524             Cartesian product of dimension 6 with 2 factors:
 525               * Nonnegative orthant in the real 3-space
 526               * Nonnegative orthant in the real 3-space
 527
 528         """
 529         return CartesianProduct(self._K, self._K)
 530
 531     def _h(self):
 532         """
 533         Return the ``h`` vector used in our CVXOPT construction.
 534
 535         The ``h`` vector appears on the right-hand side of :math:`Gx + s
 536         = h` in the statement of the CVXOPT conelp program.
 537
 538         .. warning::
 539
 540             It is not safe to cache any of the matrices passed to
 541             CVXOPT, because it can clobber them.
 542
 543         Returns
 544         -------
 545
 546         matrix
 547             A ``2*K.dimension()``-by-``1`` column vector of zeros.
 548
 549         Examples
 550         --------
 551
 552             >>> from dunshire import *
 553             >>> K = NonnegativeOrthant(3)
 554             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 555             >>> e1 = [1,2,3]
 556             >>> e2 = [1,1,1]
 557             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 558             >>> print(SLG._h())
 559             [0.0000000]
 560             [0.0000000]
 561             [0.0000000]
 562             [0.0000000]
 563             [0.0000000]
 564             [0.0000000]
 565             <BLANKLINE>
 566
 567         """
 568
 569         return matrix([self._zero(), self._zero()])
 570
 571     def _b(self):
 572         """
 573         Return the ``b`` vector used in our CVXOPT construction.
 574
 575         The vector ``b`` appears on the right-hand side of :math:`Ax =
 576         b` in the statement of the CVXOPT conelp program.
 577
 578         .. warning::
 579
 580             It is not safe to cache any of the matrices passed to
 581             CVXOPT, because it can clobber them.
 582
 583         Returns
 584         -------
 585
 586         matrix
 587             A ``1``-by-``1`` matrix containing a single entry ``1``.
 588
 589         Examples
 590         --------
 591
 592             >>> from dunshire import *
 593             >>> K = NonnegativeOrthant(3)
 594             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 595             >>> e1 = [1,2,3]
 596             >>> e2 = [1,1,1]
 597             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 598             >>> print(SLG._b())
 599             [1.0000000]
 600             <BLANKLINE>
 601
 602         """
 603         return matrix([1], tc='d')
 604
 605
 606     def _try_solution(self, tolerance):
 607         """
 608         Solve this linear game within ``tolerance``, if possible.
 609
 610         This private function is the one that does all of the actual
 611         work for :meth:`solution`. This method accepts a ``tolerance``,
 612         and what :meth:`solution` does is call this method twice with
 613         two different tolerances. First it tries a strict tolerance, and
 614         then it tries a looser one.
 615
 616         .. warning::
 617
 618             If you try to be smart and precompute the matrices used by
 619             this function (the ones passed to ``conelp``), then you're
 620             going to shoot yourself in the foot. CVXOPT can and will
 621             clobber some (but not all) of its input matrices. This isn't
 622             performance sensitive, so play it safe.
 623
 624         Parameters
 625         ----------
 626
 627         tolerance : float
 628             The absolute tolerance to pass to the CVXOPT solver.
 629
 630         Returns
 631         -------
 632
 633         :class:`Solution`
 634             A :class:`Solution` object describing the game's value and
 635             the optimal strategies of both players.
 636
 637         Raises
 638         ------
 639         GameUnsolvableException
 640             If the game could not be solved (if an optimal solution to its
 641             associated cone program was not found).
 642
 643         PoorScalingException
 644             If the game could not be solved because CVXOPT crashed while
 645             trying to take the square root of a negative number.
 646
 647         Examples
 648         --------
 649
 650         This game can be solved easily, so the first attempt in
 651         :meth:`solution` should succeed::
 652
 653             >>> from dunshire import *
 654             >>> from dunshire.matrices import norm
 655             >>> from dunshire.options import ABS_TOL
 656             >>> K = NonnegativeOrthant(3)
 657             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 658             >>> e1 = [1,1,1]
 659             >>> e2 = [1,1,1]
 660             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 661             >>> s1 = SLG.solution()
 662             >>> s2 = SLG._try_solution(options.ABS_TOL)
 663             >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL
 664             True
 665             >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL
 666             True
 667             >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL
 668             True
 669
 670         """
 671         try:
 672             solvers.options['show_progress'] = options.VERBOSE
 673             solvers.options['abs_tol'] = tolerance
 674             soln_dict = solvers.conelp(self._c(),
 675                                        self._G(),
 676                                        self._h(),
 677                                        self._C().cvxopt_dims(),
 678                                        self._A(),
 679                                        self._b())
 680         except ValueError as e:
 681             if str(e) == 'math domain error':
 682                 # Oops, CVXOPT tried to take the square root of a
 683                 # negative number. Report some details about the game
 684                 # rather than just the underlying CVXOPT crash.
 685                 raise PoorScalingException(self)
 686             else:
 687                 raise e
 688
 689         # The optimal strategies are named ``p`` and ``q`` in the
 690         # background documentation, and we need to extract them from
 691         # the CVXOPT ``x`` and ``z`` variables. The objective values
 692         # :math:`nu` and :math:`omega` can also be found in the CVXOPT
 693         # ``x`` and ``y`` variables; however, they're stored
 694         # conveniently as separate entries in the solution dictionary.
 695         p1_value = -soln_dict['primal objective']
 696         p2_value = -soln_dict['dual objective']
 697         p1_optimal = soln_dict['x'][1:]
 698         p2_optimal = soln_dict['z'][self._K.dimension():]
 699
 700         # The "status" field contains "optimal" if everything went
 701         # according to plan. Other possible values are "primal
 702         # infeasible", "dual infeasible", "unknown", all of which mean
 703         # we didn't get a solution. The "infeasible" ones are the
 704         # worst, since they indicate that CVXOPT is convinced the
 705         # problem is infeasible (and that cannot happen).
 706         if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
 707             raise GameUnsolvableException(self, soln_dict)
 708         elif soln_dict['status'] == 'unknown':
 709             # When we get a status of "unknown", we may still be able
 710             # to salvage a solution out of the returned
 711             # dictionary. Often this is the result of numerical
 712             # difficulty and we can simply check that the primal/dual
 713             # objectives match (within a tolerance) and that the
 714             # primal/dual optimal solutions are within the cone (to a
 715             # tolerance as well).
 716             #
 717             # The fudge factor of two is basically unjustified, but
 718             # makes intuitive sense when you imagine that the primal
 719             # value could be under the true optimal by ``ABS_TOL``
 720             # and the dual value could be over by the same amount.
 721             #
 722             if abs(p1_value - p2_value) > tolerance:
 723                 raise GameUnsolvableException(self, soln_dict)
 724             if (p1_optimal not in self._K) or (p2_optimal not in self._K):
 725                 raise GameUnsolvableException(self, soln_dict)
 726
 727         return Solution(p1_value, p1_optimal, p2_optimal)
 728
 729
 730     def solution(self):
 731         """
 732         Solve this linear game and return a :class:`Solution`.
 733
 734         Returns
 735         -------
 736
 737         :class:`Solution`
 738             A :class:`Solution` object describing the game's value and
 739             the optimal strategies of both players.
 740
 741         Raises
 742         ------
 743         GameUnsolvableException
 744             If the game could not be solved (if an optimal solution to its
 745             associated cone program was not found).
 746
 747         PoorScalingException
 748             If the game could not be solved because CVXOPT crashed while
 749             trying to take the square root of a negative number.
 750
 751         Examples
 752         --------
 753
 754         This example is computed in Gowda and Ravindran in the section
 755         "The value of a Z-transformation"::
 756
 757             >>> from dunshire import *
 758             >>> K = NonnegativeOrthant(3)
 759             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 760             >>> e1 = [1,1,1]
 761             >>> e2 = [1,1,1]
 762             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 763             >>> print(SLG.solution())
 764             Game value: -6.1724138
 765             Player 1 optimal:
 766               [ 0.551...]
 767               [-0.000...]
 768               [ 0.448...]
 769             Player 2 optimal:
 770               [0.448...]
 771               [0.000...]
 772               [0.551...]
 773
 774         The value of the following game can be computed using the fact
 775         that the identity is invertible::
 776
 777             >>> from dunshire import *
 778             >>> K = NonnegativeOrthant(3)
 779             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 780             >>> e1 = [1,2,3]
 781             >>> e2 = [4,5,6]
 782             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 783             >>> print(SLG.solution())
 784             Game value: 0.0312500
 785             Player 1 optimal:
 786               [0.031...]
 787               [0.062...]
 788               [0.093...]
 789             Player 2 optimal:
 790               [0.125...]
 791               [0.156...]
 792               [0.187...]
 793
 794         """
 795         try:
 796             # First try with a stricter tolerance. Who knows, it might
 797             # work. If it does, we prefer that solution.
 798             return self._try_solution(options.ABS_TOL / 10)
 799
 800         except (PoorScalingException, GameUnsolvableException):
 801             # Ok, that didn't work. Let's try it with the default
 802             # tolerance, and whatever happens, happens.
 803             return self._try_solution(options.ABS_TOL)
 804
 805
 806     def condition(self):
 807         r"""
 808         Return the condition number of this game.
 809
 810         In the CVXOPT construction of this game, two matrices ``G`` and
 811         ``A`` appear. When those matrices are nasty, numerical problems
 812         can show up. We define the condition number of this game to be
 813         the average of the condition numbers of ``G`` and ``A`` in the
 814         CVXOPT construction. If the condition number of this game is
 815         high, then you can expect numerical difficulty (such as
 816         :class:`PoorScalingException`).
 817
 818         Returns
 819         -------
 820
 821         float
 822             A real number greater than or equal to one that measures how
 823             bad this game is numerically.
 824
 825         Examples
 826         --------
 827
 828         >>> from dunshire import *
 829         >>> K = NonnegativeOrthant(1)
 830         >>> L = [[1]]
 831         >>> e1 = [1]
 832         >>> e2 = e1
 833         >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 834         >>> actual = SLG.condition()
 835         >>> expected = 1.8090169943749477
 836         >>> abs(actual - expected) < options.ABS_TOL
 837         True
 838
 839         """
 840         return (condition_number(self._G()) + condition_number(self._A()))/2
 841
 842
 843     def dual(self):
 844         r"""
 845         Return the dual game to this game.
 846
 847         If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
 848         then its dual is :math:`G^{*} =
 849         \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
 850         is symmetric, :math:`K^{*} = K`.
 851
 852         Examples
 853         --------
 854
 855             >>> from dunshire import *
 856             >>> K = NonnegativeOrthant(3)
 857             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 858             >>> e1 = [1,1,1]
 859             >>> e2 = [1,2,3]
 860             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 861             >>> print(SLG.dual())
 862             The linear game (L, K, e1, e2) where
 863               L = [  1  -1 -12]
 864                   [ -5   2 -15]
 865                   [-15  -3   1],
 866               K = Nonnegative orthant in the real 3-space,
 867               e1 = [ 1]
 868                    [ 2]
 869                    [ 3],
 870               e2 = [ 1]
 871                    [ 1]
 872                    [ 1],
 873               Condition((L, K, e1, e2)) = 44.476...
 874
 875         """
 876         # We pass ``self._L`` right back into the constructor, because
 877         # it will be transposed there. And keep in mind that ``self._K``
 878         # is its own dual.
 879         return SymmetricLinearGame(self._L,
 880                                    self._K,
 881                                    self._e2,
 882                                    self._e1)