From d68f794045ae653c1e4ac77bb1201ca261fc0a34 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Fri, 14 Oct 2016 10:29:56 -0400 Subject: [PATCH] Begin writing the background/introduction material. --- doc/README.rst | 127 +++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 119 insertions(+), 8 deletions(-) diff --git a/doc/README.rst b/doc/README.rst index 6fe9ba6..2a01957 100644 --- a/doc/README.rst +++ b/doc/README.rst @@ -1,9 +1,15 @@ Overview -------- -Dunshire is a CVXOPT-based library for solving linear (cone) -games. The notion of a cone game was introduced by Gowda[1] and -extended to asymmetric cones in my thesis[2]. +Dunshire is a `CVXOPT `_-based library for solving +linear (cone) games. The notion of a symmetric linear (cone) game was +introduced by Gowda and Ravindran [GowdaRav]_, and extended by +Orlitzky to asymmetric cones with two interior points. + +The state-of-the-art is that only symmetric games can be solved +efficiently, and thus the linear games supported by Dunshire are a +bastard of the two: the cones are symmetric, but the players get to +choose two interior points. Requirements ------------ @@ -12,10 +18,115 @@ The only requirement is the CVXOPT library, available for most Linux distributions. Dunshire is targeted at python-3.x, but python-2.x will probably work too. -[1] M. S. Gowda and G. Ravindran. On the game-theoretic value of a - linear transformation relative to a self-dual cone. Linear Algebra - and its Applications, 469:440-463, 2015. +Background +---------- + +A linear game is a generalization of a two-person zero-sum matrix +game~\cite{karlin, parthasarathy-raghavan, +von_neumann-morgenstern}. Classically, such a game involves a matrix +:math:`A \in \mathbb{R}^{n \times n}` and a set (the unit simplex) of +"strategies" :math:`\Delta = \operatorname{conv}\left( +\left\lbrace e_{1}, e_{2}, \ldots, e_{n} \right\} \right)` from which two +players are free to choose. If the players choose :math:`x,y \in \Delta` +respectively, then the game is played by evaluating :math:`y^{T}Ax` as the +"payoff" to the first player. His payoff comes from the second +player, so that their total sums to zero. + +Each player will try to maximize his payoff in this scenario, +or—what is equivalent—try to minimize the payoff of his +opponent. In fact, the existence of optimal strategies is +guaranteed [Karlin]_ for both players. The *value* of the +matrix game :math:`A` is the payoff resulting from optimal play, + +.. math:: + v\left(A\right) + = + \underset{x \in \Delta}{\max}\ + \underset{y\in \Delta}{\min} + \left( y^{T}Ax \right) + = + \underset{y \in \Delta}{\min}\ + \underset{x \in \Delta}{\max} + \left( y^{T}Ax \right). + +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(\bar{x}, \bar{y}\right) \in \Delta +\times \Delta` such that + +.. math:: + \bar{y}^{T}Ax + \le + v\left(A\right) + = + \bar{y}^{T}A\bar{x} + \le + y^{T}A\bar{x} + \text{ for all } \left(x,y\right) \in \Delta \times \Delta. + +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 +transformation :math:`L`, and whether or not the unit simplex +:math:`\Delta` can be replaced by a more general set—a base of a +symmetric cone. In fact, one can go all the way to asymmetric (but +still proper) cones. But, since Dunshire can only handle the symmetric +case, we will pretend from now on that our cones need to be +symmetric. This simplifies some definitions. + +What is a linear game? +---------------------- + +In the classical setting, the interpretation of the strategies as +probabilities results in a strategy set :math:`\Delta \subseteq +\mathbb{R}^{n}_{+}` that is compact, convex, and does not contain the +origin. Moreover, any nonzero :math:`x \in \mathbb{R}^{n}_{+}` is a +unique positive multiple :math:`x = \lambda b` of some :math:`b \in +\Delta`. Several existence and uniqueness results are predicated on +those properties. + +**Definition.** Suppose that :math:`K` is a cone and :math:`B +\subseteq K` does not contain the origin. If any nonzero :math:`x \in +K` can be uniquely represented :math:`x = \lambda b` where +:math:`\lambda > 0` and :math:`b \in B`, then :math:`B` is a *base* +of :math:`K`. + +The set :math:`\Delta` is a compact convex base for the proper cone +:math:`\mathbb{R}^{n}_{+}`. Every :math:`x \in \Delta` also has +entries that sum to unity, which can be abbreviated by the condition +:math:`\left\langle x,\mathbf{1} \right\rangle = 1` where +:math:`\mathbf{1} = \left(1,1,\ldots,1\right)^{T}` happens to lie in +the interior of :math:`\mathbb{R}^{n}_{+}`. In fact, the two +conditions :math:`x \in \mathbb{R}^{n}_{+}` and :math:`\left\langle +x,\mathbf{1} \right\rangle = 1` define :math:`\Delta`. This is no +coincidence; whenever :math:`K` is a symmetric cone and :math:`e_{2} +\in \operatorname{int}\left(K\right)`, the set :math:`\left\lbrace x +\in K \ \middle|\ \left\langle x,e_{2} \right\rangle = 1 +\right\rbrace` is a compact convex base of :math:`K`. This motivates a +generalization where :math:`\mathbb{R}^{n}_{+}` is replaced by a +symmetric cone. + +**Definition.** Let :math:`V` be a finite-dimensional real Hilbert +space. A *linear game* in :math:`V` is a tuple +:math:`\left(L,K,e_{1},e_{2}\right)` where :math:`L : V \rightarrow V` +is linear, the set :math:`K` is a symmetric cone in :math:`V`, and the +points :math:`e_{1}` and :math:`e_{2}` belong to +:math:`\operatorname{int}\left(K\right)`. + +References +---------- + +.. [GowdaRav] M. S. Gowda and G. Ravindran. On the game-theoretic + value of a linear transformation relative to a self-dual cone. Linear + Algebra and its Applications, 469:440-463, 2015. + +.. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of + games. Annals of Mathematics, 46(3):474-479, 1945. -[2] You wish. +.. [Karlin] S. Karlin. Mathematical Methods and Theory in Games, + Programming, and Economics. Addison-Wesley Publishing Company, + Reading, Massachusetts, 1959. -[3] http://cvxopt.org/ +.. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear + Algebra and its Applications, 21:35-45, 1978. -- 2.44.2