doc/source/background.rst

   1 Background
   2 ----------
   3
   4 A linear game is a generalization of a two-person zero-sum matrix game
   5 [Karlin]_. Classically, such a game involves a matrix :math:`A \in
   6 \mathbb{R}^{n \times n}` and a set (the unit simplex) of "strategies"
   7 :math:`\Delta = \operatorname{conv}\left( \left\lbrace e_{1}, e_{2},
   8 \ldots, e_{n} \right\} \right)` from which two players are free to
   9 choose. If the players choose :math:`x,y \in \Delta` respectively,
  10 then the game is played by evaluating :math:`y^{T}Ax` as the "payoff"
  11 to the first player. His payoff comes from the second player, so that
  12 their total sums to zero.
  13
  14 Each player will try to maximize his payoff in this scenario,
  15 or—what is equivalent—try to minimize the payoff of his
  16 opponent. In fact, the existence of optimal strategies is
  17 guaranteed [Karlin]_ for both players. The *value* of the
  18 matrix game :math:`A` is the payoff resulting from optimal play,
  19
  20 .. math::
  21   v\left(A\right)
  22   =
  23   \underset{x \in \Delta}{\max}\
  24   \underset{y\in \Delta}{\min}
  25   \left( y^{T}Ax \right)
  26   =
  27   \underset{y \in \Delta}{\min}\
  28   \underset{x \in \Delta}{\max}
  29   \left( y^{T}Ax \right).
  30
  31 The payoff to the first player in this case is
  32 :math:`v\left(A\right)`. Corresponding to :math:`v\left(A\right)` is an
  33 optimal strategy pair :math:`\left(\bar{x}, \bar{y}\right) \in \Delta
  34 \times \Delta` such that
  35
  36 .. math::
  37   \bar{y}^{T}Ax
  38   \le
  39   v\left(A\right)
  40   =
  41   \bar{y}^{T}A\bar{x}
  42   \le
  43   y^{T}A\bar{x}
  44   \text{ for all } \left(x,y\right) \in \Delta \times \Delta.
  45
  46 The relationship between :math:`A`, :math:`\bar{x}`, :math:`\bar{y}`,
  47 and :math:`v\left(A\right)` has been studied extensively [Kaplansky]_
  48 [Raghavan]_. Gowda and Ravindran [GowdaRav]_ were motivated by these
  49 results to ask if the matrix :math:`A` can be replaced by a linear
  50 transformation :math:`L`, and whether or not the unit simplex
  51 :math:`\Delta` can be replaced by a more general set—a base of a
  52 symmetric cone. In fact, one can go all the way to asymmetric (but
  53 still proper) cones. But, since Dunshire can only handle the symmetric
  54 case, we will pretend from now on that our cones need to be
  55 symmetric. This simplifies some definitions.
  56
  57 What is a linear game?
  58 ^^^^^^^^^^^^^^^^^^^^^^
  59
  60 In the classical setting, the interpretation of the strategies as
  61 probabilities results in a strategy set :math:`\Delta \subseteq
  62 \mathbb{R}^{n}_{+}` that is compact, convex, and does not contain the
  63 origin. Moreover, any nonzero :math:`x \in \mathbb{R}^{n}_{+}` is a
  64 unique positive multiple :math:`x = \lambda b` of some :math:`b \in
  65 \Delta`. Several existence and uniqueness results are predicated on
  66 those properties.
  67
  68 **Definition.** Suppose that :math:`K` is a cone and :math:`B
  69 \subseteq K` does not contain the origin. If any nonzero :math:`x \in
  70 K` can be uniquely represented :math:`x = \lambda b` where
  71 :math:`\lambda > 0` and :math:`b \in B`, then :math:`B` is a *base*
  72 of :math:`K`.
  73
  74 The set :math:`\Delta` is a compact convex base for the proper cone
  75 :math:`\mathbb{R}^{n}_{+}`. Every :math:`x \in \Delta` also has
  76 entries that sum to unity, which can be abbreviated by the condition
  77 :math:`\left\langle x,\mathbf{1} \right\rangle = 1` where
  78 :math:`\mathbf{1} = \left(1,1,\ldots,1\right)^{T}` happens to lie in
  79 the interior of :math:`\mathbb{R}^{n}_{+}`. In fact, the two
  80 conditions :math:`x \in \mathbb{R}^{n}_{+}` and :math:`\left\langle
  81 x,\mathbf{1} \right\rangle = 1` define :math:`\Delta`. This is no
  82 coincidence; whenever :math:`K` is a symmetric cone and :math:`e_{2}
  83 \in \operatorname{int}\left(K\right)`, the set :math:`\left\lbrace x
  84 \in K \ \middle|\ \left\langle x,e_{2} \right\rangle = 1
  85 \right\rbrace` is a compact convex base of :math:`K`. This motivates a
  86 generalization where :math:`\mathbb{R}^{n}_{+}` is replaced by a
  87 symmetric cone.
  88
  89 **Definition.** Let :math:`V` be a finite-dimensional real Hilbert
  90 space. A *linear game* in :math:`V` is a tuple
  91 :math:`\left(L,K,e_{1},e_{2}\right)` where :math:`L : V \rightarrow V`
  92 is linear, the set :math:`K` is a symmetric cone in :math:`V`, and the
  93 points :math:`e_{1}` and :math:`e_{2}` belong to
  94 :math:`\operatorname{int}\left(K\right)`.
  95
  96 **Definition.**  The strategy sets for our linear game are
  97
  98 .. math::
  99   \begin{aligned}
 100     \Delta_{1}\left(L,K,e_{1},e_{2}\right) &=
 101       \left\lbrace
 102         x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
 103       \right\rbrace\\
 104     \Delta_{2}\left(L,K,e_{1},e_{2}\right) &=
 105       \left\lbrace
 106         y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
 107       \right\rbrace.
 108   \end{aligned}
 109
 110 Since :math:`e_{1},e_{2} \in \operatorname{int}\left(K\right)`, these
 111 are bases for :math:`K`. We will usually omit the arguments and write
 112 :math:`\Delta_{i}` to mean :math:`\Delta_{i}\left(L,K,e_{1},e_{2}\right)`.
 113
 114 To play the game :math:`\left(L,K,e_{1},e_{2}\right)`, the first
 115 player chooses an :math:`x \in \Delta_{1}`, and the second player
 116 independently chooses a :math:`y \in \Delta_{2}`. This completes the
 117 turn, and the payoffs are determined by applying the payoff operator
 118 :math:`\left(x,y\right) \mapsto \left\langle L\left(x\right), y
 119 \right\rangle`. The payoff to the first player is :math:`\left\langle
 120 L\left(x\right), y \right\rangle`, and since we want the game to be
 121 zero-sum, the payoff to the second player is :math:`-\left\langle
 122 L\left(x\right), y \right\rangle`.
 123
 124 The payoff operator is continuous in both arguments because it is
 125 bilinear and the ambient space is finite-dimensional. We constructed
 126 the strategy sets :math:`\Delta_{1}` and :math:`\Delta_{2}` to be
 127 compact and convex; as a result, Karlin's [Karlin]_ general min-max
 128 Theorem 1.5.1, guarantees the existence of optimal strategies for both
 129 players.
 130
 131 **Definition.** A pair :math:`\left(\bar{x},\bar{y}\right) \in
 132 \Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game
 133 :math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point
 134 inequality*,
 135
 136 .. math::
 137   \left\langle L\left(x\right),\bar{y} \right\rangle
 138   \le
 139   \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle
 140   \le
 141   \left\langle L\left(\bar{x}\right),y \right\rangle
 142   \text{ for all }
 143   \left(x,y\right) \in \Delta_{1} \times \Delta_{2}.
 144
 145 At an optimal pair, neither player can unilaterally increase his
 146 payoff by changing his strategy. The value :math:`\left\langle L
 147 \left( \bar{x} \right) , \bar{y} \right\rangle` is unique (by the same
 148 min-max theorem); it is shared by all optimal pairs. There exists at
 149 least one optimal pair :math:`\left(\bar{x},\bar{y}\right)` of the
 150 game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is
 151 :math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle
 152 L\left(\bar{x}\right), \bar{y} \right\rangle`.
 153
 154 Thanks to Karlin [Karlin]_, we have an equivalent characterization of
 155 a game's value that does not require us to have a particular optimal
 156 pair in mind,
 157
 158 .. math::
 159   v\left( L,K,e_{1},e_{2} \right)
 160   =
 161   \underset{x \in \Delta_{1}}{\max}\
 162   \underset{y\in \Delta_{2}}{\min}\
 163   \left\langle L\left(x\right),y \right\rangle
 164   =
 165   \underset{y\in \Delta_{2}}{\min}\
 166   \underset{x \in \Delta_{1}}{\max}\
 167   \left\langle L\left(x\right),y \right\rangle.
 168
 169 Linear games reduce to two-person zero-sum matrix games in the
 170 right setting.
 171
 172 **Example.** If :math:`K = \mathbb{R}^{n}_{+}` in :math:`V =
 173 \mathbb{R}^{n}` and :math:`e_{1} = e_{2} =
 174 \left(1,1,\ldots,1\right)^{T} \in \operatorname{int}\left(K\right)`,
 175 then :math:`\Delta_{1} = \Delta_{2} = \Delta`. For any :math:`L \in
 176 \mathbb{R}^{n \times n}`, the linear game :math:`\left(
 177 L,K,e_{2},e_{2} \right)` is a two-person zero-sum matrix game. Its
 178 payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is
 179
 180 .. math::
 181   v\left( L,K,e_{1},e_{2} \right)
 182   =
 183   \underset{x \in \Delta}{\max}\
 184   \underset{y\in \Delta}{\min}\
 185   \left( y^{T}Lx \right)
 186   =
 187   \underset{y\in \Delta}{\min}\
 188   \underset{x \in \Delta}{\max}\
 189   \left( y^{T}Lx \right).
 190
 191
 192 Cone program formulation
 193 ^^^^^^^^^^^^^^^^^^^^^^^^
 194
 195 As early as 1947, von Neumann knew [Dantzig]_ that a two-person
 196 zero-sum matrix game could be expressed as a linear program. It turns
 197 out that the two concepts are equivalent, but turning a matrix game
 198 into a linear program is the simpler transformation. Cone programs are
 199 generalizations of linear programs where the cone is allowed to differ
 200 from the nonnegative orthant. We will see that any linear game can be
 201 formulated as a cone program, and if we're lucky, be solved.
 202
 203 Our main tool in formulating our cone program is the following
 204 theorem. It closely mimics a similar result in classical game theory
 205 where the cone is the nonnegative orthant and the result gives rise to
 206 a linear program. The symbols :math:`\preccurlyeq` and
 207 :math:`\succcurlyeq` indicate inequality with respect to the cone
 208 ordering; that is, :math:`x \succcurlyeq y \iff x - y \in K`.
 209
 210 **Theorem.** In the game :math:`\left(L,K,e_{1},e_{2}\right)`, we have
 211 :math:`L^{*}\left( q \right) \preccurlyeq \nu e_{2}` and
 212 :math:`L \left( p \right) \succcurlyeq \nu e_{1}` for
 213 :math:`\nu \in \mathbb{R}` if and only if :math:`\nu` is the
 214 value of the game :math:`\left(L,K,e_{1},e_{2}\right)` and
 215 :math:`\left(p,q\right)` is optimal for it.
 216
 217 The proof of this theorem is not difficult, and the version for
 218 :math:`e_{1} \ne e_{2}` can easily be deduced from the one given by
 219 Gowda and Ravidran [GowdaRav]_. Let us now restate the objectives of
 220 the two players in terms of this theorem. Player one would like to,
 221
 222 .. math::
 223   \begin{aligned}
 224     &\text{ maximize }  &\nu                &\\
 225     &\text{ subject to }& p                 &\in K&\\
 226     &                   & \nu               &\in \mathbb{R}&\\
 227     &                   & \left\langle p,e_{2} \right\rangle &= 1&\\
 228     &                   & L\left(p\right)   &\succcurlyeq \nu e_{1}.&
 229   \end{aligned}
 230
 231 Player two, on the other hand, would like to,
 232
 233 .. math::
 234
 235   \begin{aligned}
 236     &\text{ minimize }  &\omega                &\\
 237     &\text{ subject to }& q                    &\in K&\\
 238     &                   & \omega               &\in \mathbb{R}&\\
 239     &                   & \left\langle q,e_{1} \right\rangle &= 1&\\
 240     &                   & L^{*}\left(q\right)  &\preccurlyeq \omega e_{2}.&
 241   \end{aligned}
 242
 243 The `CVXOPT <http://cvxopt.org/>`_ library can solve symmetric cone
 244 programs in the following primal/dual format:
 245
 246 .. math::
 247   \text{primal} =
 248     \left\{
 249     \begin{aligned}
 250       \text{ minimize }   & c^{T}x     \\
 251       \text{ subject to } & Gx + s = h \\
 252                           & Ax     = b \\
 253                           & s \in C,
 254     \end{aligned}
 255   \right.
 256
 257 .. math::
 258   \text{dual}
 259   =
 260   \left\{
 261     \begin{aligned}
 262       \text{ maximize }   & -h^{T}z - b^{T}y        \\
 263       \text{ subject to } & G^{T}z + A^{T}y + c = 0 \\
 264                           & z \in C.
 265     \end{aligned}
 266   \right.
 267
 268 We will now pull a rabbit out of the hat, and choose the
 269 matrices/vectors in these primal/dual programs so as to reconstruct
 270 the goals of the two players. Let,
 271
 272 .. math::
 273   \begin{aligned}
 274     C &= K \times K\\
 275     x &= \begin{bmatrix} \nu \\ p \end{bmatrix} \\
 276     y &= \begin{bmatrix} \omega \end{bmatrix} \\
 277     b &= \begin{bmatrix} 1 \end{bmatrix} \\
 278     h &= 0 \\
 279     c &= \begin{bmatrix} -1 \\ 0 \end{bmatrix} \\
 280     z &= \begin{bmatrix} z_{1} \\ q \end{bmatrix} \\
 281     A &= \begin{bmatrix} 0 & e_{2}^{T} \end{bmatrix} \\
 282     G &= \begin{bmatrix}
 283            0 & -I\\
 284            e_{1} & -L
 285          \end{bmatrix}.
 286   \end{aligned}
 287
 288 Substituting these values into the primal/dual CVXOPT cone programs
 289 recovers the objectives of player one (primal) and player two (dual)
 290 exactly. Therefore, we can use this formulation to solve a linear
 291 game, and that is precisely what Dunshire does.