-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)`.
-
-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