Rename "xi" and "gamma" to "p" and "q" to avoid name clashes with CVXOPT.

diff --git a/TODO b/TODO
index 6b2a90a76c1d059ed3fbc2ddd35491650996f9e0..b0b503bc4465b5048b83ffbe91b375ea73ac6e09 100644 (file)
--- 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 7b3bf8ce6dec7caaefb2ce87d3ca6516c3ed9fe2..1a1605997b977824439c8db6c4d90316452b5eac 100644 (file)
--- 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 <http://cvxopt.org/>` library can solve symmetric cone
+The `CVXOPT <http://cvxopt.org/>`_ 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 92a3ffe7b6f684ea134ff88bdf08d745ae7a4944..43fa007c61077c90ef627e9738afbaa09dcde9c1 100644 (file)
--- 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:]