symmetric_linear_game.py

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