symmetric_linear_game.py

   1 from cvxopt import matrix, printing, solvers
   2
   3 from cones import CartesianProduct
   4 from errors import GameUnsolvableException
   5 from matrices import append_col, append_row, identity
   6
   7 printing.options['dformat'] = '%.7f'
   8 solvers.options['show_progress'] = False
   9
  10 class Solution:
  11     """
  12     A representation of the solution of a linear game. It should contain
  13     the value of the game, and both players' strategies.
  14     """
  15     def __init__(self, p1_value, p2_value, p1_optimal, p2_optimal):
  16         self._player1_value = p1_value
  17         self._player2_value = p2_value
  18         self._player1_optimal = p1_optimal
  19         self._player2_optimal = p2_optimal
  20
  21     def __str__(self):
  22         """
  23         Return a string describing the solution of a linear game.
  24
  25         The three data that are described are,
  26
  27           * The value of the game.
  28           * The optimal strategy of player one.
  29           * The optimal strategy of player two.
  30
  31         """
  32         # The string representations of the player strategy matrices
  33         # already contain trailing newlines.
  34         tpl = 'Game value: {:.7f}\n' \
  35               'Player 1 optimal: {!s}' \
  36               'Player 2 optimal: {!s}'
  37         return tpl.format(self.game_value(),
  38                           self.player1_optimal().trans(),
  39                           self.player2_optimal().trans())
  40
  41     def game_value(self):
  42         return ((self.player1_value() + self.player2_value()) / 2.0)
  43
  44     def player1_value(self):
  45         return self._player1_value
  46
  47     def player2_value(self):
  48         return self._player2_value
  49
  50     def player1_optimal(self):
  51         return self._player1_optimal
  52
  53     def player2_optimal(self):
  54         return self._player2_optimal
  55
  56
  57 class SymmetricLinearGame:
  58     """
  59     A representation of a symmetric linear game.
  60
  61     The data for a linear game are,
  62
  63       * A "payoff" operator ``L``.
  64       * A cone ``K``.
  65       * A point ``e`` in the interior of ``K``.
  66       * A point ``f`` in the interior of the dual of ``K``.
  67
  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
  71     two respectively.
  72
  73     The ambient space is assumed to be the span of ``K``.
  74     """
  75
  76     def __init__(self, L, K, e1, e2):
  77         """
  78         INPUT:
  79
  80           - ``L`` -- an n-by-b matrix represented as a list of lists
  81              of real numbers.
  82
  83           - ``K`` -- a SymmetricCone instance.
  84
  85           - ``e1`` -- the interior point of ``K`` belonging to player one,
  86                       as a column vector.
  87
  88           - ``e2`` -- the interior point of ``K`` belonging to player two,
  89                       as a column vector.
  90
  91         """
  92         self._K = K
  93         self._e1 = matrix(e1, (K.dimension(), 1))
  94         self._e2 = matrix(e2, (K.dimension(), 1))
  95         self._L = matrix(L, (K.dimension(), K.dimension()))
  96
  97         if not K.contains_strict(self._e1):
  98             raise ValueError('the point e1 must lie in the interior of K')
  99
 100         if not K.contains_strict(self._e2):
 101             raise ValueError('the point e2 must lie in the interior of K')
 102
 103     def solution(self):
 104
 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._e1, -self._L))
 113         A = matrix([0, self._e1], (1, K.dimension() + 1), 'd')
 114
 115         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 116         p1_value = soln_dict['x'][0]
 117         p2_value = soln_dict['y'][0]
 118         p1_optimal = soln_dict['x'][1:]
 119         p2_optimal = soln_dict['z'][self._K.dimension():]
 120         soln = Solution(p1_value, p2_value, p1_optimal, p2_optimal)
 121
 122         #if soln_dict['status'] != 'optimal':
 123         raise GameUnsolvableException(soln_dict['status'], soln, soln_dict)
 124
 125         return soln