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/lib/nash.pxi 6# Cython wrapper for Nash equilibrium computations 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 23cdef extern from "gambit/nash/enumpure.h": 24 cdef cppclass c_NashEnumPureStrategySolver "EnumPureStrategySolver": 25 c_NashEnumPureStrategySolver() 26 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 27 28 cdef cppclass c_NashEnumPureAgentSolver "EnumPureAgentSolver": 29 c_NashEnumPureAgentSolver() 30 c_List[c_MixedBehaviorProfileRational] Solve(c_Game) except +RuntimeError 31 32cdef class EnumPureStrategySolver(object): 33 cdef c_NashEnumPureStrategySolver *alg 34 35 def __cinit__(self): 36 self.alg = new c_NashEnumPureStrategySolver() 37 def __dealloc__(self): 38 del self.alg 39 def solve(self, Game game): 40 cdef c_List[c_MixedStrategyProfileRational] solns 41 cdef MixedStrategyProfileRational p 42 solns = self.alg.Solve(game.game) 43 ret = [ ] 44 for i in xrange(solns.Length()): 45 p = MixedStrategyProfileRational() 46 p.profile = copyitem_list_mspr(solns, i+1) 47 ret.append(p) 48 return ret 49 50cdef class EnumPureAgentSolver(object): 51 cdef c_NashEnumPureAgentSolver *alg 52 53 def __cinit__(self, p_stopAfter=0, p_maxDepth=0): 54 self.alg = new c_NashEnumPureAgentSolver() 55 def __dealloc__(self): 56 del self.alg 57 def solve(self, Game game): 58 cdef c_List[c_MixedBehaviorProfileRational] solns 59 cdef MixedBehaviorProfileRational p 60 solns = self.alg.Solve(game.game) 61 ret = [ ] 62 for i in xrange(solns.Length()): 63 p = MixedBehaviorProfileRational() 64 p.profile = copyitem_list_mbpr(solns, i+1) 65 ret.append(p) 66 return ret 67 68cdef extern from "gambit/nash/enummixed.h": 69 cdef cppclass c_NashEnumMixedStrategySolverDouble "EnumMixedStrategySolver<double>": 70 c_NashEnumMixedStrategySolverDouble() 71 c_List[c_MixedStrategyProfileDouble] Solve(c_Game) except +RuntimeError 72 73 cdef cppclass c_NashEnumMixedStrategySolverRational "EnumMixedStrategySolver<Rational>": 74 c_NashEnumMixedStrategySolverRational() 75 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 76 77 cdef cppclass c_NashEnumMixedLrsStrategySolver "EnumMixedLrsStrategySolver": 78 c_NashEnumMixedLrsStrategySolver() 79 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 80 81cdef class EnumMixedStrategySolverDouble(object): 82 cdef c_NashEnumMixedStrategySolverDouble *alg 83 84 def __cinit__(self): 85 self.alg = new c_NashEnumMixedStrategySolverDouble() 86 def __dealloc__(self): 87 del self.alg 88 def solve(self, Game game): 89 cdef c_List[c_MixedStrategyProfileDouble] solns 90 cdef MixedStrategyProfileDouble p 91 solns = self.alg.Solve(game.game) 92 ret = [ ] 93 for i in xrange(solns.Length()): 94 p = MixedStrategyProfileDouble() 95 p.profile = copyitem_list_mspd(solns, i+1) 96 ret.append(p) 97 return ret 98 99cdef class EnumMixedStrategySolverRational(object): 100 cdef c_NashEnumMixedStrategySolverRational *alg 101 102 def __cinit__(self): 103 self.alg = new c_NashEnumMixedStrategySolverRational() 104 def __dealloc__(self): 105 del self.alg 106 def solve(self, Game game): 107 cdef c_List[c_MixedStrategyProfileRational] solns 108 cdef MixedStrategyProfileRational p 109 solns = self.alg.Solve(game.game) 110 ret = [ ] 111 for i in xrange(solns.Length()): 112 p = MixedStrategyProfileRational() 113 p.profile = copyitem_list_mspr(solns, i+1) 114 ret.append(p) 115 return ret 116 117cdef class EnumMixedLrsStrategySolver(object): 118 cdef c_NashEnumMixedLrsStrategySolver *alg 119 120 def __cinit__(self): 121 self.alg = new c_NashEnumMixedLrsStrategySolver() 122 def __dealloc__(self): 123 del self.alg 124 def solve(self, Game game): 125 cdef c_List[c_MixedStrategyProfileRational] solns 126 cdef MixedStrategyProfileRational p 127 solns = self.alg.Solve(game.game) 128 ret = [ ] 129 for i in xrange(solns.Length()): 130 p = MixedStrategyProfileRational() 131 p.profile = copyitem_list_mspr(solns, i+1) 132 ret.append(p) 133 return ret 134 135cdef extern from "gambit/nash/lcp.h": 136 cdef cppclass c_NashLcpStrategySolverDouble "NashLcpStrategySolver<double>": 137 c_NashLcpStrategySolverDouble(int, int) 138 c_List[c_MixedStrategyProfileDouble] Solve(c_Game) except +RuntimeError 139 140 cdef cppclass c_NashLcpStrategySolverRational "NashLcpStrategySolver<Rational>": 141 c_NashLcpStrategySolverRational(int, int) 142 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 143 144 cdef cppclass c_NashLcpBehaviorSolverDouble "NashLcpBehaviorSolver<double>": 145 c_NashLcpBehaviorSolverDouble(int, int) 146 c_List[c_MixedBehaviorProfileDouble] Solve(c_Game) except +RuntimeError 147 148 cdef cppclass c_NashLcpBehaviorSolverRational "NashLcpBehaviorSolver<Rational>": 149 c_NashLcpBehaviorSolverRational(int, int) 150 c_List[c_MixedBehaviorProfileRational] Solve(c_Game) except +RuntimeError 151 152 153cdef class LCPBehaviorSolverDouble(object): 154 cdef c_NashLcpBehaviorSolverDouble *alg 155 156 def __cinit__(self, p_stopAfter=0, p_maxDepth=0): 157 self.alg = new c_NashLcpBehaviorSolverDouble(p_stopAfter, p_maxDepth) 158 def __dealloc__(self): 159 del self.alg 160 def solve(self, Game game): 161 cdef c_List[c_MixedBehaviorProfileDouble] solns 162 cdef MixedBehaviorProfileDouble p 163 solns = self.alg.Solve(game.game) 164 ret = [ ] 165 for i in xrange(solns.Length()): 166 p = MixedBehaviorProfileDouble() 167 p.profile = copyitem_list_mbpd(solns, i+1) 168 ret.append(p) 169 return ret 170 171cdef class LCPBehaviorSolverRational(object): 172 cdef c_NashLcpBehaviorSolverRational *alg 173 174 def __cinit__(self, p_stopAfter=0, p_maxDepth=0): 175 self.alg = new c_NashLcpBehaviorSolverRational(p_stopAfter, p_maxDepth) 176 def __dealloc__(self): 177 del self.alg 178 def solve(self, Game game): 179 cdef c_List[c_MixedBehaviorProfileRational] solns 180 cdef MixedBehaviorProfileRational p 181 solns = self.alg.Solve(game.game) 182 ret = [ ] 183 for i in xrange(solns.Length()): 184 p = MixedBehaviorProfileRational() 185 p.profile = copyitem_list_mbpr(solns, i+1) 186 ret.append(p) 187 return ret 188 189cdef class LCPStrategySolverDouble(object): 190 cdef c_NashLcpStrategySolverDouble *alg 191 192 def __cinit__(self, p_stopAfter=0, p_maxDepth=0): 193 self.alg = new c_NashLcpStrategySolverDouble(p_stopAfter, p_maxDepth) 194 def __dealloc__(self): 195 del self.alg 196 def solve(self, Game game): 197 cdef c_List[c_MixedStrategyProfileDouble] solns 198 cdef MixedStrategyProfileDouble p 199 solns = self.alg.Solve(game.game) 200 ret = [ ] 201 for i in xrange(solns.Length()): 202 p = MixedStrategyProfileDouble() 203 p.profile = copyitem_list_mspd(solns, i+1) 204 ret.append(p) 205 return ret 206 207cdef class LCPStrategySolverRational(object): 208 cdef c_NashLcpStrategySolverRational *alg 209 210 def __cinit__(self, p_stopAfter=0, p_maxDepth=0): 211 self.alg = new c_NashLcpStrategySolverRational(p_stopAfter, p_maxDepth) 212 def __dealloc__(self): 213 del self.alg 214 def solve(self, Game game): 215 cdef c_List[c_MixedStrategyProfileRational] solns 216 cdef MixedStrategyProfileRational p 217 solns = self.alg.Solve(game.game) 218 ret = [ ] 219 for i in xrange(solns.Length()): 220 p = MixedStrategyProfileRational() 221 p.profile = copyitem_list_mspr(solns, i+1) 222 ret.append(p) 223 return ret 224 225 226cdef extern from "tools/lp/nfglp.h": 227 cdef cppclass c_NashLpStrategySolverDouble "NashLpStrategySolver<double>": 228 c_NashLpStrategySolverDouble() 229 c_List[c_MixedStrategyProfileDouble] Solve(c_Game) except +RuntimeError 230 231 cdef cppclass c_NashLpStrategySolverRational "NashLpStrategySolver<Rational>": 232 c_NashLpStrategySolverRational() 233 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 234 235cdef extern from "tools/lp/efglp.h": 236 cdef cppclass c_NashLpBehavSolverDouble "NashLpBehavSolver<double>": 237 c_NashLpBehavSolverDouble() 238 c_List[c_MixedBehaviorProfileDouble] Solve(c_Game) except +RuntimeError 239 240 cdef cppclass c_NashLpBehavSolverRational "NashLpBehavSolver<Rational>": 241 c_NashLpBehavSolverRational() 242 c_List[c_MixedBehaviorProfileRational] Solve(c_Game) except +RuntimeError 243 244 245cdef class LPBehaviorSolverDouble(object): 246 cdef c_NashLpBehavSolverDouble *alg 247 248 def __cinit__(self): 249 self.alg = new c_NashLpBehavSolverDouble() 250 def __dealloc__(self): 251 del self.alg 252 def solve(self, Game game): 253 cdef c_List[c_MixedBehaviorProfileDouble] solns 254 cdef MixedBehaviorProfileDouble p 255 solns = self.alg.Solve(game.game) 256 ret = [ ] 257 for i in xrange(solns.Length()): 258 p = MixedBehaviorProfileDouble() 259 p.profile = copyitem_list_mbpd(solns, i+1) 260 ret.append(p) 261 return ret 262 263cdef class LPBehaviorSolverRational(object): 264 cdef c_NashLpBehavSolverRational *alg 265 266 def __cinit__(self): 267 self.alg = new c_NashLpBehavSolverRational() 268 def __dealloc__(self): 269 del self.alg 270 def solve(self, Game game): 271 cdef c_List[c_MixedBehaviorProfileRational] solns 272 cdef MixedBehaviorProfileRational p 273 solns = self.alg.Solve(game.game) 274 ret = [ ] 275 for i in xrange(solns.Length()): 276 p = MixedBehaviorProfileRational() 277 p.profile = copyitem_list_mbpr(solns, i+1) 278 ret.append(p) 279 return ret 280 281cdef class LPStrategySolverDouble(object): 282 cdef c_NashLpStrategySolverDouble *alg 283 284 def __cinit__(self): 285 self.alg = new c_NashLpStrategySolverDouble() 286 def __dealloc__(self): 287 del self.alg 288 def solve(self, Game game): 289 cdef c_List[c_MixedStrategyProfileDouble] solns 290 cdef MixedStrategyProfileDouble p 291 solns = self.alg.Solve(game.game) 292 ret = [ ] 293 for i in xrange(solns.Length()): 294 p = MixedStrategyProfileDouble() 295 p.profile = copyitem_list_mspd(solns, i+1) 296 ret.append(p) 297 return ret 298 299cdef class LPStrategySolverRational(object): 300 cdef c_NashLpStrategySolverRational *alg 301 302 def __cinit__(self): 303 self.alg = new c_NashLpStrategySolverRational() 304 def __dealloc__(self): 305 del self.alg 306 def solve(self, Game game): 307 cdef c_List[c_MixedStrategyProfileRational] solns 308 cdef MixedStrategyProfileRational p 309 solns = self.alg.Solve(game.game) 310 ret = [ ] 311 for i in xrange(solns.Length()): 312 p = MixedStrategyProfileRational() 313 p.profile = copyitem_list_mspr(solns, i+1) 314 ret.append(p) 315 return ret 316 317 318cdef extern from "gambit/nash/simpdiv.h": 319 cdef cppclass c_NashSimpdivStrategySolver "NashSimpdivStrategySolver": 320 c_NashSimpdivStrategySolver() 321 c_List[c_MixedStrategyProfileRational] Solve(c_Game) except +RuntimeError 322 c_List[c_MixedStrategyProfileRational] Solve(c_MixedStrategyProfileRational) except +RuntimeError 323 324cdef class SimpdivStrategySolver(object): 325 cdef c_NashSimpdivStrategySolver *alg 326 327 def __cinit__(self): 328 self.alg = new c_NashSimpdivStrategySolver() 329 def __dealloc__(self): 330 del self.alg 331 def solve(self, Game game): 332 cdef c_List[c_MixedStrategyProfileRational] solns 333 cdef MixedStrategyProfileRational p 334 solns = self.alg.Solve(game.game) 335 ret = [ ] 336 for i in xrange(solns.Length()): 337 p = MixedStrategyProfileRational() 338 p.profile = copyitem_list_mspr(solns, i+1) 339 ret.append(p) 340 return ret 341 342cdef extern from "gambit/nash/ipa.h": 343 cdef cppclass c_NashIPAStrategySolver "NashIPAStrategySolver": 344 c_NashIPAStrategySolver() 345 c_List[c_MixedStrategyProfileDouble] Solve(c_Game) except +RuntimeError 346 347cdef class IPAStrategySolver(object): 348 cdef c_NashIPAStrategySolver *alg 349 350 def __cinit__(self): 351 self.alg = new c_NashIPAStrategySolver() 352 def __dealloc__(self): 353 del self.alg 354 def solve(self, Game game): 355 cdef c_List[c_MixedStrategyProfileDouble] solns 356 cdef MixedStrategyProfileDouble p 357 solns = self.alg.Solve(game.game) 358 ret = [ ] 359 for i in xrange(solns.Length()): 360 p = MixedStrategyProfileDouble() 361 p.profile = copyitem_list_mspd(solns, i+1) 362 ret.append(p) 363 return ret 364 365cdef extern from "gambit/nash/gnm.h": 366 cdef cppclass c_NashGNMStrategySolver "NashGNMStrategySolver": 367 c_NashGNMStrategySolver() 368 c_List[c_MixedStrategyProfileDouble] Solve(c_Game) except +RuntimeError 369 370cdef class GNMStrategySolver(object): 371 cdef c_NashGNMStrategySolver *alg 372 373 def __cinit__(self): 374 self.alg = new c_NashGNMStrategySolver() 375 def __dealloc__(self): 376 del self.alg 377 def solve(self, Game game): 378 cdef c_List[c_MixedStrategyProfileDouble] solns 379 cdef MixedStrategyProfileDouble p 380 solns = self.alg.Solve(game.game) 381 ret = [ ] 382 for i in xrange(solns.Length()): 383 p = MixedStrategyProfileDouble() 384 p.profile = copyitem_list_mspd(solns, i+1) 385 ret.append(p) 386 return ret 387 388cdef extern from "tools/logit/nfglogit.h": 389 cdef cppclass c_LogitQREMixedStrategyProfile "LogitQREMixedStrategyProfile": 390 c_LogitQREMixedStrategyProfile(c_Game) 391 c_LogitQREMixedStrategyProfile(c_LogitQREMixedStrategyProfile) 392 c_Game GetGame() 393 c_MixedStrategyProfileDouble GetProfile() 394 double GetLambda() 395 int MixedProfileLength() 396 double getitem "operator[]"(int) except +IndexError 397 398 cdef cppclass c_StrategicQREEstimator "StrategicQREEstimator": 399 c_StrategicQREEstimator() 400 c_LogitQREMixedStrategyProfile Estimate(c_LogitQREMixedStrategyProfile, 401 c_MixedStrategyProfileDouble, 402 double, double, double) except +RuntimeError 403 404cdef extern from "util.h": 405 c_LogitQREMixedStrategyProfile *copyitem_list_qrem "copyitem"(c_List[c_LogitQREMixedStrategyProfile], int) 406 407cdef extern from "nash.h": 408 c_LogitQREMixedStrategyProfile *_logit_estimate "logit_estimate"(c_MixedStrategyProfileDouble *) 409 c_LogitQREMixedStrategyProfile *_logit_atlambda "logit_atlambda"(c_Game, double) 410 c_List[c_LogitQREMixedStrategyProfile] _logit_principal_branch "logit_principal_branch"(c_Game, double) 411 412cdef class LogitQREMixedStrategyProfile(object): 413 cdef c_LogitQREMixedStrategyProfile *thisptr 414 def __init__(self, game=None): 415 if game is not None: 416 self.thisptr = new c_LogitQREMixedStrategyProfile((<Game>game).game) 417 def __dealloc__(self): 418 del self.thisptr 419 def __repr__(self): 420 return "LogitQREMixedStrategyProfile(lam=%f,profile=%s)" % (self.lam, self.profile) 421 422 def __len__(self): 423 return self.thisptr.MixedProfileLength() 424 def __getitem__(self, int i): 425 return self.thisptr.getitem(i+1) 426 427 property game: 428 def __get__(self): 429 cdef Game g 430 g = Game() 431 g.game = self.thisptr.GetGame() 432 return g 433 434 property lam: 435 def __get__(self): 436 return self.thisptr.GetLambda() 437 438 property profile: 439 def __get__(self): 440 cdef MixedStrategyProfileDouble profile 441 profile = MixedStrategyProfileDouble() 442 profile.profile = new c_MixedStrategyProfileDouble(deref(self.thisptr).GetProfile()) 443 return profile 444 445def logit_estimate(MixedStrategyProfileDouble p_profile): 446 """Estimate QRE corresponding to mixed strategy profile using 447 maximum likelihood along the principal branch. 448 """ 449 cdef LogitQREMixedStrategyProfile ret 450 ret = LogitQREMixedStrategyProfile() 451 ret.thisptr = _logit_estimate(p_profile.profile) 452 return ret 453 454def logit_atlambda(Game p_game, double p_lambda): 455 """Compute the first QRE along the principal branch with the given 456 lambda parameter. 457 """ 458 cdef LogitQREMixedStrategyProfile ret 459 ret = LogitQREMixedStrategyProfile() 460 ret.thisptr = _logit_atlambda(p_game.game, p_lambda) 461 return ret 462 463def logit_principal_branch(Game p_game, double p_maxLambda=100000.0): 464 cdef c_List[c_LogitQREMixedStrategyProfile] solns 465 cdef LogitQREMixedStrategyProfile p 466 solns = _logit_principal_branch(p_game.game, p_maxLambda) 467 ret = [ ] 468 for i in xrange(solns.Length()): 469 p = LogitQREMixedStrategyProfile() 470 p.thisptr = copyitem_list_qrem(solns, i+1) 471 ret.append(p) 472 return ret 473