bastard of the two: the cones are symmetric, but the players get to
choose two interior points.
+In this game, we have two players who are competing for a "payoff."
+There is a symmetric cone :math:`K`, a linear transformation :math:`L`
+on the space in which :math:`K` lives, and two points :math:`e_{1}`
+and :math:`e_{2}` in the interior of :math:`K`. The players make their
+"moves" by choosing points from two strategy sets. Player one chooses
+an :math:`\bar{x}` from
+
+.. math::
+ \Delta_{1} =
+ \left\lbrace
+ x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
+ \right\rbrace
+
+and player two chooses a :math:`\bar{y}` from
+
+.. math::
+ \Delta_{2} &=
+ \left\lbrace
+ y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
+ \right\rbrace.
+
+That ends the turn, and player one is paid :math:`\left\langle
+L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's
+pocket. As is usual to assume in game theory, we suppose that player
+one wants to maximize his worst-case payoff, and that player two wants
+to minimize his worst-case *payout*. In other words, player one wants
+to solve the optimization problem,
+
+.. math::
+ \text{find }
+ \underset{x \in \Delta_{1}}{\max}\
+ \underset{y\in \Delta_{2}}{\min}\
+ \left\langle L\left(x\right),y \right\rangle
+
+while player two tries to (simultaneously) solve a similar problem,
+
+.. math::
+ \text{find }
+ \underset{y\in \Delta_{2}}{\min}\
+ \underset{x \in \Delta_{1}}{\max}\
+ \left\langle L\left(x\right),y \right\rangle.
+
+There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that
+solves these problems optimally, and Dunshire can find it. The optimal
+payoff, called *the value of the game*, is unique. At the moment, the
+symmetric cone :math:`K` can be either the nonnegative orthant or the
+Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of
+the simplest possible examples, showing off the ability to solve a
+game over both of those cones.
+
+First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`:
+
+.. doctest::
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(2)
+ >>> L = [[1,0],[0,1]]
+ >>> e1 = [1,1]
+ >>> e2 = e1
+ >>> G = SymmetricLinearGame(L,K,e1,e2)
+ >>> print(G.solution())
+ Game value: 0.5000000
+ Player 1 optimal:
+ [0.5000000]
+ [0.5000000]
+ Player 2 optimal:
+ [0.5000000]
+ [0.5000000]
+
+Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`:
+
+.. doctest::
+
+ >>> from dunshire import *
+ >>> K = IceCream(2)
+ >>> L = [[1,0],[0,1]]
+ >>> e1 = [1,1]
+ >>> e2 = e1
+ >>> G = SymmetricLinearGame(L,K,e1,e2)
+ >>> print(G.solution())
+ Game value: 0.5000000
+ Player 1 optimal:
+ [0.8347039]
+ [0.1652961]
+ Player 2 optimal:
+ [0.5000000]
+ [0.5000000]
+
+Note that these solutions are not unique, although the game values are.
+
Requirements
------------
Background
----------
-A linear game is a generalization of a two-person zero-sum matrix
-game~\cite{karlin, parthasarathy-raghavan,
-von_neumann-morgenstern}. Classically, such a game involves a matrix
-:math:`A \in \mathbb{R}^{n \times n}` and a set (the unit simplex) of
-"strategies" :math:`\Delta = \operatorname{conv}\left(
-\left\lbrace e_{1}, e_{2}, \ldots, e_{n} \right\} \right)` from which two
-players are free to choose. If the players choose :math:`x,y \in \Delta`
-respectively, then the game is played by evaluating :math:`y^{T}Ax` as the
-"payoff" to the first player. His payoff comes from the second
-player, so that their total sums to zero.
+A linear game is a generalization of a two-person zero-sum matrix game
+[Karlin]_. Classically, such a game involves a matrix :math:`A \in
+\mathbb{R}^{n \times n}` and a set (the unit simplex) of "strategies"
+:math:`\Delta = \operatorname{conv}\left( \left\lbrace e_{1}, e_{2},
+\ldots, e_{n} \right\} \right)` from which two players are free to
+choose. If the players choose :math:`x,y \in \Delta` respectively,
+then the game is played by evaluating :math:`y^{T}Ax` as the "payoff"
+to the first player. His payoff comes from the second player, so that
+their total sums to zero.
Each player will try to maximize his payoff in this scenario,
or—what is equivalent—try to minimize the payoff of his
The payoff to the first player in this case is
:math:`v\left(A\right)`. Corresponding to :math:`v\left(A\right)` is an
-optimal strategy pair :math:`\left(\bar{x}, \bar{y}\right) \in \Delta
+optimal strategy pair :math:`\left(\xi, \gamma\right) \in \Delta
\times \Delta` such that
.. math::
- \bar{y}^{T}Ax
+ \gamma^{T}Ax
\le
v\left(A\right)
=
- \bar{y}^{T}A\bar{x}
+ \gamma^{T}A\xi
\le
- y^{T}A\bar{x}
+ y^{T}A\xi
\text{ for all } \left(x,y\right) \in \Delta \times \Delta.
-The relationship between :math:`A`, :math:`\bar{x}`, :math:`\bar{y}`,
+The relationship between :math:`A`, :math:`\xi`, :math:`\gamma`,
and :math:`v\left(A\right)` has been studied extensively [Kaplansky]_
[Raghavan]_. Gowda and Ravindran [GowdaRav]_ were motivated by these
results to ask if the matrix :math:`A` can be replaced by a linear
symmetric. This simplifies some definitions.
What is a linear game?
-----------------------
+~~~~~~~~~~~~~~~~~~~~~~
In the classical setting, the interpretation of the strategies as
probabilities results in a strategy set :math:`\Delta \subseteq
Theorem 1.5.1, guarantees the existence of optimal strategies for both
players.
-**Definition.** A pair :math:`\left(\bar{x},\bar{y}\right) \in
+**Definition.** A pair :math:`\left(\xi,\gamma\right) \in
\Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game
:math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point
inequality*,
.. math::
- \left\langle L\left(x\right),\bar{y} \right\rangle
+ \left\langle L\left(x\right),\gamma \right\rangle
\le
- \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle
+ \left\langle L\left( \xi\right), \gamma \right\rangle
\le
- \left\langle L\left(\bar{x}\right),y \right\rangle
+ \left\langle L\left(\xi\right),y \right\rangle
\text{ for all }
\left(x,y\right) \in \Delta_{1} \times \Delta_{2}.
At an optimal pair, neither player can unilaterally increase his
payoff by changing his strategy. The value :math:`\left\langle L
-\left( \bar{x} \right) , \bar{y} \right\rangle` is unique (by the same
+\left( \xi \right) , \gamma \right\rangle` is unique (by the same
min-max theorem); it is shared by all optimal pairs. There exists at
-least one optimal pair :math:`\left(\bar{x},\bar{y}\right)` of the
+least one optimal pair :math:`\left(\xi,\gamma\right)` of the
game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is
:math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle
-L\left(\bar{x}\right), \bar{y} \right\rangle`.
+L\left(\xi\right), \gamma \right\rangle`.
Thanks to Karlin [Karlin]_, we have an equivalent characterization of
a game's value that does not require us to have a particular optimal
\left( y^{T}Lx \right).
+Cone program formulation
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+As early as 1947, von Neumann knew [Dantzig]_ that a two-person
+zero-sum matrix game could be expressed as a linear program. It turns
+out that the two concepts are equivalent, but turning a matrix game
+into a linear program is the simpler transformation. Cone programs are
+generalizations of linear programs where the cone is allowed to differ
+from the nonnegative orthant. We will see that any linear game can be
+formulated as a cone program, and if we're lucky, be solved.
+
+Our main tool in formulating our cone program is the following
+theorem. It closely mimics a similar result in classical game theory
+where the cone is the nonnegative orthant and the result gives rise to
+a linear program. The symbols :math:`\preccurlyeq` and
+:math:`\succcurlyeq` indicate inequality with respect to the cone
+ordering; that is, :math:`x \succcurlyeq y \iff x - y \in K`.
+
+**Theorem.** In the game :math:`\left(L,K,e_{1},e_{2}\right)`, we have
+:math:`L^{*}\left( \gamma \right) \preccurlyeq \nu e_{2}` and
+:math:`L \left( \xi \right) \succcurlyeq \nu e_{1}` for
+:math:`\nu \in \mathbb{R}` if and only if :math:`\nu` is the
+value of the game :math:`\left(L,K,e_{1},e_{2}\right)` and
+:math:`\left(\xi,\gamma\right)` is optimal for it.
+
+The proof of this theorem is not difficult, and the version for
+:math:`e_{1} \ne e_{2}` can easily be deduced from the one given by
+Gowda and Ravidran [GowdaRav]_. Let us now restate the objectives of
+the two players in terms of this theorem. Player one would like to,
+
+.. math::
+ \begin{aligned}
+ &\text{ maximize } &\nu &\\
+ &\text{ subject to }& \xi &\in K&\\
+ & & \left\langle \xi,e_{1} \right\rangle &= 1&\\
+ & & \nu &\in \mathbb{R}&\\
+ & & L\left(\xi\right) &\succcurlyeq \nu e_{1}.&
+ \end{aligned}
+
+Player two, on the other hand, would like to,
+
+.. math::
+
+ \begin{aligned}
+ &\text{ minimize } &\omega &\\
+ &\text{ subject to }& \gamma &\in K&\\
+ & & \left\langle \gamma,e_{2} \right\rangle &= 1&\\
+ & & \omega &\in \mathbb{R}&\\
+ & & L^{*}\left(\gamma\right) &\preccurlyeq \omega e_{2}.&
+ \end{aligned}
+
+The `CVXOPT <http://cvxopt.org/>` library can solve symmetric cone
+programs in the following primal/dual format:
+
+.. math::
+ \text{primal} =
+ \left\{
+ \begin{aligned}
+ \text{ minimize } & c^{T}x \\
+ \text{ subject to } & Gx + s = h \\
+ & Ax = b \\
+ & s \in C,
+ \end{aligned}
+ \right.
+
+.. math::
+ \text{dual}
+ =
+ \left\{
+ \begin{aligned}
+ \text{ maximize } & -h^{T}z - b^{T}y \\
+ \text{ subject to } & G^{T}z + A^{T}y + c = 0 \\
+ & z \in C.
+ \end{aligned}
+ \right.
+
+We will now pull a rabbit out of the hat, and choose the
+matrices/vectors in these primal/dual programs so as to reconstruct
+exactly the goals of the two players. Let,
+
+.. math::
+ \begin{aligned}
+ C &= K \times K\\
+ x &= \begin{bmatrix} \nu & \xi \end{bmatrix} \\
+ b &= \begin{bmatrix} 1 \end{bmatrix} \\
+ h &= 0 \\
+ c &= \begin{bmatrix} -1 & 0 \end{bmatrix} \\
+ A &= \begin{bmatrix} 0 & e_{2}^{T} \end{bmatrix} \\
+ G &= \begin{bmatrix}
+ 0 & -I\\
+ e_{1} & -L
+ \end{bmatrix}.
+ \end{aligned}
+
+Substituting these values into the primal/dual CVXOPT cone programs
+recovers the objectives of player one (primal) and player two (dual)
+exactly. Therefore, we can use this formulation to solve a linear
+game, and that is precisely what Dunshire does.
+
+
References
----------
+.. [Dantzig] G. B. Dantzig. Linear Programming and Extensions.
+ Princeton University Press, Princeton, 1963.
+
.. [GowdaRav] M. S. Gowda and G. Ravindran. On the game-theoretic
value of a linear transformation relative to a self-dual cone. Linear
Algebra and its Applications, 469:440-463, 2015.