Add tests for the "translated" and "negated" games (from a few corollaries).

diff --git a/src/dunshire/games.py b/src/dunshire/games.py
index e85fe63ddcc425f8938adf85392fccddc755901d..3db6dd07c4163ea998fcdb9eb6abfeda17757db2 100644 (file)
--- 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 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
 import options
 
 printing.options['dformat'] = options.FLOAT_FORMAT


@@ -508,6 +508,14 @@ class SymmetricLinearGameTest(TestCase):
     Tests for the SymmetricLinearGame and Solution classes.
     """
 
     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
     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)
         """
         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)
 
 
         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)]
         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)
 
 
         return (L, K, e1, e2)
 


@@ -558,6 +564,15 @@ class SymmetricLinearGameTest(TestCase):
         self.assertTrue(abs(first - second) < options.ABS_TOL)
 
 
         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,
     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()
         """
         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)
 
         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
     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)
 
         (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
     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()
         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()
         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)
         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()
         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()
         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)
 
         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)