From fa8fa4d690c5f30f7d5fee1818a9b4c15f52c5ff Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sun, 16 Oct 2016 00:24:05 -0400 Subject: [PATCH] Rename "xi" and "gamma" to "p" and "q" to avoid name clashes with CVXOPT. --- TODO | 9 +++---- doc/source/background.rst | 52 ++++++++++++++++++++------------------- src/dunshire/games.py | 6 +++++ 3 files changed, 36 insertions(+), 31 deletions(-) diff --git a/TODO b/TODO index 6b2a90a..b0b503b 100644 --- a/TODO +++ b/TODO @@ -7,12 +7,9 @@ 4. Make it work on a cartesian product of cones in the wrong order (apply a perm utation before/after). -5. Rename all of my variables so that they don't conflict with CVXOPT. - Maybe x -> xi and y -> gamma in my paper, if that works out. +5. Make sure we have the dimensions of the PSD cone correct. -6. Make sure we have the dimensions of the PSD cone correct. - -7. Come up with a fast heuristic (like making nu huge and taking e1 as +6. Come up with a fast heuristic (like making nu huge and taking e1 as our point) that finds a primal feasible point. -8. Should our one exception also spit out the game parameters? +7. Should our one exception also spit out the game parameters? diff --git a/doc/source/background.rst b/doc/source/background.rst index 7b3bf8c..1a16059 100644 --- a/doc/source/background.rst +++ b/doc/source/background.rst @@ -30,20 +30,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(\xi, \gamma\right) \in \Delta +optimal strategy pair :math:`\left(\bar{x}, \bar{y}\right) \in \Delta \times \Delta` such that .. math:: - \gamma^{T}Ax + \bar{y}^{T}Ax \le v\left(A\right) = - \gamma^{T}A\xi + \bar{y}^{T}A\bar{x} \le - y^{T}A\xi + y^{T}A\bar{x} \text{ for all } \left(x,y\right) \in \Delta \times \Delta. -The relationship between :math:`A`, :math:`\xi`, :math:`\gamma`, +The relationship between :math:`A`, :math:`\bar{x}`, :math:`\bar{y}`, 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 @@ -128,28 +128,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(\xi,\gamma\right) \in +**Definition.** A pair :math:`\left(\bar{x},\bar{y}\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),\gamma \right\rangle + \left\langle L\left(x\right),\bar{y} \right\rangle \le - \left\langle L\left( \xi\right), \gamma \right\rangle + \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle \le - \left\langle L\left(\xi\right),y \right\rangle + \left\langle L\left(\bar{x}\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( \xi \right) , \gamma \right\rangle` is unique (by the same +\left( \bar{x} \right) , \bar{y} \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(\xi,\gamma\right)` of the +least one optimal pair :math:`\left(\bar{x},\bar{y}\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(\xi\right), \gamma \right\rangle`. +L\left(\bar{x}\right), \bar{y} \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 @@ -208,11 +208,11 @@ a linear program. The symbols :math:`\preccurlyeq` and 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:`L^{*}\left( q \right) \preccurlyeq \nu e_{2}` and +:math:`L \left( p \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. +:math:`\left(p,q\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 @@ -222,10 +222,10 @@ 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&\\ + &\text{ subject to }& p &\in K&\\ & & \nu &\in \mathbb{R}&\\ - & & L\left(\xi\right) &\succcurlyeq \nu e_{1}.& + & & \left\langle p,e_{1} \right\rangle &= 1&\\ + & & L\left(p\right) &\succcurlyeq \nu e_{1}.& \end{aligned} Player two, on the other hand, would like to, @@ -234,13 +234,13 @@ Player two, on the other hand, would like to, \begin{aligned} &\text{ minimize } &\omega &\\ - &\text{ subject to }& \gamma &\in K&\\ - & & \left\langle \gamma,e_{2} \right\rangle &= 1&\\ + &\text{ subject to }& q &\in K&\\ & & \omega &\in \mathbb{R}&\\ - & & L^{*}\left(\gamma\right) &\preccurlyeq \omega e_{2}.& + & & \left\langle q,e_{2} \right\rangle &= 1&\\ + & & L^{*}\left(q\right) &\preccurlyeq \omega e_{2}.& \end{aligned} -The `CVXOPT ` library can solve symmetric cone +The `CVXOPT `_ library can solve symmetric cone programs in the following primal/dual format: .. math:: @@ -267,15 +267,17 @@ programs in the following primal/dual format: 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, +the goals of the two players. Let, .. math:: \begin{aligned} C &= K \times K\\ - x &= \begin{bmatrix} \nu & \xi \end{bmatrix} \\ + x &= \begin{bmatrix} \nu \\ p \end{bmatrix} \\ + y &= \begin{bmatrix} \omega \end{bmatrix} \\ b &= \begin{bmatrix} 1 \end{bmatrix} \\ h &= 0 \\ - c &= \begin{bmatrix} -1 & 0 \end{bmatrix} \\ + c &= \begin{bmatrix} -1 \\ 0 \end{bmatrix} \\ + z &= \begin{bmatrix} z_{1} \\ q \end{bmatrix} \\ A &= \begin{bmatrix} 0 & e_{2}^{T} \end{bmatrix} \\ G &= \begin{bmatrix} 0 & -I\\ diff --git a/src/dunshire/games.py b/src/dunshire/games.py index 92a3ffe..43fa007 100644 --- a/src/dunshire/games.py +++ b/src/dunshire/games.py @@ -427,6 +427,12 @@ class SymmetricLinearGame: # what happened. soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b) + # The optimal strategies are named ``p`` and ``q`` in the + # background documentation, and we need to extract them from + # the CVXOPT ``x`` and ``z`` variables. The objective values + # :math:`nu` and :math:`omega` can also be found in the CVXOPT + # ``x`` and ``y`` variables; however, they're stored + # conveniently as separate entries in the solution dictionary. p1_value = -soln_dict['primal objective'] p2_value = -soln_dict['dual objective'] p1_optimal = soln_dict['x'][1:] -- 2.43.2