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 <http://cvxopt.org/>`_-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}`:
+
+>>> 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}`:
+
+>>> 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.5000000]
+ [0.5000000]
+Player 2 optimal:
+ [0.5000000]
+ [0.5000000]
+
+(The answer when :math:`L`, :math:`e_{1}`, and :math:`e_{2}` are so
+simple is independent of the cone.)
Requirements
------------
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
+[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(\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)`.
+
+**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(\bar{x},\bar{y}\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),\bar{y} \right\rangle
+ \le
+ \left\langle L\left( \bar{x}\right), \bar{y} \right\rangle
+ \le
+ \left\langle L\left(\bar{x}\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( \bar{x} \right) , \bar{y} \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(\bar{x},\bar{y}\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(\bar{x}\right), \bar{y} \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).
+
+
+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.
projects / dunshire.git / blobdiff