From 08abee864006192c364c25f22c3755e89e310b9b Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sat, 15 Oct 2016 18:53:59 -0400 Subject: [PATCH] Switch to Mathjax for the docs and finish the "Background" section. --- doc/README.rst | 127 ++++++++++++++++++++++++++++++++++++++++----- doc/source/conf.py | 2 +- 2 files changed, 116 insertions(+), 13 deletions(-) diff --git a/doc/README.rst b/doc/README.rst index 71876c6..12eaf7a 100644 --- a/doc/README.rst +++ b/doc/README.rst @@ -140,20 +140,20 @@ matrix game :math:`A` is the payoff resulting from optimal play, 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 @@ -238,28 +238,28 @@ compact and convex; as a result, Karlin's [Karlin]_ general min-max 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 @@ -299,9 +299,112 @@ payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is \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 ` 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. diff --git a/doc/source/conf.py b/doc/source/conf.py index 63ffa74..d675255 100644 --- a/doc/source/conf.py +++ b/doc/source/conf.py @@ -17,8 +17,8 @@ extensions = [ 'sphinx.ext.autodoc', 'sphinx.ext.autosummary', 'sphinx.ext.doctest', + 'sphinx.ext.mathjax', 'sphinx.ext.napoleon', - 'sphinx.ext.pngmath', 'sphinx.ext.viewcode', ] -- 2.44.2