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 from cvxopt import matrix, printing, solvers
   8 from .cones import CartesianProduct
   9 from .errors import GameUnsolvableException, PoorScalingException
  10 from .matrices import (append_col, append_row, condition_number, identity,
  11                        inner_product, norm, specnorm)
  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.000...
  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         # Initial value of cached method.
 326         self._L_specnorm_value = None
 327
 328
 329     def __str__(self):
 330         """
 331         Return a string representation of this game.
 332         """
 333         tpl = 'The linear game (L, K, e1, e2) where\n' \
 334               '  L = {:s},\n' \
 335               '  K = {!s},\n' \
 336               '  e1 = {:s},\n' \
 337               '  e2 = {:s},\n' \
 338               '  Condition((L, K, e1, e2)) = {:f}.'
 339         indented_L = '\n      '.join(str(self.L()).splitlines())
 340         indented_e1 = '\n       '.join(str(self.e1()).splitlines())
 341         indented_e2 = '\n       '.join(str(self.e2()).splitlines())
 342
 343         return tpl.format(indented_L,
 344                           str(self.K()),
 345                           indented_e1,
 346                           indented_e2,
 347                           self.condition())
 348
 349
 350     def L(self):
 351         """
 352         Return the matrix ``L`` passed to the constructor.
 353
 354         Returns
 355         -------
 356
 357         matrix
 358             The matrix that defines this game's :meth:`payoff` operator.
 359
 360         Examples
 361         --------
 362
 363             >>> from dunshire import *
 364             >>> K = NonnegativeOrthant(3)
 365             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 366             >>> e1 = [1,1,1]
 367             >>> e2 = [1,2,3]
 368             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 369             >>> print(SLG.L())
 370             [  1  -5 -15]
 371             [ -1   2  -3]
 372             [-12 -15   1]
 373             <BLANKLINE>
 374
 375         """
 376         return self._L
 377
 378
 379     def K(self):
 380         """
 381         Return the cone over which this game is played.
 382
 383         Returns
 384         -------
 385
 386         SymmetricCone
 387             The :class:`SymmetricCone` over which this game is played.
 388
 389         Examples
 390         --------
 391
 392             >>> from dunshire import *
 393             >>> K = NonnegativeOrthant(3)
 394             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 395             >>> e1 = [1,1,1]
 396             >>> e2 = [1,2,3]
 397             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 398             >>> print(SLG.K())
 399             Nonnegative orthant in the real 3-space
 400
 401         """
 402         return self._K
 403
 404
 405     def e1(self):
 406         """
 407         Return player one's interior point.
 408
 409         Returns
 410         -------
 411
 412         matrix
 413             The point interior to :meth:`K` affiliated with player one.
 414
 415         Examples
 416         --------
 417
 418             >>> from dunshire import *
 419             >>> K = NonnegativeOrthant(3)
 420             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 421             >>> e1 = [1,1,1]
 422             >>> e2 = [1,2,3]
 423             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 424             >>> print(SLG.e1())
 425             [ 1]
 426             [ 1]
 427             [ 1]
 428             <BLANKLINE>
 429
 430         """
 431         return self._e1
 432
 433
 434     def e2(self):
 435         """
 436         Return player two's interior point.
 437
 438         Returns
 439         -------
 440
 441         matrix
 442             The point interior to :meth:`K` affiliated with player one.
 443
 444         Examples
 445         --------
 446
 447             >>> from dunshire import *
 448             >>> K = NonnegativeOrthant(3)
 449             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 450             >>> e1 = [1,1,1]
 451             >>> e2 = [1,2,3]
 452             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 453             >>> print(SLG.e2())
 454             [ 1]
 455             [ 2]
 456             [ 3]
 457             <BLANKLINE>
 458
 459         """
 460         return self._e2
 461
 462
 463     def payoff(self, strategy1, strategy2):
 464         r"""
 465         Return the payoff associated with ``strategy1`` and ``strategy2``.
 466
 467         The payoff operator takes pairs of strategies to a real
 468         number. For example, if player one's strategy is :math:`x` and
 469         player two's strategy is :math:`y`, then the associated payoff
 470         is :math:`\left\langle L\left(x\right),y \right\rangle` \in
 471         \mathbb{R}. Here, :math:`L` denotes the same linear operator as
 472         :meth:`L`. This method computes the payoff given the two
 473         players' strategies.
 474
 475         Parameters
 476         ----------
 477
 478         strategy1 : matrix
 479             Player one's strategy.
 480
 481         strategy2 : matrix
 482             Player two's strategy.
 483
 484         Returns
 485         -------
 486
 487         float
 488             The payoff for the game when player one plays ``strategy1``
 489             and player two plays ``strategy2``.
 490
 491         Examples
 492         --------
 493
 494         The value of the game should be the payoff at the optimal
 495         strategies::
 496
 497             >>> from dunshire import *
 498             >>> from dunshire.options import ABS_TOL
 499             >>> K = NonnegativeOrthant(3)
 500             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 501             >>> e1 = [1,1,1]
 502             >>> e2 = [1,1,1]
 503             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 504             >>> soln = SLG.solution()
 505             >>> x_bar = soln.player1_optimal()
 506             >>> y_bar = soln.player2_optimal()
 507             >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL
 508             True
 509
 510         """
 511         return inner_product(self.L()*strategy1, strategy2)
 512
 513
 514     def dimension(self):
 515         """
 516         Return the dimension of this game.
 517
 518         The dimension of a game is not needed for the theory, but it is
 519         useful for the implementation. We define the dimension of a game
 520         to be the dimension of its underlying cone. Or what is the same,
 521         the dimension of the space from which the strategies are chosen.
 522
 523         Returns
 524         -------
 525
 526         int
 527             The dimension of the cone :meth:`K`, or of the space where
 528             this game is played.
 529
 530         Examples
 531         --------
 532
 533         The dimension of a game over the nonnegative quadrant in the
 534         plane should be two (the dimension of the plane)::
 535
 536             >>> from dunshire import *
 537             >>> K = NonnegativeOrthant(2)
 538             >>> L = [[1,-5],[-1,2]]
 539             >>> e1 = [1,1]
 540             >>> e2 = [1,4]
 541             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 542             >>> SLG.dimension()
 543             2
 544
 545         """
 546         return self.K().dimension()
 547
 548
 549     def _zero(self):
 550         """
 551         Return a column of zeros that fits ``K``.
 552
 553         This is used in our CVXOPT construction.
 554
 555         .. warning::
 556
 557             It is not safe to cache any of the matrices passed to
 558             CVXOPT, because it can clobber them.
 559
 560         Returns
 561         -------
 562
 563         matrix
 564             A ``self.dimension()``-by-``1`` column vector of zeros.
 565
 566         Examples
 567         --------
 568
 569             >>> from dunshire import *
 570             >>> K = NonnegativeOrthant(3)
 571             >>> L = identity(3)
 572             >>> e1 = [1,1,1]
 573             >>> e2 = e1
 574             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 575             >>> print(SLG._zero())
 576             [0.0000000]
 577             [0.0000000]
 578             [0.0000000]
 579             <BLANKLINE>
 580
 581         """
 582         return matrix(0, (self.dimension(), 1), tc='d')
 583
 584
 585     def A(self):
 586         """
 587         Return the matrix ``A`` used in our CVXOPT construction.
 588
 589         This matrix ``A``  appears on the right-hand side of ``Ax = b``
 590         in the statement of the CVXOPT conelp program.
 591
 592         .. warning::
 593
 594             It is not safe to cache any of the matrices passed to
 595             CVXOPT, because it can clobber them.
 596
 597         Returns
 598         -------
 599
 600         matrix
 601             A ``1``-by-``(1 + self.dimension())`` row vector. Its first
 602             entry is zero, and the rest are the entries of ``e2``.
 603
 604         Examples
 605         --------
 606
 607             >>> from dunshire import *
 608             >>> K = NonnegativeOrthant(3)
 609             >>> L = [[1,1,1],[1,1,1],[1,1,1]]
 610             >>> e1 = [1,1,1]
 611             >>> e2 = [1,2,3]
 612             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 613             >>> print(SLG.A())
 614             [0.0000000 1.0000000 2.0000000 3.0000000]
 615             <BLANKLINE>
 616
 617         """
 618         return matrix([0, self.e2()], (1, self.dimension() + 1), 'd')
 619
 620
 621
 622     def _G(self):
 623         r"""
 624         Return the matrix ``G`` used in our CVXOPT construction.
 625
 626         Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
 627         in the statement of the CVXOPT conelp program.
 628
 629         .. warning::
 630
 631             It is not safe to cache any of the matrices passed to
 632             CVXOPT, because it can clobber them.
 633
 634         Returns
 635         -------
 636
 637         matrix
 638             A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix.
 639
 640         Examples
 641         --------
 642
 643             >>> from dunshire import *
 644             >>> K = NonnegativeOrthant(3)
 645             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 646             >>> e1 = [1,2,3]
 647             >>> e2 = [1,1,1]
 648             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 649             >>> print(SLG._G())
 650             [  0.0000000  -1.0000000   0.0000000   0.0000000]
 651             [  0.0000000   0.0000000  -1.0000000   0.0000000]
 652             [  0.0000000   0.0000000   0.0000000  -1.0000000]
 653             [  1.0000000  -4.0000000  -5.0000000  -6.0000000]
 654             [  2.0000000  -7.0000000  -8.0000000  -9.0000000]
 655             [  3.0000000 -10.0000000 -11.0000000 -12.0000000]
 656             <BLANKLINE>
 657
 658         """
 659         identity_matrix = identity(self.dimension())
 660         return append_row(append_col(self._zero(), -identity_matrix),
 661                           append_col(self.e1(), -self.L()))
 662
 663
 664     def _c(self):
 665         """
 666         Return the vector ``c`` used in our CVXOPT construction.
 667
 668         The column vector ``c``  appears in the objective function
 669         value ``<c,x>`` in the statement of the CVXOPT conelp program.
 670
 671         .. warning::
 672
 673             It is not safe to cache any of the matrices passed to
 674             CVXOPT, because it can clobber them.
 675
 676         Returns
 677         -------
 678
 679         matrix
 680             A ``self.dimension()``-by-``1`` column vector.
 681
 682         Examples
 683         --------
 684
 685             >>> from dunshire import *
 686             >>> K = NonnegativeOrthant(3)
 687             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 688             >>> e1 = [1,2,3]
 689             >>> e2 = [1,1,1]
 690             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 691             >>> print(SLG._c())
 692             [-1.0000000]
 693             [ 0.0000000]
 694             [ 0.0000000]
 695             [ 0.0000000]
 696             <BLANKLINE>
 697
 698         """
 699         return matrix([-1, self._zero()])
 700
 701
 702     def C(self):
 703         """
 704         Return the cone ``C`` used in our CVXOPT construction.
 705
 706         The cone ``C`` is the cone over which the conelp program takes
 707         place.
 708
 709         Returns
 710         -------
 711
 712         CartesianProduct
 713             The cartesian product of ``K`` with itself.
 714
 715         Examples
 716         --------
 717
 718             >>> from dunshire import *
 719             >>> K = NonnegativeOrthant(3)
 720             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 721             >>> e1 = [1,2,3]
 722             >>> e2 = [1,1,1]
 723             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 724             >>> print(SLG.C())
 725             Cartesian product of dimension 6 with 2 factors:
 726               * Nonnegative orthant in the real 3-space
 727               * Nonnegative orthant in the real 3-space
 728
 729         """
 730         return CartesianProduct(self._K, self._K)
 731
 732     def _h(self):
 733         """
 734         Return the ``h`` vector used in our CVXOPT construction.
 735
 736         The ``h`` vector appears on the right-hand side of :math:`Gx + s
 737         = h` in the statement of the CVXOPT conelp program.
 738
 739         .. warning::
 740
 741             It is not safe to cache any of the matrices passed to
 742             CVXOPT, because it can clobber them.
 743
 744         Returns
 745         -------
 746
 747         matrix
 748             A ``2*self.dimension()``-by-``1`` column vector of zeros.
 749
 750         Examples
 751         --------
 752
 753             >>> from dunshire import *
 754             >>> K = NonnegativeOrthant(3)
 755             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 756             >>> e1 = [1,2,3]
 757             >>> e2 = [1,1,1]
 758             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 759             >>> print(SLG._h())
 760             [0.0000000]
 761             [0.0000000]
 762             [0.0000000]
 763             [0.0000000]
 764             [0.0000000]
 765             [0.0000000]
 766             <BLANKLINE>
 767
 768         """
 769
 770         return matrix([self._zero(), self._zero()])
 771
 772
 773     @staticmethod
 774     def b():
 775         """
 776         Return the ``b`` vector used in our CVXOPT construction.
 777
 778         The vector ``b`` appears on the right-hand side of :math:`Ax =
 779         b` in the statement of the CVXOPT conelp program.
 780
 781         This method is static because the dimensions and entries of
 782         ``b`` are known beforehand, and don't depend on any other
 783         properties of the game.
 784
 785         .. warning::
 786
 787             It is not safe to cache any of the matrices passed to
 788             CVXOPT, because it can clobber them.
 789
 790         Returns
 791         -------
 792
 793         matrix
 794             A ``1``-by-``1`` matrix containing a single entry ``1``.
 795
 796         Examples
 797         --------
 798
 799             >>> from dunshire import *
 800             >>> K = NonnegativeOrthant(3)
 801             >>> L = [[4,5,6],[7,8,9],[10,11,12]]
 802             >>> e1 = [1,2,3]
 803             >>> e2 = [1,1,1]
 804             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 805             >>> print(SLG.b())
 806             [1.0000000]
 807             <BLANKLINE>
 808
 809         """
 810         return matrix([1], tc='d')
 811
 812
 813     def player1_start(self):
 814         """
 815         Return a feasible starting point for player one.
 816
 817         This starting point is for the CVXOPT formulation and not for
 818         the original game. The basic premise is that if you normalize
 819         :meth:`e2`, then you get a point in :meth:`K` that makes a unit
 820         inner product with :meth:`e2`. We then get to choose the primal
 821         objective function value such that the constraint involving
 822         :meth:`L` is satisfied.
 823         """
 824         p = self.e2() / (norm(self.e2()) ** 2)
 825         dist = self.K().ball_radius(self.e1())
 826         nu = - self._L_specnorm()/(dist*norm(self.e2()))
 827         x = matrix([nu, p], (self.dimension() + 1, 1))
 828         s = - self._G()*x
 829
 830         return {'x': x, 's': s}
 831
 832
 833     def player2_start(self):
 834         """
 835         Return a feasible starting point for player two.
 836         """
 837         q = self.e1() / (norm(self.e1()) ** 2)
 838         dist = self.K().ball_radius(self.e2())
 839         omega = self._L_specnorm()/(dist*norm(self.e1()))
 840         y = matrix([omega])
 841         z2 = q
 842         z1 = y*self.e2() - self.L().trans()*z2
 843         z = matrix([z1, z2], (self.dimension()*2, 1))
 844
 845         return {'y': y, 'z': z}
 846
 847
 848     def _L_specnorm(self):
 849         """
 850         Compute the spectral norm of ``L`` and cache it.
 851         """
 852         if self._L_specnorm_value is None:
 853             self._L_specnorm_value = specnorm(self.L())
 854         return self._L_specnorm_value
 855
 856     def solution(self):
 857         """
 858         Solve this linear game and return a :class:`Solution`.
 859
 860         Returns
 861         -------
 862
 863         :class:`Solution`
 864             A :class:`Solution` object describing the game's value and
 865             the optimal strategies of both players.
 866
 867         Raises
 868         ------
 869         GameUnsolvableException
 870             If the game could not be solved (if an optimal solution to its
 871             associated cone program was not found).
 872
 873         PoorScalingException
 874             If the game could not be solved because CVXOPT crashed while
 875             trying to take the square root of a negative number.
 876
 877         Examples
 878         --------
 879
 880         This example is computed in Gowda and Ravindran in the section
 881         "The value of a Z-transformation"::
 882
 883             >>> from dunshire import *
 884             >>> K = NonnegativeOrthant(3)
 885             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 886             >>> e1 = [1,1,1]
 887             >>> e2 = [1,1,1]
 888             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 889             >>> print(SLG.solution())
 890             Game value: -6.172...
 891             Player 1 optimal:
 892               [0.551...]
 893               [0.000...]
 894               [0.448...]
 895             Player 2 optimal:
 896               [0.448...]
 897               [0.000...]
 898               [0.551...]
 899
 900         The value of the following game can be computed using the fact
 901         that the identity is invertible::
 902
 903             >>> from dunshire import *
 904             >>> K = NonnegativeOrthant(3)
 905             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 906             >>> e1 = [1,2,3]
 907             >>> e2 = [4,5,6]
 908             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 909             >>> print(SLG.solution())
 910             Game value: 0.031...
 911             Player 1 optimal:
 912               [0.031...]
 913               [0.062...]
 914               [0.093...]
 915             Player 2 optimal:
 916               [0.125...]
 917               [0.156...]
 918               [0.187...]
 919
 920         This is another Gowda/Ravindran example that is supposed to have
 921         a negative game value::
 922
 923             >>> from dunshire import *
 924             >>> from dunshire.options import ABS_TOL
 925             >>> L = [[1, -2], [-2, 1]]
 926             >>> K = NonnegativeOrthant(2)
 927             >>> e1 = [1, 1]
 928             >>> e2 = e1
 929             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 930             >>> SLG.solution().game_value() < -ABS_TOL
 931             True
 932
 933         The following two games are problematic numerically, but we
 934         should be able to solve them::
 935
 936             >>> from dunshire import *
 937             >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
 938             ...      [ 1.30481749924621448500, 1.65278664543326403447]]
 939             >>> K = NonnegativeOrthant(2)
 940             >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
 941             >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
 942             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 943             >>> print(SLG.solution())
 944             Game value: 18.767...
 945             Player 1 optimal:
 946               [0.000...]
 947               [9.766...]
 948             Player 2 optimal:
 949               [1.047...]
 950               [0.000...]
 951
 952         ::
 953
 954             >>> from dunshire import *
 955             >>> L = [[1.54159395026049472754, 2.21344728574316684799],
 956             ...      [1.33147433507846657541, 1.17913616272988108769]]
 957             >>> K = NonnegativeOrthant(2)
 958             >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
 959             >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
 960             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 961             >>> print(SLG.solution())
 962             Game value: 24.614...
 963             Player 1 optimal:
 964               [6.371...]
 965               [0.000...]
 966             Player 2 optimal:
 967               [2.506...]
 968               [0.000...]
 969
 970         """
 971         try:
 972             opts = {'show_progress': False}
 973             soln_dict = solvers.conelp(self._c(),
 974                                        self._G(),
 975                                        self._h(),
 976                                        self.C().cvxopt_dims(),
 977                                        self.A(),
 978                                        self.b(),
 979                                        primalstart=self.player1_start(),
 980                                        options=opts)
 981         except ValueError as error:
 982             if str(error) == 'math domain error':
 983                 # Oops, CVXOPT tried to take the square root of a
 984                 # negative number. Report some details about the game
 985                 # rather than just the underlying CVXOPT crash.
 986                 printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
 987                 raise PoorScalingException(self)
 988             else:
 989                 raise error
 990
 991         # The optimal strategies are named ``p`` and ``q`` in the
 992         # background documentation, and we need to extract them from
 993         # the CVXOPT ``x`` and ``z`` variables. The objective values
 994         # :math:`nu` and :math:`omega` can also be found in the CVXOPT
 995         # ``x`` and ``y`` variables; however, they're stored
 996         # conveniently as separate entries in the solution dictionary.
 997         p1_value = -soln_dict['primal objective']
 998         p2_value = -soln_dict['dual objective']
 999         p1_optimal = soln_dict['x'][1:]
1000         p2_optimal = soln_dict['z'][self.dimension():]
1001
1002         # The "status" field contains "optimal" if everything went
1003         # according to plan. Other possible values are "primal
1004         # infeasible", "dual infeasible", "unknown", all of which mean
1005         # we didn't get a solution.
1006         #
1007         # The "infeasible" ones are the worst, since they indicate
1008         # that CVXOPT is convinced the problem is infeasible (and that
1009         # cannot happen).
1010         if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
1011             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
1012             raise GameUnsolvableException(self, soln_dict)
1013
1014         # The "optimal" and "unknown" results, we actually treat the
1015         # same. Even if CVXOPT bails out due to numerical difficulty,
1016         # it will have some candidate points in mind. If those
1017         # candidates are good enough, we take them. We do the same
1018         # check (perhaps pointlessly so) for "optimal" results.
1019         #
1020         # First we check that the primal/dual objective values are
1021         # close enough (one could be low by ABS_TOL, the other high by
1022         # it) because otherwise CVXOPT might return "unknown" and give
1023         # us two points in the cone that are nowhere near optimal.
1024         if abs(p1_value - p2_value) > 2*options.ABS_TOL:
1025             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
1026             raise GameUnsolvableException(self, soln_dict)
1027
1028         # And we also check that the points it gave us belong to the
1029         # cone, just in case...
1030         if (p1_optimal not in self._K) or (p2_optimal not in self._K):
1031             printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
1032             raise GameUnsolvableException(self, soln_dict)
1033
1034         # For the game value, we could use any of:
1035         #
1036         #   * p1_value
1037         #   * p2_value
1038         #   * (p1_value + p2_value)/2
1039         #   * the game payoff
1040         #
1041         # We want the game value to be the payoff, however, so it
1042         # makes the most sense to just use that, even if it means we
1043         # can't test the fact that p1_value/p2_value are close to the
1044         # payoff.
1045         payoff = self.payoff(p1_optimal, p2_optimal)
1046         return Solution(payoff, p1_optimal, p2_optimal)
1047
1048
1049     def condition(self):
1050         r"""
1051         Return the condition number of this game.
1052
1053         In the CVXOPT construction of this game, two matrices ``G`` and
1054         ``A`` appear. When those matrices are nasty, numerical problems
1055         can show up. We define the condition number of this game to be
1056         the average of the condition numbers of ``G`` and ``A`` in the
1057         CVXOPT construction. If the condition number of this game is
1058         high, then you can expect numerical difficulty (such as
1059         :class:`PoorScalingException`).
1060
1061         Returns
1062         -------
1063
1064         float
1065             A real number greater than or equal to one that measures how
1066             bad this game is numerically.
1067
1068         Examples
1069         --------
1070
1071         >>> from dunshire import *
1072         >>> K = NonnegativeOrthant(1)
1073         >>> L = [[1]]
1074         >>> e1 = [1]
1075         >>> e2 = e1
1076         >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1077         >>> actual = SLG.condition()
1078         >>> expected = 1.8090169943749477
1079         >>> abs(actual - expected) < options.ABS_TOL
1080         True
1081
1082         """
1083         return (condition_number(self._G()) + condition_number(self.A()))/2
1084
1085
1086     def dual(self):
1087         r"""
1088         Return the dual game to this game.
1089
1090         If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
1091         then its dual is :math:`G^{*} =
1092         \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
1093         is symmetric, :math:`K^{*} = K`.
1094
1095         Examples
1096         --------
1097
1098             >>> from dunshire import *
1099             >>> K = NonnegativeOrthant(3)
1100             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
1101             >>> e1 = [1,1,1]
1102             >>> e2 = [1,2,3]
1103             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
1104             >>> print(SLG.dual())
1105             The linear game (L, K, e1, e2) where
1106               L = [  1  -1 -12]
1107                   [ -5   2 -15]
1108                   [-15  -3   1],
1109               K = Nonnegative orthant in the real 3-space,
1110               e1 = [ 1]
1111                    [ 2]
1112                    [ 3],
1113               e2 = [ 1]
1114                    [ 1]
1115                    [ 1],
1116               Condition((L, K, e1, e2)) = 44.476...
1117
1118         """
1119         # We pass ``self.L()`` right back into the constructor, because
1120         # it will be transposed there. And keep in mind that ``self._K``
1121         # is its own dual.
1122         return SymmetricLinearGame(self.L(),
1123                                    self.K(),
1124                                    self.e2(),
1125                                    self.e1())