X-Git-Url: https://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=doc%2Fsource%2Fbackground.rst;fp=doc%2Fsource%2Fbackground.rst;h=7b3bf8ce6dec7caaefb2ce87d3ca6516c3ed9fe2;hb=843d46c5be5605d071f17481c48ed0cb7f5acbaf;hp=0000000000000000000000000000000000000000;hpb=6344038e97380527bef52ba48ba54cc9180c7a82;p=dunshire.git diff --git a/doc/source/background.rst b/doc/source/background.rst new file mode 100644 index 0000000..7b3bf8c --- /dev/null +++ b/doc/source/background.rst @@ -0,0 +1,289 @@ +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.