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 In this game, we have two players who are competing for a "payoff."
  15 There is a symmetric cone :math:`K`, a linear transformation :math:`L`
  16 on the space in which :math:`K` lives, and two points :math:`e_{1}`
  17 and :math:`e_{2}` in the interior of :math:`K`. The players make their
  18 "moves" by choosing points from two strategy sets. Player one chooses
  19 an :math:`\bar{x}` from
  20
  21 .. math::
  22   \Delta_{1} =
  23     \left\lbrace
  24       x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
  25     \right\rbrace
  26
  27 and player two chooses a :math:`\bar{y}` from
  28
  29 .. math::
  30   \Delta_{2} &=
  31     \left\lbrace
  32       y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
  33     \right\rbrace.
  34
  35 That ends the turn, and player one is paid :math:`\left\langle
  36 L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's
  37 pocket. As is usual to assume in game theory, we suppose that player
  38 one wants to maximize his worst-case payoff, and that player two wants
  39 to minimize his worst-case *payout*. In other words, player one wants
  40 to solve the optimization problem,
  41
  42 .. math::
  43   \text{find }
  44   \underset{x \in \Delta_{1}}{\max}\
  45   \underset{y\in \Delta_{2}}{\min}\
  46   \left\langle L\left(x\right),y \right\rangle
  47
  48 while player two tries to (simultaneously) solve a similar problem,
  49
  50 .. math::
  51   \text{find }
  52   \underset{y\in \Delta_{2}}{\min}\
  53   \underset{x \in \Delta_{1}}{\max}\
  54   \left\langle L\left(x\right),y \right\rangle.
  55
  56 There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that
  57 solves these problems optimally, and Dunshire can find it. The optimal
  58 payoff, called *the value of the game*, is unique. At the moment, the
  59 symmetric cone :math:`K` can be either the nonnegative orthant or the
  60 Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of
  61 the simplest possible examples, showing off the ability to solve a
  62 game over both of those cones.
  63
  64 First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`:
  65
  66 >>> from dunshire import *
  67 >>> K = NonnegativeOrthant(2)
  68 >>> L = [[1,0],[0,1]]
  69 >>> e1 = [1,1]
  70 >>> e2 = e1
  71 >>> G = SymmetricLinearGame(L,K,e1,e2)
  72 >>> print(G.solution())
  73 Game value: 0.5000000
  74 Player 1 optimal:
  75   [0.5000000]
  76   [0.5000000]
  77 Player 2 optimal:
  78   [0.5000000]
  79   [0.5000000]
  80
  81 Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`:
  82
  83 >>> from dunshire import *
  84 >>> K = IceCream(2)
  85 >>> L = [[1,0],[0,1]]
  86 >>> e1 = [1,1]
  87 >>> e2 = e1
  88 >>> G = SymmetricLinearGame(L,K,e1,e2)
  89 >>> print(G.solution())
  90 Game value: 0.5000000
  91 Player 1 optimal:
  92   [0.5000000]
  93   [0.5000000]
  94 Player 2 optimal:
  95   [0.5000000]
  96   [0.5000000]
  97
  98 (The answer when :math:`L`, :math:`e_{1}`, and :math:`e_{2}` are so
  99 simple is independent of the cone.)
 100
 101 Requirements
 102 ------------
 103
 104 The only requirement is the CVXOPT library, available for most Linux
 105 distributions. Dunshire is targeted at python-3.x, but python-2.x will
 106 probably work too.
 107
 108 Background
 109 ----------
 110
 111 A linear game is a generalization of a two-person zero-sum matrix game
 112 [Karlin]_. Classically, such a game involves a matrix :math:`A \in
 113 \mathbb{R}^{n \times n}` and a set (the unit simplex) of "strategies"
 114 :math:`\Delta = \operatorname{conv}\left( \left\lbrace e_{1}, e_{2},
 115 \ldots, e_{n} \right\} \right)` from which two players are free to
 116 choose. If the players choose :math:`x,y \in \Delta` respectively,
 117 then the game is played by evaluating :math:`y^{T}Ax` as the "payoff"
 118 to the first player. His payoff comes from the second player, so that
 119 their total sums to zero.
 120
 121 Each player will try to maximize his payoff in this scenario,
 122 or—what is equivalent—try to minimize the payoff of his
 123 opponent. In fact, the existence of optimal strategies is
 124 guaranteed [Karlin]_ for both players. The *value* of the
 125 matrix game :math:`A` is the payoff resulting from optimal play,
 126
 127 .. math::
 128   v\left(A\right)
 129   =
 130   \underset{x \in \Delta}{\max}\
 131   \underset{y\in \Delta}{\min}
 132   \left( y^{T}Ax \right)
 133   =
 134   \underset{y \in \Delta}{\min}\
 135   \underset{x \in \Delta}{\max}
 136   \left( y^{T}Ax \right).
 137
 138 The payoff to the first player in this case is
 139 :math:`v\left(A\right)`. Corresponding to :math:`v\left(A\right)` is an
 140 optimal strategy pair :math:`\left(\bar{x}, \bar{y}\right) \in \Delta
 141 \times \Delta` such that
 142
 143 .. math::
 144   \bar{y}^{T}Ax
 145   \le
 146   v\left(A\right)
 147   =
 148   \bar{y}^{T}A\bar{x}
 149   \le
 150   y^{T}A\bar{x}
 151   \text{ for all } \left(x,y\right) \in \Delta \times \Delta.
 152
 153 The relationship between :math:`A`, :math:`\bar{x}`, :math:`\bar{y}`,
 154 and :math:`v\left(A\right)` has been studied extensively [Kaplansky]_
 155 [Raghavan]_. Gowda and Ravindran [GowdaRav]_ were motivated by these
 156 results to ask if the matrix :math:`A` can be replaced by a linear
 157 transformation :math:`L`, and whether or not the unit simplex
 158 :math:`\Delta` can be replaced by a more general set—a base of a
 159 symmetric cone. In fact, one can go all the way to asymmetric (but
 160 still proper) cones. But, since Dunshire can only handle the symmetric
 161 case, we will pretend from now on that our cones need to be
 162 symmetric. This simplifies some definitions.
 163
 164 What is a linear game?
 165 ~~~~~~~~~~~~~~~~~~~~~~
 166
 167 In the classical setting, the interpretation of the strategies as
 168 probabilities results in a strategy set :math:`\Delta \subseteq
 169 \mathbb{R}^{n}_{+}` that is compact, convex, and does not contain the
 170 origin. Moreover, any nonzero :math:`x \in \mathbb{R}^{n}_{+}` is a
 171 unique positive multiple :math:`x = \lambda b` of some :math:`b \in
 172 \Delta`. Several existence and uniqueness results are predicated on
 173 those properties.
 174
 175 **Definition.** Suppose that :math:`K` is a cone and :math:`B
 176 \subseteq K` does not contain the origin. If any nonzero :math:`x \in
 177 K` can be uniquely represented :math:`x = \lambda b` where
 178 :math:`\lambda > 0` and :math:`b \in B`, then :math:`B` is a *base*
 179 of :math:`K`.
 180
 181 The set :math:`\Delta` is a compact convex base for the proper cone
 182 :math:`\mathbb{R}^{n}_{+}`. Every :math:`x \in \Delta` also has
 183 entries that sum to unity, which can be abbreviated by the condition
 184 :math:`\left\langle x,\mathbf{1} \right\rangle = 1` where
 185 :math:`\mathbf{1} = \left(1,1,\ldots,1\right)^{T}` happens to lie in
 186 the interior of :math:`\mathbb{R}^{n}_{+}`. In fact, the two
 187 conditions :math:`x \in \mathbb{R}^{n}_{+}` and :math:`\left\langle
 188 x,\mathbf{1} \right\rangle = 1` define :math:`\Delta`. This is no
 189 coincidence; whenever :math:`K` is a symmetric cone and :math:`e_{2}
 190 \in \operatorname{int}\left(K\right)`, the set :math:`\left\lbrace x
 191 \in K \ \middle|\ \left\langle x,e_{2} \right\rangle = 1
 192 \right\rbrace` is a compact convex base of :math:`K`. This motivates a
 193 generalization where :math:`\mathbb{R}^{n}_{+}` is replaced by a
 194 symmetric cone.
 195
 196 **Definition.** Let :math:`V` be a finite-dimensional real Hilbert
 197 space. A *linear game* in :math:`V` is a tuple
 198 :math:`\left(L,K,e_{1},e_{2}\right)` where :math:`L : V \rightarrow V`
 199 is linear, the set :math:`K` is a symmetric cone in :math:`V`, and the
 200 points :math:`e_{1}` and :math:`e_{2}` belong to
 201 :math:`\operatorname{int}\left(K\right)`.
 202
 203 **Definition.**  The strategy sets for our linear game are
 204
 205 .. math::
 206   \begin{aligned}
 207     \Delta_{1}\left(L,K,e_{1},e_{2}\right) &=
 208       \left\lbrace
 209         x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
 210       \right\rbrace\\
 211     \Delta_{2}\left(L,K,e_{1},e_{2}\right) &=
 212       \left\lbrace
 213         y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
 214       \right\rbrace.
 215   \end{aligned}
 216
 217 Since :math:`e_{1},e_{2} \in \operatorname{int}\left(K\right)`, these
 218 are bases for :math:`K`. We will usually omit the arguments and write
 219 :math:`\Delta_{i}` to mean :math:`\Delta_{i}\left(L,K,e_{1},e_{2}\right)`.
 220
 221 To play the game :math:`\left(L,K,e_{1},e_{2}\right)`, the first
 222 player chooses an :math:`x \in \Delta_{1}`, and the second player
 223 independently chooses a :math:`y \in \Delta_{2}`. This completes the
 224 turn, and the payoffs are determined by applying the payoff operator
 225 :math:`\left(x,y\right) \mapsto \left\langle L\left(x\right), y
 226 \right\rangle`. The payoff to the first player is :math:`\left\langle
 227 L\left(x\right), y \right\rangle`, and since we want the game to be
 228 zero-sum, the payoff to the second player is :math:`-\left\langle
 229 L\left(x\right), y \right\rangle`.
 230
 231 The payoff operator is continuous in both arguments because it is
 232 bilinear and the ambient space is finite-dimensional. We constructed
 233 the strategy sets :math:`\Delta_{1}` and :math:`\Delta_{2}` to be
 234 compact and convex; as a result, Karlin's [Karlin]_ general min-max
 235 Theorem 1.5.1, guarantees the existence of optimal strategies for both
 236 players.
 237
 238 **Definition.** A pair :math:`\left(\bar{x},\bar{y}\right) \in
 239 \Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game
 240 :math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point
 241 inequality*,
 242
 243 .. math::
 244   \left\langle L\left(x\right),\bar{y} \right\rangle
 245   \le
 246   \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle
 247   \le
 248   \left\langle L\left(\bar{x}\right),y \right\rangle
 249   \text{ for all }
 250   \left(x,y\right) \in \Delta_{1} \times \Delta_{2}.
 251
 252 At an optimal pair, neither player can unilaterally increase his
 253 payoff by changing his strategy. The value :math:`\left\langle L
 254 \left( \bar{x} \right) , \bar{y} \right\rangle` is unique (by the same
 255 min-max theorem); it is shared by all optimal pairs. There exists at
 256 least one optimal pair :math:`\left(\bar{x},\bar{y}\right)` of the
 257 game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is
 258 :math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle
 259 L\left(\bar{x}\right), \bar{y} \right\rangle`.
 260
 261 Thanks to Karlin [Karlin]_, we have an equivalent characterization of
 262 a game's value that does not require us to have a particular optimal
 263 pair in mind,
 264
 265 .. math::
 266   v\left( L,K,e_{1},e_{2} \right)
 267   =
 268   \underset{x \in \Delta_{1}}{\max}\
 269   \underset{y\in \Delta_{2}}{\min}\
 270   \left\langle L\left(x\right),y \right\rangle
 271   =
 272   \underset{y\in \Delta_{2}}{\min}\
 273   \underset{x \in \Delta_{1}}{\max}\
 274   \left\langle L\left(x\right),y \right\rangle.
 275
 276 Linear games reduce to two-person zero-sum matrix games in the
 277 right setting.
 278
 279 **Example.** If :math:`K = \mathbb{R}^{n}_{+}` in :math:`V =
 280 \mathbb{R}^{n}` and :math:`e_{1} = e_{2} =
 281 \left(1,1,\ldots,1\right)^{T} \in \operatorname{int}\left(K\right)`,
 282 then :math:`\Delta_{1} = \Delta_{2} = \Delta`. For any :math:`L \in
 283 \mathbb{R}^{n \times n}`, the linear game :math:`\left(
 284 L,K,e_{2},e_{2} \right)` is a two-person zero-sum matrix game. Its
 285 payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is
 286
 287 .. math::
 288   v\left( L,K,e_{1},e_{2} \right)
 289   =
 290   \underset{x \in \Delta}{\max}\
 291   \underset{y\in \Delta}{\min}\
 292   \left( y^{T}Lx \right)
 293   =
 294   \underset{y\in \Delta}{\min}\
 295   \underset{x \in \Delta}{\max}\
 296   \left( y^{T}Lx \right).
 297
 298
 299 References
 300 ----------
 301
 302 .. [GowdaRav] M. S. Gowda and G. Ravindran. On the game-theoretic
 303    value of a linear transformation relative to a self-dual cone. Linear
 304    Algebra and its Applications, 469:440-463, 2015.
 305
 306 .. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of
 307    games. Annals of Mathematics, 46(3):474-479, 1945.
 308
 309 .. [Karlin] S. Karlin. Mathematical Methods and Theory in Games,
 310    Programming, and Economics. Addison-Wesley Publishing Company,
 311    Reading, Massachusetts, 1959.
 312
 313 .. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear
 314    Algebra and its Applications, 21:35-45, 1978.