Switch to Mathjax for the docs and finish the "Background" section.

[dunshire.git] / doc / README.rst

Overview
--------

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}`:

.. 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 <http://cvxopt.org/>` 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.