From 2b44481f8a79cbab75ddc0f73eea813b66e17d62 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Fri, 4 Nov 2016 19:13:21 -0400 Subject: [PATCH] Add game accessor methods for its L, K, e1, e2, and dimension. --- dunshire/games.py | 230 +++++++++++++++++++++++++++-- test/randomgen.py | 50 +++---- test/symmetric_linear_game_test.py | 17 +-- 3 files changed, 251 insertions(+), 46 deletions(-) diff --git a/dunshire/games.py b/dunshire/games.py index 08a6d6f..3575da5 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -8,7 +8,8 @@ knows how to solve a linear game. from cvxopt import matrix, printing, solvers from .cones import CartesianProduct from .errors import GameUnsolvableException, PoorScalingException -from .matrices import append_col, append_row, condition_number, identity +from .matrices import (append_col, append_row, condition_number, identity, + inner_product) from . import options printing.options['dformat'] = options.FLOAT_FORMAT @@ -345,6 +346,205 @@ class SymmetricLinearGame: self.condition()) + def L(self): + """ + Return the matrix ``L`` passed to the constructor. + + Returns + ------- + + matrix + The matrix that defines this game's :meth:`payoff` operator. + + Examples + -------- + + >>> from dunshire import * + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,2,3] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.L()) + [ 1 -5 -15] + [ -1 2 -3] + [-12 -15 1] + + + """ + return self._L + + + def K(self): + """ + Return the cone over which this game is played. + + Returns + ------- + + SymmetricCone + The :class:`SymmetricCone` over which this game is played. + + Examples + -------- + + >>> from dunshire import * + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,2,3] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.K()) + Nonnegative orthant in the real 3-space + + """ + return self._K + + + def e1(self): + """ + Return player one's interior point. + + Returns + ------- + + matrix + The point interior to :meth:`K` affiliated with player one. + + Examples + -------- + + >>> from dunshire import * + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,2,3] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.e1()) + [ 1] + [ 1] + [ 1] + + + """ + return self._e1 + + + def e2(self): + """ + Return player two's interior point. + + Returns + ------- + + matrix + The point interior to :meth:`K` affiliated with player one. + + Examples + -------- + + >>> from dunshire import * + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,2,3] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.e2()) + [ 1] + [ 2] + [ 3] + + + """ + return self._e2 + + + def payoff(self, strategy1, strategy2): + r""" + Return the payoff associated with ``strategy1`` and ``strategy2``. + + The payoff operator takes pairs of strategies to a real + number. For example, if player one's strategy is :math:`x` and + player two's strategy is :math:`y`, then the associated payoff + is :math:`\left\langle L\left(x\right),y \right\rangle` \in + \mathbb{R}. Here, :math:`L` denotes the same linear operator as + :meth:`L`. This method computes the payoff given the two + players' strategies. + + Parameters + ---------- + + strategy1 : matrix + Player one's strategy. + + strategy2 : matrix + Player two's strategy. + + Returns + ------- + + float + The payoff for the game when player one plays ``strategy1`` + and player two plays ``strategy2``. + + Examples + -------- + + The value of the game should be the payoff at the optimal + strategies:: + + >>> from dunshire import * + >>> from dunshire.options import ABS_TOL + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,1,1] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> soln = SLG.solution() + >>> x_bar = soln.player1_optimal() + >>> y_bar = soln.player2_optimal() + >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL + True + + """ + return inner_product(self.L()*strategy1, strategy2) + + + def dimension(self): + """ + Return the dimension of this game. + + The dimension of a game is not needed for the theory, but it is + useful for the implementation. We define the dimension of a game + to be the dimension of its underlying cone. Or what is the same, + the dimension of the space from which the strategies are chosen. + + Returns + ------- + + int + The dimension of the cone :meth:`K`, or of the space where + this game is played. + + Examples + -------- + + The dimension of a game over the nonnegative quadrant in the + plane should be two (the dimension of the plane):: + + >>> from dunshire import * + >>> K = NonnegativeOrthant(2) + >>> L = [[1,-5],[-1,2]] + >>> e1 = [1,1] + >>> e2 = [1,4] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> SLG.dimension() + 2 + + """ + return self.K().dimension() + + def _zero(self): """ Return a column of zeros that fits ``K``. @@ -360,7 +560,7 @@ class SymmetricLinearGame: ------- matrix - A ``K.dimension()``-by-``1`` column vector of zeros. + A ``self.dimension()``-by-``1`` column vector of zeros. Examples -------- @@ -378,7 +578,7 @@ class SymmetricLinearGame: """ - return matrix(0, (self._K.dimension(), 1), tc='d') + return matrix(0, (self.dimension(), 1), tc='d') def _A(self): @@ -397,7 +597,7 @@ class SymmetricLinearGame: ------- matrix - A ``1``-by-``(1 + K.dimension())`` row vector. Its first + A ``1``-by-``(1 + self.dimension())`` row vector. Its first entry is zero, and the rest are the entries of ``e2``. Examples @@ -414,7 +614,7 @@ class SymmetricLinearGame: """ - return matrix([0, self._e2], (1, self._K.dimension() + 1), 'd') + return matrix([0, self._e2], (1, self.dimension() + 1), 'd') @@ -434,7 +634,7 @@ class SymmetricLinearGame: ------- matrix - A ``2*K.dimension()``-by-``1 + K.dimension()`` matrix. + A ``2*self.dimension()``-by-``(1 + self.dimension())`` matrix. Examples -------- @@ -455,8 +655,8 @@ class SymmetricLinearGame: """ - I = identity(self._K.dimension()) - return append_row(append_col(self._zero(), -I), + identity_matrix = identity(self.dimension()) + return append_row(append_col(self._zero(), -identity_matrix), append_col(self._e1, -self._L)) @@ -476,7 +676,7 @@ class SymmetricLinearGame: ------- matrix - A ``K.dimension()``-by-``1`` column vector. + A ``self.dimension()``-by-``1`` column vector. Examples -------- @@ -544,7 +744,7 @@ class SymmetricLinearGame: ------- matrix - A ``2*K.dimension()``-by-``1`` column vector of zeros. + A ``2*self.dimension()``-by-``1`` column vector of zeros. Examples -------- @@ -568,13 +768,19 @@ class SymmetricLinearGame: return matrix([self._zero(), self._zero()]) - def _b(self): + + @staticmethod + def _b(): """ Return the ``b`` vector used in our CVXOPT construction. The vector ``b`` appears on the right-hand side of :math:`Ax = b` in the statement of the CVXOPT conelp program. + This method is static because the dimensions and entries of + ``b`` are known beforehand, and don't depend on any other + properties of the game. + .. warning:: It is not safe to cache any of the matrices passed to @@ -719,7 +925,7 @@ class SymmetricLinearGame: p1_value = -soln_dict['primal objective'] p2_value = -soln_dict['dual objective'] p1_optimal = soln_dict['x'][1:] - p2_optimal = soln_dict['z'][self._K.dimension():] + p2_optimal = soln_dict['z'][self.dimension():] # The "status" field contains "optimal" if everything went # according to plan. Other possible values are "primal diff --git a/test/randomgen.py b/test/randomgen.py index 9fee2f7..8c5ebfc 100644 --- a/test/randomgen.py +++ b/test/randomgen.py @@ -407,16 +407,16 @@ def random_ll_orthant_game(): """ G = random_orthant_game() - L = random_diagonal_matrix(G._K.dimension()) + L = random_diagonal_matrix(G.dimension()) # Replace the totally-random ``L`` with random Lyapunov-like one. - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) while G.condition() > MAX_COND: # Try again until the condition number is satisfactory. G = random_orthant_game() - L = random_diagonal_matrix(G._K.dimension()) - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + L = random_diagonal_matrix(G.dimension()) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) return G @@ -445,16 +445,16 @@ def random_ll_icecream_game(): """ G = random_icecream_game() - L = random_lyapunov_like_icecream(G._K.dimension()) + L = random_lyapunov_like_icecream(G.dimension()) # Replace the totally-random ``L`` with random Lyapunov-like one. - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) while G.condition() > MAX_COND: # Try again until the condition number is satisfactory. G = random_icecream_game() - L = random_lyapunov_like_icecream(G._K.dimension()) - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + L = random_lyapunov_like_icecream(G.dimension()) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) return G @@ -485,16 +485,16 @@ def random_positive_orthant_game(): """ G = random_orthant_game() - L = random_nonnegative_matrix(G._K.dimension()) + L = random_nonnegative_matrix(G.dimension()) # Replace the totally-random ``L`` with the random nonnegative one. - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) while G.condition() > MAX_COND: # Try again until the condition number is satisfactory. G = random_orthant_game() - L = random_nonnegative_matrix(G._K.dimension()) - G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + L = random_nonnegative_matrix(G.dimension()) + G = SymmetricLinearGame(L, G.K(), G.e1(), G.e2()) return G @@ -526,21 +526,21 @@ def random_nn_scaling(G): >>> (alpha, H) = random_nn_scaling(G) >>> alpha >= 0 True - >>> G._K == H._K + >>> G.K() == H.K() True - >>> norm(G._e1 - H._e1) < ABS_TOL + >>> norm(G.e1() - H.e1()) < ABS_TOL True - >>> norm(G._e2 - H._e2) < ABS_TOL + >>> norm(G.e2() - H.e2()) < ABS_TOL True """ alpha = random_nn_scalar() - H = SymmetricLinearGame(alpha*G._L.trans(), G._K, G._e1, G._e2) + H = SymmetricLinearGame(alpha*G.L().trans(), G.K(), G.e1(), G.e2()) while H.condition() > MAX_COND: # Loop until the condition number of H doesn't suck. alpha = random_nn_scalar() - H = SymmetricLinearGame(alpha*G._L.trans(), G._K, G._e1, G._e2) + H = SymmetricLinearGame(alpha*G.L().trans(), G.K(), G.e1(), G.e2()) return (alpha, H) @@ -571,23 +571,23 @@ def random_translation(G): >>> from dunshire.options import ABS_TOL >>> G = random_orthant_game() >>> (alpha, H) = random_translation(G) - >>> G._K == H._K + >>> G.K() == H.K() True - >>> norm(G._e1 - H._e1) < ABS_TOL + >>> norm(G.e1() - H.e1()) < ABS_TOL True - >>> norm(G._e2 - H._e2) < ABS_TOL + >>> norm(G.e2() - H.e2()) < ABS_TOL True """ alpha = random_scalar() - tensor_prod = G._e1 * G._e2.trans() - M = G._L + alpha*tensor_prod + tensor_prod = G.e1() * G.e2().trans() + M = G.L() + alpha*tensor_prod - H = SymmetricLinearGame(M.trans(), G._K, G._e1, G._e2) + H = SymmetricLinearGame(M.trans(), G.K(), G.e1(), G.e2()) while H.condition() > MAX_COND: # Loop until the condition number of H doesn't suck. alpha = random_scalar() - M = G._L + alpha*tensor_prod - H = SymmetricLinearGame(M.trans(), G._K, G._e1, G._e2) + M = G.L() + alpha*tensor_prod + H = SymmetricLinearGame(M.trans(), G.K(), G.e1(), G.e2()) return (alpha, H) diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py index 936a7e8..bba2f7c 100644 --- a/test/symmetric_linear_game_test.py +++ b/test/symmetric_linear_game_test.py @@ -66,8 +66,7 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ soln = G.solution() - expected = inner_product(G._L*soln.player1_optimal(), - soln.player2_optimal()) + expected = G.payoff(soln.player1_optimal(), soln.player2_optimal()) self.assert_within_tol(soln.game_value(), expected, G.condition()) @@ -171,7 +170,7 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 # Make sure the same optimal pair works. self.assert_within_tol(value2, - inner_product(H._L*x_bar, y_bar), + H.payoff(x_bar, y_bar), H.condition()) @@ -200,11 +199,11 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ # This is the "correct" representation of ``M``, but # COLUMN indexed... - M = -G._L.trans() + M = -G.L().trans() # so we have to transpose it when we feed it to the constructor. # Note: the condition number of ``H`` should be comparable to ``G``. - H = SymmetricLinearGame(M.trans(), G._K, G._e2, G._e1) + H = SymmetricLinearGame(M.trans(), G.K(), G.e2(), G.e1()) soln1 = G.solution() x_bar = soln1.player1_optimal() @@ -217,7 +216,7 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 # Make sure the switched optimal pair works. self.assert_within_tol(soln2.game_value(), - inner_product(M*y_bar, x_bar), + H.payoff(y_bar, x_bar), H.condition()) @@ -249,10 +248,10 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 y_bar = soln.player2_optimal() value = soln.game_value() - ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1) + ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1()) self.assert_within_tol(ip1, 0, G.condition()) - ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar) + ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar) self.assert_within_tol(ip2, 0, G.condition()) @@ -298,7 +297,7 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 # # See :meth:`assert_within_tol` for an explanation of the # fudge factors. - eigs = eigenvalues_re(G._L) + eigs = eigenvalues_re(G.L()) if soln.game_value() > EPSILON: # L should be positive stable -- 2.44.2