-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
----------
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
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
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.
projects / dunshire.git / blobdiff