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