X-Git-Url: http://gitweb.michael.orlitzky.com/?p=dunshire.git;a=blobdiff_plain;f=dunshire%2Fgames.py;h=672810de8094df7c37005cd5106fe5b8175888c4;hp=2d6d6dae8d75352e4876954ba0cc2eff454c67f7;hb=5d752b41ea1f09292f9e64278ba81cf0b395c001;hpb=7080424243887787b6ff925d611a837e8229ec6e diff --git a/dunshire/games.py b/dunshire/games.py index 2d6d6da..672810d 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -335,12 +335,12 @@ class SymmetricLinearGame: ' 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()) + 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), + str(self.K()), indented_e1, indented_e2, self.condition()) @@ -581,7 +581,7 @@ class SymmetricLinearGame: return matrix(0, (self.dimension(), 1), tc='d') - def _A(self): + def A(self): """ Return the matrix ``A`` used in our CVXOPT construction. @@ -609,12 +609,12 @@ class SymmetricLinearGame: >>> e1 = [1,1,1] >>> e2 = [1,2,3] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._A()) + >>> print(SLG.A()) [0.0000000 1.0000000 2.0000000 3.0000000] """ - return matrix([0, self._e2], (1, self.dimension() + 1), 'd') + return matrix([0, self.e2()], (1, self.dimension() + 1), 'd') @@ -657,7 +657,7 @@ class SymmetricLinearGame: """ identity_matrix = identity(self.dimension()) return append_row(append_col(self._zero(), -identity_matrix), - append_col(self._e1, -self._L)) + append_col(self.e1(), -self.L())) def _c(self): @@ -698,7 +698,7 @@ class SymmetricLinearGame: return matrix([-1, self._zero()]) - def _C(self): + def C(self): """ Return the cone ``C`` used in our CVXOPT construction. @@ -720,7 +720,7 @@ class SymmetricLinearGame: >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._C()) + >>> 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 @@ -770,7 +770,7 @@ class SymmetricLinearGame: @staticmethod - def _b(): + def b(): """ Return the ``b`` vector used in our CVXOPT construction. @@ -801,7 +801,7 @@ class SymmetricLinearGame: >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._b()) + >>> print(SLG.b()) [1.0000000] @@ -809,29 +809,10 @@ class SymmetricLinearGame: 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. + def solution(self): + """ + Solve this linear game and return a :class:`Solution`. Returns ------- @@ -853,65 +834,112 @@ class SymmetricLinearGame: Examples -------- - This game can be solved easily, so the first attempt in - :meth:`solution` should succeed:: + This example is computed in Gowda and Ravindran in the section + "The value of a Z-transformation":: >>> 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 + >>> 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...] - This game cannot be solved with the default tolerance, but it - can be solved with a weaker one:: + 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...] + + This is another Gowda/Ravindran example that is supposed to have + a negative game value:: >>> from dunshire import * >>> from dunshire.options import ABS_TOL - >>> L = [[ 0.58538005706658102767, 1.53764301129883040886], - ... [-1.34901059721452210027, 1.50121179114155500756]] + >>> L = [[1, -2], [-2, 1]] + >>> K = NonnegativeOrthant(2) + >>> e1 = [1, 1] + >>> e2 = e1 + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> SLG.solution().game_value() < -ABS_TOL + True + + The following two games are problematic numerically, but we + should be able to solve them:: + + >>> from dunshire import * + >>> L = [[-0.95237953890954685221, 1.83474556206462535712], + ... [ 1.30481749924621448500, 1.65278664543326403447]] >>> 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 + >>> e1 = [0.95477167524644313001, 0.63270781756540095397] + >>> e2 = [0.39633793037154141370, 0.10239281495640320530] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.solution()) + Game value: 18.767... Player 1 optimal: - [-0.0000000] - [ 8.4776631] + [-0.000...] + [ 9.766...] Player 2 optimal: - [0.0000000] - [0.7158216] + [1.047...] + [0.000...] + + :: + + >>> from dunshire import * + >>> L = [[1.54159395026049472754, 2.21344728574316684799], + ... [1.33147433507846657541, 1.17913616272988108769]] + >>> K = NonnegativeOrthant(2) + >>> e1 = [0.39903040089404784307, 0.12377403622479113410] + >>> e2 = [0.15695181142215544612, 0.85527381344651265405] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.solution()) + Game value: 24.614... + Player 1 optimal: + [ 6.371...] + [-0.000...] + Player 2 optimal: + [2.506...] + [0.000...] """ try: - opts = {'show_progress': options.VERBOSE, 'abstol': tolerance} + opts = {'show_progress': False} soln_dict = solvers.conelp(self._c(), self._G(), self._h(), - self._C().cvxopt_dims(), - self._A(), - self._b(), + 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. + printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT raise PoorScalingException(self) else: raise error @@ -930,112 +958,48 @@ class SymmetricLinearGame: # 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). + # 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']: + printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT 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) + # The "optimal" and "unknown" results, we actually treat the + # same. Even if CVXOPT bails out due to numerical difficulty, + # it will have some candidate points in mind. If those + # candidates are good enough, we take them. We do the same + # check (perhaps pointlessly so) for "optimal" results. + # + # First we check that the primal/dual objective values are + # close enough (one could be low by ABS_TOL, the other high by + # it) because otherwise CVXOPT might return "unknown" and give + # us two points in the cone that are nowhere near optimal. + if abs(p1_value - p2_value) > 2*options.ABS_TOL: + printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT + raise GameUnsolvableException(self, soln_dict) - 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...] + # And we also check that the points it gave us belong to the + # cone, just in case... + if (p1_optimal not in self._K) or (p2_optimal not in self._K): + printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT + raise GameUnsolvableException(self, soln_dict) - """ - 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 + # For the game value, we could use any of: + # + # * p1_value + # * p2_value + # * (p1_value + p2_value)/2 + # * the game payoff + # + # We want the game value to be the payoff, however, so it + # makes the most sense to just use that, even if it means we + # can't test the fact that p1_value/p2_value are close to the + # payoff. + payoff = self.payoff(p1_optimal, p2_optimal) + return Solution(payoff, p1_optimal, p2_optimal) def condition(self): @@ -1072,7 +1036,7 @@ class SymmetricLinearGame: True """ - return (condition_number(self._G()) + condition_number(self._A()))/2 + return (condition_number(self._G()) + condition_number(self.A()))/2 def dual(self): @@ -1108,10 +1072,10 @@ class SymmetricLinearGame: Condition((L, K, e1, e2)) = 44.476... """ - # We pass ``self._L`` right back into the constructor, because + # 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) + return SymmetricLinearGame(self.L(), + self.K(), + self.e2(), + self.e1())