OverviewΒΆ

Dunshire is a 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 compromise between 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 \(K\), a linear transformation \(L\) on the space in which \(K\) lives, and two points \(e_{1}\) and \(e_{2}\) in the interior of \(K\). The players make their “moves” by choosing points from two strategy sets. Player one chooses an \(\bar{x}\) from

\[\Delta_{1} = \left\lbrace x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1 \right\rbrace\]

and player two chooses a \(\bar{y}\) from

\[\begin{split}\Delta_{2} &= \left\lbrace y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1 \right\rbrace.\end{split}\]

That ends the turn, and player one is paid \(\left\langle L\left(\bar{x}\right),\bar{y}\right\rangle\) out of player two’s pocket. As is usual 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,

\[\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,

\[\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 \(\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 \(K\) can be either the nonnegative orthant or the Lorentz “ice cream” cone in \(\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 \(\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.500...
Player 1 optimal:
  [0.500...]
  [0.500...]
Player 2 optimal:
  [0.500...]
  [0.500...]

Next we try the Lorentz ice-cream cone in \(\mathbb{R}^{2}\):

>>> from dunshire import *
>>> K = IceCream(2)
>>> L = [[1,0],[0,1]]
>>> e1 = [1,0]
>>> e2 = e1
>>> G = SymmetricLinearGame(L,K,e1,e2)
>>> print(G.solution())
Game value: 1.000...
Player 1 optimal:
  [1.000...]
  [0.000...]
Player 2 optimal:
  [1.000...]
  [0.000...]

Note that these solutions are not unique, although the game values are.