X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=doc%2FREADME.rst;h=84f8321a78aa4aecafc3ef4c61f2adafbbe898c1;hb=HEAD;hp=12eaf7a8ad675f787d09f496e0464a86683c88d0;hpb=08abee864006192c364c25f22c3755e89e310b9b;p=dunshire.git diff --git a/doc/README.rst b/doc/README.rst index 12eaf7a..afa8d46 100644 --- a/doc/README.rst +++ b/doc/README.rst @@ -1,420 +1,16 @@ -Overview --------- - -Dunshire is a `CVXOPT `_-based library for solving +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. - -In this game, we have two players who are competing for a "payoff." -There is a symmetric cone :math:`K`, a linear transformation :math:`L` -on the space in which :math:`K` lives, and two points :math:`e_{1}` -and :math:`e_{2}` in the interior of :math:`K`. The players make their -"moves" by choosing points from two strategy sets. Player one chooses -an :math:`\bar{x}` from - -.. math:: - \Delta_{1} = - \left\lbrace - x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1 - \right\rbrace - -and player two chooses a :math:`\bar{y}` from - -.. math:: - \Delta_{2} &= - \left\lbrace - y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1 - \right\rbrace. - -That ends the turn, and player one is paid :math:`\left\langle -L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's -pocket. As is usual to assume in game theory, we suppose that player -one wants to maximize his worst-case payoff, and that player two wants -to minimize his worst-case *payout*. In other words, player one wants -to solve the optimization problem, - -.. math:: - \text{find } - \underset{x \in \Delta_{1}}{\max}\ - \underset{y\in \Delta_{2}}{\min}\ - \left\langle L\left(x\right),y \right\rangle - -while player two tries to (simultaneously) solve a similar problem, - -.. math:: - \text{find } - \underset{y\in \Delta_{2}}{\min}\ - \underset{x \in \Delta_{1}}{\max}\ - \left\langle L\left(x\right),y \right\rangle. - -There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that -solves these problems optimally, and Dunshire can find it. The optimal -payoff, called *the value of the game*, is unique. At the moment, the -symmetric cone :math:`K` can be either the nonnegative orthant or the -Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of -the simplest possible examples, showing off the ability to solve a -game over both of those cones. - -First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`: - -.. doctest:: - - >>> from dunshire import * - >>> K = NonnegativeOrthant(2) - >>> L = [[1,0],[0,1]] - >>> e1 = [1,1] - >>> e2 = e1 - >>> G = SymmetricLinearGame(L,K,e1,e2) - >>> print(G.solution()) - Game value: 0.5000000 - Player 1 optimal: - [0.5000000] - [0.5000000] - Player 2 optimal: - [0.5000000] - [0.5000000] - -Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`: - -.. doctest:: - - >>> from dunshire import * - >>> K = IceCream(2) - >>> L = [[1,0],[0,1]] - >>> e1 = [1,1] - >>> e2 = e1 - >>> G = SymmetricLinearGame(L,K,e1,e2) - >>> print(G.solution()) - Game value: 0.5000000 - Player 1 optimal: - [0.8347039] - [0.1652961] - Player 2 optimal: - [0.5000000] - [0.5000000] - -Note that these solutions are not unique, although the game values are. - -Requirements ------------- - -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. - -Background ----------- - -A linear game is a generalization of a two-person zero-sum matrix game -[Karlin]_. 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(\xi, \gamma\right) \in \Delta -\times \Delta` such that - -.. math:: - \gamma^{T}Ax - \le - v\left(A\right) - = - \gamma^{T}A\xi - \le - y^{T}A\xi - \text{ for all } \left(x,y\right) \in \Delta \times \Delta. - -The relationship between :math:`A`, :math:`\xi`, :math:`\gamma`, -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)`. - -**Definition.** The strategy sets for our linear game are - -.. math:: - \begin{aligned} - \Delta_{1}\left(L,K,e_{1},e_{2}\right) &= - \left\lbrace - x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1 - \right\rbrace\\ - \Delta_{2}\left(L,K,e_{1},e_{2}\right) &= - \left\lbrace - y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1 - \right\rbrace. - \end{aligned} - -Since :math:`e_{1},e_{2} \in \operatorname{int}\left(K\right)`, these -are bases for :math:`K`. We will usually omit the arguments and write -:math:`\Delta_{i}` to mean :math:`\Delta_{i}\left(L,K,e_{1},e_{2}\right)`. - -To play the game :math:`\left(L,K,e_{1},e_{2}\right)`, the first -player chooses an :math:`x \in \Delta_{1}`, and the second player -independently chooses a :math:`y \in \Delta_{2}`. This completes the -turn, and the payoffs are determined by applying the payoff operator -:math:`\left(x,y\right) \mapsto \left\langle L\left(x\right), y -\right\rangle`. The payoff to the first player is :math:`\left\langle -L\left(x\right), y \right\rangle`, and since we want the game to be -zero-sum, the payoff to the second player is :math:`-\left\langle -L\left(x\right), y \right\rangle`. - -The payoff operator is continuous in both arguments because it is -bilinear and the ambient space is finite-dimensional. We constructed -the strategy sets :math:`\Delta_{1}` and :math:`\Delta_{2}` to be -compact and convex; as a result, Karlin's [Karlin]_ general min-max -Theorem 1.5.1, guarantees the existence of optimal strategies for both -players. - -**Definition.** A pair :math:`\left(\xi,\gamma\right) \in -\Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game -:math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point -inequality*, - -.. math:: - \left\langle L\left(x\right),\gamma \right\rangle - \le - \left\langle L\left( \xi\right), \gamma \right\rangle - \le - \left\langle L\left(\xi\right),y \right\rangle - \text{ for all } - \left(x,y\right) \in \Delta_{1} \times \Delta_{2}. - -At an optimal pair, neither player can unilaterally increase his -payoff by changing his strategy. The value :math:`\left\langle L -\left( \xi \right) , \gamma \right\rangle` is unique (by the same -min-max theorem); it is shared by all optimal pairs. There exists at -least one optimal pair :math:`\left(\xi,\gamma\right)` of the -game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is -:math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle -L\left(\xi\right), \gamma \right\rangle`. - -Thanks to Karlin [Karlin]_, we have an equivalent characterization of -a game's value that does not require us to have a particular optimal -pair in mind, - -.. math:: - v\left( L,K,e_{1},e_{2} \right) - = - \underset{x \in \Delta_{1}}{\max}\ - \underset{y\in \Delta_{2}}{\min}\ - \left\langle L\left(x\right),y \right\rangle - = - \underset{y\in \Delta_{2}}{\min}\ - \underset{x \in \Delta_{1}}{\max}\ - \left\langle L\left(x\right),y \right\rangle. - -Linear games reduce to two-person zero-sum matrix games in the -right setting. - -**Example.** If :math:`K = \mathbb{R}^{n}_{+}` in :math:`V = -\mathbb{R}^{n}` and :math:`e_{1} = e_{2} = -\left(1,1,\ldots,1\right)^{T} \in \operatorname{int}\left(K\right)`, -then :math:`\Delta_{1} = \Delta_{2} = \Delta`. For any :math:`L \in -\mathbb{R}^{n \times n}`, the linear game :math:`\left( -L,K,e_{2},e_{2} \right)` is a two-person zero-sum matrix game. Its -payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is - -.. math:: - v\left( L,K,e_{1},e_{2} \right) - = - \underset{x \in \Delta}{\max}\ - \underset{y\in \Delta}{\min}\ - \left( y^{T}Lx \right) - = - \underset{y\in \Delta}{\min}\ - \underset{x \in \Delta}{\max}\ - \left( y^{T}Lx \right). - - -Cone program formulation -~~~~~~~~~~~~~~~~~~~~~~~~ - -As early as 1947, von Neumann knew [Dantzig]_ that a two-person -zero-sum matrix game could be expressed as a linear program. It turns -out that the two concepts are equivalent, but turning a matrix game -into a linear program is the simpler transformation. Cone programs are -generalizations of linear programs where the cone is allowed to differ -from the nonnegative orthant. We will see that any linear game can be -formulated as a cone program, and if we're lucky, be solved. - -Our main tool in formulating our cone program is the following -theorem. It closely mimics a similar result in classical game theory -where the cone is the nonnegative orthant and the result gives rise to -a linear program. The symbols :math:`\preccurlyeq` and -:math:`\succcurlyeq` indicate inequality with respect to the cone -ordering; that is, :math:`x \succcurlyeq y \iff x - y \in K`. - -**Theorem.** In the game :math:`\left(L,K,e_{1},e_{2}\right)`, we have -:math:`L^{*}\left( \gamma \right) \preccurlyeq \nu e_{2}` and -:math:`L \left( \xi \right) \succcurlyeq \nu e_{1}` for -:math:`\nu \in \mathbb{R}` if and only if :math:`\nu` is the -value of the game :math:`\left(L,K,e_{1},e_{2}\right)` and -:math:`\left(\xi,\gamma\right)` is optimal for it. - -The proof of this theorem is not difficult, and the version for -:math:`e_{1} \ne e_{2}` can easily be deduced from the one given by -Gowda and Ravidran [GowdaRav]_. Let us now restate the objectives of -the two players in terms of this theorem. Player one would like to, - -.. math:: - \begin{aligned} - &\text{ maximize } &\nu &\\ - &\text{ subject to }& \xi &\in K&\\ - & & \left\langle \xi,e_{1} \right\rangle &= 1&\\ - & & \nu &\in \mathbb{R}&\\ - & & L\left(\xi\right) &\succcurlyeq \nu e_{1}.& - \end{aligned} - -Player two, on the other hand, would like to, - -.. math:: - - \begin{aligned} - &\text{ minimize } &\omega &\\ - &\text{ subject to }& \gamma &\in K&\\ - & & \left\langle \gamma,e_{2} \right\rangle &= 1&\\ - & & \omega &\in \mathbb{R}&\\ - & & L^{*}\left(\gamma\right) &\preccurlyeq \omega e_{2}.& - \end{aligned} - -The `CVXOPT ` library can solve symmetric cone -programs in the following primal/dual format: - -.. math:: - \text{primal} = - \left\{ - \begin{aligned} - \text{ minimize } & c^{T}x \\ - \text{ subject to } & Gx + s = h \\ - & Ax = b \\ - & s \in C, - \end{aligned} - \right. - -.. math:: - \text{dual} - = - \left\{ - \begin{aligned} - \text{ maximize } & -h^{T}z - b^{T}y \\ - \text{ subject to } & G^{T}z + A^{T}y + c = 0 \\ - & z \in C. - \end{aligned} - \right. - -We will now pull a rabbit out of the hat, and choose the -matrices/vectors in these primal/dual programs so as to reconstruct -exactly the goals of the two players. Let, - -.. math:: - \begin{aligned} - C &= K \times K\\ - x &= \begin{bmatrix} \nu & \xi \end{bmatrix} \\ - b &= \begin{bmatrix} 1 \end{bmatrix} \\ - h &= 0 \\ - c &= \begin{bmatrix} -1 & 0 \end{bmatrix} \\ - A &= \begin{bmatrix} 0 & e_{2}^{T} \end{bmatrix} \\ - G &= \begin{bmatrix} - 0 & -I\\ - e_{1} & -L - \end{bmatrix}. - \end{aligned} - -Substituting these values into the primal/dual CVXOPT cone programs -recovers the objectives of player one (primal) and player two (dual) -exactly. Therefore, we can use this formulation to solve a linear -game, and that is precisely what Dunshire does. - - -References ----------- - -.. [Dantzig] G. B. Dantzig. Linear Programming and Extensions. - Princeton University Press, Princeton, 1963. - -.. [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. - -.. [Karlin] S. Karlin. Mathematical Methods and Theory in Games, - Programming, and Economics. Addison-Wesley Publishing Company, - Reading, Massachusetts, 1959. - -.. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear - Algebra and its Applications, 21:35-45, 1978. +introduced by Gowda and Ravindran in *On the game-theoretic value of a +linear transformation relative to a self-dual cone*. I've extended +their results to asymmetric cones and two interior points in my +thesis, which does not exist yet. + +The main idea can be gleaned from Gowda and Ravindran, however. +Additional details and our problem formulation can be found in the +full Dunshire documentation. The state-of-the-art is that only +symmetric games can be solved efficiently, and thus the linear games +supported by Dunshire are a compromise between the two: the cones are +symmetric, but the players get to choose two interior points. + +Only the nonnegative orthant and the ice-cream cone are supported at +the moment. The symmetric positive-semidefinite cone is coming soon.