1 from cvxopt
import matrix
, printing
, solvers
3 from cones
import CartesianProduct
4 from errors
import GameUnsolvableException
, GameValueMismatchException
5 from matrices
import append_col
, append_row
, identity
7 printing
.options
['dformat'] = '%.7f'
8 solvers
.options
['show_progress'] = False
10 class SymmetricLinearGame
:
12 A representation of a symmetric linear game.
14 The data for a linear game are,
16 * A "payoff" operator ``L``.
18 * A point ``e`` in the interior of ``K``.
19 * A point ``f`` in the interior of the dual of ``K``.
21 In a symmetric game, the cone ``K`` is be self-dual. We therefore
22 name the two interior points ``e1`` and ``e2`` to indicate that
23 they come from the same cone but are "chosen" by players one and
26 The ambient space is assumed to be the span of ``K``.
29 def __init__(self
, L
, K
, e1
, e2
):
33 - ``L`` -- an n-by-b matrix represented as a list of lists
36 - ``K`` -- a SymmetricCone instance.
38 - ``e1`` -- the interior point of ``K`` belonging to player one,
41 - ``e2`` -- the interior point of ``K`` belonging to player two,
46 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
47 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
48 self
._L = matrix(L
, (K
.dimension(), K
.dimension()))
50 if not K
.contains_strict(self
._e
1):
51 raise ValueError('the point e1 must lie in the interior of K')
53 if not K
.contains_strict(self
._e
2):
54 raise ValueError('the point e2 must lie in the interior of K')
58 C
= CartesianProduct(K
, K
)
59 b
= matrix([1], tc
='d')
60 # A column of zeros that fits K.
61 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
62 h
= matrix([zero
, zero
])
63 c
= matrix([-1, zero
])
64 G
= append_row(append_col(zero
, -identity(K
.dimension())),
65 append_col(self
._e
1, -self
._L))
66 A
= matrix([0, self
._e
1], (1, K
.dimension() + 1), 'd')
68 soln
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
70 #if soln['status'] != 'optimal':
71 raise GameUnsolvableException(soln
['status'], soln
)
73 p1_value
= soln
['x'][0]
74 p2_value
= soln
['y'][0]
75 p1_strategy
= soln
['x'][1:]
76 p2_strategy
= soln
['z'][self
._K
.dimension():]
78 #if p1_value != p2_value:
79 raise GameValueMismatchException(p1_value
, p2_value
, soln
)
81 return {'game value': p1_value
,
82 'player one': p1_strategy
,
83 'player two': p2_strategy
}