gambit
gambit copied to clipboard
gambitproject
FEAT: Incorporate Kontogiannis-Spirakis algorithm
Branch master15_ks (from commit 13d7918) contains an implementation of the Kontogiannis-Spirakis algorithm in Python, to compute a 2/3 well-supported approximate Nash equilibrium of a bimatrix game.
The initial commit implements the algorithm and provides a test suite (which tests run successfully).
A code review should be done to assess whether some of the routines should be moved or refactored - in particular potentially useful general-purpose routines for converting to/from numpy matrices to games are included.
Some thought should be given to how this fits vis-a-vis the exact Nash computation methods, in terms of the object hierarchy for game solutions.
Finally, relevant documentation should be added as appropriate.
A code review should be done to assess whether some of the routines should be moved or refactored - in particular potentially useful general-purpose routines for converting to/from numpy matrices to games are included.
To clarify are you looking for someone to perform a review?
TBH I haven't even given this task any thought since I posted it; I posted it just so it wouldn't get forgotten!
very good, thanks! --Bernhard
- Ted Turocy [email protected] [09-04-2015 07:58:29 -0700]:
TBH I haven't even given this task any thought since I posted it; I posted it just so it wouldn't get forgotten!
Reply to this email directly or view it on GitHub: https://github.com/gambitproject/gambit/issues/145#issuecomment-91255368
Prof Bernhard von Stengel email: [email protected] Department of Mathematics http://www.maths.lse.ac.uk/Personal/stengel London School of Economics phone: +44-20-7955 6438 (office) Houghton St, Room COL 4.12 +44-20-7226 2325 (home) London WC2A 2AE, United Kingdom
Just to mention a few things.
As mentioned earlier, it would be best to move the conversion to and from numpy matrices to a place where it would fit in better rather than floating within the 'approx.py' and 'test_approx.py' files.
Besides that, the current implementation is good to go, most especially the definition of 'ApproximateSolution'. At some point, it might be best to have the implementation similar to that for Nash equilibria, where the algorithms are called externally.
Finally, with regards to extending this framework to include further algorithms, we've got implementations of most 2-player approximation algorithms in C/CPLEX, which could be ported. https://github.com/bimatrix-games/eps-nash-algos
Kind Regards, Tobenna P. Igwe.
