]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/symmetric_linear_game.py
b6489ba6de43877dd5707a39b3d7811dd9d2e4a7
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
9 from unittest
import TestCase
11 from cones
import CartesianProduct
12 from errors
import GameUnsolvableException
13 from matrices
import append_col
, append_row
, identity
, inner_product
16 printing
.options
['dformat'] = options
.FLOAT_FORMAT
17 solvers
.options
['show_progress'] = options
.VERBOSE
22 A representation of the solution of a linear game. It should contain
23 the value of the game, and both players' strategies.
25 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
27 Create a new Solution object from a game value and two optimal
28 strategies for the players.
30 self
._game
_value
= game_value
31 self
._player
1_optimal
= p1_optimal
32 self
._player
2_optimal
= p2_optimal
36 Return a string describing the solution of a linear game.
38 The three data that are described are,
40 * The value of the game.
41 * The optimal strategy of player one.
42 * The optimal strategy of player two.
46 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
47 Game value: 10.0000000
56 tpl
= 'Game value: {:.7f}\n' \
57 'Player 1 optimal:{:s}\n' \
58 'Player 2 optimal:{:s}'
60 p1_str
= '\n{!s}'.format(self
.player1_optimal())
61 p1_str
= '\n '.join(p1_str
.splitlines())
62 p2_str
= '\n{!s}'.format(self
.player2_optimal())
63 p2_str
= '\n '.join(p2_str
.splitlines())
65 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
70 Return the game value for this solution.
72 return self
._game
_value
75 def player1_optimal(self
):
77 Return player one's optimal strategy in this solution.
79 return self
._player
1_optimal
82 def player2_optimal(self
):
84 Return player two's optimal strategy in this solution.
86 return self
._player
2_optimal
89 class SymmetricLinearGame
:
91 A representation of a symmetric linear game.
93 The data for a linear game are,
95 * A "payoff" operator ``L``.
97 * A point ``e`` in the interior of ``K``.
98 * A point ``f`` in the interior of the dual of ``K``.
100 In a symmetric game, the cone ``K`` is be self-dual. We therefore
101 name the two interior points ``e1`` and ``e2`` to indicate that
102 they come from the same cone but are "chosen" by players one and
105 The ambient space is assumed to be the span of ``K``.
107 def __init__(self
, L
, K
, e1
, e2
):
111 - ``L`` -- an square matrix represented as a list of lists
112 of real numbers. ``L`` itself is interpreted as a list of
113 ROWS, which agrees with (for example) SageMath and NumPy,
114 but not with CVXOPT (whose matrix constructor accepts a
117 - ``K`` -- a SymmetricCone instance.
119 - ``e1`` -- the interior point of ``K`` belonging to player one;
120 it can be of any enumerable type having the correct length.
122 - ``e2`` -- the interior point of ``K`` belonging to player two;
123 it can be of any enumerable type having the correct length.
127 Lists can (and probably should) be used for every argument:
129 >>> from cones import NonnegativeOrthant
130 >>> K = NonnegativeOrthant(2)
131 >>> L = [[1,0],[0,1]]
134 >>> G = SymmetricLinearGame(L, K, e1, e2)
136 The linear game (L, K, e1, e2) where
139 K = Nonnegative orthant in the real 2-space,
145 The points ``e1`` and ``e2`` can also be passed as some other
146 enumerable type (of the correct length) without much harm, since
147 there is no row/column ambiguity:
151 >>> from cones import NonnegativeOrthant
152 >>> K = NonnegativeOrthant(2)
153 >>> L = [[1,0],[0,1]]
154 >>> e1 = cvxopt.matrix([1,1])
155 >>> e2 = numpy.matrix([1,1])
156 >>> G = SymmetricLinearGame(L, K, e1, e2)
158 The linear game (L, K, e1, e2) where
161 K = Nonnegative orthant in the real 2-space,
167 However, ``L`` will always be intepreted as a list of rows, even
168 if it is passed as a ``cvxopt.base.matrix`` which is otherwise
172 >>> from cones import NonnegativeOrthant
173 >>> K = NonnegativeOrthant(2)
174 >>> L = [[1,2],[3,4]]
177 >>> G = SymmetricLinearGame(L, K, e1, e2)
179 The linear game (L, K, e1, e2) where
182 K = Nonnegative orthant in the real 2-space,
187 >>> L = cvxopt.matrix(L)
192 >>> G = SymmetricLinearGame(L, K, e1, e2)
194 The linear game (L, K, e1, e2) where
197 K = Nonnegative orthant in the real 2-space,
204 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
205 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
207 # Our input ``L`` is indexed by rows but CVXOPT matrices are
208 # indexed by columns, so we need to transpose the input before
209 # feeding it to CVXOPT.
210 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
212 if not K
.contains_strict(self
._e
1):
213 raise ValueError('the point e1 must lie in the interior of K')
215 if not K
.contains_strict(self
._e
2):
216 raise ValueError('the point e2 must lie in the interior of K')
220 Return a string representatoin of this game.
224 >>> from cones import NonnegativeOrthant
225 >>> K = NonnegativeOrthant(3)
226 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
229 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
231 The linear game (L, K, e1, e2) where
235 K = Nonnegative orthant in the real 3-space,
244 tpl
= 'The linear game (L, K, e1, e2) where\n' \
249 indented_L
= '\n '.join(str(self
._L).splitlines())
250 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
251 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
252 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
257 Solve this linear game and return a Solution object.
261 If the cone program associated with this game could be
262 successfully solved, then a Solution object containing the
263 game's value and optimal strategies is returned. If the game
264 could *not* be solved -- which should never happen -- then a
265 GameUnsolvableException is raised. It can be printed to get the
266 raw output from CVXOPT.
270 This example is computed in Gowda and Ravindran in the section
271 "The value of a Z-transformation":
273 >>> from cones import NonnegativeOrthant
274 >>> K = NonnegativeOrthant(3)
275 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
278 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
279 >>> print(SLG.solution())
280 Game value: -6.1724138
290 The value of the following game can be computed using the fact
291 that the identity is invertible:
293 >>> from cones import NonnegativeOrthant
294 >>> K = NonnegativeOrthant(3)
295 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
298 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
299 >>> print(SLG.solution())
300 Game value: 0.0312500
311 # The cone "C" that appears in the statement of the CVXOPT
313 C
= CartesianProduct(self
._K
, self
._K
)
315 # The column vector "b" that appears on the right-hand side of
316 # Ax = b in the statement of the CVXOPT conelp program.
317 b
= matrix([1], tc
='d')
319 # A column of zeros that fits K.
320 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
322 # The column vector "h" that appears on the right-hand side of
323 # Gx + s = h in the statement of the CVXOPT conelp program.
324 h
= matrix([zero
, zero
])
326 # The column vector "c" that appears in the objective function
327 # value <c,x> in the statement of the CVXOPT conelp program.
328 c
= matrix([-1, zero
])
330 # The matrix "G" that appears on the left-hand side of Gx + s = h
331 # in the statement of the CVXOPT conelp program.
332 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
333 append_col(self
._e
1, -self
._L))
335 # The matrix "A" that appears on the right-hand side of Ax = b
336 # in the statement of the CVXOPT conelp program.
337 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
339 # Actually solve the thing and obtain a dictionary describing
341 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
343 # The "status" field contains "optimal" if everything went
344 # according to plan. Other possible values are "primal
345 # infeasible", "dual infeasible", "unknown", all of which
346 # mean we didn't get a solution. That should never happen,
347 # because by construction our game has a solution, and thus
348 # the cone program should too.
349 if soln_dict
['status'] != 'optimal':
350 raise GameUnsolvableException(soln_dict
)
352 p1_value
= soln_dict
['x'][0]
353 p1_optimal
= soln_dict
['x'][1:]
354 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
356 return Solution(p1_value
, p1_optimal
, p2_optimal
)
360 Return the dual game to this game.
364 >>> from cones import NonnegativeOrthant
365 >>> K = NonnegativeOrthant(3)
366 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
369 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
370 >>> print(SLG.dual())
371 The linear game (L, K, e1, e2) where
375 K = Nonnegative orthant in the real 3-space,
384 return SymmetricLinearGame(self
._L, # It will be transposed in __init__().
385 self
._K
, # Since "K" is symmetric.
390 class SymmetricLinearGameTest(TestCase
):
392 def assertEqualWithinTol(self
, first
, second
):
394 Test that ``first`` and ``second`` are equal within our default
397 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
400 def test_solution_exists(self
):
402 Every linear game has a solution, so we should be able to solve
403 every symmetric linear game. Pick some parameters randomly and
406 from cones
import NonnegativeOrthant
407 from random
import randint
, uniform
408 ambient_dim
= randint(1,10)
409 K
= NonnegativeOrthant(ambient_dim
)
410 e1
= [uniform(0.1, 10) for idx
in range(ambient_dim
)]
411 e2
= [uniform(0.1, 10) for idx
in range(ambient_dim
)]
412 L
= [[uniform(-10, 10) for i
in range(ambient_dim
)]
413 for j
in range(ambient_dim
)]
414 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
416 L_matrix
= matrix(L
).trans()
417 expected
= inner_product(L_matrix
*soln
.player1_optimal(),
418 soln
.player2_optimal())
419 self
.assertEqualWithinTol(soln
.game_value(), expected
)