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 reexport 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)[source]¶ Bases:
dunshire.cones.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 3space * Lorentz "ice cream" cone in the real 2space

__contains__
(point)[source]¶ Return whether or not
point
belongs to this cone.The
point
is expected to be a tuple of points which will be tested for membership in this cone’s factors. If each point in the tuple belongs to its corresponding factor, then the whole point belongs to this cone. Otherwise, it doesn’t.Parameters: point (tuple of matrix) – A tuple of
cvxopt.base.matrix
corresponding to thefactors()
of this cartesian product.Returns: True
ifpoint
belongs to this cone,False
otherwise.Return type: bool
Raises: TypeError
– Ifpoint
is not a tuple ofcvxopt.base.matrix
.TypeError
– If any element ofpoint
has the wrong dimensions.
Examples
The result depends on how containment is defined for our factors:
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K True
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> (matrix([0,0,0]), matrix([1,0,1])) in K True
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> (matrix([1,1,1]), matrix([1,1,1])) in K False
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> (matrix([1,1,1]), matrix([1,0,1])) in K False
Junk arguments don’t work:
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> [[1,2,3],[4,5,6]] in K Traceback (most recent call last): ... TypeError: the given point is not a cvxopt.base.matrix
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) >>> (matrix([1,2]), matrix([3,4,5,6])) in K Traceback (most recent call last): ... TypeError: the given point has the wrong dimensions

cvxopt_dims
()[source]¶ 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], [])


class
IceCream
(dimension)[source]¶ Bases:
dunshire.cones.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 3space

__contains__
(point)[source]¶ Return whether or not
point
belongs to this cone.Since this test is expected to work on points whose components are floating point numbers, it doesn’t make any sense to distinguish between strict and nonstrict containment – the test uses a tolerance parameter.
Parameters: point (matrix) – A
cvxopt.base.matrix
having dimensions(n,1)
wheren
is thedimension()
of this cone.Returns: True
ifpoint
belongs to this cone,False
otherwise.Return type: bool
Raises: TypeError
– Ifpoint
is not acvxopt.base.matrix
.TypeError
– Ifpoint
has the wrong dimensions.
Examples
This point lies well within the ice cream cone:
>>> K = IceCream(3) >>> matrix([1,0.5,0.5]) in K True
This one lies on its boundary:
>>> K = IceCream(3) >>> matrix([1,0,1]) in K True
This point lies entirely outside of the ice cream cone:
>>> K = IceCream(3) >>> matrix([1,1,1]) in K False
Junk arguments don’t work:
>>> K = IceCream(3) >>> [1,2,3] in K Traceback (most recent call last): ... TypeError: the given point is not a cvxopt.base.matrix
>>> K = IceCream(3) >>> matrix([1,2]) in K Traceback (most recent call last): ... TypeError: the given point has the wrong dimensions

ball_radius
(point)[source]¶ 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 thepoint
and that projection, it becomes clear that the distance betweenpoint
and its projection is a factor of \(1/\sqrt(2)\) times the “horizontal” distance frompoint
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 radiusr
centered atpoint
is contained entirely within this cone.Return type: float
Raises: TypeError
– Ifpoint
is not acvxopt.base.matrix
.TypeError
– Ifpoint
has the wrong dimensions.ValueError
– ifpoint
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 heightone cross section is also one. Note that the last two coordinates ofx
are half of the way to the boundary of the cone, and in the direction of a 306090 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)[source]¶ Bases:
dunshire.cones.SymmetricCone
The nonnegative orthant in the given number of dimensions.
Examples
>>> K = NonnegativeOrthant(3) >>> print(K) Nonnegative orthant in the real 3space

__contains__
(point)[source]¶ Return whether or not
point
belongs to this cone.Since this test is expected to work on points whose components are floating point numbers, it doesn’t make any sense to distinguish between strict and nonstrict containment – the test uses a tolerance parameter.
Parameters: point (matrix) – A
cvxopt.base.matrix
having dimensions(n,1)
wheren
is thedimension()
of this cone.Returns: True
ifpoint
belongs to this cone,False
otherwise.Return type: bool
Raises: TypeError
– Ifpoint
is not acvxopt.base.matrix
.TypeError
– Ifpoint
has the wrong dimensions.
Examples
All of these coordinates are positive enough:
>>> K = NonnegativeOrthant(3) >>> matrix([1,2,3]) in K True
The one negative coordinate pushes this point outside of
K
:>>> K = NonnegativeOrthant(3) >>> matrix([1,0.1,3]) in K False
 A boundary point is considered inside of
K
: >>> K = NonnegativeOrthant(3) >>> matrix([1,0,3]) in K True
Junk arguments don’t work:
>>> K = NonnegativeOrthant(3) >>> [1,2,3] in K Traceback (most recent call last): ... TypeError: the given point is not a cvxopt.base.matrix
>>> K = NonnegativeOrthant(3) >>> matrix([1,2]) in K Traceback (most recent call last): ... TypeError: the given point has the wrong dimensions

ball_radius
(point)[source]¶ 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 frompoint
to the boundary of this cone is the smallest coordinate ofpoint
. 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 radiusr
centered atpoint
is contained entirely within this cone.Return type: float
Raises: TypeError
– Ifpoint
is not acvxopt.base.matrix
.TypeError
– Ifpoint
has the wrong dimensions.ValueError
– ifpoint
is not contained in this cone.
Examples
>>> K = NonnegativeOrthant(5) >>> K.ball_radius(matrix([1,2,3,4,5])) 0.5


class
SymmetricCone
(dimension)[source]¶ Bases:
object
An instance of a symmetric (selfdual and homogeneous) cone.
There are three types of symmetric cones supported by CVXOPT:
 The nonnegative orthant in the real nspace.
 The Lorentz “ice cream” cone, or the secondorder cone.
 The cone of symmetric positivesemidefinite 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.
__contains__
(point)[source]¶ Return whether or not
point
belongs to this cone.Parameters: point (matrix) – The point to test for membership in this cone. Raises: NotImplementedError
– Always, this method must be implemented in subclasses.Examples
>>> K = SymmetricCone(5) >>> matrix([1,2]) in K Traceback (most recent call last): ... NotImplementedError

ball_radius
(point)[source]¶ 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 radiusr
centered atpoint
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
()[source]¶ 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 inself._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)[source]¶ Bases:
dunshire.cones.SymmetricCone
The cone of real symmetric positivesemidefinite matrices.
This cone has a dimension
n
associated with it, but we letn
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, ourn
is then
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 positivesemidefinite matrices on the real 3space >>> K.dimension() 3

__contains__
(point)[source]¶ Return whether or not
point
belongs to this cone.Since this test is expected to work on points whose components are floating point numbers, it doesn’t make any sense to distinguish between strict and nonstrict containment – the test uses a tolerance parameter.
Parameters: point (matrix) – A
cvxopt.base.matrix
having dimensions(n,n)
wheren
is thedimension()
of this cone.Returns: True
ifpoint
belongs to this cone,False
otherwise.Return type: bool
Raises: TypeError
– Ifpoint
is not acvxopt.base.matrix
.TypeError
– Ifpoint
has the wrong dimensions.
Examples
These all lie in the interior of the Symmetric PSD cone:
>>> K = SymmetricPSD(2) >>> matrix([[1,0],[0,1]]) in K True
>>> K = SymmetricPSD(3) >>> matrix([[2,1,0],[1,2,1],[0,1,2]]) in K True
>>> K = SymmetricPSD(5) >>> A = matrix([[5,4,3,2,1], ... [4,5,4,3,2], ... [3,4,5,4,3], ... [2,3,4,5,4], ... [1,2,3,4,5]]) >>> A in K True
Boundary points lie in the cone as well:
>>> K = SymmetricPSD(2) >>> matrix([[0,0],[0,0]]) in K True
>>> K = SymmetricPSD(5) >>> A = matrix([[1,0,0,0,0], ... [0,1,0,0,0], ... [0,0,0,0,0], ... [0,0,0,1,0], ... [0,0,0,0,1]]) >>> A in K True
However, this matrix has a negative eigenvalue:
>>> K = SymmetricPSD(2) >>> A = matrix([[ 1, 2], ... [2, 1]]) >>> A in K False
An asymmetric cone with positive eigenvalues is not in the cone:
>>> K = SymmetricPSD(2) >>> A = matrix([[10, 2], ... [4, 8]]) >>> A in K False
Junk arguments don’t work:
>>> K = SymmetricPSD(2) >>> [[1,2],[2,3]] in K Traceback (most recent call last): ... TypeError: the given point is not a cvxopt.base.matrix
>>> K = SymmetricPSD(3) >>> matrix([[1,2],[3,4]]) in K Traceback (most recent call last): ... TypeError: the given point has the wrong dimensions

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)[source]¶ 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]

__str__
()[source]¶ Return a string describing the solution of a linear game.
The three data that are described are,
 The value of the game.
 The optimal strategy of player one.
 The optimal strategy of player two.
The two optimal strategy vectors are indented by two spaces.

game_value
()[source]¶ Return the game value for this solution.
Examples
>>> s = Solution(10, matrix([1,2]), matrix([3,4])) >>> s.game_value() 10


class
SymmetricLinearGame
(L, K, e1, e2)[source]¶ 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
ande2
in the interior ofK
.
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 minmax 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 eithere1
ore2
lie outside of the coneK
.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 3space, 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 2space, e1 = [ 1] [ 1], e2 = [ 1] [ 1]
The points
e1
ande2
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 >>> import numpy >>> from dunshire import * >>> K = NonnegativeOrthant(2) >>> L = [[1,0],[0,1]] >>> e1 = cvxopt.matrix([1,1]) >>> e2 = numpy.matrix([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 2space, e1 = [ 1] [ 1], e2 = [ 1] [ 1]
However,
L
will always be intepreted as a list of rows, even if it is passed as acvxopt.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 2space, 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 2space, e1 = [ 1] [ 1], e2 = [ 1] [ 1]

A
()[source]¶ Return the matrix
A
used in our CVXOPT construction.This matrix \(A\) appears on the righthand 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 ofe2()
.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
()[source]¶ 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 3space * Nonnegative orthant in the real 3space

G
()[source]¶ Return the matrix
G
used in our CVXOPT construction.Thus matrix \(G\) appears on the lefthand 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
()[source]¶ 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 3space

L
()[source]¶ 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
()[source]¶ Return the
b
vector used in our CVXOPT construction.The vector \(b\) appears on the righthand 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
by1
matrix containing a single entry1
.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
()[source]¶ 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()
by1
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
()[source]¶ Return the condition number of this game.
In the CVXOPT construction of this game, two matrices
G
andA
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 ofG
andA
in the CVXOPT construction. If the condition number of this game is high, you can problems likePoorScalingException
.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 illconditioned 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
()[source]¶ 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
()[source]¶ 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 3space, e1 = [ 1] [ 2] [ 3], e2 = [ 1] [ 1] [ 1]

e1
()[source]¶ 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
()[source]¶ 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
()[source]¶ Return the
h
vector used in our CVXOPT construction.The \(h\) vector appears on the righthand 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()
by1
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)[source]¶ Return the payoff associated with
strategy1
andstrategy2
.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 playsstrategy2
.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
()[source]¶ 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 inK()
that makes a unit inner product withe2()
. We then get to choose the primal objective function value such that the constraint involvingL()
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 vectors
is essentially a dummy variable, and is computed from the equality constraing in the CVXOPT primal problem.Return type: dict

player2_start
()[source]¶ 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 inK()
that makes a unit inner product withe1()
. We then get to choose the dual objective function value such that the constraint involvingL()
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
by1
vectory
consists of the dual objective function value. The lastdimension()
entries of the vectorz
contain the strategy (for player two) that achieves it. The remaining entries ofz
are essentially dummy variables, computed from the equality constraint in the CVXOPT dual problem.Return type: dict

solution
()[source]¶ 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: 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 Ztransformation”:
>>> 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)[source]¶ 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 expectx
andy
to be withindunshire.options.ABS_TOL
of each other, than the inner product ofL*x
andy
can be as far apart as the spectral norm ofL
times the sum of the norms ofx
andy
. Such a comparison is made insolution()
, 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 around5.464
, and the optimal strategies both have norm one, so we expect the tolerance scale to be somewhere around2 * 5.464
, or10.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...
 A “payoff” operator