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 from unittest import TestCase
  10
  11 from cones import CartesianProduct
  12 from errors import GameUnsolvableException
  13 from matrices import append_col, append_row, identity, inner_product
  14 import options
  15
  16 printing.options['dformat'] = options.FLOAT_FORMAT
  17 solvers.options['show_progress'] = options.VERBOSE
  18
  19
  20 class Solution:
  21     """
  22     A representation of the solution of a linear game. It should contain
  23     the value of the game, and both players' strategies.
  24     """
  25     def __init__(self, game_value, p1_optimal, p2_optimal):
  26         """
  27         Create a new Solution object from a game value and two optimal
  28         strategies for the players.
  29         """
  30         self._game_value = game_value
  31         self._player1_optimal = p1_optimal
  32         self._player2_optimal = p2_optimal
  33
  34     def __str__(self):
  35         """
  36         Return a string describing the solution of a linear game.
  37
  38         The three data that are described are,
  39
  40           * The value of the game.
  41           * The optimal strategy of player one.
  42           * The optimal strategy of player two.
  43
  44         EXAMPLES:
  45
  46            >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
  47            Game value: 10.0000000
  48            Player 1 optimal:
  49              [ 1]
  50              [ 2]
  51            Player 2 optimal:
  52              [ 3]
  53              [ 4]
  54
  55         """
  56         tpl = 'Game value: {:.7f}\n' \
  57               'Player 1 optimal:{:s}\n' \
  58               'Player 2 optimal:{:s}'
  59
  60         p1_str = '\n{!s}'.format(self.player1_optimal())
  61         p1_str = '\n  '.join(p1_str.splitlines())
  62         p2_str = '\n{!s}'.format(self.player2_optimal())
  63         p2_str = '\n  '.join(p2_str.splitlines())
  64
  65         return tpl.format(self.game_value(), p1_str, p2_str)
  66
  67
  68     def game_value(self):
  69         """
  70         Return the game value for this solution.
  71         """
  72         return self._game_value
  73
  74
  75     def player1_optimal(self):
  76         """
  77         Return player one's optimal strategy in this solution.
  78         """
  79         return self._player1_optimal
  80
  81
  82     def player2_optimal(self):
  83         """
  84         Return player two's optimal strategy in this solution.
  85         """
  86         return self._player2_optimal
  87
  88
  89 class SymmetricLinearGame:
  90     """
  91     A representation of a symmetric linear game.
  92
  93     The data for a linear game are,
  94
  95       * A "payoff" operator ``L``.
  96       * A cone ``K``.
  97       * A point ``e`` in the interior of ``K``.
  98       * A point ``f`` in the interior of the dual of ``K``.
  99
 100     In a symmetric game, the cone ``K`` is be self-dual. We therefore
 101     name the two interior points ``e1`` and ``e2`` to indicate that
 102     they come from the same cone but are "chosen" by players one and
 103     two respectively.
 104
 105     The ambient space is assumed to be the span of ``K``.
 106     """
 107     def __init__(self, L, K, e1, e2):
 108         """
 109         INPUT:
 110
 111           - ``L`` -- an square matrix represented as a list of lists
 112              of real numbers. ``L`` itself is interpreted as a list of
 113              ROWS, which agrees with (for example) SageMath and NumPy,
 114              but not with CVXOPT (whose matrix constructor accepts a
 115              list of columns).
 116
 117           - ``K`` -- a SymmetricCone instance.
 118
 119           - ``e1`` -- the interior point of ``K`` belonging to player one;
 120             it can be of any enumerable type having the correct length.
 121
 122           - ``e2`` -- the interior point of ``K`` belonging to player two;
 123             it can be of any enumerable type having the correct length.
 124
 125         EXAMPLES:
 126
 127         Lists can (and probably should) be used for every argument:
 128
 129             >>> from cones import NonnegativeOrthant
 130             >>> K = NonnegativeOrthant(2)
 131             >>> L = [[1,0],[0,1]]
 132             >>> e1 = [1,1]
 133             >>> e2 = [1,1]
 134             >>> G = SymmetricLinearGame(L, K, e1, e2)
 135             >>> print(G)
 136             The linear game (L, K, e1, e2) where
 137               L = [ 1  0]
 138                   [ 0  1],
 139               K = Nonnegative orthant in the real 2-space,
 140               e1 = [ 1]
 141                    [ 1],
 142               e2 = [ 1]
 143                    [ 1].
 144
 145         The points ``e1`` and ``e2`` can also be passed as some other
 146         enumerable type (of the correct length) without much harm, since
 147         there is no row/column ambiguity:
 148
 149             >>> import cvxopt
 150             >>> import numpy
 151             >>> from cones import NonnegativeOrthant
 152             >>> K = NonnegativeOrthant(2)
 153             >>> L = [[1,0],[0,1]]
 154             >>> e1 = cvxopt.matrix([1,1])
 155             >>> e2 = numpy.matrix([1,1])
 156             >>> G = SymmetricLinearGame(L, K, e1, e2)
 157             >>> print(G)
 158             The linear game (L, K, e1, e2) where
 159               L = [ 1  0]
 160                   [ 0  1],
 161               K = Nonnegative orthant in the real 2-space,
 162               e1 = [ 1]
 163                    [ 1],
 164               e2 = [ 1]
 165                    [ 1].
 166
 167         However, ``L`` will always be intepreted as a list of rows, even
 168         if it is passed as a ``cvxopt.base.matrix`` which is otherwise
 169         indexed by columns:
 170
 171             >>> import cvxopt
 172             >>> from cones import NonnegativeOrthant
 173             >>> K = NonnegativeOrthant(2)
 174             >>> L = [[1,2],[3,4]]
 175             >>> e1 = [1,1]
 176             >>> e2 = e1
 177             >>> G = SymmetricLinearGame(L, K, e1, e2)
 178             >>> print(G)
 179             The linear game (L, K, e1, e2) where
 180               L = [ 1  2]
 181                   [ 3  4],
 182               K = Nonnegative orthant in the real 2-space,
 183               e1 = [ 1]
 184                    [ 1],
 185               e2 = [ 1]
 186                    [ 1].
 187             >>> L = cvxopt.matrix(L)
 188             >>> print(L)
 189             [ 1  3]
 190             [ 2  4]
 191             <BLANKLINE>
 192             >>> G = SymmetricLinearGame(L, K, e1, e2)
 193             >>> print(G)
 194             The linear game (L, K, e1, e2) where
 195               L = [ 1  2]
 196                   [ 3  4],
 197               K = Nonnegative orthant in the real 2-space,
 198               e1 = [ 1]
 199                    [ 1],
 200               e2 = [ 1]
 201                    [ 1].
 202         """
 203         self._K = K
 204         self._e1 = matrix(e1, (K.dimension(), 1))
 205         self._e2 = matrix(e2, (K.dimension(), 1))
 206
 207         # Our input ``L`` is indexed by rows but CVXOPT matrices are
 208         # indexed by columns, so we need to transpose the input before
 209         # feeding it to CVXOPT.
 210         self._L = matrix(L, (K.dimension(), K.dimension())).trans()
 211
 212         if not K.contains_strict(self._e1):
 213             raise ValueError('the point e1 must lie in the interior of K')
 214
 215         if not K.contains_strict(self._e2):
 216             raise ValueError('the point e2 must lie in the interior of K')
 217
 218     def __str__(self):
 219         """
 220         Return a string representatoin of this game.
 221
 222         EXAMPLES:
 223
 224             >>> from cones import NonnegativeOrthant
 225             >>> K = NonnegativeOrthant(3)
 226             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 227             >>> e1 = [1,1,1]
 228             >>> e2 = [1,2,3]
 229             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 230             >>> print(SLG)
 231             The linear game (L, K, e1, e2) where
 232               L = [  1  -5 -15]
 233                   [ -1   2  -3]
 234                   [-12 -15   1],
 235               K = Nonnegative orthant in the real 3-space,
 236               e1 = [ 1]
 237                    [ 1]
 238                    [ 1],
 239               e2 = [ 1]
 240                    [ 2]
 241                    [ 3].
 242
 243         """
 244         tpl = 'The linear game (L, K, e1, e2) where\n' \
 245               '  L = {:s},\n' \
 246               '  K = {!s},\n' \
 247               '  e1 = {:s},\n' \
 248               '  e2 = {:s}.'
 249         indented_L = '\n      '.join(str(self._L).splitlines())
 250         indented_e1 = '\n       '.join(str(self._e1).splitlines())
 251         indented_e2 = '\n       '.join(str(self._e2).splitlines())
 252         return tpl.format(indented_L, str(self._K), indented_e1, indented_e2)
 253
 254
 255     def solution(self):
 256         """
 257         Solve this linear game and return a Solution object.
 258
 259         OUTPUT:
 260
 261         If the cone program associated with this game could be
 262         successfully solved, then a Solution object containing the
 263         game's value and optimal strategies is returned. If the game
 264         could *not* be solved -- which should never happen -- then a
 265         GameUnsolvableException is raised. It can be printed to get the
 266         raw output from CVXOPT.
 267
 268         EXAMPLES:
 269
 270         This example is computed in Gowda and Ravindran in the section
 271         "The value of a Z-transformation":
 272
 273             >>> from cones import NonnegativeOrthant
 274             >>> K = NonnegativeOrthant(3)
 275             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 276             >>> e1 = [1,1,1]
 277             >>> e2 = [1,1,1]
 278             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 279             >>> print(SLG.solution())
 280             Game value: -6.1724138
 281             Player 1 optimal:
 282               [ 0.5517241]
 283               [-0.0000000]
 284               [ 0.4482759]
 285             Player 2 optimal:
 286               [0.4482759]
 287               [0.0000000]
 288               [0.5517241]
 289
 290         The value of the following game can be computed using the fact
 291         that the identity is invertible:
 292
 293             >>> from cones import NonnegativeOrthant
 294             >>> K = NonnegativeOrthant(3)
 295             >>> L = [[1,0,0],[0,1,0],[0,0,1]]
 296             >>> e1 = [1,2,3]
 297             >>> e2 = [4,5,6]
 298             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 299             >>> print(SLG.solution())
 300             Game value: 0.0312500
 301             Player 1 optimal:
 302               [0.0312500]
 303               [0.0625000]
 304               [0.0937500]
 305             Player 2 optimal:
 306               [0.1250000]
 307               [0.1562500]
 308               [0.1875000]
 309
 310         """
 311         # The cone "C" that appears in the statement of the CVXOPT
 312         # conelp program.
 313         C = CartesianProduct(self._K, self._K)
 314
 315         # The column vector "b" that appears on the right-hand side of
 316         # Ax = b in the statement of the CVXOPT conelp program.
 317         b = matrix([1], tc='d')
 318
 319         # A column of zeros that fits K.
 320         zero = matrix(0, (self._K.dimension(), 1), tc='d')
 321
 322         # The column vector "h" that appears on the right-hand side of
 323         # Gx + s = h in the statement of the CVXOPT conelp program.
 324         h = matrix([zero, zero])
 325
 326         # The column vector "c" that appears in the objective function
 327         # value <c,x> in the statement of the CVXOPT conelp program.
 328         c = matrix([-1, zero])
 329
 330         # The matrix "G" that appears on the left-hand side of Gx + s = h
 331         # in the statement of the CVXOPT conelp program.
 332         G = append_row(append_col(zero, -identity(self._K.dimension())),
 333                        append_col(self._e1, -self._L))
 334
 335         # The matrix "A" that appears on the right-hand side of Ax = b
 336         # in the statement of the CVXOPT conelp program.
 337         A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
 338
 339         # Actually solve the thing and obtain a dictionary describing
 340         # what happened.
 341         soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
 342
 343         # The "status" field contains "optimal" if everything went
 344         # according to plan. Other possible values are "primal
 345         # infeasible", "dual infeasible", "unknown", all of which
 346         # mean we didn't get a solution. That should never happen,
 347         # because by construction our game has a solution, and thus
 348         # the cone program should too.
 349         if soln_dict['status'] != 'optimal':
 350             raise GameUnsolvableException(soln_dict)
 351
 352         p1_value = soln_dict['x'][0]
 353         p1_optimal = soln_dict['x'][1:]
 354         p2_optimal = soln_dict['z'][self._K.dimension():]
 355
 356         return Solution(p1_value, p1_optimal, p2_optimal)
 357
 358     def dual(self):
 359         """
 360         Return the dual game to this game.
 361
 362         EXAMPLES:
 363
 364             >>> from cones import NonnegativeOrthant
 365             >>> K = NonnegativeOrthant(3)
 366             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
 367             >>> e1 = [1,1,1]
 368             >>> e2 = [1,2,3]
 369             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
 370             >>> print(SLG.dual())
 371             The linear game (L, K, e1, e2) where
 372               L = [  1  -1 -12]
 373                   [ -5   2 -15]
 374                   [-15  -3   1],
 375               K = Nonnegative orthant in the real 3-space,
 376               e1 = [ 1]
 377                    [ 2]
 378                    [ 3],
 379               e2 = [ 1]
 380                    [ 1]
 381                    [ 1].
 382
 383         """
 384         return SymmetricLinearGame(self._L, # It will be transposed in __init__().
 385                                    self._K, # Since "K" is symmetric.
 386                                    self._e2,
 387                                    self._e1)
 388
 389
 390 class SymmetricLinearGameTest(TestCase):
 391
 392     def assertEqualWithinTol(self, first, second):
 393         """
 394         Test that ``first`` and ``second`` are equal within our default
 395         tolerance.
 396         """
 397         self.assertTrue(abs(first - second) < options.ABS_TOL)
 398
 399
 400     def test_solution_exists(self):
 401         """
 402         Every linear game has a solution, so we should be able to solve
 403         every symmetric linear game. Pick some parameters randomly and
 404         give it a shot.
 405         """
 406         from cones import NonnegativeOrthant
 407         from random import randint, uniform
 408         ambient_dim = randint(1,10)
 409         K = NonnegativeOrthant(ambient_dim)
 410         e1 = [uniform(0.1, 10) for idx in range(ambient_dim)]
 411         e2 = [uniform(0.1, 10) for idx in range(ambient_dim)]
 412         L = [[uniform(-10, 10) for i in range(ambient_dim)]
 413               for j in range(ambient_dim)]
 414         G = SymmetricLinearGame(L, K, e1, e2)
 415         soln = G.solution()
 416         L_matrix = matrix(L).trans()
 417         expected = inner_product(L_matrix*soln.player1_optimal(),
 418                                  soln.player2_optimal())
 419         self.assertEqualWithinTol(soln.game_value(), expected)