From 6332794f1ecd2af0afdf5eab527bebcaaa9f58a2 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Thu, 6 Oct 2016 13:39:06 -0400 Subject: [PATCH] Add the game dual() method and document symmetric_linear_game.py. --- src/dunshire/symmetric_linear_game.py | 67 ++++++++++++++++++++++++++- 1 file changed, 66 insertions(+), 1 deletion(-) diff --git a/src/dunshire/symmetric_linear_game.py b/src/dunshire/symmetric_linear_game.py index e92e820..07385d7 100644 --- a/src/dunshire/symmetric_linear_game.py +++ b/src/dunshire/symmetric_linear_game.py @@ -21,6 +21,10 @@ class Solution: the value of the game, and both players' strategies. """ def __init__(self, game_value, p1_optimal, p2_optimal): + """ + Create a new Solution object from a game value and two optimal + strategies for the players. + """ self._game_value = game_value self._player1_optimal = p1_optimal self._player2_optimal = p2_optimal @@ -50,14 +54,23 @@ class Solution: def game_value(self): + """ + Return the game value for this solution. + """ return self._game_value def player1_optimal(self): + """ + Return player one's optimal strategy in this solution. + """ return self._player1_optimal def player2_optimal(self): + """ + Return player two's optimal strategy in this solution. + """ return self._player2_optimal @@ -79,7 +92,6 @@ class SymmetricLinearGame: The ambient space is assumed to be the span of ``K``. """ - def __init__(self, L, K, e1, e2): """ INPUT: @@ -107,19 +119,63 @@ class SymmetricLinearGame: if not K.contains_strict(self._e2): raise ValueError('the point e2 must lie in the interior of K') + def __str__(self): + """ + Return a string representatoin of this game. + """ + return "a game" + def solution(self): + """ + Solve this linear game and return a Solution object. + + OUTPUT: + + If the cone program associated with this game could be + successfully solved, then a Solution object containing the + game's value and optimal strategies is returned. If the game + could *not* be solved -- which should never happen -- then a + GameUnsolvableException is raised. It can be printed to get the + raw output from CVXOPT. + """ + # The cone "C" that appears in the statement of the CVXOPT + # conelp program. C = CartesianProduct(self._K, self._K) + + # The column vector "b" that appears on the right-hand side of + # Ax = b in the statement of the CVXOPT conelp program. b = matrix([1], tc='d') + # A column of zeros that fits K. zero = matrix(0, (self._K.dimension(), 1), tc='d') + + # The column vector "h" that appears on the right-hand side of + # Gx + s = h in the statement of the CVXOPT conelp program. h = matrix([zero, zero]) + + # The column vector "c" that appears in the objective function + # value in the statement of the CVXOPT conelp program. c = matrix([-1, zero]) + + # The matrix "G" that appears on the left-hand side of Gx + s = h + # in the statement of the CVXOPT conelp program. G = append_row(append_col(zero, -identity(self._K.dimension())), append_col(self._e1, -self._L)) + + # The matrix "A" that appears on the right-hand side of Ax = b + # in the statement of the CVXOPT conelp program. A = matrix([0, self._e1], (1, self._K.dimension() + 1), 'd') + # Actually solve the thing and obtain a dictionary describing + # what happened. soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b) + # The "status" field contains "optimal" if everything went + # according to plan. Other possible values are "primal + # infeasible", "dual infeasible", "unknown", all of which + # mean we didn't get a solution. That should never happen, + # because by construction our game has a solution, and thus + # the cone program should too. if soln_dict['status'] != 'optimal': raise GameUnsolvableException(soln_dict) @@ -128,3 +184,12 @@ class SymmetricLinearGame: p2_optimal = soln_dict['z'][self._K.dimension():] return Solution(p1_value, p1_optimal, p2_optimal) + + def dual(self): + """ + Return the dual game to this game. + """ + return SymmetricLinearGame(self._L.trans(), + self._K, # Since "K" is symmetric. + self._e2, + self._e1) -- 2.44.2