Nash equilibria algorithms#
The table below summarizes the available PyGambit functions and corresponding Gambit CLI commandsto algorithms for computing Nash equilibria. Scroll down for detailed descriptions of each algorithm.
Algorithm |
Description |
PyGambit function |
CLI command |
|---|---|---|---|
Enumerate pure-strategy equilibria of a game |
|||
Enumerate equilibria in a two-player game |
|||
Compute equilibria of a game using polynomial systems of equations |
|||
Compute equilibria in a two-player constant-sum game via linear programming |
|||
Compute equilibria in a two-player game via linear complementarity |
|||
Compute Nash equilibria using function minimization |
|||
Compute quantal response equilbria |
|||
Compute equilibria via simplicial subdivision |
|||
Compute Nash equilibria using iterated polymatrix approximation |
|||
Compute Nash equilibria using a global Newton method |
enumpure#
Reads a game on standard input and searches for pure-strategy Nash equilibria.
enummixed#
Reads a two-player game on standard input and computes Nash equilibria using extreme point enumeration.
In a two-player strategic game, the set of Nash equilibria can be expressed as the union of convex sets. This program generates all the extreme points of those convex sets. (Mangasarian [Man64]) This is a superset of the points generated by the path-following procedure of Lemke and Howson (see lcp). It was shown by Shapley [Sha74] that there are equilibria not accessible via the method in lcp, whereas the output of enummixed is guaranteed to return all the extreme points.
enumpoly#
Reads a game on standard input and computes Nash equilibria by solving systems of polynomial equations and inequalities.
This program searches for all Nash equilibria in a strategic game using a support enumeration approach. This approach computes all the supports which could, in principle, be the support of a Nash equilibrium. For each candidate support, it attempts to compute totally mixed equilibria on that support by successively subdividing the space of mixed strategy profiles or mixed behavior profiles (as appropriate). By using the fact that the equilibrium conditions imply a collection of equations and inequalities which can be expressed as multilinear polynomials, the subdivision constructed is such that each cell contains either no equilibria or exactly one equilibrium.
For strategic games, the program searches supports in the order proposed by Porter, Nudelman, and Shoham [PNS04]. For two-player games, this prioritises supports for which both players have the same number of strategies. For games with three or more players, this prioritises supports which have the fewest strategies in total. For many classes of games, this will tend to lower the average time until finding one equilibrium, as well as finding the second equilibrium (if one exists).
lp#
Reads a two-player constant-sum game on standard input and computes a Nash equilibrium by solving a linear program. The program uses the sequence form formulation of Koller, Megiddo, and von Stengel [KolMegSte94] for extensive games.
While the set of equilibria in a two-player constant-sum strategic game is convex, this method will only identify one of the extreme points of that set.
lcp#
Reads a two-player game on standard input and computes Nash equilibria by finding solutions to a linear complementarity problem. For extensive games, the program uses the sequence form representation of the extensive game, as defined by Koller, Megiddo, and von Stengel [KolMegSte94], and applies the algorithm developed by Lemke.
For strategic games, the program uses the method of Lemke and Howson [LemHow64]. In this case, the method will find all “accessible” equilibria, i.e., those that can be found as concatenations of Lemke-Howson paths that start at the artificial equilibrium. There exist strategic-form games for which some equilibria cannot be found by this method, i.e., some equilibria are inaccessible; see Shapley [Sha74].
In a two-player strategic game, the set of Nash equilibria can be expressed as the union of convex sets. This program will find extreme points of those convex sets. See enummixed for a method which is guaranteed to find all the extreme points for a strategic game.
liap#
Reads a game on standard input and computes approximate Nash equilibria using a function minimization approach.
This procedure searches for equilibria by generating random starting points and using conjugate gradient descent to minimize the Lyapunov function of the game. This is a nonnegative function which is zero exactly at strategy profiles which are Nash equilibria.
Note that this procedure is not globally convergent. That is, it is not guaranteed to find all, or even any, Nash equilibria.
logit#
Reads a game on standard input and computes the principal branch of the (logit) quantal response correspondence.
The method is based on the procedure described in Turocy [Tur05] for strategic games and Turocy [Tur10] for extensive games. It uses standard path-following methods (as described in Allgower and Georg’s “Numerical Continuation Methods”) to adaptively trace the principal branch of the correspondence efficiently and securely.
The method used is a predictor-corrector method, which first generates a prediction using the differential equations describing the branch of the correspondence, followed by a corrector step which refines the prediction using Newton’s method for finding a zero of a function. Two parameters control the operation of this tracing.
In extensive games, logit quantal response equilibria are not well-defined if an information set is not reached due to being the successor of chance moves with zero probability. In such games, the implementation treats the beliefs at such information sets as being uniform across all member nodes.
simpdiv#
Reads a game on standard input and computes approximations to Nash equilibria using a simplicial subdivision approach.
This program implements the algorithm of van der Laan, Talman, and van Der Heyden [VTH87]. The algorithm proceeds by constructing a triangulated grid over the space of mixed strategy profiles, and uses a path-following method to compute an approximate fixed point. This approximate fixed point can then be used as a starting point on a refinement of the grid. The program continues this process with finer and finer grids until locating a mixed strategy profile at which the maximum regret is small.
ipa#
Reads a game on standard input and computes Nash equilibria using an iterated polymatrix approximation approach developed by Govindan and Wilson [GovWil04]. This program is based on the Gametracer 0.2 implementation by Ben Blum and Christian Shelton.
The algorithm takes as a parameter a mixed strategy profile. This profile is interpreted as defining a ray in the space of games. The profile must have the property that, for each player, the most frequently played strategy must be unique.
gnm#
Reads a game on standard input and computes Nash equilibria using a global Newton method approach developed by Govindan and Wilson [GovWil03]. This program is based on the Gametracer 0.2 implementation by Ben Blum and Christian Shelton.
The algorithm takes as a parameter a mixed strategy profile. This profile is interpreted as defining a ray in the space of games. The profile must have the property that, for each player, the most frequently played strategy must be unique.