""" Symmetric linear games and their solutions. This module contains the main :class:`SymmetricLinearGame` class that 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 . import options printing.options['dformat'] = options.FLOAT_FORMAT 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] """ 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] """ 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 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) 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], Condition((L, K, e1, e2)) = 31.834... Lists can (and probably should) be used for every argument:: >>> from dunshire import * >>> 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], Condition((L, K, e1, e2)) = 1.707... 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 dunshire import * >>> 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], Condition((L, K, e1, e2)) = 1.707... 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 dunshire import * >>> 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], Condition((L, K, e1, e2)) = 6.073... >>> L = cvxopt.matrix(L) >>> print(L) [ 1 3] [ 2 4] >>> 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], Condition((L, K, e1, e2)) = 6.073... """ 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},\n' \ ' Condition((L, K, e1, e2)) = {:f}.' 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, self.condition()) def _zero(self): """ Return a column of zeros that fits ``K``. This is used in our CVXOPT construction. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``K.dimension()``-by-``1`` column vector of zeros. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = identity(3) >>> e1 = [1,1,1] >>> e2 = e1 >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._zero()) [0.0000000] [0.0000000] [0.0000000] """ return matrix(0, (self._K.dimension(), 1), tc='d') def _A(self): """ Return the matrix ``A`` used in our CVXOPT construction. This matrix ``A`` appears on the right-hand side of ``Ax = b`` in the statement of the CVXOPT conelp program. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``1``-by-``(1 + K.dimension())`` row vector. Its first entry is zero, and the rest are the entries of ``e2``. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[1,1,1],[1,1,1],[1,1,1]] >>> e1 = [1,1,1] >>> e2 = [1,2,3] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._A()) [0.0000000 1.0000000 2.0000000 3.0000000] """ return matrix([0, self._e2], (1, self._K.dimension() + 1), 'd') def _G(self): r""" Return the matrix ``G`` used in our CVXOPT construction. Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h`` in the statement of the CVXOPT conelp program. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``2*K.dimension()``-by-``1 + K.dimension()`` matrix. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[4,5,6],[7,8,9],[10,11,12]] >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._G()) [ 0.0000000 -1.0000000 0.0000000 0.0000000] [ 0.0000000 0.0000000 -1.0000000 0.0000000] [ 0.0000000 0.0000000 0.0000000 -1.0000000] [ 1.0000000 -4.0000000 -5.0000000 -6.0000000] [ 2.0000000 -7.0000000 -8.0000000 -9.0000000] [ 3.0000000 -10.0000000 -11.0000000 -12.0000000] """ I = identity(self._K.dimension()) return append_row(append_col(self._zero(), -I), append_col(self._e1, -self._L)) def _c(self): """ Return the vector ``c`` used in our CVXOPT construction. The column vector ``c`` appears in the objective function value ```` in the statement of the CVXOPT conelp program. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``K.dimension()``-by-``1`` column vector. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[4,5,6],[7,8,9],[10,11,12]] >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._c()) [-1.0000000] [ 0.0000000] [ 0.0000000] [ 0.0000000] """ return matrix([-1, self._zero()]) def _C(self): """ Return the cone ``C`` used in our CVXOPT construction. The cone ``C`` is the cone over which the conelp program takes place. Returns ------- CartesianProduct The cartesian product of ``K`` with itself. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[4,5,6],[7,8,9],[10,11,12]] >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._C()) Cartesian product of dimension 6 with 2 factors: * Nonnegative orthant in the real 3-space * Nonnegative orthant in the real 3-space """ return CartesianProduct(self._K, self._K) def _h(self): """ Return the ``h`` vector used in our CVXOPT construction. The ``h`` vector appears on the right-hand side of :math:`Gx + s = h` in the statement of the CVXOPT conelp program. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``2*K.dimension()``-by-``1`` column vector of zeros. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[4,5,6],[7,8,9],[10,11,12]] >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._h()) [0.0000000] [0.0000000] [0.0000000] [0.0000000] [0.0000000] [0.0000000] """ return matrix([self._zero(), self._zero()]) def _b(self): """ 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. .. warning:: It is not safe to cache any of the matrices passed to CVXOPT, because it can clobber them. Returns ------- matrix A ``1``-by-``1`` matrix containing a single entry ``1``. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(3) >>> L = [[4,5,6],[7,8,9],[10,11,12]] >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> print(SLG._b()) [1.0000000] """ return matrix([1], tc='d') def _try_solution(self, tolerance): """ Solve this linear game within ``tolerance``, if possible. This private function is the one that does all of the actual work for :meth:`solution`. This method accepts a ``tolerance``, and what :meth:`solution` does is call this method twice with two different tolerances. First it tries a strict tolerance, and then it tries a looser one. .. warning:: If you try to be smart and precompute the matrices used by this function (the ones passed to ``conelp``), then you're going to shoot yourself in the foot. CVXOPT can and will clobber some (but not all) of its input matrices. This isn't performance sensitive, so play it safe. Parameters ---------- tolerance : float The absolute tolerance to pass to the CVXOPT solver. 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). PoorScalingException If the game could not be solved because CVXOPT crashed while trying to take the square root of a negative number. Examples -------- This game can be solved easily, so the first attempt in :meth:`solution` should succeed:: >>> from dunshire import * >>> from dunshire.matrices import norm >>> 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) >>> s1 = SLG.solution() >>> s2 = SLG._try_solution(options.ABS_TOL) >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL True >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL True >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL True This game cannot be solved with the default tolerance, but it can be solved with a weaker one:: >>> from dunshire import * >>> from dunshire.options import ABS_TOL >>> L = [[ 0.58538005706658102767, 1.53764301129883040886], ... [-1.34901059721452210027, 1.50121179114155500756]] >>> K = NonnegativeOrthant(2) >>> e1 = [1.04537193228494995623, 1.39699624965841895374] >>> e2 = [0.35326554172108337593, 0.11795703527854853321] >>> SLG = SymmetricLinearGame(L,K,e1,e2) >>> print(SLG._try_solution(ABS_TOL / 10)) Traceback (most recent call last): ... dunshire.errors.GameUnsolvableException: Solution failed... >>> print(SLG._try_solution(ABS_TOL)) Game value: 9.1100945 Player 1 optimal: [-0.0000000] [ 8.4776631] Player 2 optimal: [0.0000000] [0.7158216] """ try: opts = {'show_progress': options.VERBOSE, 'abstol': tolerance} soln_dict = solvers.conelp(self._c(), self._G(), self._h(), self._C().cvxopt_dims(), self._A(), self._b(), options=opts) except ValueError as error: if str(error) == 'math domain error': # Oops, CVXOPT tried to take the square root of a # negative number. Report some details about the game # rather than just the underlying CVXOPT crash. raise PoorScalingException(self) else: raise error # The optimal strategies are named ``p`` and ``q`` in the # background documentation, and we need to extract them from # the CVXOPT ``x`` and ``z`` variables. The objective values # :math:`nu` and :math:`omega` can also be found in the CVXOPT # ``x`` and ``y`` variables; however, they're stored # conveniently as separate entries in the solution dictionary. 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(self, 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). # # The fudge factor of two is basically unjustified, but # makes intuitive sense when you imagine that the primal # value could be under the true optimal by ``ABS_TOL`` # and the dual value could be over by the same amount. # if abs(p1_value - p2_value) > tolerance: raise GameUnsolvableException(self, soln_dict) if (p1_optimal not in self._K) or (p2_optimal not in self._K): raise GameUnsolvableException(self, soln_dict) return Solution(p1_value, p1_optimal, p2_optimal) 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). PoorScalingException If the game could not be solved because CVXOPT crashed while trying to take the square root of a negative number. Examples -------- This example is computed in Gowda and Ravindran in the section "The value of a Z-transformation":: >>> from dunshire import * >>> 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.551...] [-0.000...] [ 0.448...] Player 2 optimal: [0.448...] [0.000...] [0.551...] The value of the following game can be computed using the fact that the identity is invertible:: >>> from dunshire import * >>> 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.031...] [0.062...] [0.093...] Player 2 optimal: [0.125...] [0.156...] [0.187...] """ try: # First try with a stricter tolerance. Who knows, it might # work. If it does, we prefer that solution. return self._try_solution(options.ABS_TOL / 10) except (PoorScalingException, GameUnsolvableException): # Ok, that didn't work. Let's try it with the default # tolerance, and whatever happens, happens. return self._try_solution(options.ABS_TOL) def condition(self): r""" Return the condition number of this game. In the CVXOPT construction of this game, two matrices ``G`` and ``A`` appear. When those matrices are nasty, numerical problems can show up. We define the condition number of this game to be the average of the condition numbers of ``G`` and ``A`` in the CVXOPT construction. If the condition number of this game is high, then you can expect numerical difficulty (such as :class:`PoorScalingException`). Returns ------- float A real number greater than or equal to one that measures how bad this game is numerically. Examples -------- >>> from dunshire import * >>> K = NonnegativeOrthant(1) >>> L = [[1]] >>> e1 = [1] >>> e2 = e1 >>> SLG = SymmetricLinearGame(L, K, e1, e2) >>> actual = SLG.condition() >>> expected = 1.8090169943749477 >>> abs(actual - expected) < options.ABS_TOL True """ return (condition_number(self._G()) + condition_number(self._A()))/2 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 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.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], Condition((L, K, e1, e2)) = 44.476... """ # 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)