tturocy
commented
4 years ago There are no time limits on those algorithms.
gambit-liap is not globally convergent - it is not guaranteed to converge to an equilibrium from a given starting point.
gambit-gnm is from the gametracer package and isn't native to Gambit. In principle it should be globally convergent, but in practice it might not be for numerical reasons for some perturbation rays - I cannot speak as to how well it is implemented internally in gametracer. However it is unclear even if it were implemented carefully that it would be feasible to solve your game. Govindan and Wilson quote running times from their implementation (see https://faculty-gsb.stanford.edu/wilson/PDF/Game%20Theory/A%20global%20newton%20method%20to%20compute%20Nash%20equilibria.pdf) It looks like their experience is for 3-player games, running times roughly double for each two strategies added. Assuming that and extrapolating to 50 strategies per player, that would imply an expected running time of about 53,000 hours to find an equilibrium.
Most likely your best hope for such a game would be gambit-logit - but in general games of that size are probably not feasible to solve if they have no structure you can exploit.
lanctot
Firstly, thank you for gambit and continued support all these years!
I am looking into computing a Nash equilibrium for an arbitrary large normal-form game (e.g. 3-player game with 50 strategies each). When I try to run
gambit-liapandgambit-gnm, I notice that the algorithm times out after a while and finishes without printing any output. On smaller games it terminates fast and prints out the equilibrium.I'm wondering if there is a time limit setting that I could increase, or even just set something some values in the source to be higher. Looking at GNM, there is a
STEPSparameter but from the docs it's not entirely clear that it's related to the default maximum time spent looking for an equilibrium.Thanks for any advice on this!