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         n = self._K.dimension()
  47         self._L  = matrix(L,  (n,n))
  48         self._e1 = matrix(e1, (n,1)) # TODO: check that e1 and e2
  49         self._e2 = matrix(e2, (n,1)) # are in the interior of K...
  50         self._h  = matrix(0,  (2*n,1), 'd')
  51         self._b = matrix(1,   (1,1), 'd')
  52         self._c = matrix([-1] + [0]*n, (n+1,1), 'd')
  53         self._G = append_row(append_col(matrix(0,(n,1)), -identity(n)),
  54                              append_col(self._e1, -self._L))
  55         self._A = matrix([0] + e1, (1, n+1), 'd')
  56
  57     def solution(self):
  58         soln = solvers.conelp(self._c,
  59                               self._G,
  60                               self._h,
  61                               self._C.cvxopt_dims(),
  62                               self._A,
  63                               self._b)
  64         return soln
  65
  66     def solve(self):
  67         soln = self.solution()
  68         nu = soln['x'][0]
  69         print('Value of the game (player one): {:f}'.format(nu))
  70
  71         opt1 = soln['x'][1:]
  72         print('Optimal strategy (player one):')
  73         print(opt1)
  74
  75         omega = soln['y'][0]
  76         n = self._K.dimension()
  77         opt2 = soln['z'][n:]
  78         print('Value of the game (player two): {:f}'.format(omega))
  79         print('Optimal strategy (player two):')
  80         print(opt2)