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