symmetric_linear_game.py

   1 """
   2 Symmetric linear games and their solutions.
   3
   4 This module contains the main SymmetricLinearGame class that knows how
   5 to solve a linear game.
   6 """
   7
   8 from cvxopt import matrix, printing, solvers
   9
  10 from cones import CartesianProduct
  11 from errors import GameUnsolvableException
  12 from matrices import append_col, append_row, identity
  13
  14 printing.options['dformat'] = '%.7f'
  15 solvers.options['show_progress'] = False
  16
  17
  18 class Solution:
  19     """
  20     A representation of the solution of a linear game. It should contain
  21     the value of the game, and both players' strategies.
  22     """
  23     def __init__(self, game_value, p1_optimal, p2_optimal):
  24         self._game_value = game_value
  25         self._player1_optimal = p1_optimal
  26         self._player2_optimal = p2_optimal
  27
  28     def __str__(self):
  29         """
  30         Return a string describing the solution of a linear game.
  31
  32         The three data that are described are,
  33
  34           * The value of the game.
  35           * The optimal strategy of player one.
  36           * The optimal strategy of player two.
  37
  38         """
  39
  40         tpl = 'Game value: {:.7f}\n' \
  41               'Player 1 optimal:{:s}\n' \
  42               'Player 2 optimal:{:s}\n'
  43
  44         p1_str = '\n{!s}'.format(self.player1_optimal())
  45         p1_str = '\n  '.join(p1_str.splitlines())
  46         p2_str = '\n{!s}'.format(self.player2_optimal())
  47         p2_str = '\n  '.join(p2_str.splitlines())
  48
  49         return tpl.format(self.game_value(), p1_str, p2_str)
  50
  51
  52     def game_value(self):
  53         return self._game_value
  54
  55
  56     def player1_optimal(self):
  57         return self._player1_optimal
  58
  59
  60     def player2_optimal(self):
  61         return self._player2_optimal
  62
  63
  64 class SymmetricLinearGame:
  65     """
  66     A representation of a symmetric linear game.
  67
  68     The data for a linear game are,
  69
  70       * A "payoff" operator ``L``.
  71       * A cone ``K``.
  72       * A point ``e`` in the interior of ``K``.
  73       * A point ``f`` in the interior of the dual of ``K``.
  74
  75     In a symmetric game, the cone ``K`` is be self-dual. We therefore
  76     name the two interior points ``e1`` and ``e2`` to indicate that
  77     they come from the same cone but are "chosen" by players one and
  78     two respectively.
  79
  80     The ambient space is assumed to be the span of ``K``.
  81     """
  82
  83     def __init__(self, L, K, e1, e2):
  84         """
  85         INPUT:
  86
  87           - ``L`` -- an n-by-b matrix represented as a list of lists
  88              of real numbers.
  89
  90           - ``K`` -- a SymmetricCone instance.
  91
  92           - ``e1`` -- the interior point of ``K`` belonging to player one,
  93                       as a column vector.
  94
  95           - ``e2`` -- the interior point of ``K`` belonging to player two,
  96                       as a column vector.
  97
  98         """
  99         self._K = K
 100         self._e1 = matrix(e1, (K.dimension(), 1))
 101         self._e2 = matrix(e2, (K.dimension(), 1))
 102         self._L = matrix(L, (K.dimension(), K.dimension()))
 103
 104         if not K.contains_strict(self._e1):
 105             raise ValueError('the point e1 must lie in the interior of K')
 106
 107         if not K.contains_strict(self._e2):
 108             raise ValueError('the point e2 must lie in the interior of K')
 109
 110     def solution(self):
 111         C = CartesianProduct(self._K, self._K)
 112         b = matrix([1], tc='d')
 113         # A column of zeros that fits K.
 114         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 115         h = matrix([zero, zero])
 116         c = matrix([-1, zero])
 117         G = append_row(append_col(zero, -identity(self._K.dimension())),
 118                        append_col(self._e1, -self._L))
 119         A = matrix([0, self._e1], (1, self._K.dimension() + 1), 'd')
 120
 121         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 122
 123         if soln_dict['status'] != 'optimal':
 124             raise GameUnsolvableException(soln_dict)
 125
 126         p1_value = soln_dict['x'][0]
 127         p1_optimal = soln_dict['x'][1:]
 128         p2_optimal = soln_dict['z'][self._K.dimension():]
 129
 130         return Solution(p1_value, p1_optimal, p2_optimal)