doc/README.rst

   1 Overview
   2 --------
   3
   4 Dunshire is a `CVXOPT <http://cvxopt.org/>`_-based library for solving
   5 linear (cone) games. The notion of a symmetric linear (cone) game was
   6 introduced by Gowda and Ravindran [GowdaRav]_, and extended by
   7 Orlitzky to asymmetric cones with two interior points.
   8
   9 The state-of-the-art is that only symmetric games can be solved
  10 efficiently, and thus the linear games supported by Dunshire are a
  11 bastard of the two: the cones are symmetric, but the players get to
  12 choose two interior points.
  13
  14 Requirements
  15 ------------
  16
  17 The only requirement is the CVXOPT library, available for most Linux
  18 distributions. Dunshire is targeted at python-3.x, but python-2.x will
  19 probably work too.
  20
  21 Background
  22 ----------
  23
  24 A linear game is a generalization of a two-person zero-sum matrix
  25 game~\cite{karlin, parthasarathy-raghavan,
  26 von_neumann-morgenstern}. Classically, such a game involves a matrix
  27 :math:`A \in \mathbb{R}^{n \times n}` and a set (the unit simplex) of
  28 "strategies" :math:`\Delta = \operatorname{conv}\left(
  29 \left\lbrace e_{1}, e_{2}, \ldots, e_{n} \right\} \right)` from which two
  30 players are free to choose. If the players choose :math:`x,y \in \Delta`
  31 respectively, then the game is played by evaluating :math:`y^{T}Ax` as the
  32 "payoff" to the first player. His payoff comes from the second
  33 player, so that their total sums to zero.
  34
  35 Each player will try to maximize his payoff in this scenario,
  36 or—what is equivalent—try to minimize the payoff of his
  37 opponent. In fact, the existence of optimal strategies is
  38 guaranteed [Karlin]_ for both players. The *value* of the
  39 matrix game :math:`A` is the payoff resulting from optimal play,
  40
  41 .. math::
  42   v\left(A\right)
  43   =
  44   \underset{x \in \Delta}{\max}\
  45   \underset{y\in \Delta}{\min}
  46   \left( y^{T}Ax \right)
  47   =
  48   \underset{y \in \Delta}{\min}\
  49   \underset{x \in \Delta}{\max}
  50   \left( y^{T}Ax \right).
  51
  52 The payoff to the first player in this case is
  53 :math:`v\left(A\right)`. Corresponding to :math:`v\left(A\right)` is an
  54 optimal strategy pair :math:`\left(\bar{x}, \bar{y}\right) \in \Delta
  55 \times \Delta` such that
  56
  57 .. math::
  58   \bar{y}^{T}Ax
  59   \le
  60   v\left(A\right)
  61   =
  62   \bar{y}^{T}A\bar{x}
  63   \le
  64   y^{T}A\bar{x}
  65   \text{ for all } \left(x,y\right) \in \Delta \times \Delta.
  66
  67 The relationship between :math:`A`, :math:`\bar{x}`, :math:`\bar{y}`,
  68 and :math:`v\left(A\right)` has been studied extensively [Kaplansky]_
  69 [Raghavan]_. Gowda and Ravindran [GowdaRav]_ were motivated by these
  70 results to ask if the matrix :math:`A` can be replaced by a linear
  71 transformation :math:`L`, and whether or not the unit simplex
  72 :math:`\Delta` can be replaced by a more general set—a base of a
  73 symmetric cone. In fact, one can go all the way to asymmetric (but
  74 still proper) cones. But, since Dunshire can only handle the symmetric
  75 case, we will pretend from now on that our cones need to be
  76 symmetric. This simplifies some definitions.
  77
  78 What is a linear game?
  79 ----------------------
  80
  81 In the classical setting, the interpretation of the strategies as
  82 probabilities results in a strategy set :math:`\Delta \subseteq
  83 \mathbb{R}^{n}_{+}` that is compact, convex, and does not contain the
  84 origin. Moreover, any nonzero :math:`x \in \mathbb{R}^{n}_{+}` is a
  85 unique positive multiple :math:`x = \lambda b` of some :math:`b \in
  86 \Delta`. Several existence and uniqueness results are predicated on
  87 those properties.
  88
  89 **Definition.** Suppose that :math:`K` is a cone and :math:`B
  90 \subseteq K` does not contain the origin. If any nonzero :math:`x \in
  91 K` can be uniquely represented :math:`x = \lambda b` where
  92 :math:`\lambda > 0` and :math:`b \in B`, then :math:`B` is a *base*
  93 of :math:`K`.
  94
  95 The set :math:`\Delta` is a compact convex base for the proper cone
  96 :math:`\mathbb{R}^{n}_{+}`. Every :math:`x \in \Delta` also has
  97 entries that sum to unity, which can be abbreviated by the condition
  98 :math:`\left\langle x,\mathbf{1} \right\rangle = 1` where
  99 :math:`\mathbf{1} = \left(1,1,\ldots,1\right)^{T}` happens to lie in
 100 the interior of :math:`\mathbb{R}^{n}_{+}`. In fact, the two
 101 conditions :math:`x \in \mathbb{R}^{n}_{+}` and :math:`\left\langle
 102 x,\mathbf{1} \right\rangle = 1` define :math:`\Delta`. This is no
 103 coincidence; whenever :math:`K` is a symmetric cone and :math:`e_{2}
 104 \in \operatorname{int}\left(K\right)`, the set :math:`\left\lbrace x
 105 \in K \ \middle|\ \left\langle x,e_{2} \right\rangle = 1
 106 \right\rbrace` is a compact convex base of :math:`K`. This motivates a
 107 generalization where :math:`\mathbb{R}^{n}_{+}` is replaced by a
 108 symmetric cone.
 109
 110 **Definition.** Let :math:`V` be a finite-dimensional real Hilbert
 111 space. A *linear game* in :math:`V` is a tuple
 112 :math:`\left(L,K,e_{1},e_{2}\right)` where :math:`L : V \rightarrow V`
 113 is linear, the set :math:`K` is a symmetric cone in :math:`V`, and the
 114 points :math:`e_{1}` and :math:`e_{2}` belong to
 115 :math:`\operatorname{int}\left(K\right)`.
 116
 117 **Definition.**  The strategy sets for our linear game are
 118
 119 .. math::
 120   \begin{aligned}
 121     \Delta_{1}\left(L,K,e_{1},e_{2}\right) &=
 122       \left\lbrace
 123         x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
 124       \right\rbrace\\
 125     \Delta_{2}\left(L,K,e_{1},e_{2}\right) &=
 126       \left\lbrace
 127         y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
 128       \right\rbrace.
 129   \end{aligned}
 130
 131 Since :math:`e_{1},e_{2} \in \operatorname{int}\left(K\right)`, these
 132 are bases for :math:`K`. We will usually omit the arguments and write
 133 :math:`\Delta_{i}` to mean :math:`\Delta_{i}\left(L,K,e_{1},e_{2}\right)`.
 134
 135 To play the game :math:`\left(L,K,e_{1},e_{2}\right)`, the first
 136 player chooses an :math:`x \in \Delta_{1}`, and the second player
 137 independently chooses a :math:`y \in \Delta_{2}`. This completes the
 138 turn, and the payoffs are determined by applying the payoff operator
 139 :math:`\left(x,y\right) \mapsto \left\langle L\left(x\right), y
 140 \right\rangle`. The payoff to the first player is :math:`\left\langle
 141 L\left(x\right), y \right\rangle`, and since we want the game to be
 142 zero-sum, the payoff to the second player is :math:`-\left\langle
 143 L\left(x\right), y \right\rangle`.
 144
 145 The payoff operator is continuous in both arguments because it is
 146 bilinear and the ambient space is finite-dimensional. We constructed
 147 the strategy sets :math:`\Delta_{1}` and :math:`\Delta_{2}` to be
 148 compact and convex; as a result, Karlin's [Karlin]_ general min-max
 149 Theorem 1.5.1, guarantees the existence of optimal strategies for both
 150 players.
 151
 152 **Definition.** A pair :math:`\left(\bar{x},\bar{y}\right) \in
 153 \Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game
 154 :math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point
 155 inequality*,
 156
 157 .. math::
 158   \left\langle L\left(x\right),\bar{y} \right\rangle
 159   \le
 160   \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle
 161   \le
 162   \left\langle L\left(\bar{x}\right),y \right\rangle
 163   \text{ for all }
 164   \left(x,y\right) \in \Delta_{1} \times \Delta_{2}.
 165
 166 At an optimal pair, neither player can unilaterally increase his
 167 payoff by changing his strategy. The value :math:`\left\langle L
 168 \left( \bar{x} \right) , \bar{y} \right\rangle` is unique (by the same
 169 min-max theorem); it is shared by all optimal pairs. There exists at
 170 least one optimal pair :math:`\left(\bar{x},\bar{y}\right)` of the
 171 game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is
 172 :math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle
 173 L\left(\bar{x}\right), \bar{y} \right\rangle`.
 174
 175 Thanks to Karlin [Karlin]_, we have an equivalent characterization of
 176 a game's value that does not require us to have a particular optimal
 177 pair in mind,
 178
 179 .. math::
 180   v\left( L,K,e_{1},e_{2} \right)
 181   =
 182   \underset{x \in \Delta_{1}}{\max}\
 183   \underset{y\in \Delta_{2}}{\min}\
 184   \left\langle L\left(x\right),y \right\rangle
 185   =
 186   \underset{y\in \Delta_{2}}{\min}\
 187   \underset{x \in \Delta_{1}}{\max}\
 188   \left\langle L\left(x\right),y \right\rangle.
 189
 190 Linear games reduce to two-person zero-sum matrix games in the
 191 right setting.
 192
 193 **Example.** If :math:`K = \mathbb{R}^{n}_{+}` in :math:`V =
 194 \mathbb{R}^{n}` and :math:`e_{1} = e_{2} =
 195 \left(1,1,\ldots,1\right)^{T} \in \operatorname{int}\left(K\right)`,
 196 then :math:`\Delta_{1} = \Delta_{2} = \Delta`. For any :math:`L \in
 197 \mathbb{R}^{n \times n}`, the linear game :math:`\left(
 198 L,K,e_{2},e_{2} \right)` is a two-person zero-sum matrix game. Its
 199 payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is
 200
 201 .. math::
 202   v\left( L,K,e_{1},e_{2} \right)
 203   =
 204   \underset{x \in \Delta}{\max}\
 205   \underset{y\in \Delta}{\min}\
 206   \left( y^{T}Lx \right)
 207   =
 208   \underset{y\in \Delta}{\min}\
 209   \underset{x \in \Delta}{\max}\
 210   \left( y^{T}Lx \right).
 211
 212
 213 References
 214 ----------
 215
 216 .. [GowdaRav] M. S. Gowda and G. Ravindran. On the game-theoretic
 217    value of a linear transformation relative to a self-dual cone. Linear
 218    Algebra and its Applications, 469:440-463, 2015.
 219
 220 .. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of
 221    games. Annals of Mathematics, 46(3):474-479, 1945.
 222
 223 .. [Karlin] S. Karlin. Mathematical Methods and Theory in Games,
 224    Programming, and Economics. Addison-Wesley Publishing Company,
 225    Reading, Massachusetts, 1959.
 226
 227 .. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear
 228    Algebra and its Applications, 21:35-45, 1978.