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 square matrix represented as a list of lists
 110              of real numbers. ``L`` itself is interpreted as a list of
 111              ROWS, which agrees with (for example) SageMath and NumPy,
 112              but not with CVXOPT (whose matrix constructor accepts a
 113              list of columns).
 114
 115           - ``K`` -- a SymmetricCone instance.
 116
 117           - ``e1`` -- the interior point of ``K`` belonging to player one;
 118             it can be of any enumerable type having the correct length.
 119
 120           - ``e2`` -- the interior point of ``K`` belonging to player two;
 121             it can be of any enumerable type having the correct length.
 122
 123         EXAMPLES:
 124
 125         Lists can (and probably should) be used for every argument:
 126
 127             >>> from cones import NonnegativeOrthant
 128             >>> K = NonnegativeOrthant(2)
 129             >>> L = [[1,0],[0,1]]
 130             >>> e1 = [1,1]
 131             >>> e2 = [1,1]
 132             >>> G = SymmetricLinearGame(L, K, e1, e2)
 133             >>> print(G)
 134             The linear game (L, K, e1, e2) where
 135               L = [ 1  0]
 136                   [ 0  1],
 137               K = Nonnegative orthant in the real 2-space,
 138               e1 = [ 1]
 139                    [ 1],
 140               e2 = [ 1]
 141                    [ 1].
 142
 143         The points ``e1`` and ``e2`` can also be passed as some other
 144         enumerable type (of the correct length) without much harm, since
 145         there is no row/column ambiguity:
 146
 147             >>> import cvxopt
 148             >>> import numpy
 149             >>> from cones import NonnegativeOrthant
 150             >>> K = NonnegativeOrthant(2)
 151             >>> L = [[1,0],[0,1]]
 152             >>> e1 = cvxopt.matrix([1,1])
 153             >>> e2 = numpy.matrix([1,1])
 154             >>> G = SymmetricLinearGame(L, K, e1, e2)
 155             >>> print(G)
 156             The linear game (L, K, e1, e2) where
 157               L = [ 1  0]
 158                   [ 0  1],
 159               K = Nonnegative orthant in the real 2-space,
 160               e1 = [ 1]
 161                    [ 1],
 162               e2 = [ 1]
 163                    [ 1].
 164
 165         However, ``L`` will always be intepreted as a list of rows, even
 166         if it is passed as a ``cvxopt.base.matrix`` which is otherwise
 167         indexed by columns:
 168
 169             >>> import cvxopt
 170             >>> from cones import NonnegativeOrthant
 171             >>> K = NonnegativeOrthant(2)
 172             >>> L = [[1,2],[3,4]]
 173             >>> e1 = [1,1]
 174             >>> e2 = e1
 175             >>> G = SymmetricLinearGame(L, K, e1, e2)
 176             >>> print(G)
 177             The linear game (L, K, e1, e2) where
 178               L = [ 1  2]
 179                   [ 3  4],
 180               K = Nonnegative orthant in the real 2-space,
 181               e1 = [ 1]
 182                    [ 1],
 183               e2 = [ 1]
 184                    [ 1].
 185             >>> L = cvxopt.matrix(L)
 186             >>> print(L)
 187             [ 1  3]
 188             [ 2  4]
 189             <BLANKLINE>
 190             >>> G = SymmetricLinearGame(L, K, e1, e2)
 191             >>> print(G)
 192             The linear game (L, K, e1, e2) where
 193               L = [ 1  2]
 194                   [ 3  4],
 195               K = Nonnegative orthant in the real 2-space,
 196               e1 = [ 1]
 197                    [ 1],
 198               e2 = [ 1]
 199                    [ 1].
 200         """
 201         self._K = K
 202         self._e1 = matrix(e1, (K.dimension(), 1))
 203         self._e2 = matrix(e2, (K.dimension(), 1))
 204
 205         # Our input ``L`` is indexed by rows but CVXOPT matrices are
 206         # indexed by columns, so we need to transpose the input before
 207         # feeding it to CVXOPT.
 208         self._L = matrix(L, (K.dimension(), K.dimension())).trans()
 209
 210         if not K.contains_strict(self._e1):
 211             raise ValueError('the point e1 must lie in the interior of K')
 212
 213         if not K.contains_strict(self._e2):
 214             raise ValueError('the point e2 must lie in the interior of K')
 215
 216     def __str__(self):
 217         """
 218         Return a string representatoin of this game.
 219
 220         EXAMPLES:
 221
 222             >>> from cones import NonnegativeOrthant
 223             >>> K = NonnegativeOrthant(3)
 224             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 225             >>> e1 = [1,1,1]
 226             >>> e2 = [1,2,3]
 227             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 228             >>> print(SLG)
 229             The linear game (L, K, e1, e2) where
 230               L = [  1  -5 -15]
 231                   [ -1   2  -3]
 232                   [-12 -15   1],
 233               K = Nonnegative orthant in the real 3-space,
 234               e1 = [ 1]
 235                    [ 1]
 236                    [ 1],
 237               e2 = [ 1]
 238                    [ 2]
 239                    [ 3].
 240
 241         """
 242         tpl = 'The linear game (L, K, e1, e2) where\n' \
 243               '  L = {:s},\n' \
 244               '  K = {!s},\n' \
 245               '  e1 = {:s},\n' \
 246               '  e2 = {:s}.'
 247         indented_L = '\n      '.join(str(self._L).splitlines())
 248         indented_e1 = '\n       '.join(str(self._e1).splitlines())
 249         indented_e2 = '\n       '.join(str(self._e2).splitlines())
 250         return tpl.format(indented_L, str(self._K), indented_e1, indented_e2)
 251
 252
 253     def solution(self):
 254         """
 255         Solve this linear game and return a Solution object.
 256
 257         OUTPUT:
 258
 259         If the cone program associated with this game could be
 260         successfully solved, then a Solution object containing the
 261         game's value and optimal strategies is returned. If the game
 262         could *not* be solved -- which should never happen -- then a
 263         GameUnsolvableException is raised. It can be printed to get the
 264         raw output from CVXOPT.
 265
 266         EXAMPLES:
 267
 268         This example is computed in Gowda and Ravindran in the section
 269         "The value of a Z-transformation":
 270
 271             >>> from cones import NonnegativeOrthant
 272             >>> K = NonnegativeOrthant(3)
 273             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 274             >>> e1 = [1,1,1]
 275             >>> e2 = [1,1,1]
 276             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 277             >>> print(SLG.solution())
 278             Game value: -6.1724138
 279             Player 1 optimal:
 280               [ 0.5517241]
 281               [-0.0000000]
 282               [ 0.4482759]
 283             Player 2 optimal:
 284               [0.4482759]
 285               [0.0000000]
 286               [0.5517241]
 287
 288         The value of the following game can be computed using the fact
 289         that the identity is invertible:
 290
 291             >>> from cones import NonnegativeOrthant
 292             >>> K = NonnegativeOrthant(3)
 293             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 294             >>> e1 = [1,2,3]
 295             >>> e2 = [4,5,6]
 296             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 297             >>> print(SLG.solution())
 298             Game value: 0.0312500
 299             Player 1 optimal:
 300               [0.0312500]
 301               [0.0625000]
 302               [0.0937500]
 303             Player 2 optimal:
 304               [0.1250000]
 305               [0.1562500]
 306               [0.1875000]
 307
 308         """
 309         # The cone "C" that appears in the statement of the CVXOPT
 310         # conelp program.
 311         C = CartesianProduct(self._K, self._K)
 312
 313         # The column vector "b" that appears on the right-hand side of
 314         # Ax = b in the statement of the CVXOPT conelp program.
 315         b = matrix([1], tc='d')
 316
 317         # A column of zeros that fits K.
 318         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 319
 320         # The column vector "h" that appears on the right-hand side of
 321         # Gx + s = h in the statement of the CVXOPT conelp program.
 322         h = matrix([zero, zero])
 323
 324         # The column vector "c" that appears in the objective function
 325         # value <c,x> in the statement of the CVXOPT conelp program.
 326         c = matrix([-1, zero])
 327
 328         # The matrix "G" that appears on the left-hand side of Gx + s = h
 329         # in the statement of the CVXOPT conelp program.
 330         G = append_row(append_col(zero, -identity(self._K.dimension())),
 331                        append_col(self._e1, -self._L))
 332
 333         # The matrix "A" that appears on the right-hand side of Ax = b
 334         # in the statement of the CVXOPT conelp program.
 335         A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
 336
 337         # Actually solve the thing and obtain a dictionary describing
 338         # what happened.
 339         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 340
 341         # The "status" field contains "optimal" if everything went
 342         # according to plan. Other possible values are "primal
 343         # infeasible", "dual infeasible", "unknown", all of which
 344         # mean we didn't get a solution. That should never happen,
 345         # because by construction our game has a solution, and thus
 346         # the cone program should too.
 347         if soln_dict['status'] != 'optimal':
 348             raise GameUnsolvableException(soln_dict)
 349
 350         p1_value = soln_dict['x'][0]
 351         p1_optimal = soln_dict['x'][1:]
 352         p2_optimal = soln_dict['z'][self._K.dimension():]
 353
 354         return Solution(p1_value, p1_optimal, p2_optimal)
 355
 356     def dual(self):
 357         """
 358         Return the dual game to this game.
 359
 360         EXAMPLES:
 361
 362             >>> from cones import NonnegativeOrthant
 363             >>> K = NonnegativeOrthant(3)
 364             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 365             >>> e1 = [1,1,1]
 366             >>> e2 = [1,2,3]
 367             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 368             >>> print(SLG.dual())
 369             The linear game (L, K, e1, e2) where
 370               L = [  1  -1 -12]
 371                   [ -5   2 -15]
 372                   [-15  -3   1],
 373               K = Nonnegative orthant in the real 3-space,
 374               e1 = [ 1]
 375                    [ 2]
 376                    [ 3],
 377               e2 = [ 1]
 378                    [ 1]
 379                    [ 1].
 380
 381         """
 382         return SymmetricLinearGame(self._L, # It will be transposed in __init__().
 383                                    self._K, # Since "K" is symmetric.
 384                                    self._e2,
 385                                    self._e1)