-Overview
---------
-
-Dunshire is a `CVXOPT <http://cvxopt.org/>`_-based library for solving
+Dunshire is a `CVXOPT <https://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.
-
-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~\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)`.
-
-**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.
-
-.. [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.
projects / dunshire.git / blobdiff