# Computing equilibria in games with three or more players

Theodore L. Turocy
University of East Anglia

### EC'16 Workshop 24 July 2016

In [1]:
import gambit


### Three player games¶

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.

In [2]:
g = gambit.Game.read_game("2x2x2.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))

Out[2]:

# 2x2x2 Example from McKelvey-McLennan, with 9 Nash equilibria, 2 totally mixed

Subtable with strategies:
Player 3 Strategy 1
 1 2 1 9,8,12 0,0,0 2 0,0,0 9,8,2
Subtable with strategies:
Player 3 Strategy 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).

In [3]:
!gambit-simpdiv 2x2x2.nfg

Compute Nash equilibria using simplicial subdivision
Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project

NE,1,0,1,0,1,0

In [4]:
!gambit-simpdiv -h

Compute Nash equilibria using simplicial subdivision
Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project

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)

In [5]:
!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

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.

In [6]:
!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

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

In [7]:
!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

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.

In [8]:
!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

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).

In [9]:
!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

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

In [10]:
!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

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.

In [11]:
!gambit-logit 2x2x2.nfg

Compute a branch of the logit equilibrium correspondence
Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project

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).

In [12]:
!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

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


### A game with an equilibrium set with positive dimension¶

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).

In [18]:
g = gambit.Game.read_game("2x2x2-nau.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))

Out[18]:

# 2x2x2 example with 3 pure, 2 incompletely mixed, and a continuum of completely mixed NE

Subtable with strategies:
Player 3 Strategy 1
 1 2 1 0,0,2 0,3,0 2 3,0,0 0,0,0
Subtable with strategies:
Player 3 Strategy 2
 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.

In [19]:
!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

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

In [20]:
!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

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... ;)

In [21]:
!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

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.

In [22]:
!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

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).