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 References
 118 ----------
 119
 120 .. [GowdaRav] M. S. Gowda and G. Ravindran. On the game-theoretic
 121    value of a linear transformation relative to a self-dual cone. Linear
 122    Algebra and its Applications, 469:440-463, 2015.
 123
 124 .. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of
 125    games. Annals of Mathematics, 46(3):474-479, 1945.
 126
 127 .. [Karlin] S. Karlin. Mathematical Methods and Theory in Games,
 128    Programming, and Economics. Addison-Wesley Publishing Company,
 129    Reading, Massachusetts, 1959.
 130
 131 .. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear
 132    Algebra and its Applications, 21:35-45, 1978.