]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/symmetric_linear_game.py
2 Symmetric linear games and their solutions.
4 This module contains the main SymmetricLinearGame class that knows how
5 to solve a linear game.
8 from cvxopt
import matrix
, printing
, solvers
10 from cones
import CartesianProduct
11 from errors
import GameUnsolvableException
12 from matrices
import append_col
, append_row
, identity
14 printing
.options
['dformat'] = '%.7f'
15 solvers
.options
['show_progress'] = False
20 A representation of the solution of a linear game. It should contain
21 the value of the game, and both players' strategies.
23 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
24 self
._game
_value
= game_value
25 self
._player
1_optimal
= p1_optimal
26 self
._player
2_optimal
= p2_optimal
30 Return a string describing the solution of a linear game.
32 The three data that are described are,
34 * The value of the game.
35 * The optimal strategy of player one.
36 * The optimal strategy of player two.
40 tpl
= 'Game value: {:.7f}\n' \
41 'Player 1 optimal:{:s}\n' \
42 'Player 2 optimal:{:s}\n'
44 p1_str
= '\n{!s}'.format(self
.player1_optimal())
45 p1_str
= '\n '.join(p1_str
.splitlines())
46 p2_str
= '\n{!s}'.format(self
.player2_optimal())
47 p2_str
= '\n '.join(p2_str
.splitlines())
49 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
53 return self
._game
_value
56 def player1_optimal(self
):
57 return self
._player
1_optimal
60 def player2_optimal(self
):
61 return self
._player
2_optimal
64 class SymmetricLinearGame
:
66 A representation of a symmetric linear game.
68 The data for a linear game are,
70 * A "payoff" operator ``L``.
72 * A point ``e`` in the interior of ``K``.
73 * A point ``f`` in the interior of the dual of ``K``.
75 In a symmetric game, the cone ``K`` is be self-dual. We therefore
76 name the two interior points ``e1`` and ``e2`` to indicate that
77 they come from the same cone but are "chosen" by players one and
80 The ambient space is assumed to be the span of ``K``.
83 def __init__(self
, L
, K
, e1
, e2
):
87 - ``L`` -- an n-by-b matrix represented as a list of lists
90 - ``K`` -- a SymmetricCone instance.
92 - ``e1`` -- the interior point of ``K`` belonging to player one,
95 - ``e2`` -- the interior point of ``K`` belonging to player two,
100 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
101 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
102 self
._L = matrix(L
, (K
.dimension(), K
.dimension()))
104 if not K
.contains_strict(self
._e
1):
105 raise ValueError('the point e1 must lie in the interior of K')
107 if not K
.contains_strict(self
._e
2):
108 raise ValueError('the point e2 must lie in the interior of K')
111 C
= CartesianProduct(self
._K
, self
._K
)
112 b
= matrix([1], tc
='d')
113 # A column of zeros that fits K.
114 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
115 h
= matrix([zero
, zero
])
116 c
= matrix([-1, zero
])
117 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
118 append_col(self
._e
1, -self
._L))
119 A
= matrix([0, self
._e
1], (1, self
._K
.dimension() + 1), 'd')
121 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
123 if soln_dict
['status'] != 'optimal':
124 raise GameUnsolvableException(soln_dict
)
126 p1_value
= soln_dict
['x'][0]
127 p1_optimal
= soln_dict
['x'][1:]
128 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
130 return Solution(p1_value
, p1_optimal
, p2_optimal
)