X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=dunshire%2Fgames.py;h=2d6d6dae8d75352e4876954ba0cc2eff454c67f7;hb=7080424243887787b6ff925d611a837e8229ec6e;hp=4451606c42c27d4e02d4cdfc30c469a1756d99e5;hpb=465df68194eff71cadf77281a3a612111d6b0785;p=dunshire.git diff --git a/dunshire/games.py b/dunshire/games.py index 4451606..2d6d6da 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -8,12 +8,11 @@ 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 -solvers.options['show_progress'] = options.VERBOSE - class Solution: """ @@ -222,7 +221,7 @@ class SymmetricLinearGame: e2 = [ 1] [ 2] [ 3], - Condition((L, K, e1, e2)) = 31.834895. + Condition((L, K, e1, e2)) = 31.834... Lists can (and probably should) be used for every argument:: @@ -241,7 +240,7 @@ class SymmetricLinearGame: [ 1], e2 = [ 1] [ 1], - Condition((L, K, e1, e2)) = 1.707107. + 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 @@ -264,7 +263,7 @@ class SymmetricLinearGame: [ 1], e2 = [ 1] [ 1], - Condition((L, K, e1, e2)) = 1.707107. + 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 @@ -286,7 +285,7 @@ class SymmetricLinearGame: [ 1], e2 = [ 1] [ 1], - Condition((L, K, e1, e2)) = 6.073771. + Condition((L, K, e1, e2)) = 6.073... >>> L = cvxopt.matrix(L) >>> print(L) [ 1 3] @@ -302,7 +301,7 @@ class SymmetricLinearGame: [ 1], e2 = [ 1] [ 1], - Condition((L, K, e1, e2)) = 6.073771. + Condition((L, K, e1, e2)) = 6.073... """ def __init__(self, L, K, e1, e2): @@ -324,8 +323,6 @@ class SymmetricLinearGame: if not self._e2 in K: raise ValueError('the point e2 must lie in the interior of K') - # Cached result of the self._zero() method. - self._zero_col = None def __str__(self): @@ -346,7 +343,206 @@ class SymmetricLinearGame: str(self._K), indented_e1, indented_e2, - self._condition()) + 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): @@ -354,11 +550,35 @@ class SymmetricLinearGame: 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 ``self.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] + + """ - if self._zero_col is None: - # Cache it, it's constant. - self._zero_col = matrix(0, (self._K.dimension(), 1), tc='d') - return self._zero_col + return matrix(0, (self.dimension(), 1), tc='d') def _A(self): @@ -367,25 +587,251 @@ class SymmetricLinearGame: 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 + self.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') + return matrix([0, self._e2], (1, self.dimension() + 1), 'd') + def _G(self): r""" Return the matrix ``G`` used in our CVXOPT construction. - Thus matrix ``G``that appears on the left-hand side of ``Gx + s = h`` + 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*self.dimension()``-by-``(1 + self.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), + identity_matrix = identity(self.dimension()) + return append_row(append_col(self._zero(), -identity_matrix), append_col(self._e1, -self._L)) - def solution(self): + def _c(self): """ - Solve this linear game and return a :class:`Solution`. + 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 ``self.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*self.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()]) + + + @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 + 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 ------- @@ -407,76 +853,68 @@ class SymmetricLinearGame: Examples -------- - This example is computed in Gowda and Ravindran in the section - "The value of a Z-transformation":: + 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) - >>> 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:: + >>> 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 * - >>> 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 + >>> 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.0312500] - [0.0625000] - [0.0937500] + [-0.0000000] + [ 8.4776631] Player 2 optimal: - [0.1250000] - [0.1562500] - [0.1875000] + [0.0000000] + [0.7158216] """ - # 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') - - # 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([self._zero(), self._zero()]) - - # The column vector "c" that appears in the objective function - # value in the statement of the CVXOPT conelp program. - c = matrix([-1, self._zero()]) - - # Actually solve the thing and obtain a dictionary describing - # what happened. try: - soln_dict = solvers.conelp(c, self._G(), h, - C.cvxopt_dims(), self._A(), b) - except ValueError as e: - if str(e) == 'math domain error': + 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 e + raise error # The optimal strategies are named ``p`` and ``q`` in the # background documentation, and we need to extract them from @@ -487,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 @@ -511,7 +949,7 @@ class SymmetricLinearGame: # 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) > 2*options.ABS_TOL: + 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) @@ -519,7 +957,88 @@ class SymmetricLinearGame: return Solution(p1_value, p1_optimal, p2_optimal) - def _condition(self): + 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.. + try: + return self._try_solution(options.ABS_TOL / 10) + except (PoorScalingException, GameUnsolvableException) as error: + # Well, that didn't work either. Let's verbosify the matrix + # output format before we allow the exception to be raised. + printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT + raise error + + + def condition(self): r""" Return the condition number of this game. @@ -547,7 +1066,7 @@ class SymmetricLinearGame: >>> e1 = [1] >>> e2 = e1 >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> actual = SLG._condition() + >>> actual = SLG.condition() >>> expected = 1.8090169943749477 >>> abs(actual - expected) < options.ABS_TOL True @@ -586,7 +1105,7 @@ class SymmetricLinearGame: e2 = [ 1] [ 1] [ 1], - Condition((L, K, e1, e2)) = 44.476765. + Condition((L, K, e1, e2)) = 44.476... """ # We pass ``self._L`` right back into the constructor, because