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