1#
2# This file is part of Gambit
3# Copyright (c) 1994-2016, The Gambit Project (http://www.gambit-project.org)
4#
5# FILE: src/python/gambit/nhas.py
6# A set of utilities for computing Nash equilibria
7#
8# This program is free software; you can redistribute it and/or modify
9# it under the terms of the GNU General Public License as published by
10# the Free Software Foundation; either version 2 of the License, or
11# (at your option) any later version.
12#
13# This program is distributed in the hope that it will be useful,
14# but WITHOUT ANY WARRANTY; without even the implied warranty of
15# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16# GNU General Public License for more details.
17#
18# You should have received a copy of the GNU General Public License
19# along with this program; if not, write to the Free Software
20# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21#
22"""
23A set of utilities for computing Nash equilibria
24"""
25
26import sys
27import subprocess
28from fractions import Fraction
29from gambit.profiles import Solution
30
31class NashSolution(Solution):
32    def __init__(self, profile):
33        Solution.__init__(self, profile)
34    def __repr__(self):
35        return "<NashProfile for '%s': %s>" % (self._profile.game.title,
36                                               self._profile)
37
38
39class ExternalSolver(object):
40    """
41    Base class for managing calls to external programs.
42    """
43    def launch(self, prog, game):
44        """
45        Helper function for launching calls to external programs.
46        Calls the specified program 'prog', passing the game to standard
47        input in .efg format (if a tree) or .nfg format (if a table).
48        Returns the object referencing standard output of the external program.
49        """
50        p = subprocess.Popen("%s -q" % prog, shell=True,
51                             stdin=subprocess.PIPE, stdout=subprocess.PIPE,
52                             close_fds=True if sys.platform != "win32" else False)
53        child_stdin, child_stdout = p.stdin, p.stdout
54        child_stdin.write(game.write(format='native'))
55        # Need to close, or at least flush, stdin of the child, or else
56        # processing won't begin...
57        child_stdin.close()
58        return child_stdout
59
60    def _parse_output(self, stream, game, rational, extensive=False):
61        profiles = [ ]
62        for line in stream:
63            entries = line.strip().split(",")
64            if entries[0] != "NE":  continue
65            if extensive:
66                profile = game.mixed_behavior_profile(rational=rational)
67            else:
68                profile = game.mixed_strategy_profile(rational=rational)
69            for (i, p) in enumerate(entries[1:]):
70                if rational:
71                    profile[i] = Fraction(p)
72                else:
73                    profile[i] = float(p)
74            profiles.append(NashSolution(profile))
75        return profiles
76
77class ExternalEnumPureSolver(ExternalSolver):
78    """
79    Algorithm class to manage calls to external gambit-enumpure solver
80    for computing pure-strategy equilibria.
81    """
82    def solve(self, game, use_strategic=False):
83        if not game.is_perfect_recall:
84            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
85        command_line = "gambit-enumpure"
86        if use_strategic and game.is_tree:
87            command_line += " -S"
88        return self._parse_output(self.launch(command_line, game),
89                                  game, rational=True,
90                                  extensive=game.is_tree and not use_strategic)
91
92class ExternalLPSolver(ExternalSolver):
93    """
94    Algorithm class to manage calls to external gambit-lp solver
95    for computing equilibria in two-player games using linear programming.
96    """
97    def solve(self, game, rational=False, use_strategic=False):
98        if len(game.players) != 2:
99            raise RuntimeError("Method only valid for two-player games.")
100        if not game.is_const_sum:
101            raise RuntimeError("Method only valid for constant-sum games.")
102        if not game.is_perfect_recall:
103            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
104        if rational:
105            command_line = "gambit-lp"
106        else:
107            command_line = "gambit-lp -d 10"
108        if use_strategic and game.is_tree:
109            command_line += " -S"
110        return self._parse_output(self.launch(command_line, game),
111                                  game, rational,
112                                  extensive=game.is_tree and not use_strategic)
113
114class ExternalLCPSolver(ExternalSolver):
115    """
116    Algorithm class to manage calls to external gambit-lcp solver
117    for computing equilibria in two-player games using linear complementarity
118    programming.
119    """
120    def solve(self, game, rational=False, use_strategic=False):
121        if len(game.players) != 2:
122            raise RuntimeError("Method only valid for two-player games.")
123        if not game.is_perfect_recall:
124            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
125        if rational:
126            command_line = "gambit-lcp"
127        else:
128            command_line = "gambit-lcp -d 10"
129        if use_strategic and game.is_tree:
130            command_line += " -S"
131        return self._parse_output(self.launch(command_line, game),
132                                  game, rational,
133                                  extensive=game.is_tree and not use_strategic)
134
135class ExternalEnumMixedSolver(ExternalSolver):
136    """
137    Algorithm class to manage calls to external gambit-enummixed solver
138    for computing equilibria in two-player games using enumeration of extreme points.
139    """
140    def solve(self, game, rational=False):
141        if not game.is_perfect_recall:
142            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
143        if rational:
144            command_line = "gambit-enummixed"
145        else:
146            command_line = "gambit-enummixed -d 10"
147        return self._parse_output(self.launch(command_line, game),
148                                  game, rational)
149
150class ExternalSimpdivSolver(ExternalSolver):
151    """
152    Algorithm class to manage calls to external gambit-simpdiv solver
153    for computing equilibria in N-player games using simpicial subdivision.
154    """
155    def solve(self, game):
156        if not game.is_perfect_recall:
157            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
158        command_line = "gambit-simpdiv"
159        return self._parse_output(self.launch(command_line, game),
160                                  game, rational=True)
161
162class ExternalGlobalNewtonSolver(ExternalSolver):
163    """
164    Algorithm class to manage calls to external gambit-gnm solver
165    for computing equilibria in N-player games using the global Newton method.
166    """
167    def solve(self, game):
168        if not game.is_perfect_recall:
169            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
170        command_line = "gambit-gnm -d 10"
171        return self._parse_output(self.launch(command_line, game),
172                                  game, rational=False)
173
174class ExternalEnumPolySolver(ExternalSolver):
175    """
176    Algorithm class to manage calls to external gambit-enumpoly solver
177    for computing equilibria in N-player games systems of polynomial equations.
178    """
179    def solve(self, game, use_strategic=False):
180        if not game.is_perfect_recall:
181            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
182        command_line = "gambit-enumpoly -d 10"
183        if use_strategic and game.is_tree:
184            command_line += " -S"
185        return self._parse_output(self.launch(command_line, game),
186                                  game, rational=False,
187                                  extensive=game.is_tree and not use_strategic)
188
189class ExternalLyapunovSolver(ExternalSolver):
190    """
191    Algorithm class to manage calls to external gambit-liap solver
192    for computing equilibria in N-player games using Lyapunov function minimization.
193    """
194    def solve(self, game, use_strategic=False):
195        if not game.is_perfect_recall:
196            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
197        command_line = "gambit-liap -d 10"
198        if use_strategic and game.is_tree:
199            command_line += " -S"
200        return self._parse_output(self.launch(command_line, game),
201                                  game, rational=False,
202                                  extensive=game.is_tree and not use_strategic)
203
204class ExternalIteratedPolymatrixSolver(ExternalSolver):
205    """
206    Algorithm class to manage calls to external gambit-ipa solver
207    for computing equilibria in N-player games using iterated polymatrix approximation.
208    """
209    def solve(self, game):
210        if not game.is_perfect_recall:
211            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
212        command_line = "gambit-ipa -d 10"
213        return self._parse_output(self.launch(command_line, game),
214                                  game, rational=False)
215
216class ExternalLogitSolver(ExternalSolver):
217    """
218    Algorithm class to manage calls to external gambit-logit solver
219    for computing equilibria in N-player games using quantal response equilibrium.
220    """
221    def solve(self, game, use_strategic=False):
222        if not game.is_perfect_recall:
223            raise RuntimeError("Computing equilibria of games with imperfect recall is not supported.")
224        profiles = [ ]
225        command_line = "gambit-logit -d 20 -e"
226        if use_strategic and game.is_tree:
227            command_line += " -S"
228        return self._parse_output(self.launch(command_line, game),
229                                  game, rational=False,
230                                  extensive=game.is_tree and not use_strategic)
231
232
233import gambit.lib.libgambit
234
235def enumpure_solve(game, use_strategic=True, external=False):
236    """Convenience function to solve game to find pure-strategy Nash equilibria.
237    """
238    if external:
239        return ExternalEnumPureSolve().solve(game, use_strategic=True)
240    if not game.is_tree or use_strategic:
241        alg = gambit.lib.libgambit.EnumPureStrategySolver()
242    else:
243        alg = gambit.lib.libgambit.EnumPureAgentSolver()
244    return alg.solve(game)
245
246def enummixed_solve(game, rational=True, external=False, use_lrs=False):
247    """Convenience function to solve two-player game to find all
248    mixed-strategy Nash equilibria.
249    """
250    if external:
251        return ExternalEnumMixedSolver().solve(game, rational=rational)
252    if use_lrs:
253        alg = gambit.lib.libgambit.EnumMixedLrsStrategySolver()
254    if rational:
255        alg = gambit.lib.libgambit.EnumMixedStrategySolverRational()
256    else:
257        alg = gambit.lib.libgambit.EnumMixedStrategySolverDouble()
258    return alg.solve(game)
259
260def lcp_solve(game, rational=True, use_strategic=False, external=False,
261              stop_after=None, max_depth=None):
262    """Convenience function to solve game using an appropriate linear
263    complementarity solver.
264    """
265    if stop_after is None: stop_after = 0
266    if max_depth is None:  max_depth = 0
267    if external:
268        return ExternalLCPSolver().solve(game, rational=rational,
269                                         use_strategic=use_strategic)
270    if not game.is_tree or use_strategic:
271        if rational:
272            alg = gambit.lib.libgambit.LCPStrategySolverRational(stop_after, max_depth)
273        else:
274            alg = gambit.lib.libgambit.LCPStrategySolverDouble(stop_after, max_depth)
275    else:
276        if rational:
277            alg = gambit.lib.libgambit.LCPBehaviorSolverRational(stop_after, max_depth)
278        else:
279            alg = gambit.lib.libgambit.LCPBehaviorSolverDouble(stop_after, max_depth)
280    return alg.solve(game)
281
282def lp_solve(game, rational=True, use_strategic=False, external=False):
283    """Convenience function to solve game using an appropriate linear
284    programming solver.
285    """
286    if external:
287        return ExternalLPSolver().solve(game, rational=rational,
288                                         use_strategic=use_strategic)
289    if not game.is_tree or use_strategic:
290        if rational:
291            alg = gambit.lib.libgambit.LPStrategySolverRational()
292        else:
293            alg = gambit.lib.libgambit.LPStrategySolverDouble()
294    else:
295        if rational:
296            alg = gambit.lib.libgambit.LPBehaviorSolverRational()
297        else:
298            alg = gambit.lib.libgambit.LPBehaviorSolverDouble()
299    return alg.solve(game)
300
301def simpdiv_solve(game, external=False):
302    """Convenience function to solve game to find a mixed-strategy
303    Nash equilibrium using simplicial subdivision.
304    """
305    if external:
306        return ExternalSimpdivSolver().solve(game)
307    alg = gambit.lib.libgambit.SimpdivStrategySolver()
308    return alg.solve(game)
309
310def ipa_solve(game, external=False):
311    """Convenience function to solve game to find a mixed-strategy
312    Nash equilibrium using iterated polymatrix appoximation.
313    """
314    if external:
315        return ExternalIPASolver().solve(game)
316    alg = gambit.lib.libgambit.IPAStrategySolver()
317    return alg.solve(game)
318
319def gnm_solve(game, external=False):
320    """Convenience function to solve game to find mixed-strategy
321    Nash equilibria using the global Newton method.
322    """
323    if external:
324        return ExternalGNMSolver().solve(game)
325    alg = gambit.lib.libgambit.GNMStrategySolver()
326    return alg.solve(game)
327
328logit_estimate = gambit.lib.libgambit.logit_estimate
329logit_atlambda = gambit.lib.libgambit.logit_atlambda
330logit_principal_branch = gambit.lib.libgambit.logit_principal_branch
331
332