gambit-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. 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.
The algorithm begins with any mixed strategy profile consisting of
rational numbers as probabilities. Without any options, the algorithm
begins with the centroid, and computes one Nash equilibrium. To
attempt to compute other equilibria that may exist, use
the -r or -s options to specify
additional starting points for the algorithm.
-d DECIMALSExpress all output using decimal representations with DECIMALS digits. Because the algorithm is based on a grid, this algorithm inherently computes using rational numbers. By default, these rational probabilities are output. Expressing the profile probabilities as decimal numbers may make reading the output easier.
-g MULTSets the granularity of the grid refinement. By default, when
the grid is refined, the stepsize is cut in half, which corresponds to
specifying -g 2. If this parameter
is specified, the grid is refined at each step by a multiple of
MULT.
-hPrints a help message listing the available options.
-n COUNTRandomly generate
COUNT starting points.
Only applicable if option -r is also specified.
-qSuppresses printing of the banner at program launch.
-r DENOMGenerate random starting points with denominator DENOM. Since this algorithm operates on a grid, by its nature the probabilities it works with are always rational numbers. If this parameter is specified, starting points for the procedure are generated randomly using the uniform distribution over strategy profiles with probabilities having denominator DENOM.
-s FILESpecifies 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).
-vSets verbose mode. In verbose mode, initial points, as well as the approximations computed at each grid refinement, are all output, in addition to the approximate equilibrium profile found.