[dunshire.git] / src / dunshire / games.py

"""
Symmetric linear games and their solutions.

This module contains the main :class:`SymmetricLinearGame` class that
knows how to solve a linear game.
"""

# These few are used only for tests.
from math import sqrt
from random import randint, uniform
from unittest import TestCase

# These are mostly actually needed.
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, norm
import options

printing.options['dformat'] = options.FLOAT_FORMAT
solvers.options['show_progress'] = options.VERBOSE


class Solution:
    """
    A representation of the solution of a linear game. It should contain
    the value of the game, and both players' strategies.

    Examples
    --------

        >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
        Game value: 10.0000000
        Player 1 optimal:
          [ 1]
          [ 2]
        Player 2 optimal:
          [ 3]
          [ 4]

    """
    def __init__(self, game_value, p1_optimal, p2_optimal):
        """
        Create a new Solution object from a game value and two optimal
        strategies for the players.
        """
        self._game_value = game_value
        self._player1_optimal = p1_optimal
        self._player2_optimal = p2_optimal

    def __str__(self):
        """
        Return a string describing the solution of a linear game.

        The three data that are described are,

          * The value of the game.
          * The optimal strategy of player one.
          * The optimal strategy of player two.

        The two optimal strategy vectors are indented by two spaces.
        """
        tpl = 'Game value: {:.7f}\n' \
              'Player 1 optimal:{:s}\n' \
              'Player 2 optimal:{:s}'

        p1_str = '\n{!s}'.format(self.player1_optimal())
        p1_str = '\n  '.join(p1_str.splitlines())
        p2_str = '\n{!s}'.format(self.player2_optimal())
        p2_str = '\n  '.join(p2_str.splitlines())

        return tpl.format(self.game_value(), p1_str, p2_str)


    def game_value(self):
        """
        Return the game value for this solution.

        Examples
        --------

            >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
            >>> s.game_value()
            10

        """
        return self._game_value


    def player1_optimal(self):
        """
        Return player one's optimal strategy in this solution.

        Examples
        --------

            >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
            >>> print(s.player1_optimal())
            [ 1]
            [ 2]
            <BLANKLINE>

        """
        return self._player1_optimal


    def player2_optimal(self):
        """
        Return player two's optimal strategy in this solution.

        Examples
        --------

            >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
            >>> print(s.player2_optimal())
            [ 3]
            [ 4]
            <BLANKLINE>

        """
        return self._player2_optimal


class SymmetricLinearGame:
    r"""
    A representation of a symmetric linear game.

    The data for a symmetric linear game are,

      * A "payoff" operator ``L``.
      * A symmetric cone ``K``.
      * Two points ``e1`` and ``e2`` in the interior of ``K``.

    The ambient space is assumed to be the span of ``K``.

    With those data understood, the game is played as follows. Players
    one and two choose points :math:`x` and :math:`y` respectively, from
    their respective strategy sets,

    .. math::
        \begin{aligned}
            \Delta_{1}
            &=
            \left\{
              x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
            \right\}\\
            \Delta_{2}
            &=
            \left\{
              y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
            \right\}.
        \end{aligned}

    Afterwards, a "payout" is computed as :math:`\left\langle
    L\left(x\right), y \right\rangle` and is paid to player one out of
    player two's pocket. The game is therefore zero sum, and we suppose
    that player one would like to guarantee himself the largest minimum
    payout possible. That is, player one wishes to,

    .. math::
        \begin{aligned}
            \text{maximize }
              &\underset{y \in \Delta_{2}}{\min}\left(
                \left\langle L\left(x\right), y \right\rangle
              \right)\\
            \text{subject to } & x \in \Delta_{1}.
        \end{aligned}

    Player two has the simultaneous goal to,

    .. math::
        \begin{aligned}
            \text{minimize }
              &\underset{x \in \Delta_{1}}{\max}\left(
                \left\langle L\left(x\right), y \right\rangle
              \right)\\
            \text{subject to } & y \in \Delta_{2}.
        \end{aligned}

    These goals obviously conflict (the game is zero sum), but an
    existence theorem guarantees at least one optimal min-max solution
    from which neither player would like to deviate. This class is
    able to find such a solution.

    Parameters
    ----------

    L : list of list of float
        A matrix represented as a list of ROWS. This representation
        agrees with (for example) SageMath and NumPy, but not with CVXOPT
        (whose matrix constructor accepts a list of columns).

    K : :class:`SymmetricCone`
        The symmetric cone instance over which the game is played.

    e1 : iterable float
        The interior point of ``K`` belonging to player one; it
        can be of any iterable type having the correct length.

    e2 : iterable float
        The interior point of ``K`` belonging to player two; it
        can be of any enumerable type having the correct length.

    Raises
    ------

    ValueError
        If either ``e1`` or ``e2`` lie outside of the cone ``K``.

    Examples
    --------

        >>> from cones import NonnegativeOrthant
        >>> 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)
        The linear game (L, K, e1, e2) where
          L = [  1  -5 -15]
              [ -1   2  -3]
              [-12 -15   1],
          K = Nonnegative orthant in the real 3-space,
          e1 = [ 1]
               [ 1]
               [ 1],
          e2 = [ 1]
               [ 2]
               [ 3].

    Lists can (and probably should) be used for every argument::

        >>> from cones import NonnegativeOrthant
        >>> K = NonnegativeOrthant(2)
        >>> L = [[1,0],[0,1]]
        >>> e1 = [1,1]
        >>> e2 = [1,1]
        >>> G = SymmetricLinearGame(L, K, e1, e2)
        >>> print(G)
        The linear game (L, K, e1, e2) where
          L = [ 1  0]
              [ 0  1],
          K = Nonnegative orthant in the real 2-space,
          e1 = [ 1]
               [ 1],
          e2 = [ 1]
               [ 1].

    The points ``e1`` and ``e2`` can also be passed as some other
    enumerable type (of the correct length) without much harm, since
    there is no row/column ambiguity::

        >>> import cvxopt
        >>> import numpy
        >>> from cones import NonnegativeOrthant
        >>> K = NonnegativeOrthant(2)
        >>> L = [[1,0],[0,1]]
        >>> e1 = cvxopt.matrix([1,1])
        >>> e2 = numpy.matrix([1,1])
        >>> G = SymmetricLinearGame(L, K, e1, e2)
        >>> print(G)
        The linear game (L, K, e1, e2) where
          L = [ 1  0]
              [ 0  1],
          K = Nonnegative orthant in the real 2-space,
          e1 = [ 1]
               [ 1],
          e2 = [ 1]
               [ 1].

    However, ``L`` will always be intepreted as a list of rows, even
    if it is passed as a :class:`cvxopt.base.matrix` which is
    otherwise indexed by columns::

        >>> import cvxopt
        >>> from cones import NonnegativeOrthant
        >>> K = NonnegativeOrthant(2)
        >>> L = [[1,2],[3,4]]
        >>> e1 = [1,1]
        >>> e2 = e1
        >>> G = SymmetricLinearGame(L, K, e1, e2)
        >>> print(G)
        The linear game (L, K, e1, e2) where
          L = [ 1  2]
              [ 3  4],
          K = Nonnegative orthant in the real 2-space,
          e1 = [ 1]
               [ 1],
          e2 = [ 1]
               [ 1].
        >>> L = cvxopt.matrix(L)
        >>> print(L)
        [ 1  3]
        [ 2  4]
        <BLANKLINE>
        >>> G = SymmetricLinearGame(L, K, e1, e2)
        >>> print(G)
        The linear game (L, K, e1, e2) where
          L = [ 1  2]
              [ 3  4],
          K = Nonnegative orthant in the real 2-space,
          e1 = [ 1]
               [ 1],
          e2 = [ 1]
               [ 1].

    """
    def __init__(self, L, K, e1, e2):
        """
        Create a new SymmetricLinearGame object.
        """
        self._K = K
        self._e1 = matrix(e1, (K.dimension(), 1))
        self._e2 = matrix(e2, (K.dimension(), 1))

        # Our input ``L`` is indexed by rows but CVXOPT matrices are
        # indexed by columns, so we need to transpose the input before
        # feeding it to CVXOPT.
        self._L = matrix(L, (K.dimension(), K.dimension())).trans()

        if not self._e1 in K:
            raise ValueError('the point e1 must lie in the interior of K')

        if not self._e2 in K:
            raise ValueError('the point e2 must lie in the interior of K')

    def __str__(self):
        """
        Return a string representation of this game.
        """
        tpl = 'The linear game (L, K, e1, e2) where\n' \
              '  L = {:s},\n' \
              '  K = {!s},\n' \
              '  e1 = {:s},\n' \
              '  e2 = {:s}.'
        indented_L = '\n      '.join(str(self._L).splitlines())
        indented_e1 = '\n       '.join(str(self._e1).splitlines())
        indented_e2 = '\n       '.join(str(self._e2).splitlines())
        return tpl.format(indented_L, str(self._K), indented_e1, indented_e2)


    def solution(self):
        """
        Solve this linear game and return a :class:`Solution`.

        Returns
        -------

        :class:`Solution`
            A :class:`Solution` object describing the game's value and
            the optimal strategies of both players.

        Raises
        ------
        GameUnsolvableException
            If the game could not be solved (if an optimal solution to its
            associated cone program was not found).

        Examples
        --------

        This example is computed in Gowda and Ravindran in the section
        "The value of a Z-transformation"::

            >>> from cones import NonnegativeOrthant
            >>> 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)
            >>> print(SLG.solution())
            Game value: -6.1724138
            Player 1 optimal:
              [ 0.5517241]
              [-0.0000000]
              [ 0.4482759]
            Player 2 optimal:
              [0.4482759]
              [0.0000000]
              [0.5517241]

        The value of the following game can be computed using the fact
        that the identity is invertible::

            >>> from cones import NonnegativeOrthant
            >>> K = NonnegativeOrthant(3)
            >>> L = [[1,0,0],[0,1,0],[0,0,1]]
            >>> e1 = [1,2,3]
            >>> e2 = [4,5,6]
            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
            >>> print(SLG.solution())
            Game value: 0.0312500
            Player 1 optimal:
              [0.0312500]
              [0.0625000]
              [0.0937500]
            Player 2 optimal:
              [0.1250000]
              [0.1562500]
              [0.1875000]

        """
        # The cone "C" that appears in the statement of the CVXOPT
        # conelp program.
        C = CartesianProduct(self._K, self._K)

        # The column vector "b" that appears on the right-hand side of
        # Ax = b in the statement of the CVXOPT conelp program.
        b = matrix([1], tc='d')

        # A column of zeros that fits K.
        zero = matrix(0, (self._K.dimension(), 1), tc='d')

        # The column vector "h" that appears on the right-hand side of
        # Gx + s = h in the statement of the CVXOPT conelp program.
        h = matrix([zero, zero])

        # The column vector "c" that appears in the objective function
        # value <c,x> in the statement of the CVXOPT conelp program.
        c = matrix([-1, zero])

        # The matrix "G" that appears on the left-hand side of Gx + s = h
        # in the statement of the CVXOPT conelp program.
        G = append_row(append_col(zero, -identity(self._K.dimension())),
                       append_col(self._e1, -self._L))

        # The matrix "A" that appears on the right-hand side of Ax = b
        # in the statement of the CVXOPT conelp program.
        A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')

        # Actually solve the thing and obtain a dictionary describing
        # what happened.
        soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)

        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():]

        # The "status" field contains "optimal" if everything went
        # according to plan. Other possible values are "primal
        # infeasible", "dual infeasible", "unknown", all of which mean
        # we didn't get a solution. The "infeasible" ones are the
        # worst, since they indicate that CVXOPT is convinced the
        # problem is infeasible (and that cannot happen).
        if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
            raise GameUnsolvableException(soln_dict)
        elif soln_dict['status'] == 'unknown':
            # When we get a status of "unknown", we may still be able
            # to salvage a solution out of the returned
            # dictionary. Often this is the result of numerical
            # difficulty and we can simply check that the primal/dual
            # objectives match (within a tolerance) and that the
            # primal/dual optimal solutions are within the cone (to a
            # tolerance as well).
            if (abs(p1_value - p2_value) > options.ABS_TOL):
                raise GameUnsolvableException(soln_dict)
            if (p1_optimal not in self._K) or (p2_optimal not in self._K):
                raise GameUnsolvableException(soln_dict)

        return Solution(p1_value, p1_optimal, p2_optimal)


    def dual(self):
        r"""
        Return the dual game to this game.

        If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
        then its dual is :math:`G^{*} =
        \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
        is symmetric, :math:`K^{*} = K`.

        Examples
        --------

            >>> from cones import NonnegativeOrthant
            >>> 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.dual())
            The linear game (L, K, e1, e2) where
              L = [  1  -1 -12]
                  [ -5   2 -15]
                  [-15  -3   1],
              K = Nonnegative orthant in the real 3-space,
              e1 = [ 1]
                   [ 2]
                   [ 3],
              e2 = [ 1]
                   [ 1]
                   [ 1].

        """
        # We pass ``self._L`` right back into the constructor, because
        # it will be transposed there. And keep in mind that ``self._K``
        # is its own dual.
        return SymmetricLinearGame(self._L,
                                   self._K,
                                   self._e2,
                                   self._e1)


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
        random game over the nonnegative orthant.
        """
        ambient_dim = randint(1, 10)
        K = NonnegativeOrthant(ambient_dim)
        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)


    def random_icecream_params(self):
        """
        Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
        random game over the ice cream cone.
        """
        # Use a minimum dimension of two to avoid divide-by-zero in
        # the fudge factor we make up later.
        ambient_dim = randint(2, 10)
        K = IceCream(ambient_dim)
        e1 = [1] # Set the "height" of e1 to one
        e2 = [1] # And the same for e2

        # If we choose the rest of the components of e1,e2 randomly
        # between 0 and 1, then the largest the squared norm of the
        # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
        # need to make it less than one (the height of the cone) so
        # that the whole thing is in the cone. The norm of the
        # non-height part is sqrt(dim(K) - 1), and we can divide by
        # twice that.
        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 = self.random_square_matrix(K.dimension())

        return (L, K, e1, e2)


    def assert_within_tol(self, first, second):
        """
        Test that ``first`` and ``second`` are equal within our default
        tolerance.
        """
        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,
        ensure that that game has a 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)


    def test_solution_exists_nonnegative_orthant(self):
        """
        Every linear game has a solution, so we should be able to solve
        every symmetric linear game over the NonnegativeOrthant. Pick
        some parameters randomly and give it a shot. The resulting
        optimal solutions should give us the optimal game value when we
        apply the payoff operator to them.
        """
        (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
        over the ice cream cone.
        """
        (L, K, e1, e2) = self.random_icecream_params()
        self.assert_solution_exists(L, K, e1, e2)


    def test_negative_value_Z_operator(self):
        """
        Test the example given in Gowda/Ravindran of a Z-matrix with
        negative game value on the nonnegative orthant.
        """
        K = NonnegativeOrthant(2)
        e1 = [1,1]
        e2 = e1
        L = [[1,-2],[-2,1]]
        G = SymmetricLinearGame(L, K, e1, e2)
        self.assertTrue(G.solution().game_value() < -options.ABS_TOL)


    def test_nonnegative_scaling_orthant(self):
        """
        Test that scaling ``L`` by a nonnegative number scales the value
        of the game by the same number. Use the nonnegative orthant as
        our cone.
        """
        (L, K, e1, e2) = self.random_orthant_params()
        # 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)
        G2 = SymmetricLinearGame(alpha*L, K, e1, e2)
        value2 = G2.solution().game_value()
        self.assert_within_tol(alpha*value1, value2)


    def test_nonnegative_scaling_icecream(self):
        """
        The same test as :meth:`test_nonnegative_scaling_orthant`,
        except over the ice cream cone.
        """
        (L, K, e1, e2) = self.random_icecream_params()
        # 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)
        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)