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
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.
projects / dunshire.git / commitdiff