]>
gitweb.michael.orlitzky.com - dunshire.git/blob - symmetric_linear_game.py
694e09f6a9f21930ee028d732f96ddda9cdbb553
1 from cvxopt
import matrix
, printing
, solvers
3 from cones
import CartesianProduct
4 from errors
import GameUnsolvableException
5 from matrices
import append_col
, append_row
, identity
7 printing
.options
['dformat'] = '%.7f'
8 solvers
.options
['show_progress'] = False
13 A representation of the solution of a linear game. It should contain
14 the value of the game, and both players' strategies.
16 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
17 self
._game
_value
= game_value
18 self
._player
1_optimal
= p1_optimal
19 self
._player
2_optimal
= p2_optimal
23 Return a string describing the solution of a linear game.
25 The three data that are described are,
27 * The value of the game.
28 * The optimal strategy of player one.
29 * The optimal strategy of player two.
33 tpl
= 'Game value: {:.7f}\n' \
34 'Player 1 optimal:{:s}\n' \
35 'Player 2 optimal:{:s}\n'
37 p1
= '\n{!s}'.format(self
.player1_optimal())
38 p1
= '\n '.join(p1
.splitlines())
39 p2
= '\n{!s}'.format(self
.player2_optimal())
40 p2
= '\n '.join(p2
.splitlines())
42 return tpl
.format(self
.game_value(), p1
, p2
)
46 return self
._game
_value
49 def player1_optimal(self
):
50 return self
._player
1_optimal
53 def player2_optimal(self
):
54 return self
._player
2_optimal
57 class SymmetricLinearGame
:
59 A representation of a symmetric linear game.
61 The data for a linear game are,
63 * A "payoff" operator ``L``.
65 * A point ``e`` in the interior of ``K``.
66 * A point ``f`` in the interior of the dual of ``K``.
68 In a symmetric game, the cone ``K`` is be self-dual. We therefore
69 name the two interior points ``e1`` and ``e2`` to indicate that
70 they come from the same cone but are "chosen" by players one and
73 The ambient space is assumed to be the span of ``K``.
76 def __init__(self
, L
, K
, e1
, e2
):
80 - ``L`` -- an n-by-b matrix represented as a list of lists
83 - ``K`` -- a SymmetricCone instance.
85 - ``e1`` -- the interior point of ``K`` belonging to player one,
88 - ``e2`` -- the interior point of ``K`` belonging to player two,
93 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
94 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
95 self
._L = matrix(L
, (K
.dimension(), K
.dimension()))
97 if not K
.contains_strict(self
._e
1):
98 raise ValueError('the point e1 must lie in the interior of K')
100 if not K
.contains_strict(self
._e
2):
101 raise ValueError('the point e2 must lie in the interior of K')
105 C
= CartesianProduct(K
, K
)
106 b
= matrix([1], tc
='d')
107 # A column of zeros that fits K.
108 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
109 h
= matrix([zero
, zero
])
110 c
= matrix([-1, zero
])
111 G
= append_row(append_col(zero
, -identity(K
.dimension())),
112 append_col(self
._e
1, -self
._L))
113 A
= matrix([0, self
._e
1], (1, K
.dimension() + 1), 'd')
115 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
117 if soln_dict
['status'] != 'optimal':
118 raise GameUnsolvableException(soln_dict
)
120 p1_value
= soln_dict
['x'][0]
121 p1_optimal
= soln_dict
['x'][1:]
122 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
124 return Solution(p1_value
, p1_optimal
, p2_optimal
)