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
  11 class Solution:
  12     """
  13     A representation of the solution of a linear game. It should contain
  14     the value of the game, and both players' strategies.
  15     """
  16     def __init__(self, game_value, p1_optimal, p2_optimal):
  17         self._game_value = game_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
  33         tpl = 'Game value: {:.7f}\n' \
  34               'Player 1 optimal:{:s}\n' \
  35               'Player 2 optimal:{:s}\n'
  36
  37         p1 = '\n{!s}'.format(self.player1_optimal())
  38         p1 = '\n  '.join(p1.splitlines())
  39         p2 = '\n{!s}'.format(self.player2_optimal())
  40         p2 = '\n  '.join(p2.splitlines())
  41
  42         return tpl.format(self.game_value(), p1, p2)
  43
  44
  45     def game_value(self):
  46         return self._game_value
  47
  48
  49     def player1_optimal(self):
  50         return self._player1_optimal
  51
  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
 117         if soln_dict['status'] != 'optimal':
 118             raise GameUnsolvableException(soln_dict)
 119
 120         p1_value = soln_dict['x'][0]
 121         p1_optimal = soln_dict['x'][1:]
 122         p2_optimal = soln_dict['z'][self._K.dimension():]
 123
 124         return Solution(p1_value, p1_optimal, p2_optimal)