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
 813     def solution(self):
 814         """
 815         Solve this linear game and return a :class:`Solution`.
 816
 817         Returns
 818         -------
 819
 820         :class:`Solution`
 821             A :class:`Solution` object describing the game's value and
 822             the optimal strategies of both players.
 823
 824         Raises
 825         ------
 826         GameUnsolvableException
 827             If the game could not be solved (if an optimal solution to its
 828             associated cone program was not found).
 829
 830         PoorScalingException
 831             If the game could not be solved because CVXOPT crashed while
 832             trying to take the square root of a negative number.
 833
 834         Examples
 835         --------
 836
 837         This example is computed in Gowda and Ravindran in the section
 838         "The value of a Z-transformation"::
 839
 840             >>> from dunshire import *
 841             >>> K = NonnegativeOrthant(3)
 842             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 843             >>> e1 = [1,1,1]
 844             >>> e2 = [1,1,1]
 845             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 846             >>> print(SLG.solution())
 847             Game value: -6.1724138
 848             Player 1 optimal:
 849               [ 0.551...]
 850               [-0.000...]
 851               [ 0.448...]
 852             Player 2 optimal:
 853               [0.448...]
 854               [0.000...]
 855               [0.551...]
 856
 857         The value of the following game can be computed using the fact
 858         that the identity is invertible::
 859
 860             >>> from dunshire import *
 861             >>> K = NonnegativeOrthant(3)
 862             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 863             >>> e1 = [1,2,3]
 864             >>> e2 = [4,5,6]
 865             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 866             >>> print(SLG.solution())
 867             Game value: 0.0312500
 868             Player 1 optimal:
 869               [0.031...]
 870               [0.062...]
 871               [0.093...]
 872             Player 2 optimal:
 873               [0.125...]
 874               [0.156...]
 875               [0.187...]
 876
 877         This is another Gowda/Ravindran example that is supposed to have
 878         a negative game value::
 879
 880             >>> from dunshire import *
 881             >>> from dunshire.options import ABS_TOL
 882             >>> L = [[1, -2], [-2, 1]]
 883             >>> K = NonnegativeOrthant(2)
 884             >>> e1 = [1, 1]
 885             >>> e2 = e1
 886             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 887             >>> SLG.solution().game_value() < -ABS_TOL
 888             True
 889
 890         The following two games are problematic numerically, but we
 891         should be able to solve them::
 892
 893             >>> from dunshire import *
 894             >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
 895             ...      [ 1.30481749924621448500, 1.65278664543326403447]]
 896             >>> K = NonnegativeOrthant(2)
 897             >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
 898             >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
 899             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 900             >>> print(SLG.solution())
 901             Game value: 18.767...
 902             Player 1 optimal:
 903               [-0.000...]
 904               [ 9.766...]
 905             Player 2 optimal:
 906               [1.047...]
 907               [0.000...]
 908
 909         ::
 910
 911             >>> from dunshire import *
 912             >>> L = [[1.54159395026049472754, 2.21344728574316684799],
 913             ...      [1.33147433507846657541, 1.17913616272988108769]]
 914             >>> K = NonnegativeOrthant(2)
 915             >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
 916             >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
 917             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 918             >>> print(SLG.solution())
 919             Game value: 24.614...
 920             Player 1 optimal:
 921               [ 6.371...]
 922               [-0.000...]
 923             Player 2 optimal:
 924               [2.506...]
 925               [0.000...]
 926
 927         """
 928         try:
 929             opts = {'show_progress': False}
 930             soln_dict = solvers.conelp(self._c(),
 931                                        self._G(),
 932                                        self._h(),
 933                                        self.C().cvxopt_dims(),
 934                                        self.A(),
 935                                        self.b(),
 936                                        options=opts)
 937         except ValueError as error:
 938             if str(error) == 'math domain error':
 939                 # Oops, CVXOPT tried to take the square root of a
 940                 # negative number. Report some details about the game
 941                 # rather than just the underlying CVXOPT crash.
 942                 printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
 943                 raise PoorScalingException(self)
 944             else:
 945                 raise error
 946
 947         # The optimal strategies are named ``p`` and ``q`` in the
 948         # background documentation, and we need to extract them from
 949         # the CVXOPT ``x`` and ``z`` variables. The objective values
 950         # :math:`nu` and :math:`omega` can also be found in the CVXOPT
 951         # ``x`` and ``y`` variables; however, they're stored
 952         # conveniently as separate entries in the solution dictionary.
 953         p1_value = -soln_dict['primal objective']
 954         p2_value = -soln_dict['dual objective']
 955         p1_optimal = soln_dict['x'][1:]
 956         p2_optimal = soln_dict['z'][self.dimension():]
 957
 958         # The "status" field contains "optimal" if everything went
 959         # according to plan. Other possible values are "primal
 960         # infeasible", "dual infeasible", "unknown", all of which mean
 961         # we didn't get a solution.
 962         #
 963         # The "infeasible" ones are the worst, since they indicate
 964         # that CVXOPT is convinced the problem is infeasible (and that
 965         # cannot happen).
 966         if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
 967             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
 968             raise GameUnsolvableException(self, soln_dict)
 969
 970         # The "optimal" and "unknown" results, we actually treat the
 971         # same. Even if CVXOPT bails out due to numerical difficulty,
 972         # it will have some candidate points in mind. If those
 973         # candidates are good enough, we take them. We do the same
 974         # check (perhaps pointlessly so) for "optimal" results.
 975         #
 976         # First we check that the primal/dual objective values are
 977         # close enough (one could be low by ABS_TOL, the other high by
 978         # it) because otherwise CVXOPT might return "unknown" and give
 979         # us two points in the cone that are nowhere near optimal.
 980         if abs(p1_value - p2_value) > 2*options.ABS_TOL:
 981             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
 982             raise GameUnsolvableException(self, soln_dict)
 983
 984         # And we also check that the points it gave us belong to the
 985         # cone, just in case...
 986         if (p1_optimal not in self._K) or (p2_optimal not in self._K):
 987             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
 988             raise GameUnsolvableException(self, soln_dict)
 989
 990         # For the game value, we could use any of:
 991         #
 992         #   * p1_value
 993         #   * p2_value
 994         #   * (p1_value + p2_value)/2
 995         #   * the game payoff
 996         #
 997         # We want the game value to be the payoff, however, so it
 998         # makes the most sense to just use that, even if it means we
 999         # can't test the fact that p1_value/p2_value are close to the
1000         # payoff.
1001         payoff = self.payoff(p1_optimal, p2_optimal)
1002         return Solution(payoff, p1_optimal, p2_optimal)
1003
1004
1005     def condition(self):
1006         r"""
1007         Return the condition number of this game.
1008
1009         In the CVXOPT construction of this game, two matrices ``G`` and
1010         ``A`` appear. When those matrices are nasty, numerical problems
1011         can show up. We define the condition number of this game to be
1012         the average of the condition numbers of ``G`` and ``A`` in the
1013         CVXOPT construction. If the condition number of this game is
1014         high, then you can expect numerical difficulty (such as
1015         :class:`PoorScalingException`).
1016
1017         Returns
1018         -------
1019
1020         float
1021             A real number greater than or equal to one that measures how
1022             bad this game is numerically.
1023
1024         Examples
1025         --------
1026
1027         >>> from dunshire import *
1028         >>> K = NonnegativeOrthant(1)
1029         >>> L = [[1]]
1030         >>> e1 = [1]
1031         >>> e2 = e1
1032         >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1033         >>> actual = SLG.condition()
1034         >>> expected = 1.8090169943749477
1035         >>> abs(actual - expected) < options.ABS_TOL
1036         True
1037
1038         """
1039         return (condition_number(self._G()) + condition_number(self.A()))/2
1040
1041
1042     def dual(self):
1043         r"""
1044         Return the dual game to this game.
1045
1046         If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1047         then its dual is :math:`G^{*} =
1048         \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1049         is symmetric, :math:`K^{*} = K`.
1050
1051         Examples
1052         --------
1053
1054             >>> from dunshire import *
1055             >>> K = NonnegativeOrthant(3)
1056             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1057             >>> e1 = [1,1,1]
1058             >>> e2 = [1,2,3]
1059             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1060             >>> print(SLG.dual())
1061             The linear game (L, K, e1, e2) where
1062               L = [  1  -1 -12]
1063                   [ -5   2 -15]
1064                   [-15  -3   1],
1065               K = Nonnegative orthant in the real 3-space,
1066               e1 = [ 1]
1067                    [ 2]
1068                    [ 3],
1069               e2 = [ 1]
1070                    [ 1]
1071                    [ 1],
1072               Condition((L, K, e1, e2)) = 44.476...
1073
1074         """
1075         # We pass ``self.L()`` right back into the constructor, because
1076         # it will be transposed there. And keep in mind that ``self._K``
1077         # is its own dual.
1078         return SymmetricLinearGame(self.L(),
1079                                    self.K(),
1080                                    self.e2(),
1081                                    self.e1())