From 0bb1c93e213bf346b1c5da8ffa29a6649d55d82a Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Wed, 12 Oct 2016 12:18:53 -0400 Subject: [PATCH] Add tests for the "translated" and "negated" games (from a few corollaries). --- src/dunshire/games.py | 146 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 134 insertions(+), 12 deletions(-) diff --git a/src/dunshire/games.py b/src/dunshire/games.py index e85fe63..3db6dd0 100644 --- a/src/dunshire/games.py +++ b/src/dunshire/games.py @@ -14,7 +14,7 @@ from unittest import TestCase from cvxopt import matrix, printing, solvers from cones import CartesianProduct, IceCream, NonnegativeOrthant from errors import GameUnsolvableException -from matrices import append_col, append_row, identity, inner_product +from matrices import append_col, append_row, identity, inner_product, norm import options printing.options['dformat'] = options.FLOAT_FORMAT @@ -508,6 +508,14 @@ class SymmetricLinearGameTest(TestCase): Tests for the SymmetricLinearGame and Solution classes. """ + def random_square_matrix(self, dims): + """ + Generate a random square (``dims``-by-``dims``) matrix, + represented as a list of rows. + """ + return [[uniform(-10, 10) for i in range(dims)] for j in range(dims)] + + def random_orthant_params(self): """ Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a @@ -515,10 +523,9 @@ class SymmetricLinearGameTest(TestCase): """ ambient_dim = randint(1, 10) K = NonnegativeOrthant(ambient_dim) - e1 = [uniform(0.1, 10) for idx in range(K.dimension())] - e2 = [uniform(0.1, 10) for idx in range(K.dimension())] - L = [[uniform(-10, 10) for i in range(K.dimension())] - for j in range(K.dimension())] + e1 = [uniform(0.5, 10) for idx in range(K.dimension())] + e2 = [uniform(0.5, 10) for idx in range(K.dimension())] + L = self.random_square_matrix(K.dimension()) return (L, K, e1, e2) @@ -544,8 +551,7 @@ class SymmetricLinearGameTest(TestCase): fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0)) e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)] e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)] - L = [[uniform(-10, 10) for i in range(K.dimension())] - for j in range(K.dimension())] + L = self.random_square_matrix(K.dimension()) return (L, K, e1, e2) @@ -558,6 +564,15 @@ class SymmetricLinearGameTest(TestCase): self.assertTrue(abs(first - second) < options.ABS_TOL) + def assert_norm_within_tol(self, first, second): + """ + Test that ``first`` and ``second`` vectors are equal in the + sense that the norm of their difference is within our default + tolerance. + """ + self.assert_within_tol(norm(first - second), 0) + + def assert_solution_exists(self, L, K, e1, e2): """ Given the parameters needed to construct a SymmetricLinearGame, @@ -565,11 +580,16 @@ class SymmetricLinearGameTest(TestCase): """ G = SymmetricLinearGame(L, K, e1, e2) soln = G.solution() + + # The matrix() constructor assumes that ``L`` is a list of + # columns, so we transpose it to agree with what + # SymmetricLinearGame() thinks. L_matrix = matrix(L).trans() expected = inner_product(L_matrix*soln.player1_optimal(), soln.player2_optimal()) self.assert_within_tol(soln.game_value(), expected) + def test_solution_exists_nonnegative_orthant(self): """ Every linear game has a solution, so we should be able to solve @@ -581,6 +601,7 @@ class SymmetricLinearGameTest(TestCase): (L, K, e1, e2) = self.random_orthant_params() self.assert_solution_exists(L, K, e1, e2) + def test_solution_exists_ice_cream(self): """ Like :meth:`test_solution_exists_nonnegative_orthant`, except @@ -610,11 +631,13 @@ class SymmetricLinearGameTest(TestCase): our cone. """ (L, K, e1, e2) = self.random_orthant_params() - L = matrix(L) # So that we can scale it by alpha below. + # Make ``L`` a matrix so that we can scale it by alpha. Its + # random, so who cares if it gets transposed. + L = matrix(L) G1 = SymmetricLinearGame(L, K, e1, e2) value1 = G1.solution().game_value() - alpha = uniform(0.1, 10) + alpha = uniform(0.1, 10) G2 = SymmetricLinearGame(alpha*L, K, e1, e2) value2 = G2.solution().game_value() self.assert_within_tol(alpha*value1, value2) @@ -626,13 +649,112 @@ class SymmetricLinearGameTest(TestCase): except over the ice cream cone. """ (L, K, e1, e2) = self.random_icecream_params() - L = matrix(L) # So that we can scale it by alpha below. - + # Make ``L`` a matrix so that we can scale it by alpha. Its + # random, so who cares if it gets transposed. + L = matrix(L) G1 = SymmetricLinearGame(L, K, e1, e2) value1 = G1.solution().game_value() - alpha = uniform(0.1, 10) + alpha = uniform(0.1, 10) G2 = SymmetricLinearGame(alpha*L, K, e1, e2) value2 = G2.solution().game_value() self.assert_within_tol(alpha*value1, value2) + + def assert_translation_works(self, L, K, e1, e2): + """ + Check that translating ``L`` by alpha*(e1*e2.trans()) increases + the value of the associated game by alpha. + """ + e1 = matrix(e1, (K.dimension(), 1)) + e2 = matrix(e2, (K.dimension(), 1)) + G = SymmetricLinearGame(L, K, e1, e2) + G_soln = G.solution() + value_G = G_soln.game_value() + x_bar = G_soln.player1_optimal() + y_bar = G_soln.player2_optimal() + + alpha = uniform(-10, 10) + # Make ``L`` a CVXOPT matrix so that we can do math with + # it. Note that this gives us the "correct" representation of + # ``L`` (in agreement with what G has), but COLUMN indexed. + L = matrix(L).trans() + E = e1*e2.trans() + # Likewise, this is the "correct" representation of ``M``, but + # COLUMN indexed... + M = L + alpha*E + + # so we have to transpose it when we feed it to the constructor. + H = SymmetricLinearGame(M.trans(), K, e1, e2) + value_H = H.solution().game_value() + + # Make sure the same optimal pair works. + H_payoff = inner_product(M*x_bar, y_bar) + + self.assert_within_tol(value_G + alpha, value_H) + self.assert_within_tol(value_H, H_payoff) + + + def test_translation_orthant(self): + """ + Test that translation works over the nonnegative orthant. + """ + (L, K, e1, e2) = self.random_orthant_params() + self.assert_translation_works(L, K, e1, e2) + + + def test_translation_icecream(self): + """ + The same as :meth:`test_translation_orthant`, except over the + ice cream cone. + """ + (L, K, e1, e2) = self.random_icecream_params() + self.assert_translation_works(L, K, e1, e2) + + + def assert_opposite_game_works(self, L, K, e1, e2): + e1 = matrix(e1, (K.dimension(), 1)) + e2 = matrix(e2, (K.dimension(), 1)) + G = SymmetricLinearGame(L, K, e1, e2) + + # Make ``L`` a CVXOPT matrix so that we can do math with + # it. Note that this gives us the "correct" representation of + # ``L`` (in agreement with what G has), but COLUMN indexed. + L = matrix(L).trans() + + # Likewise, this is the "correct" representation of ``M``, but + # COLUMN indexed... + M = -L.trans() + + # so we have to transpose it when we feed it to the constructor. + H = SymmetricLinearGame(M.trans(), K, e2, e1) + + G_soln = G.solution() + x_bar = G_soln.player1_optimal() + y_bar = G_soln.player2_optimal() + H_soln = H.solution() + + # Make sure the switched optimal pair works. + H_payoff = inner_product(M*y_bar, x_bar) + + self.assert_within_tol(-G_soln.game_value(), H_soln.game_value()) + self.assert_within_tol(H_soln.game_value(), H_payoff) + + + def test_opposite_game_orthant(self): + """ + Check the value of the "opposite" game that gives rise to a + value that is the negation of the original game. Comes from + some corollary. + """ + (L, K, e1, e2) = self.random_orthant_params() + self.assert_opposite_game_works(L, K, e1, e2) + + + def test_opposite_game_icecream(self): + """ + Like :meth:`test_opposite_game_orthant`, except over the + ice-cream cone. + """ + (L, K, e1, e2) = self.random_icecream_params() + self.assert_opposite_game_works(L, K, e1, e2) -- 2.44.2