gambit-enummixed: Enumerate equilibria in a two-player game

gambit-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 gambit-lcp: Compute equilibria in a two-player game via linear complementarity). It was shown by Shapley [Sha74] that there are equilibria not accessible via the method in gambit-lcp: Compute equilibria in a two-player game via linear complementarity, whereas the output of gambit-enummixed is guaranteed to return all the extreme points.

-d

By default, this program computes using exact rational arithmetic. Since the extreme points computed by this method are guaranteed to be rational when the payoffs in the game are rational, this permits exact computation of the equilibrium set. Computation using rational arithmetic is in general slow, however. For most games, acceptable results can be obtained by computing using the computer’s native floating-point arithmetic. Using this flag enables computation in floating-point, and expresses all output using decimal representations with the specified number of digits.

-D

Since all Nash equilibria involve only strategies which survive iterative elimination of strictly dominated strategies, the program carries out the elimination automatically prior to computation. This is recommended, since it almost always results in superior performance. Specifying -D skips the elimination step and performs the enumeration on the full game.

-c

The program outputs the extreme equilibria as it finds them, prefixed by the tag NE . If this option is specified, once all extreme equilbria are identified, the program computes the convex sets which make up the set of equilibria. The program then additionally outputs each convex set, prefixed by convex-N , where N indexes the set. The set of all equilibria, then, is the union of these convex sets.

-h

Prints a help message listing the available options.

-q

Suppresses printing of the banner at program launch.

-L

Use lrslib by David Avis to carry out the enumeration process. This is an experimental feature that has not been widely tested.

Computing the equilibria, in mixed strategies, of e02.nfg, the reduced strategic form of the example in Figure 2 of Selten (International Journal of Game Theory, 1975):

$ gambit-enummixed e02.nfg
Compute Nash equilibria by enumerating extreme points
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
Enumeration code based on lrslib 4.2b,
Copyright (C) 1995-2005 by David Avis (avis@cs.mcgill.ca)
This is free software, distributed under the GNU GPL

NE,1,0,0,1,0
NE,1,0,0,1/2,1/2

In fact, the game e02.nfg has a one-dimensional continuum of equilibria. This fact can be observed by examining the connectedness information using the -c switch:

$ gambit-enummixed -c e02.nfg
Compute Nash equilibria by enumerating extreme points
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
Enumeration code based on lrslib 4.2b,
Copyright (C) 1995-2005 by David Avis (avis@cs.mcgill.ca)
This is free software, distributed under the GNU GPL

NE,1,0,0,1,0
NE,1,0,0,1/2,1/2
convex-1,1,0,0,1/2,1/2
convex-1,1,0,0,1,0