import gambit
The situation with games with three (or more) players is a bit more complex. There are several methods which can be used to compute equilibria for games with three or more players, but all have some limitations, whether theoretical, practical, or both.
We will use a three-player game as our example, in which each player has exactly two strategies each. This game has nine Nash equilibria, which is the maximum number of isolated equilibria a game of this dimension can have. It is also well-behaved in that the game continues to have nine equilibria even if payoffs are perturbed slightly.
g = gambit.Game.read_game("2x2x2.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))
1 | 2 | |
1 | 9,8,12 | 0,0,0 |
2 | 0,0,0 | 9,8,2 |
1 | 2 | |
1 | 0,0,0 | 3,4,6 |
2 | 3,4,6 | 0,0,0 |
For this example, I will run the various methods using the command-line tools via the shell. Several of these tools optionally print out some useful status information when run on the command-line, which is not (yet) logged and returned by the Python calls.
First up is simplicial subdivision, gambit-simpdiv
. This operates essentially like the proof of the Brouwer fixed point theorem: It divides up the space of mixed strategies into a "grid" of simplices, and follows a path along that grid. The grid is then refined, and the process repeated.
Each run of the algorithm requires a starting point in the space of mixed strategy profiles. Which equilibrium you find depends on your starting point, and there's no guarantee the equilibrium you find bears any clear relationship to your starting point (it could in principle be arbitrarily far away in the space of mixed strategy profiles).
!gambit-simpdiv 2x2x2.nfg
Compute Nash equilibria using simplicial subdivision Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL NE,1,0,1,0,1,0
!gambit-simpdiv -h
Compute Nash equilibria using simplicial subdivision Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL Usage: gambit-simpdiv [OPTIONS] [file] If file is not specified, attempts to read game from standard input. With no options, computes one approximate Nash equilibrium. Options: -g MULT granularity of grid refinement at each step (default is 2) -h, --help print this help message -r DENOM generate random starting points with denominator DENOM -n COUNT number of starting points to generate (requires -r) -s FILE file containing starting points -q quiet mode (suppresses banner) -V, --verbose verbose mode (shows intermediate output) -v, --version print version information (default is to only show equilibria)
!gambit-simpdiv -n 5 -r 16 -V 2x2x2.nfg
Compute Nash equilibria using simplicial subdivision Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL start,5/16,11/16,7/8,1/8,11/16,5/16 1/32,1,0,1,0,1,0 NE,1,0,1,0,1,0 start,3/4,1/4,11/16,5/16,3/8,5/8 1/32,1,0,1,0,1,0 NE,1,0,1,0,1,0 start,1/4,3/4,1,0,15/16,1/16 1/32,1,0,1,0,1,0 NE,1,0,1,0,1,0 start,9/16,7/16,15/16,1/16,1/4,3/4 1/32,1,0,1,0,1,0 NE,1,0,1,0,1,0 start,1,0,3/16,13/16,1,0 1/32,1,0,1,0,1,0 NE,1,0,1,0,1,0
The next two methods were proposed by Govindan and Wilson, and this implementation is based on the Gametracer package by Blum and Shelton. The global Newton method gambit-gnm
uses the idea of the structure theorem (as we encountered in Bagwell's example). It picks a perturbation vector of the payoffs of the game, goes far out enough in that "direction" in payoff space such that the game has a unique equilibrium, and then traces backwards towards the original game. As the path of equilibria is followed, it may cross the original game more than once, so it is possible that this method will find more than one equilibrium - but it will not necessarily find all of them, and which equilibria are found depends on the choice of the perturbation vector.
!gambit-gnm 2x2x2.nfg
Compute Nash equilibria using a global Newton method Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 NE,0.500000,0.500000,0.400000,0.600000,0.250000,0.750000 NE,0.400000,0.600000,0.500000,0.500000,0.333333,0.666667 NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000 NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000 NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667 NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000
!gambit-gnm -h
Compute Nash equilibria using a global Newton method Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL Usage: gambit-gnm [OPTIONS] [file] If file is not specified, attempts to read game from standard input. Options: -d DECIMALS show equilibria as floating point with DECIMALS digits -h, --help print this help message -n COUNT number of perturbation vectors to generate -s FILE file containing perturbation vectors -q quiet mode (suppresses banner) -V, --verbose verbose mode (shows intermediate output) -v, --version print version information (default is to only show equilibria)
We can use the -V
switch to understand a bit more how the equilibria are found. Each intermediate step shows, in the first column, the homotopy parameter (how much the perturbation vector is multiplied by). Each entry shows a "turning point" in the path.
!gambit-gnm -V 2x2x2.nfg
Compute Nash equilibria using a global Newton method Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL pert,0.611434,0.105483,0.189587,0.527330,0.210106,0.506811 start,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 -0.494119,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 -0.494119,0.750328,0.249672,0.000000,1.000000,0.000000,1.000000 -0.236365,0.619746,0.380254,0.260821,0.739179,0.000000,1.000000 -1.1317,0.109407,0.890593,1.000000,0.000000,0.822777,0.177223 0.122597,0.357583,0.642417,1.000000,0.000000,0.187972,0.812028 0.158741,0.419582,0.580418,0.660623,0.339377,0.000000,1.000000 0.494119,0.249672,0.750328,1.000000,0.000000,0.000000,1.000000 0.494119,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000 -1.68518,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000 -1.68518,0.000000,1.000000,1.000000,0.000000,0.902490,0.097510 0.0671458,0.000000,1.000000,0.220116,0.779884,0.310655,0.689345 0.0756722,0.216326,0.783674,0.000000,1.000000,0.288286,0.711714 0.561726,0.000000,1.000000,0.000000,1.000000,0.534206,0.465794 0.561726,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000 -1.97389,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000 -1.97389,0.000000,1.000000,1.000000,0.000000,1.000000,0.000000 gnm(): return since the path crosses no more support boundaries and no next eqlm NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 NE,0.500000,0.500000,0.400000,0.600000,0.250000,0.750000 NE,0.400000,0.600000,0.500000,0.500000,0.333333,0.666667 NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000 NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000 NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667 NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000
Closely related (and also proposed by Govindan and Wilson and implemented in Gametracer by Blum and Shelton) is iterated polymatrix approximation, which speeds up the homotopy calculation by approximating the game as a polymatrix game (i.e., one where each player, in effect, plays a two-player game against each other player).
!gambit-ipa -h
Compute Nash equilibria using iterated polymatrix approximation Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL Usage: gambit-ipa [OPTIONS] [file] If file is not specified, attempts to read game from standard input. Options: -d DECIMALS show equilibria as floating point with DECIMALS digits -h, --help print this help message -q quiet mode (suppresses banner) -V, --verbose verbose mode (shows intermediate output) -v, --version print version information
!gambit-ipa 2x2x2.nfg
Compute Nash equilibria using iterated polymatrix approximation Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000
Another path-following approach uses quantal response equilibria, as proposed by McKelvey and Palfrey (1995) and implemented by Turocy (2005). Instead of perturbing the payoffs of the game, QRE perturbs the accuracy of the best response. Turocy (2005) showed that using the logit form of the accuracy of the best response has nice computational properties. The method starts from uniform randomisation across all strategies, and in the limit computes a Nash equilibrium. As instrumented here, this computes one Nash equilibrium (which McKelvey-Palfrey called the "logit solution"), but there do exist other branches of the QRE correspondence which can be used to compute equilibria (if you can find them, which is the tricky part...)
This is at present the best and most reliable way to compute one equilibrium of a game with three or more players. This is not a theoretical claim; this is simply because I invested a lot of time implementing it carefully for the 2005 GEB paper (and subsequent use in experimental game theory), so it has received rather more love and attention than other methods to date.
!gambit-logit 2x2x2.nfg
Compute a branch of the logit equilibrium correspondence Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL 0.000000,0.5,0.5,0.5,0.5,0.5,0.5 0.028284,0.5,0.5,0.5,0.5,0.503535,0.496465 0.059397,0.5,0.5,0.5,0.5,0.507424,0.492576 0.093620,0.5,0.5,0.5,0.5,0.5117,0.4883 0.131264,0.5,0.5,0.5,0.5,0.516402,0.483598 0.172672,0.5,0.5,0.5,0.5,0.521571,0.478429 0.218218,0.5,0.5,0.5,0.5,0.52725,0.47275 0.268314,0.5,0.5,0.5,0.5,0.533489,0.466511 0.323415,0.5,0.5,0.5,0.5,0.540339,0.459661 0.384018,0.5,0.5,0.5,0.5,0.547855,0.452145 0.450670,0.5,0.5,0.5,0.5,0.556097,0.443903 0.523972,0.5,0.5,0.5,0.5,0.565124,0.434876 0.604581,0.5,0.5,0.5,0.5,0.575002,0.424998 0.693220,0.5,0.5,0.5,0.5,0.585795,0.414205 0.790681,0.5,0.5,0.5,0.5,0.597568,0.402432 0.897830,0.5,0.5,0.5,0.5,0.610381,0.389619 1.015617,0.5,0.5,0.5,0.5,0.624293,0.375707 1.145079,0.5,0.5,0.5,0.5,0.639349,0.360651 1.287348,0.5,0.5,0.5,0.5,0.655584,0.344416 1.443663,0.5,0.5,0.5,0.5,0.67301,0.32699 1.615373,0.5,0.5,0.5,0.5,0.691616,0.308384 1.803949,0.5,0.5,0.5,0.5,0.711355,0.288645 2.010994,0.5,0.5,0.5,0.5,0.732138,0.267862 2.238253,0.5,0.5,0.5,0.5,0.753827,0.246173 2.487633,0.5,0.5,0.5,0.5,0.776228,0.223772 2.761212,0.5,0.5,0.5,0.5,0.799088,0.200912 3.061267,0.5,0.5,0.5,0.5,0.822099,0.177901 3.390293,0.5,0.5,0.5,0.5,0.8449,0.1551 3.751038,0.5,0.5,0.5,0.5,0.867096,0.132904 4.146537,0.5,0.5,0.5,0.5,0.888278,0.111722 4.580150,0.5,0.5,0.5,0.5,0.908052,0.0919483 5.055609,0.5,0.5,0.5,0.5,0.926068,0.0739318 5.577064,0.5,0.5,0.5,0.5,0.942053,0.0579471 6.149130,0.5,0.5,0.5,0.5,0.955831,0.0441687 6.776937,0.5,0.5,0.5,0.5,0.967342,0.0326578 7.466175,0.5,0.5,0.5,0.5,0.97664,0.0233601 8.223140,0.5,0.5,0.5,0.5,0.983882,0.016118 9.054784,0.5,0.5,0.5,0.5,0.989307,0.0106932 9.968763,0.5,0.5,0.5,0.5,0.993203,0.00679749 10.973496,0.5,0.5,0.5,0.5,0.995876,0.00412421 12.078225,0.5,0.5,0.5,0.5,0.997622,0.00237801 13.293090,0.5,0.5,0.5,0.5,0.998703,0.00129682 14.629220,0.5,0.5,0.5,0.5,0.999335,0.000665298 16.098822,0.5,0.5,0.5,0.5,0.999681,0.000319188 17.715304,0.5,0.5,0.5,0.5,0.999858,0.000142269 19.493389,0.5,0.5,0.5,0.5,0.999942,5.84843e-05 21.449260,0.5,0.5,0.5,0.5,0.999978,2.1996e-05 23.600709,0.5,0.5,0.5,0.5,0.999992,7.50184e-06 25.967298,0.5,0.5,0.5,0.5,0.999998,2.29759e-06 28.570544,0.5,0.5,0.5,0.5,0.999999,6.25151e-07 31.434114,0.5,0.5,0.5,0.5,1,1.49337e-07 34.584041,0.5,0.5,0.5,0.5,1,3.09151e-08 38.048961,0.5,0.5,0.5,0.5,1,5.4673e-09 41.860373,0.5,0.5,0.5,0.5,1,8.13084e-10 46.052926,0.5,0.5,0.5,0.5,1,9.99388e-11 50.664734,0.5,0.5,0.5,0.5,1,9.96077e-12 55.737724,0.5,0.5,0.5,0.5,1,7.88328e-13 61.318012,0.5,0.5,0.5,0.5,1,4.84131e-14 67.456328,0.5,0.5,0.5,0.5,1,2.24928e-15 74.208477,0.5,0.5,0.5,0.5,1,7.68836e-17 81.635840,0.5,0.5,0.5,0.5,1,1.87501e-18 89.805940,0.5,0.5,0.5,0.5,1,3.15419e-20 98.793050,0.5,0.5,0.5,0.5,1,3.52665e-22 108.678870,0.5,0.5,0.5,0.5,1,2.51584e-24 119.553273,0.5,0.5,0.5,0.5,1,1.0948e-26 131.515116,0.5,0.5,0.5,0.5,1,2.76602e-29 144.673144,0.5,0.5,0.5,0.5,1,3.84261e-32 159.146974,0.5,0.5,0.5,0.5,1,2.76486e-35 175.068187,0.5,0.5,0.5,0.5,1,9.64776e-39 192.581521,0.5,0.5,0.5,0.5,1,1.51864e-42 211.846189,0.5,0.5,0.5,0.5,1,9.95829e-47 233.037323,0.5,0.5,0.5,0.5,1,2.49223e-51 256.347571,0.5,0.5,0.5,0.5,1,2.16188e-56 281.988844,0.5,0.5,0.5,0.5,1,5.84656e-62 310.194244,0.5,0.5,0.5,0.5,1,4.38708e-68 341.220184,0.5,0.5,0.5,0.5,1,8.03486e-75 375.348719,0.5,0.5,0.5,0.5,1,3.11933e-82 412.890106,0.5,0.5,0.5,0.5,1,2.19813e-90 454.185632,0.5,0.5,0.5,0.5,1,2.37052e-99 499.610711,0.5,0.5,0.5,0.5,1,3.24274e-109 549.578298,0.5,0.5,0.5,0.5,1,4.57708e-120 604.542644,0.5,0.5,0.5,0.5,1,5.31169e-132 665.003424,0.5,0.5,0.5,0.5,1,3.94767e-145 731.510282,0.5,0.5,0.5,0.5,1,1.42745e-159 804.667826,0.5,0.5,0.5,0.5,1,1.8561e-175 885.141124,0.5,0.5,0.5,0.5,1,6.22368e-193 973.661752,0.5,0.5,0.5,0.5,1,3.73282e-212 1071.034443,0.5,0.5,0.5,0.5,1,2.67809e-233 1178.144403,0.5,0.5,0.5,0.5,1,1.47636e-256 1295.965359,0.5,0.5,0.5,0.5,1,3.84324e-282 1425.568410,0.5,0.5,0.5,0.5,1,2.76537e-310 1568.131767,0.5,0.5,0.5,0.5,1,0 1724.951459,0.5,0.5,0.5,0.5,1,0 1897.453121,0.5,0.5,0.5,0.5,1,0 2087.204949,0.5,0.5,0.5,0.5,1,0 2295.931959,0.5,0.5,0.5,0.5,1,0 2525.531671,0.5,0.5,0.5,0.5,1,0 2778.091354,0.5,0.5,0.5,0.5,1,0 3055.907005,0.5,0.5,0.5,0.5,1,0 3361.504221,0.5,0.5,0.5,0.5,1,0 3697.661159,0.5,0.5,0.5,0.5,1,0 4067.433790,0.5,0.5,0.5,0.5,1,0 4474.183685,0.5,0.5,0.5,0.5,1,0 4921.608569,0.5,0.5,0.5,0.5,1,0 5413.775942,0.5,0.5,0.5,0.5,1,0 5955.160052,0.5,0.5,0.5,0.5,1,0 6550.682573,0.5,0.5,0.5,0.5,1,0 7205.757345,0.5,0.5,0.5,0.5,1,0 7926.339596,0.5,0.5,0.5,0.5,1,0 8718.980071,0.5,0.5,0.5,0.5,1,0 9590.884594,0.5,0.5,0.5,0.5,1,0 10549.979569,0.5,0.5,0.5,0.5,1,0 11604.984041,0.5,0.5,0.5,0.5,1,0 12765.488961,0.5,0.5,0.5,0.5,1,0 14042.044373,0.5,0.5,0.5,0.5,1,0 15446.255326,0.5,0.5,0.5,0.5,1,0 16990.887374,0.5,0.5,0.5,0.5,1,0 18689.982627,0.5,0.5,0.5,0.5,1,0 20558.987406,0.5,0.5,0.5,0.5,1,0 22614.892662,0.5,0.5,0.5,0.5,1,0 24876.388444,0.5,0.5,0.5,0.5,1,0 27364.033804,0.5,0.5,0.5,0.5,1,0 30100.443700,0.5,0.5,0.5,0.5,1,0 33110.494586,0.5,0.5,0.5,0.5,1,0 36421.550560,0.5,0.5,0.5,0.5,1,0 40063.712132,0.5,0.5,0.5,0.5,1,0 44070.089861,0.5,0.5,0.5,0.5,1,0 48477.105363,0.5,0.5,0.5,0.5,1,0 53324.822414,0.5,0.5,0.5,0.5,1,0 58657.311172,0.5,0.5,0.5,0.5,1,0 64523.048804,0.5,0.5,0.5,0.5,1,0 70975.360201,0.5,0.5,0.5,0.5,1,0 78072.902736,0.5,0.5,0.5,0.5,1,0 85880.199526,0.5,0.5,0.5,0.5,1,0 94468.225994,0.5,0.5,0.5,0.5,1,0 103915.055109,0.5,0.5,0.5,0.5,1,0 114306.567136,0.5,0.5,0.5,0.5,1,0 125737.230365,0.5,0.5,0.5,0.5,1,0 138310.959917,0.5,0.5,0.5,0.5,1,0 152142.062424,0.5,0.5,0.5,0.5,1,0 167356.275182,0.5,0.5,0.5,0.5,1,0 184091.909216,0.5,0.5,0.5,0.5,1,0 202501.106654,0.5,0.5,0.5,0.5,1,0 222751.223835,0.5,0.5,0.5,0.5,1,0 245026.352734,0.5,0.5,0.5,0.5,1,0 269528.994523,0.5,0.5,0.5,0.5,1,0 296481.900491,0.5,0.5,0.5,0.5,1,0 326130.097056,0.5,0.5,0.5,0.5,1,0 358743.113277,0.5,0.5,0.5,0.5,1,0 394617.431121,0.5,0.5,0.5,0.5,1,0 434079.180748,0.5,0.5,0.5,0.5,1,0 477487.105339,0.5,0.5,0.5,0.5,1,0 525235.822388,0.5,0.5,0.5,0.5,1,0 577759.411143,0.5,0.5,0.5,0.5,1,0 635535.358773,0.5,0.5,0.5,0.5,1,0 699088.901166,0.5,0.5,0.5,0.5,1,0 768997.797798,0.5,0.5,0.5,0.5,1,0 845897.584094,0.5,0.5,0.5,0.5,1,0 930487.349019,0.5,0.5,0.5,0.5,1,0 1023536.090436,0.5,0.5,0.5,0.5,1,0
All methods so far compute one, or possibly many, equilibria, but none are guaranteed to find all equilibria in all games. There is exactly one such method, which operates by enumerating all of the subsets of supports in the game, and, for each of them, asks whether there is a totally mixed equilibrium on that support. The latter question amounts to a collection of polynomial equations. The number of possible supports grows quickly (but searching them is embarrassingly parallelizable!), but finding all solutions to a system of polynomial equations does take a bit of work in practice.
In Gambit, we have one implementation of this, done in the mid-1990s by Andrew McLennan, which currently ships as gambit-enumpoly
. It uses the Pelican library by Birk Huber, which dates from the early 1990s, which I believe was translated from FORTRAN (and which is the bane of my existence in terms of maintenance with each new compiler version...)
If you give the -V
switch, you can see each candidate support reported as it is inspected. In the case of this example, it works great on most of the supports, but has a problem with the full support (on which there are two totally mixed equilibria).
!gambit-enumpoly -V 2x2x2.nfg
Compute Nash equilibria by solving polynomial systems Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project Heuristic search implementation Copyright (C) 2006, Litao Wei This is free software, distributed under the GNU GPL candidate,10,10,10 NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000 candidate,10,01,01 NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 candidate,01,01,10 NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000 candidate,01,10,01 NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000 candidate,10,11,11 candidate,01,11,11 NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667 candidate,11,11,10 NE,0.500000,0.500000,0.500000,0.500000,1.000000,0.000000 candidate,11,01,11 candidate,11,10,11 NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000 candidate,11,11,01 candidate,11,11,11 ^C
This example comes from Nau et al (IJGT 2004) On the geometry of Nash equilibria and correlated equilibria. It is a very useful example case for computing Nash equilibria, in that there is an equilibrium component which is one-dimensional, and also spans three different supports. If you think of the set of mixed strategy profiles of this 2x2x2 game as a cube, this component starts along one edge (corresponding to incompletely-mixed equilibria), then curves across through the centre of the cube until it reaches the edge catercorner from the first, then continues along that edge (corresponding to more incompletely-mixed equilibria).
g = gambit.Game.read_game("2x2x2-nau.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))
1 | 2 | |
1 | 0,0,2 | 0,3,0 |
2 | 3,0,0 | 0,0,0 |
1 | 2 | |
1 | 1,1,0 | 0,0,0 |
2 | 0,0,0 | 0,0,3 |
None of the existing implementations do very well at giving the naive user much insight into the equilibrium structure.
!gambit-gnm -V 2x2x2-nau.nfg
Compute Nash equilibria using a global Newton method Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL pert,0.611434,0.105483,0.189587,0.527330,0.210106,0.506811 start,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 0.496714,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000 0.496714,1.000000,0.000000,0.439246,0.560754,0.000000,1.000000 2.49584e-05,1.000000,0.000000,0.000022,0.999978,0.249987,0.750013 gnm(): return due to too much error. error is 0.0108534
!gambit-ipa 2x2x2-nau.nfg
Compute Nash equilibria using iterated polymatrix approximation Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000
gambit-logit
does successfully pick out one of the totally-mixed equilibria at least, but doesn't (on its own) warn you about the one-dimensional component.
Interesting observation: This is the equilibrium in that component that has the highest entropy. I have a conjecture that any limiting QRE is either a local max or local min of entropy over the set of Nash equilibria. Anyone interested in having a go at trying to prove this, chat to me! I have no idea what use such a result would be however... ;)
!gambit-logit 2x2x2-nau.nfg
Compute a branch of the logit equilibrium correspondence Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project This is free software, distributed under the GNU GPL 0.000000,0.5,0.5,0.5,0.5,0.5,0.5 0.026524,0.49673,0.50327,0.49673,0.50327,0.498234,0.501766 0.055756,0.493234,0.506766,0.493234,0.506766,0.496043,0.503957 0.087975,0.489522,0.510478,0.489522,0.510478,0.493347,0.506653 0.123487,0.485609,0.514391,0.485609,0.514391,0.490056,0.509944 0.162631,0.481522,0.518478,0.481522,0.518478,0.486069,0.513931 0.205779,0.477299,0.522701,0.477299,0.522701,0.481282,0.518718 0.253343,0.472994,0.527006,0.472994,0.527006,0.475587,0.524413 0.305776,0.468673,0.531327,0.468673,0.531327,0.468881,0.531119 0.363588,0.46442,0.53558,0.46442,0.53558,0.461069,0.538931 0.427345,0.46033,0.53967,0.46033,0.53967,0.45208,0.54792 0.497687,0.456516,0.543484,0.456516,0.543484,0.441872,0.558128 0.575339,0.453098,0.546902,0.453098,0.546902,0.430448,0.569552 0.661126,0.450202,0.549798,0.450202,0.549798,0.417867,0.582133 0.755990,0.447952,0.552048,0.447952,0.552048,0.404251,0.595749 0.861001,0.446468,0.553532,0.446468,0.553532,0.389795,0.610205 0.977371,0.445847,0.554153,0.445847,0.554153,0.374761,0.625239 1.106452,0.446166,0.553834,0.446166,0.553834,0.359475,0.640525 1.249739,0.447461,0.552539,0.447461,0.552539,0.344301,0.655699 1.408844,0.449725,0.550275,0.449725,0.550275,0.329617,0.670383 1.585485,0.452905,0.547095,0.452905,0.547095,0.315781,0.684219 1.781461,0.456895,0.543105,0.456895,0.543105,0.30309,0.69691 1.998653,0.461552,0.538448,0.461552,0.538448,0.291762,0.708238 2.239037,0.466703,0.533297,0.466703,0.533297,0.281911,0.718089 2.504725,0.47217,0.52783,0.47217,0.52783,0.273556,0.726444 2.798012,0.477778,0.522222,0.477778,0.522222,0.266634,0.733366 3.121431,0.483377,0.516623,0.483377,0.516623,0.261022,0.738978 3.477796,0.488842,0.511158,0.488842,0.511158,0.256564,0.743436 3.870241,0.494084,0.505916,0.494084,0.505916,0.253094,0.746906 4.302252,0.49904,0.50096,0.49904,0.50096,0.250447,0.749553 4.777696,0.503672,0.496328,0.503672,0.496328,0.248474,0.751526 5.300850,0.507965,0.492035,0.507965,0.492035,0.247042,0.752958 5.876440,0.511915,0.488085,0.511915,0.488085,0.246038,0.753962 6.509676,0.515532,0.484468,0.515532,0.484468,0.24537,0.75463 7.206299,0.51883,0.48117,0.51883,0.48117,0.244961,0.755039 7.972631,0.521828,0.478172,0.521828,0.478172,0.24475,0.75525 8.815632,0.524549,0.475451,0.524549,0.475451,0.244687,0.755313 9.742958,0.527013,0.472987,0.527013,0.472987,0.244734,0.755266 10.763036,0.529244,0.470756,0.529244,0.470756,0.24486,0.75514 11.885135,0.53126,0.46874,0.53126,0.46874,0.245043,0.754957 13.119456,0.533083,0.466917,0.533083,0.466917,0.245263,0.754737 14.477217,0.534731,0.465269,0.534731,0.465269,0.245506,0.754494 15.970759,0.53622,0.46378,0.53622,0.46378,0.245763,0.754237 17.613661,0.537566,0.462434,0.537566,0.462434,0.246025,0.753975 19.420856,0.538782,0.461218,0.538782,0.461218,0.246286,0.753714 21.408772,0.539882,0.460118,0.539882,0.460118,0.246542,0.753458 23.595483,0.540876,0.459124,0.540876,0.459124,0.24679,0.75321 26.000866,0.541776,0.458224,0.541776,0.458224,0.247027,0.752973 28.646788,0.54259,0.45741,0.54259,0.45741,0.247253,0.752747 31.557303,0.543327,0.456673,0.543327,0.456673,0.247467,0.752533 34.758871,0.543994,0.456006,0.543994,0.456006,0.247667,0.752333 38.280595,0.544598,0.455402,0.544598,0.455402,0.247855,0.752145 42.154493,0.545145,0.454855,0.545145,0.454855,0.24803,0.75197 46.415780,0.545641,0.454359,0.545641,0.454359,0.248193,0.751807 51.103197,0.546091,0.453909,0.546091,0.453909,0.248344,0.751656 56.259355,0.546498,0.453502,0.546498,0.453502,0.248483,0.751517 61.931129,0.546868,0.453132,0.546868,0.453132,0.248612,0.751388 68.170080,0.547203,0.452797,0.547203,0.452797,0.248731,0.751269 75.032927,0.547507,0.452493,0.547507,0.452493,0.24884,0.75116 82.582059,0.547782,0.452218,0.547782,0.452218,0.248941,0.751059 90.886103,0.548032,0.451968,0.548032,0.451968,0.249033,0.750967 100.020552,0.54826,0.45174,0.54826,0.45174,0.249117,0.750883 110.068446,0.548466,0.451534,0.548466,0.451534,0.249195,0.750805 121.121130,0.548653,0.451347,0.548653,0.451347,0.249266,0.750734 133.279082,0.548823,0.451177,0.548823,0.451177,0.24933,0.75067 146.652829,0.548977,0.451023,0.548977,0.451023,0.24939,0.75061 161.363951,0.549117,0.450883,0.549117,0.450883,0.249444,0.750556 177.546184,0.549244,0.450756,0.549244,0.450756,0.249493,0.750507 195.346642,0.54936,0.45064,0.54936,0.45064,0.249539,0.750461 214.927145,0.549465,0.450535,0.549465,0.450535,0.24958,0.75042 236.465698,0.54956,0.45044,0.54956,0.45044,0.249617,0.750383 260.158107,0.549647,0.450353,0.549647,0.450353,0.249652,0.750348 286.219756,0.549726,0.450274,0.549726,0.450274,0.249683,0.750317 314.887571,0.549797,0.450203,0.549797,0.450203,0.249711,0.750289 346.422167,0.549862,0.450138,0.549862,0.450138,0.249737,0.750263 381.110223,0.549921,0.450079,0.549921,0.450079,0.249761,0.750239 419.267084,0.549975,0.450025,0.549975,0.450025,0.249783,0.750217 461.239631,0.550024,0.449976,0.550024,0.449976,0.249802,0.750198 507.409433,0.550068,0.449932,0.550068,0.449932,0.24982,0.75018 558.196215,0.550108,0.449892,0.550108,0.449892,0.249836,0.750164 614.061675,0.550145,0.449855,0.550145,0.449855,0.249851,0.750149 675.513682,0.550178,0.449822,0.550178,0.449822,0.249865,0.750135 743.110889,0.550208,0.449792,0.550208,0.449792,0.249877,0.750123 817.467817,0.550236,0.449764,0.550236,0.449764,0.249888,0.750112 899.260437,0.550261,0.449739,0.550261,0.449739,0.249898,0.750102 989.232320,0.550283,0.449717,0.550283,0.449717,0.249907,0.750093 1088.201391,0.550304,0.449696,0.550304,0.449696,0.249916,0.750084 1197.067369,0.550323,0.449677,0.550323,0.449677,0.249923,0.750077 1316.819945,0.55034,0.44966,0.55034,0.44966,0.24993,0.75007 1448.547778,0.550355,0.449645,0.550355,0.449645,0.249937,0.750063 1593.448395,0.550369,0.449631,0.550369,0.449631,0.249942,0.750058 1752.839073,0.550382,0.449618,0.550382,0.449618,0.249948,0.750052 1928.168819,0.550394,0.449606,0.550394,0.449606,0.249952,0.750048 2121.031540,0.550405,0.449595,0.550405,0.449595,0.249957,0.750043 2333.180533,0.550414,0.449586,0.550414,0.449586,0.249961,0.750039 2566.544425,0.550423,0.449577,0.550423,0.449577,0.249964,0.750036 2823.244706,0.550431,0.449569,0.550431,0.449569,0.249967,0.750033 3105.615016,0.550438,0.449562,0.550438,0.449562,0.24997,0.75003 3416.222357,0.550445,0.449555,0.550445,0.449555,0.249973,0.750027 3757.890431,0.550451,0.449549,0.550451,0.449549,0.249976,0.750024 4133.725313,0.550456,0.449544,0.550456,0.449544,0.249978,0.750022 4547.143683,0.550461,0.449539,0.550461,0.449539,0.24998,0.75002 5001.903890,0.550465,0.449535,0.550465,0.449535,0.249982,0.750018 5502.140118,0.550469,0.449531,0.550469,0.449531,0.249983,0.750017 6052.399969,0.550473,0.449527,0.550473,0.449527,0.249985,0.750015 6657.685805,0.550477,0.449523,0.550477,0.449523,0.249986,0.750014 7323.500224,0.55048,0.44952,0.55048,0.44952,0.249987,0.750013 8055.896086,0.550482,0.449518,0.550482,0.449518,0.249989,0.750011 8861.531533,0.550485,0.449515,0.550485,0.449515,0.24999,0.75001 9747.730525,0.550487,0.449513,0.550487,0.449513,0.249991,0.750009 10722.549417,0.550489,0.449511,0.550489,0.449511,0.249991,0.750009 11794.850197,0.550491,0.449509,0.550491,0.449509,0.249992,0.750008 12974.381056,0.550493,0.449507,0.550493,0.449507,0.249993,0.750007 14271.865000,0.550495,0.449505,0.550495,0.449505,0.249994,0.750006 15699.097339,0.550496,0.449504,0.550496,0.449504,0.249994,0.750006 17269.052912,0.550497,0.449503,0.550497,0.449503,0.249995,0.750005 18996.004042,0.550498,0.449502,0.550498,0.449502,0.249995,0.750005 20895.650285,0.5505,0.4495,0.5505,0.4495,0.249996,0.750004 22985.261153,0.550501,0.449499,0.550501,0.449499,0.249996,0.750004 25283.833107,0.550501,0.449499,0.550501,0.449499,0.249996,0.750004 27812.262256,0.550502,0.449498,0.550502,0.449498,0.249997,0.750003 30593.534321,0.550503,0.449497,0.550503,0.449497,0.249997,0.750003 33652.933592,0.550504,0.449496,0.550504,0.449496,0.249997,0.750003 37018.272790,0.550504,0.449496,0.550504,0.449496,0.249998,0.750002 40720.145908,0.550505,0.449495,0.550505,0.449495,0.249998,0.750002 44792.206338,0.550505,0.449495,0.550505,0.449495,0.249998,0.750002 49271.472810,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002 54198.665930,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002 59618.578362,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002 65580.482037,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001 72138.576080,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001 79352.479527,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001 87287.773318,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001 96016.596489,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001 105618.301977,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001 116180.178013,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001 127798.241654,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001 140578.111658,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001 154635.968663,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001 170099.611368,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001 187109.618343,0.550509,0.449491,0.550509,0.449491,0.25,0.75 205820.626017,0.550509,0.449491,0.550509,0.449491,0.25,0.75 226402.734457,0.550509,0.449491,0.550509,0.449491,0.25,0.75 249043.053742,0.550509,0.449491,0.550509,0.449491,0.25,0.75 273947.404955,0.550509,0.449491,0.550509,0.449491,0.25,0.75 301342.191289,0.55051,0.44949,0.55051,0.44949,0.25,0.75 331476.456257,0.55051,0.44949,0.55051,0.44949,0.25,0.75 364624.147721,0.55051,0.44949,0.55051,0.44949,0.25,0.75 401086.608332,0.55051,0.44949,0.55051,0.44949,0.25,0.75 441195.315005,0.55051,0.44949,0.55051,0.44949,0.25,0.75 485314.892344,0.55051,0.44949,0.55051,0.44949,0.25,0.75 533846.427417,0.55051,0.44949,0.55051,0.44949,0.25,0.75 587231.115998,0.55051,0.44949,0.55051,0.44949,0.25,0.75 645954.273437,0.55051,0.44949,0.55051,0.44949,0.25,0.75 710549.746619,0.55051,0.44949,0.55051,0.44949,0.25,0.75 781604.767120,0.55051,0.44949,0.55051,0.44949,0.25,0.75 859765.289671,0.55051,0.44949,0.55051,0.44949,0.25,0.75 945741.864477,0.55051,0.44949,0.55051,0.44949,0.25,0.75 1040316.096763,0.55051,0.44949,0.55051,0.44949,0.25,0.75
The performance of gambit-enumpoly
on this game is a bit of a mixed bag. It fails to find anything but the pure equilibria. However, it does provide interesting diagnostic information, that some of the supports are "singular." Actually, this mostly just means that something went wrong and it gave up - but often this happens because the set of equations has a positive-dimensional set of solutions. So at least it provides some diagnostics that one might want to inspect those supports more closely.
!gambit-enumpoly -V 2x2x2-nau.nfg
Compute Nash equilibria by solving polynomial systems Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project Heuristic search implementation Copyright (C) 2006, Litao Wei This is free software, distributed under the GNU GPL candidate,10,01,10 NE,1.000000,0.000000,0.000000,1.000000,1.000000,0.000000 candidate,01,01,01 NE,0.000000,1.000000,0.000000,1.000000,0.000000,1.000000 candidate,01,10,10 NE,0.000000,1.000000,1.000000,0.000000,1.000000,0.000000 candidate,01,10,11 singular,01,10,11 candidate,10,01,11 singular,10,01,11 candidate,11,11,11 singular,11,11,11
There is however some hope on the horizon. Both PHCpack http://homepages.math.uic.edu/~jan/download.html and Bertini https://bertini.nd.edu are polynomial system solvers that deal with positive-dimensional sets of solutions. There is a Python script in the contrib/
directory of the Gambit repository which interfaces with these (but the script needs updating to the current version of the Python interface).