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