User API Documentation

You should only need to work with two modules, dunshire.cones and dunshire.games. For convenience, you can import everything from the dunshire package, and it will re-export what you need. For example,

from dunshire import *
K = IceCream(3)
L = [[1,-1,12],[0,1,22],[-17,1,0]]
e1 = [1,0.5,0.25]
e2 = [1,0.25,0.5]
G = SymmetricLinearGame(L,K,e1,e2)
G.solution()

dunshire.cones module

Class definitions for all of the symmetric cones (and their superclass, SymmetricCone) supported by CVXOPT.

class CartesianProduct(*factors)

Bases: SymmetricCone

A cartesian product of symmetric cones, which is itself a symmetric cone.

Examples

>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
>>> print(K)
Cartesian product of dimension 5 with 2 factors:
  * Nonnegative orthant in the real 3-space
  * Lorentz "ice cream" cone in the real 2-space

cvxopt_dims()

Return a dictionary of dimensions corresponding to the factors of this cartesian product. The format of this dictionary is described in the CVXOPT user’s guide.

Returns:

A dimension dictionary suitable to feed to CVXOPT.

Return type:

dict

Examples

>>> K = CartesianProduct(NonnegativeOrthant(3),
...                      IceCream(2),
...                      IceCream(3))
>>> d = K.cvxopt_dims()
>>> (d['l'], d['q'], d['s'])
(3, [2, 3], [])

factors()

Return a tuple containing the factors (in order) of this cartesian product.

Returns:

The factors of this cartesian product.

Return type:

tuple of SymmetricCone.

Examples

>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
>>> len(K.factors())
2

class IceCream(dimension)

Bases: SymmetricCone

The Lorentz “ice cream” cone in the given number of dimensions.

Examples

>>> K = IceCream(3)
>>> print(K)
Lorentz "ice cream" cone in the real 3-space

ball_radius(point)

Return the radius of a ball around point in this cone.

Since a radius cannot be negative, the point must be contained in this cone; otherwise, an error is raised.

The minimum distance from point to the complement of this cone will always occur at its projection onto that set. It is not hard to see that the projection is at a “down and out” angle of \(\pi/4\) towards the outside of the cone. If one draws a right triangle involving the point and that projection, it becomes clear that the distance between point and its projection is a factor of \(1/\sqrt(2)\) times the “horizontal” distance from point to boundary of this cone. For simplicity we take \(1/2\) instead.

Parameters:

point (matrix) – A point contained in this cone.

Returns:

A radius r such that the ball of radius r centered at point is contained entirely within this cone.

Return type:

float

Raises:

• TypeError – If point is not a cvxopt.base.matrix.

• TypeError – If point has the wrong dimensions.

• ValueError – if point is not contained in this cone.

Examples

The height of x below is one (its first coordinate), and so the radius of the circle obtained from a height-one cross section is also one. Note that the last two coordinates of x are half of the way to the boundary of the cone, and in the direction of a 30-60-90 triangle. If one follows those coordinates, they hit at \(\left(1, \frac{\sqrt(3)}{2}, \frac{1}{2}\right)\) having unit norm. Thus the “horizontal” distance to the boundary of the cone is \(1 - \left\lVert x \right\rVert\), which simplifies to \(1/2\). And rather than involve a square root, we divide by two for a final safe radius of \(1/4\).

>>> from math import sqrt
>>> K = IceCream(3)
>>> x = matrix([1, sqrt(3)/4.0, 1/4.0])
>>> K.ball_radius(x)
0.25

class NonnegativeOrthant(dimension)

Bases: SymmetricCone

The nonnegative orthant in the given number of dimensions.

Examples

>>> K = NonnegativeOrthant(3)
>>> print(K)
Nonnegative orthant in the real 3-space

ball_radius(point)

Return the radius of a ball around point in this cone.

Since a radius cannot be negative, the point must be contained in this cone; otherwise, an error is raised.

The minimum distance from point to the complement of this cone will always occur at its projection onto that set. It is not hard to see that the projection is directly along one of the coordinates, and so the minimum distance from point to the boundary of this cone is the smallest coordinate of point. Therefore any radius less than that will work; we divide it in half somewhat arbitrarily.

Parameters:

point (matrix) – A point contained in this cone.

Returns:

A radius r such that the ball of radius r centered at point is contained entirely within this cone.

Return type:

float

Raises:

• TypeError – If point is not a cvxopt.base.matrix.

• TypeError – If point has the wrong dimensions.

• ValueError – if point is not contained in this cone.

Examples

>>> K = NonnegativeOrthant(5)
>>> K.ball_radius(matrix([1,2,3,4,5]))
0.5

class SymmetricCone(dimension)

Bases: object

An instance of a symmetric (self-dual and homogeneous) cone.

There are three types of symmetric cones supported by CVXOPT:

1. The nonnegative orthant in the real n-space.

2. The Lorentz “ice cream” cone, or the second-order cone.

3. The cone of symmetric positive-semidefinite matrices.

This class is intended to encompass them all.

When constructing a single symmetric cone (i.e. not a CartesianProduct of them), the only information that we need is its dimension. We take that dimension as a parameter, and store it for later.

Parameters:

dimension (int) – The dimension of this cone.

Raises:

ValueError – If you try to create a cone with dimension zero or less.

ball_radius(point)

Return the radius of a ball around point in this cone.

Since a radius cannot be negative, the point must be contained in this cone; otherwise, an error is raised.

Parameters:

point (matrix) – A point contained in this cone.

Returns:

A radius r such that the ball of radius r centered at point is contained entirely within this cone.

Return type:

float

Raises:

NotImplementedError – Always, this method must be implemented in subclasses.

Examples

>>> K = SymmetricCone(5)
>>> K.ball_radius(matrix([1,1,1,1,1]))
Traceback (most recent call last):
...
NotImplementedError

dimension()

Return the dimension of this symmetric cone.

The dimension of this symmetric cone is recorded during its creation. This method simply returns the recorded value, and should not need to be overridden in subclasses. We prefer to do any special computation in __init__() and record the result in self._dimension.

Returns:

The stored dimension (from when this cone was constructed) of this cone.

Return type:

int

Examples

>>> K = SymmetricCone(5)
>>> K.dimension()
5

class SymmetricPSD(dimension)

Bases: SymmetricCone

The cone of real symmetric positive-semidefinite matrices.

This cone has a dimension n associated with it, but we let n refer to the dimension of the domain of our matrices and not the dimension of the (much larger) space in which the matrices themselves live. In other words, our n is the n that appears in the usual notation \(S^{n}\) for symmetric matrices.

As a result, the cone SymmetricPSD(n) lives in a space of dimension \(\left(n^{2} + n\right)/2)\).

Examples

>>> K = SymmetricPSD(3)
>>> print(K)
Cone of symmetric positive-semidefinite matrices on the real 3-space
>>> K.dimension()
3

dunshire.games module

Symmetric linear games and their solutions.

This module contains the main SymmetricLinearGame class that knows how to solve a linear game.

class Solution(game_value, p1_optimal, p2_optimal)

Bases: object

A representation of the solution of a linear game. It should contain the value of the game, and both players’ strategies.

Examples

>>> print(Solution(10, matrix([1,2]), matrix([3,4])))
Game value: 10.000...
Player 1 optimal:
  [ 1]
  [ 2]
Player 2 optimal:
  [ 3]
  [ 4]

game_value()

Return the game value for this solution.

Examples

>>> s = Solution(10, matrix([1,2]), matrix([3,4]))
>>> s.game_value()
10

player1_optimal()

Return player one’s optimal strategy in this solution.

Examples

>>> s = Solution(10, matrix([1,2]), matrix([3,4]))
>>> print(s.player1_optimal())
[ 1]
[ 2]

player2_optimal()

Return player two’s optimal strategy in this solution.

Examples

>>> s = Solution(10, matrix([1,2]), matrix([3,4]))
>>> print(s.player2_optimal())
[ 3]
[ 4]

class SymmetricLinearGame(L, K, e1, e2)

Bases: object

A representation of a symmetric linear game.

The data for a symmetric linear game are,

• A “payoff” operator L.

• A symmetric cone K.

• Two points e1 and e2 in the interior of K.

The ambient space is assumed to be the span of K.

With those data understood, the game is played as follows. Players one and two choose points \(x\) and \(y\) respectively, from their respective strategy sets,

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

Afterwards, a “payout” is computed as \(\left\langle L\left(x\right), y \right\rangle\) and is paid to player one out of player two’s pocket. The game is therefore zero sum, and we suppose that player one would like to guarantee himself the largest minimum payout possible. That is, player one wishes to,

\[\begin{split}\begin{aligned} \text{maximize } &\underset{y \in \Delta_{2}}{\min}\left( \left\langle L\left(x\right), y \right\rangle \right)\\ \text{subject to } & x \in \Delta_{1}. \end{aligned}\end{split}\]

Player two has the simultaneous goal to,

\[\begin{split}\begin{aligned} \text{minimize } &\underset{x \in \Delta_{1}}{\max}\left( \left\langle L\left(x\right), y \right\rangle \right)\\ \text{subject to } & y \in \Delta_{2}. \end{aligned}\end{split}\]

These goals obviously conflict (the game is zero sum), but an existence theorem guarantees at least one optimal min-max solution from which neither player would like to deviate. This class is able to find such a solution.

Parameters:

• L (list of list of float) – A matrix represented as a list of rows. This representation agrees with (for example) SageMath and NumPy, but not with CVXOPT (whose matrix constructor accepts a list of columns). In reality, L can be any iterable type of the correct length; however, you should be extremely wary of the way we interpret anything other than a list of rows.

• K (dunshire.cones.SymmetricCone) – The symmetric cone instance over which the game is played.

• e1 (iterable float) – The interior point of K belonging to player one; it can be of any iterable type having the correct length.

• e2 (iterable float) – The interior point of K belonging to player two; it can be of any enumerable type having the correct length.

Raises:

ValueError – If either e1 or e2 lie outside of the cone K.

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG)
The linear game (L, K, e1, e2) where
  L = [  1  -5 -15]
      [ -1   2  -3]
      [-12 -15   1],
  K = Nonnegative orthant in the real 3-space,
  e1 = [ 1]
       [ 1]
       [ 1],
  e2 = [ 1]
       [ 2]
       [ 3]

Lists can (and probably should) be used for every argument:

>>> from dunshire import *
>>> K = NonnegativeOrthant(2)
>>> L = [[1,0],[0,1]]
>>> e1 = [1,1]
>>> e2 = [1,1]
>>> G = SymmetricLinearGame(L, K, e1, e2)
>>> print(G)
The linear game (L, K, e1, e2) where
  L = [ 1  0]
      [ 0  1],
  K = Nonnegative orthant in the real 2-space,
  e1 = [ 1]
       [ 1],
  e2 = [ 1]
       [ 1]

The points e1 and e2 can also be passed as some other enumerable type (of the correct length) without much harm, since there is no row/column ambiguity:

>>> import cvxopt
>>> from dunshire import *
>>> K = NonnegativeOrthant(2)
>>> L = [[1,0],[0,1]]
>>> e1 = cvxopt.matrix([1,1])
>>> e2 = (1,1)
>>> G = SymmetricLinearGame(L, K, e1, e2)
>>> print(G)
The linear game (L, K, e1, e2) where
  L = [ 1  0]
      [ 0  1],
  K = Nonnegative orthant in the real 2-space,
  e1 = [ 1]
       [ 1],
  e2 = [ 1]
       [ 1]

However, L will always be intepreted as a list of rows, even if it is passed as a cvxopt.base.matrix which is otherwise indexed by columns:

>>> import cvxopt
>>> from dunshire import *
>>> K = NonnegativeOrthant(2)
>>> L = [[1,2],[3,4]]
>>> e1 = [1,1]
>>> e2 = e1
>>> G = SymmetricLinearGame(L, K, e1, e2)
>>> print(G)
The linear game (L, K, e1, e2) where
  L = [ 1  2]
      [ 3  4],
  K = Nonnegative orthant in the real 2-space,
  e1 = [ 1]
       [ 1],
  e2 = [ 1]
       [ 1]
>>> L = cvxopt.matrix(L)
>>> print(L)
[ 1  3]
[ 2  4]

>>> G = SymmetricLinearGame(L, K, e1, e2)
>>> print(G)
The linear game (L, K, e1, e2) where
  L = [ 1  2]
      [ 3  4],
  K = Nonnegative orthant in the real 2-space,
  e1 = [ 1]
       [ 1],
  e2 = [ 1]
       [ 1]

A()

Return the matrix A used in our CVXOPT construction.

This matrix \(A\) appears on the right-hand side of \(Ax = b\) in the statement of the CVXOPT conelp program.

Warning

It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them.

Returns:

A 1-by-(1 + self.dimension()) row vector. Its first entry is zero, and the rest are the entries of e2().

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,1,1],[1,1,1],[1,1,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.A())
[0.0000000 1.0000000 2.0000000 3.0000000]

C()

Return the cone C used in our CVXOPT construction.

This is the cone over which the CVXOPT conelp program takes place.

Returns:

The cartesian product of K with itself.

Return type:

CartesianProduct

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[4,5,6],[7,8,9],[10,11,12]]
>>> e1 = [1,2,3]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.C())
Cartesian product of dimension 6 with 2 factors:
  * Nonnegative orthant in the real 3-space
  * Nonnegative orthant in the real 3-space

G()

Return the matrix G used in our CVXOPT construction.

Thus matrix \(G\) appears on the left-hand side of \(Gx + s = h\) in the statement of the CVXOPT conelp program.

Warning

It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them.

Returns:

A 2*self.dimension()-by-(1 + self.dimension()) matrix.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[4,5,6],[7,8,9],[10,11,12]]
>>> e1 = [1,2,3]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.G())
[  0.0000000  -1.0000000   0.0000000   0.0000000]
[  0.0000000   0.0000000  -1.0000000   0.0000000]
[  0.0000000   0.0000000   0.0000000  -1.0000000]
[  1.0000000  -4.0000000  -5.0000000  -6.0000000]
[  2.0000000  -7.0000000  -8.0000000  -9.0000000]
[  3.0000000 -10.0000000 -11.0000000 -12.0000000]

K()

Return the cone over which this game is played.

Returns:

The SymmetricCone over which this game is played.

Return type:

SymmetricCone

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.K())
Nonnegative orthant in the real 3-space

L()

Return the matrix L passed to the constructor.

Returns:

The matrix that defines this game’s payoff() operator.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.L())
[  1  -5 -15]
[ -1   2  -3]
[-12 -15   1]

static b()

Return the b vector used in our CVXOPT construction.

The vector \(b\) appears on the right-hand side of \(Ax = b\) in the statement of the CVXOPT conelp program.

This method is static because the dimensions and entries of b are known beforehand, and don’t depend on any other properties of the game.

Warning

It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them.

Returns:

A 1-by-1 matrix containing a single entry 1.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[4,5,6],[7,8,9],[10,11,12]]
>>> e1 = [1,2,3]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.b())
[1.0000000]

c()

Return the vector c used in our CVXOPT construction.

The column vector \(c\) appears in the objective function value \(\left\langle c,x \right\rangle\) in the statement of the CVXOPT conelp program.

Warning

It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them.

Returns:

A dimension()-by-1 column vector.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[4,5,6],[7,8,9],[10,11,12]]
>>> e1 = [1,2,3]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.c())
[-1.0000000]
[ 0.0000000]
[ 0.0000000]
[ 0.0000000]

condition()

Return the condition number of this game.

In the CVXOPT construction of this game, two matrices G and A appear. When those matrices are nasty, numerical problems can show up. We define the condition number of this game to be the average of the condition numbers of G and A in the CVXOPT construction. If the condition number of this game is high, you can problems like PoorScalingException.

Random testing shows that a condition number of around 125 is about the best that we can solve reliably. However, the failures are intermittent, and you may get lucky with an ill-conditioned game.

Returns:

A real number greater than or equal to one that measures how bad this game is numerically.

Return type:

float

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(1)
>>> L = [[1]]
>>> e1 = [1]
>>> e2 = e1
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> SLG.condition()
1.809...

dimension()

Return the dimension of this game.

The dimension of a game is not needed for the theory, but it is useful for the implementation. We define the dimension of a game to be the dimension of its underlying cone. Or what is the same, the dimension of the space from which the strategies are chosen.

Returns:

The dimension of the cone K(), or of the space where this game is played.

Return type:

int

Examples

The dimension of a game over the nonnegative quadrant in the plane should be two (the dimension of the plane):

>>> from dunshire import *
>>> K = NonnegativeOrthant(2)
>>> L = [[1,-5],[-1,2]]
>>> e1 = [1,1]
>>> e2 = [1,4]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> SLG.dimension()
2

dual()

Return the dual game to this game.

If \(G = \left(L,K,e_{1},e_{2}\right)\) is a linear game, then its dual is \(G^{*} = \left(L^{*},K^{*},e_{2},e_{1}\right)\). However, since this cone is symmetric, \(K^{*} = K\).

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.dual())
The linear game (L, K, e1, e2) where
  L = [  1  -1 -12]
      [ -5   2 -15]
      [-15  -3   1],
  K = Nonnegative orthant in the real 3-space,
  e1 = [ 1]
       [ 2]
       [ 3],
  e2 = [ 1]
       [ 1]
       [ 1]

e1()

Return player one’s interior point.

Returns:

The point interior to K() affiliated with player one.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.e1())
[ 1]
[ 1]
[ 1]

e2()

Return player two’s interior point.

Returns:

The point interior to K() affiliated with player one.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,2,3]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.e2())
[ 1]
[ 2]
[ 3]

h()

Return the h vector used in our CVXOPT construction.

The \(h\) vector appears on the right-hand side of \(Gx + s = h\) in the statement of the CVXOPT conelp program.

Warning

It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them.

Returns:

A 2*self.dimension()-by-1 column vector of zeros.

Return type:

matrix

Examples

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[4,5,6],[7,8,9],[10,11,12]]
>>> e1 = [1,2,3]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.h())
[0.0000000]
[0.0000000]
[0.0000000]
[0.0000000]
[0.0000000]
[0.0000000]

payoff(strategy1, strategy2)

Return the payoff associated with strategy1 and strategy2.

The payoff operator takes pairs of strategies to a real number. For example, if player one’s strategy is \(x\) and player two’s strategy is \(y\), then the associated payoff is \(\left\langle L\left(x\right),y \right\rangle \in \mathbb{R}\). Here, \(L\) denotes the same linear operator as L(). This method computes the payoff given the two players’ strategies.

Parameters:

• strategy1 (matrix) – Player one’s strategy.

• strategy2 (matrix) – Player two’s strategy.

Returns:

The payoff for the game when player one plays strategy1 and player two plays strategy2.

Return type:

float

Examples

The value of the game should be the payoff at the optimal strategies:

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> soln = SLG.solution()
>>> x_bar = soln.player1_optimal()
>>> y_bar = soln.player2_optimal()
>>> SLG.payoff(x_bar, y_bar) == soln.game_value()
True

player1_start()

Return a feasible starting point for player one.

This starting point is for the CVXOPT formulation and not for the original game. The basic premise is that if you scale e2() by the reciprocal of its squared norm, then you get a point in K() that makes a unit inner product with e2(). We then get to choose the primal objective function value such that the constraint involving L() is satisfied.

Returns:

A dictionary with two keys, 'x' and 's', which contain the vectors of the same name in the CVXOPT primal problem formulation.

The vector x consists of the primal objective function value concatenated with the strategy (for player one) that achieves it. The vector s is essentially a dummy variable, and is computed from the equality constraing in the CVXOPT primal problem.

Return type:

dict

player2_start()

Return a feasible starting point for player two.

This starting point is for the CVXOPT formulation and not for the original game. The basic premise is that if you scale e1() by the reciprocal of its squared norm, then you get a point in K() that makes a unit inner product with e1(). We then get to choose the dual objective function value such that the constraint involving L() is satisfied.

Returns:

A dictionary with two keys, 'y' and 'z', which contain the vectors of the same name in the CVXOPT dual problem formulation.

The 1-by-1 vector y consists of the dual objective function value. The last dimension() entries of the vector z contain the strategy (for player two) that achieves it. The remaining entries of z are essentially dummy variables, computed from the equality constraint in the CVXOPT dual problem.

Return type:

dict

solution()

Solve this linear game and return a Solution.

Returns:

A Solution object describing the game’s value and the optimal strategies of both players.

Return type:

Solution

Raises:

• GameUnsolvableException – If the game could not be solved (if an optimal solution to its associated cone program was not found).

• PoorScalingException – If the game could not be solved because CVXOPT crashed while trying to take the square root of a negative number.

Examples

This example is computed in Gowda and Ravindran in the section “The value of a Z-transformation”:

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
>>> e1 = [1,1,1]
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
Game value: -6.172...
Player 1 optimal:
  [0.551...]
  [0.000...]
  [0.448...]
Player 2 optimal:
  [0.448...]
  [0.000...]
  [0.551...]

The value of the following game can be computed using the fact that the identity is invertible:

>>> from dunshire import *
>>> K = NonnegativeOrthant(3)
>>> L = [[1,0,0],[0,1,0],[0,0,1]]
>>> e1 = [1,2,3]
>>> e2 = [4,5,6]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
Game value: 0.031...
Player 1 optimal:
  [0.031...]
  [0.062...]
  [0.093...]
Player 2 optimal:
  [0.125...]
  [0.156...]
  [0.187...]

This is another Gowda/Ravindran example that is supposed to have a negative game value:

>>> from dunshire import *
>>> from dunshire.options import ABS_TOL
>>> L = [[1, -2], [-2, 1]]
>>> K = NonnegativeOrthant(2)
>>> e1 = [1, 1]
>>> e2 = e1
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> SLG.solution().game_value() < -ABS_TOL
True

The following two games are problematic numerically, but we should be able to solve them:

>>> from dunshire import *
>>> L = [[-0.95237953890954685221, 1.83474556206462535712],
...      [ 1.30481749924621448500, 1.65278664543326403447]]
>>> K = NonnegativeOrthant(2)
>>> e1 = [0.95477167524644313001, 0.63270781756540095397]
>>> e2 = [0.39633793037154141370, 0.10239281495640320530]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
Game value: 18.767...
Player 1 optimal:
  [0.000...]
  [9.766...]
Player 2 optimal:
  [1.047...]
  [0.000...]

>>> from dunshire import *
>>> L = [[1.54159395026049472754, 2.21344728574316684799],
...      [1.33147433507846657541, 1.17913616272988108769]]
>>> K = NonnegativeOrthant(2)
>>> e1 = [0.39903040089404784307, 0.12377403622479113410]
>>> e2 = [0.15695181142215544612, 0.85527381344651265405]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
Game value: 24.614...
Player 1 optimal:
  [6.371...]
  [0.000...]
Player 2 optimal:
  [2.506...]
  [0.000...]

This is another one that was difficult numerically, and caused trouble even after we fixed the first two:

>>> from dunshire import *
>>> L = [[57.22233908627052301199, 41.70631373437460354126],
...      [83.04512571985074487202, 57.82581810406928468637]]
>>> K = NonnegativeOrthant(2)
>>> e1 = [7.31887017043399268346, 0.89744171905822367474]
>>> e2 = [0.11099824781179848388, 6.12564670639315345113]
>>> SLG = SymmetricLinearGame(L,K,e1,e2)
>>> print(SLG.solution())
Game value: 70.437...
Player 1 optimal:
  [9.009...]
  [0.000...]
Player 2 optimal:
  [0.136...]
  [0.000...]

And finally, here’s one that returns an “optimal” solution, but whose primal/dual objective function values are far apart:

>>> from dunshire import *
>>> L = [[ 6.49260076597376212248, -0.60528030227678542019],
...      [ 2.59896077096751731972, -0.97685530240286766457]]
>>> K = IceCream(2)
>>> e1 = [1, 0.43749513972645248661]
>>> e2 = [1, 0.46008379832200291260]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
Game value: 11.596...
Player 1 optimal:
  [ 1.852...]
  [-1.852...]
Player 2 optimal:
  [ 1.777...]
  [-1.777...]

tolerance_scale(solution)

Return a scaling factor that should be applied to dunshire.options.ABS_TOL for this game.

When performing certain comparisons, the default tolerance dunshire.options.ABS_TOL may not be appropriate. For example, if we expect x and y to be within dunshire.options.ABS_TOL of each other, than the inner product of L*x and y can be as far apart as the spectral norm of L times the sum of the norms of x and y. Such a comparison is made in solution(), and in many of our unit tests.

The returned scaling factor found from the inner product mentioned above is

\[\left\lVert L \right\rVert_{2} \left( \left\lVert \bar{x} \right\rVert + \left\lVert \bar{y} \right\rVert \right),\]

where \(\bar{x}\) and \(\bar{y}\) are optimal solutions for players one and two respectively. This scaling factor is not formally justified, but attempting anything smaller leads to test failures.

Warning

Optimal solutions are not unique, so the scaling factor obtained from solution may not work when comparing other solutions.

Parameters:

solution (Solution) – A solution of this game, used to obtain the norms of the optimal strategies.

Returns:

A scaling factor to be multiplied by dunshire.options.ABS_TOL when making comparisons involving solutions of this game.

Return type:

float

Examples

The spectral norm of L in this case is around 5.464, and the optimal strategies both have norm one, so we expect the tolerance scale to be somewhere around 2 * 5.464, or 10.929:

>>> from dunshire import *
>>> L = [[1,2],[3,4]]
>>> K = NonnegativeOrthant(2)
>>> e1 = [1,1]
>>> e2 = e1
>>> SLG = SymmetricLinearGame(L,K,e1,e2)
>>> SLG.tolerance_scale(SLG.solution())
10.929...