symmetric_linear_game.py

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