src/dunshire/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         """
  25         Create a new Solution object from a game value and two optimal
  26         strategies for the players.
  27         """
  28         self._game_value = game_value
  29         self._player1_optimal = p1_optimal
  30         self._player2_optimal = p2_optimal
  31
  32     def __str__(self):
  33         """
  34         Return a string describing the solution of a linear game.
  35
  36         The three data that are described are,
  37
  38           * The value of the game.
  39           * The optimal strategy of player one.
  40           * The optimal strategy of player two.
  41
  42         EXAMPLES:
  43
  44            >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
  45            Game value: 10.0000000
  46            Player 1 optimal:
  47              [ 1]
  48              [ 2]
  49            Player 2 optimal:
  50              [ 3]
  51              [ 4]
  52
  53         """
  54         tpl = 'Game value: {:.7f}\n' \
  55               'Player 1 optimal:{:s}\n' \
  56               'Player 2 optimal:{:s}'
  57
  58         p1_str = '\n{!s}'.format(self.player1_optimal())
  59         p1_str = '\n  '.join(p1_str.splitlines())
  60         p2_str = '\n{!s}'.format(self.player2_optimal())
  61         p2_str = '\n  '.join(p2_str.splitlines())
  62
  63         return tpl.format(self.game_value(), p1_str, p2_str)
  64
  65
  66     def game_value(self):
  67         """
  68         Return the game value for this solution.
  69         """
  70         return self._game_value
  71
  72
  73     def player1_optimal(self):
  74         """
  75         Return player one's optimal strategy in this solution.
  76         """
  77         return self._player1_optimal
  78
  79
  80     def player2_optimal(self):
  81         """
  82         Return player two's optimal strategy in this solution.
  83         """
  84         return self._player2_optimal
  85
  86
  87 class SymmetricLinearGame:
  88     """
  89     A representation of a symmetric linear game.
  90
  91     The data for a linear game are,
  92
  93       * A "payoff" operator ``L``.
  94       * A cone ``K``.
  95       * A point ``e`` in the interior of ``K``.
  96       * A point ``f`` in the interior of the dual of ``K``.
  97
  98     In a symmetric game, the cone ``K`` is be self-dual. We therefore
  99     name the two interior points ``e1`` and ``e2`` to indicate that
 100     they come from the same cone but are "chosen" by players one and
 101     two respectively.
 102
 103     The ambient space is assumed to be the span of ``K``.
 104     """
 105     def __init__(self, L, K, e1, e2):
 106         """
 107         INPUT:
 108
 109           - ``L`` -- an n-by-b matrix represented as a list of lists
 110              of real numbers.
 111
 112           - ``K`` -- a SymmetricCone instance.
 113
 114           - ``e1`` -- the interior point of ``K`` belonging to player one,
 115                       as a column vector.
 116
 117           - ``e2`` -- the interior point of ``K`` belonging to player two,
 118                       as a column vector.
 119
 120         """
 121         self._K = K
 122         self._e1 = matrix(e1, (K.dimension(), 1))
 123         self._e2 = matrix(e2, (K.dimension(), 1))
 124         self._L = matrix(L, (K.dimension(), K.dimension()))
 125
 126         if not K.contains_strict(self._e1):
 127             raise ValueError('the point e1 must lie in the interior of K')
 128
 129         if not K.contains_strict(self._e2):
 130             raise ValueError('the point e2 must lie in the interior of K')
 131
 132     def __str__(self):
 133         """
 134         Return a string representatoin of this game.
 135
 136         EXAMPLES:
 137
 138             >>> from cones import NonnegativeOrthant
 139             >>> K = NonnegativeOrthant(3)
 140             >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
 141             >>> e1 = [1,1,1]
 142             >>> e2 = [1,2,3]
 143             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 144             >>> print(SLG)
 145             The linear game (L, K, e1, e2) where
 146               L = [  1  -5 -15]
 147                   [ -1   2  -3]
 148                   [-12 -15   1],
 149               K = Nonnegative orthant in the real 3-space,
 150               e1 = [ 1]
 151                    [ 1]
 152                    [ 1],
 153               e2 = [ 1]
 154                    [ 2]
 155                    [ 3].
 156
 157         """
 158         tpl = 'The linear game (L, K, e1, e2) where\n' \
 159               '  L = {:s},\n' \
 160               '  K = {!s},\n' \
 161               '  e1 = {:s},\n' \
 162               '  e2 = {:s}.'
 163         L_str = '\n      '.join(str(self._L).splitlines())
 164         e1_str = '\n       '.join(str(self._e1).splitlines())
 165         e2_str = '\n       '.join(str(self._e2).splitlines())
 166         return tpl.format(L_str, str(self._K), e1_str, e2_str)
 167
 168
 169     def solution(self):
 170         """
 171         Solve this linear game and return a Solution object.
 172
 173         OUTPUT:
 174
 175         If the cone program associated with this game could be
 176         successfully solved, then a Solution object containing the
 177         game's value and optimal strategies is returned. If the game
 178         could *not* be solved -- which should never happen -- then a
 179         GameUnsolvableException is raised. It can be printed to get the
 180         raw output from CVXOPT.
 181
 182         EXAMPLES:
 183
 184         This example is computed in Gowda and Ravindran in the section
 185         "The value of a Z-transformation":
 186
 187             >>> from cones import NonnegativeOrthant
 188             >>> K = NonnegativeOrthant(3)
 189             >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
 190             >>> e1 = [1,1,1]
 191             >>> e2 = [1,1,1]
 192             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 193             >>> print(SLG.solution())
 194             Game value: -6.1724138
 195             Player 1 optimal:
 196               [ 0.5517241]
 197               [-0.0000000]
 198               [ 0.4482759]
 199             Player 2 optimal:
 200               [0.4482759]
 201               [0.0000000]
 202               [0.5517241]
 203
 204         The value of the following game can be computed using the fact
 205         that the identity is invertible:
 206
 207             >>> from cones import NonnegativeOrthant
 208             >>> K = NonnegativeOrthant(3)
 209             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 210             >>> e1 = [1,2,3]
 211             >>> e2 = [4,5,6]
 212             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 213             >>> print(SLG.solution())
 214             Game value: 0.0312500
 215             Player 1 optimal:
 216               [0.0312500]
 217               [0.0625000]
 218               [0.0937500]
 219             Player 2 optimal:
 220               [0.1250000]
 221               [0.1562500]
 222               [0.1875000]
 223
 224         """
 225         # The cone "C" that appears in the statement of the CVXOPT
 226         # conelp program.
 227         C = CartesianProduct(self._K, self._K)
 228
 229         # The column vector "b" that appears on the right-hand side of
 230         # Ax = b in the statement of the CVXOPT conelp program.
 231         b = matrix([1], tc='d')
 232
 233         # A column of zeros that fits K.
 234         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 235
 236         # The column vector "h" that appears on the right-hand side of
 237         # Gx + s = h in the statement of the CVXOPT conelp program.
 238         h = matrix([zero, zero])
 239
 240         # The column vector "c" that appears in the objective function
 241         # value <c,x> in the statement of the CVXOPT conelp program.
 242         c = matrix([-1, zero])
 243
 244         # The matrix "G" that appears on the left-hand side of Gx + s = h
 245         # in the statement of the CVXOPT conelp program.
 246         G = append_row(append_col(zero, -identity(self._K.dimension())),
 247                        append_col(self._e1, -self._L))
 248
 249         # The matrix "A" that appears on the right-hand side of Ax = b
 250         # in the statement of the CVXOPT conelp program.
 251         A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
 252
 253         # Actually solve the thing and obtain a dictionary describing
 254         # what happened.
 255         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 256
 257         # The "status" field contains "optimal" if everything went
 258         # according to plan. Other possible values are "primal
 259         # infeasible", "dual infeasible", "unknown", all of which
 260         # mean we didn't get a solution. That should never happen,
 261         # because by construction our game has a solution, and thus
 262         # the cone program should too.
 263         if soln_dict['status'] != 'optimal':
 264             raise GameUnsolvableException(soln_dict)
 265
 266         p1_value = soln_dict['x'][0]
 267         p1_optimal = soln_dict['x'][1:]
 268         p2_optimal = soln_dict['z'][self._K.dimension():]
 269
 270         return Solution(p1_value, p1_optimal, p2_optimal)
 271
 272     def dual(self):
 273         """
 274         Return the dual game to this game.
 275
 276         EXAMPLES:
 277
 278             >>> from cones import NonnegativeOrthant
 279             >>> K = NonnegativeOrthant(3)
 280             >>> L = [[1,-1,-12],[-5,2,-15],[-15,-3,1]]
 281             >>> e1 = [1,1,1]
 282             >>> e2 = [1,2,3]
 283             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 284             >>> print(SLG.dual())
 285             The linear game (L, K, e1, e2) where
 286               L = [  1  -1 -12]
 287                   [ -5   2 -15]
 288                   [-15  -3   1],
 289               K = Nonnegative orthant in the real 3-space,
 290               e1 = [ 1]
 291                    [ 2]
 292                    [ 3],
 293               e2 = [ 1]
 294                    [ 1]
 295                    [ 1].
 296
 297         """
 298         return SymmetricLinearGame(self._L.trans(),
 299                                    self._K, # Since "K" is symmetric.
 300                                    self._e2,
 301                                    self._e1)