symmetric_linear_game.py

   1 from cvxopt import matrix, printing, solvers
   2
   3 from cones import CartesianProduct
   4 from errors import GameUnsolvableException, GameValueMismatchException
   5 from matrices import append_col, append_row, identity
   6
   7 printing.options['dformat'] = '%.7f'
   8 solvers.options['show_progress'] = False
   9
  10 class SymmetricLinearGame:
  11     """
  12     A representation of a symmetric linear game.
  13
  14     The data for a linear game are,
  15
  16       * A "payoff" operator ``L``.
  17       * A cone ``K``.
  18       * A point ``e`` in the interior of ``K``.
  19       * A point ``f`` in the interior of the dual of ``K``.
  20
  21     In a symmetric game, the cone ``K`` is be self-dual. We therefore
  22     name the two interior points ``e1`` and ``e2`` to indicate that
  23     they come from the same cone but are "chosen" by players one and
  24     two respectively.
  25
  26     The ambient space is assumed to be the span of ``K``.
  27     """
  28
  29     def __init__(self, L, K, e1, e2):
  30         """
  31         INPUT:
  32
  33           - ``L`` -- an n-by-b matrix represented as a list of lists
  34              of real numbers.
  35
  36           - ``K`` -- a SymmetricCone instance.
  37
  38           - ``e1`` -- the interior point of ``K`` belonging to player one,
  39                       as a column vector.
  40
  41           - ``e2`` -- the interior point of ``K`` belonging to player two,
  42                       as a column vector.
  43
  44         """
  45         self._K = K
  46         self._e1 = matrix(e1, (K.dimension(), 1))
  47         self._e2 = matrix(e2, (K.dimension(), 1))
  48         self._L = matrix(L, (K.dimension(), K.dimension()))
  49
  50         if not K.contains_strict(self._e1):
  51             raise ValueError('the point e1 must lie in the interior of K')
  52
  53         if not K.contains_strict(self._e2):
  54             raise ValueError('the point e2 must lie in the interior of K')
  55
  56     def solution(self):
  57
  58         C = CartesianProduct(K, K)
  59         b = matrix([1], tc='d')
  60         # A column of zeros that fits K.
  61         zero = matrix(0, (self._K.dimension(), 1), tc='d')
  62         h = matrix([zero, zero])
  63         c = matrix([-1, zero])
  64         G = append_row(append_col(zero, -identity(K.dimension())),
  65                       append_col(self._e1, -self._L))
  66         A = matrix([0, self._e1], (1, K.dimension() + 1), 'd')
  67
  68         soln = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
  69
  70         #if soln['status'] != 'optimal':
  71         raise GameUnsolvableException(soln['status'], soln)
  72
  73         p1_value = soln['x'][0]
  74         p2_value = soln['y'][0]
  75         p1_strategy = soln['x'][1:]
  76         p2_strategy = soln['z'][self._K.dimension():]
  77
  78         #if p1_value != p2_value:
  79         raise GameValueMismatchException(p1_value, p2_value, soln)
  80
  81         return {'game value': p1_value,
  82                 'player one': p1_strategy,
  83                 'player two': p2_strategy}