gambit-gnm: Compute Nash equilibria in a strategic game using a global Newton method#

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

The algorithm finds a subset of equilibria starting from any given profile. Multiple starting profiles may be generated via the -n option or specified via the -s option; different starting profiles may result in different subsets of equilibria being found.

-d#: Express all output using decimal representations with the specified number of digits.

-h#: Prints a help message listing the available options.

-n#: Randomly generate the specified number of perturbation vectors.

-q#: Suppresses printing of the banner at program launch.

-s#: Specifies a file containing a list of starting points for the algorithm. The format of the file is comma-separated values, one mixed strategy profile per line, in the same format used for output of equilibria (excluding the initial NE tag).

-m LAMBDA#: New in version 16.2.0.

Specifies the value of lambda at which to assume no more equilibria are accessible via the specified ray, and terminate tracing. Must be a negative number; default is -10.

-f FREQ#: New in version 16.2.0.

Specifies the frequency to run a local Newton method step. This is a correction step that reduces accumulated errors in the path-following. Default is 3.

-i MAXITS#: New in version 16.2.0.

Specifies the maximum number of iterations in a local Newton method step. Default is 10.

-c STEPS#: New in version 16.2.0.

Specifies the number of steps to take within a support cell. Larger values trade off speed for security in tracing the path. Default is 100.

-v#: Show intermediate output of the algorithm. If this option is not specified, only the equilibria found are reported.

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

$ gambit-gnm e02.nfg
Compute Nash equilibria using a global Newton method
Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL

NE,1,0,2.99905e-12,0.5,0.5