From 2030b75d2cd3074319de8c15e241723a1b9d75d2 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Thu, 6 Oct 2016 01:45:48 -0400 Subject: [PATCH] More work-in-progress on solutions and their errors. --- errors.py | 70 +++++++++++++++++++------------------- symmetric_linear_game.py | 72 +++++++++++++++++++++++++++++++--------- 2 files changed, 92 insertions(+), 50 deletions(-) diff --git a/errors.py b/errors.py index cc3b57e..028f5e7 100644 --- a/errors.py +++ b/errors.py @@ -2,55 +2,55 @@ Errors that can occur when solving a linear game. """ -class GameUnsolvableException(Exception): +from cvxopt import matrix + +class GameException(Exception): """ - Every linear game has a solution (this follows from a general - min-max theorem). If we can't solve the conic program associated - with a linear game, then something is wrong with either the model of - the input. + The base class for all exceptions that can occur during the solution + of a linear game. """ - def __init__(self, solution_dict): + def pretty_print_dict(self, solution_dict): """ - Create a new GameUnsolvableException object. - - INPUT: - - - ``primal`` -- the objective value of the primal cone program. - - - ``dual`` -- the objective value of the dual cone program. - - - ``solution_dict`` -- the solution dictionary returned from the cone program. - + Return a pretty-printed string representation of a CVXOPT + solution dictionary. """ - tpl = 'solution failed with error: {:s}\n' \ - 'CVXOPT returned:\n{!s}' - self.message = tpl.format(solution_dict['status'], solution_dict) + result = '' + for (k,v) in solution_dict.items(): + if isinstance(v, matrix): + # Try to display vectors as rows on one line. + result += ' {:s}: {!s}'.format(k,v.trans()) + else: + result += ' {:s}: {!s}\n'.format(k,v) + return result -class GameValueMismatchException(Exception): + +class GameUnsolvableException(GameException): """ - This error occurs when the primal and dual objective value of the - conic program associated with a linear game do not agree. By - construction, every conic program derived from a linear game must - have a solution and the same objective value (the "value of the - game") is shared by both players. - - Each instance of this class will know the two mismatched values, and - its ``message`` field will explain why they can't be so. + Every linear game has a solution (this follows from a general + min-max theorem). If we can't solve the conic program associated + with a linear game, then something is wrong with either the model of + the input. """ - def __init__(self, primal, dual, solution_dict): + def __init__(self, status, solution, solution_dict): """ - Create a new GameValueMismatchException. + Create a new GameUnsolvableException object. INPUT: - - ``primal`` -- the objective value of the primal cone program. + - ``status`` -- the failure status code returned by CVXOPT. - - ``dual`` -- the objective value of the dual cone program. + - ``solution`` -- a Solution object. - - ``solution_dict`` -- the solution dictionary returned from the cone program. + - ``solution_dict`` -- the solution dictionary returned from the + cone program. """ - tpl = 'game value mismatch for player1={:.7f}, player2={:.7f}\n' \ + tpl = 'Solution failed with error "{:s}".\n' \ + '{!s}\n' \ 'CVXOPT returned:\n{!s}' - self.message = tpl.format(primal, dual, solution_dict) + # TODO: dont convert the solution to a string, we need + # to output the two values as well. + self.message = tpl.format(status, + solution, + self.pretty_print_dict(solution_dict)) diff --git a/symmetric_linear_game.py b/symmetric_linear_game.py index a33c345..8c37c66 100644 --- a/symmetric_linear_game.py +++ b/symmetric_linear_game.py @@ -1,12 +1,59 @@ from cvxopt import matrix, printing, solvers from cones import CartesianProduct -from errors import GameUnsolvableException, GameValueMismatchException +from errors import GameUnsolvableException from matrices import append_col, append_row, identity printing.options['dformat'] = '%.7f' solvers.options['show_progress'] = False +class Solution: + """ + A representation of the solution of a linear game. It should contain + the value of the game, and both players' strategies. + """ + def __init__(self, p1_value, p2_value, p1_optimal, p2_optimal): + self._player1_value = p1_value + self._player2_value = p2_value + self._player1_optimal = p1_optimal + self._player2_optimal = p2_optimal + + def __str__(self): + """ + Return a string describing the solution of a linear game. + + The three data that are described are, + + * The value of the game. + * The optimal strategy of player one. + * The optimal strategy of player two. + + """ + # The string representations of the player strategy matrices + # already contain trailing newlines. + tpl = 'Game value: {:.7f}\n' \ + 'Player 1 optimal: {!s}' \ + 'Player 2 optimal: {!s}' + return tpl.format(self.game_value(), + self.player1_optimal().trans(), + self.player2_optimal().trans()) + + def game_value(self): + return ((self.player1_value() + self.player2_value()) / 2.0) + + def player1_value(self): + return self._player1_value + + def player2_value(self): + return self._player2_value + + def player1_optimal(self): + return self._player1_optimal + + def player2_optimal(self): + return self._player2_optimal + + class SymmetricLinearGame: """ A representation of a symmetric linear game. @@ -65,19 +112,14 @@ class SymmetricLinearGame: append_col(self._e1, -self._L)) A = matrix([0, self._e1], (1, K.dimension() + 1), 'd') - soln = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b) - - #if soln['status'] != 'optimal': - raise GameUnsolvableException(soln['status'], soln) - - p1_value = soln['x'][0] - p2_value = soln['y'][0] - p1_strategy = soln['x'][1:] - p2_strategy = soln['z'][self._K.dimension():] + soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b) + p1_value = soln_dict['x'][0] + p2_value = soln_dict['y'][0] + p1_optimal = soln_dict['x'][1:] + p2_optimal = soln_dict['z'][self._K.dimension():] + soln = Solution(p1_value, p2_value, p1_optimal, p2_optimal) - #if p1_value != p2_value: - raise GameValueMismatchException(p1_value, p2_value, soln) + #if soln_dict['status'] != 'optimal': + raise GameUnsolvableException(soln_dict['status'], soln, soln_dict) - return {'game value': p1_value, - 'player one': p1_strategy, - 'player two': p2_strategy} + return soln -- 2.43.2