Action Graph Game Solver
Albert Xin Jiang and Kevin Leyton-Brown
CONTENTS
1.Introduction
2.Installation
3.Usage
4.Acknowledgements
1.Introduction
Action-graph games (AGGs) are a compact representation of games.
For more information on action graph games and efficient algorithms for computing in AGGs,
see the paper "Action-Graph Games" by Albert Xin Jiang, Kevin Leyton-Brown and Navin Bhat,
to appear in Games and Economic Behavior, 2010, available online at
http://www.cs.ubc.ca/~jiang/papers/AGG.pdf
Bayesian action-graph games (BAGGs) are an extension of AGGs that compactly represents Bayesian games.
For more information on BAGGs see the paper "Bayesian Action-Graph Games" by Albert Xin Jiang and Kevin Leyton-Brown,
NIPS 2010, available online at http://www.cs.ubc.ca/~jiang/papers/BAGG.pdf
This software reads in a description of an AGG or a BAGG, and computes one or more Nash equilibria of
the game (Bayes-Nash equilibria for BAGGs) using either Govindan & Wilson's Global Newton's Method (GNM)
or van der Laan, Talman & van der Heyden's simplicial subdivision algorithm.
2.Installation
After unpacking the files, just type
make
to compile the sources. This has been tested under Linux and Windows systems, but
should work under other Unix systems too.
3. Usage
3.0 Input file format
The format of the AGG description file is specified in the file AGGFORMAT
in this package.
The BAGG file format is specified in the file BAGG/FORMAT.txt in this package.
3.1 gnm_agg
The executable gnm_agg takes an AGG and computes one or more Nash equilibria using
Govindan & Wilson's Global Newton Method (GNM).
gnm_agg -sym numPlayers numActionNodes gameSeed strategySeed numRuns
gnm_agg -coffee numPlayers numRows numCols gameSeed strategySeed numRuns
gnm_agg -f filename strategySeed numRuns
-sym Generate a random symmetric game as AGG
-coffee Generate a coffee shop game as AGG
-f Reads in an AGG from filename
gameSeed: seed for generating the game
strategySeed: seed for generating the initial perturbation ray
numRuns: number of runs (each with a different initial ray)
3.2 gnm_bagg
gnm_bagg takes a BAGG and computes one or more Bayes-Nash equilibria using the GNM algorithm.
gnm_agg -coffee numPlayers numTypes numRows numCols gameSeed strategySeed numRuns
gnm_agg -f filename strategySeed numRuns
-coffee Generate a coffee shop Bayesian game
-f Reads in an BAGG from filename
gameSeed: seed for generating the game
strategySeed: seed for generating the initial perturbation ray
numRuns: number of runs (each with a different initial ray)
3.3 gnm_ksym_agg
Takes an AGG or a symmetric BAGG and computes k-symmetric Nash equilibria using a modified GNM algorithm.
gnm_ksym_agg -sym numPlayers numActionNodes gameSeed strategySeed numRuns
gnm_ksym_agg -coffee numPlayers numRows numCols gameSeed strategySeed numRuns
gnm_ksym_agg -f aggFilename strategySeed numRuns
gnm_ksym_agg -b baggFilename strategySeed numRuns
-sym Generate a random symmetric game as AGG
-coffee Generate a coffee shop game as AGG
-f Reads in an AGG from filename
-b Reads in an BAGG from filename
gameSeed: seed for generating the game
strategySeed: seed for generating the initial perturbation ray
numRuns: number of runs (each with a different initial ray)
3.4 gnm_tracing_agg
Takes an AGG/BAGG and a file containing initial mixed strategy profiles, for each initial
mixed strategy profile sigma run a version of the GNM algorithm
that simulates the linear tracing procedure starting from sigma.
Good approximate equilibria can be used as "warm starts".
gnm_tracing_agg [OPTIONS] INITFILE
Accepts game on standard input
INITFILE is a file containing initial strategy profiles;
each strategy profile is a list of numbers separated by commas
Options:
-b input is a Bayesian action-graph game (default input is AGG)
-k compute k-symmetric equilibria
-t Steps set number of steps spent per support profile
-l LNMFreq set LNMFreq. The Local Newton Method will run every LNMFreq steps
-v verbose mode
-h print this help message
3.5 ipa_agg / ipa_bagg
Takes an AGG/BAGG and computes an approximate Nash equilibrium using Govindan & Wilson's Iterated Polymatrix Approximation
algorithm.
ipa_agg filename rayseed
ipa_bagg filename rayseed
filename: name of the AGG file
rayseed: seed for generating the initial perturbation ray
3.6 simpdiv
The executable simpdiv takes an AGG/BAGG and computes one or more Nash/Bayes-Nash equilibria using the
simplicial subdivision algorithm as implemented in GAMBIT.
simpdiv [OPTIONS]
The program accepts a AGG file on standard input, unless option -b is specified, in which case it takes a BAGG.
The program accepts the following command-line options:
-b: Input a BAGG.
-v: Verbose output. Lists the profile computed at each stage of the
mesh refinement. Default is off, in which case the program only
prints the (approximate) Nash equilibrium of the last refinement.
-s : A list of strategy profiles to use as starting points
-f: Print profiles in floating-point (even though the algorithm inherently
computes using rational numbers)
-d #: Number of decimals to show in floating-point output
(Only has an effect in conjunction with -f)
-r #: Generate random starting points with denominator #.
-n #: Stop after # equilibria (only effective with -r)
-g #: Multiplier for grid restart (default is 2)
4. Acknowledgements
Kevin Leyton-Brown is the supervisor of this project.
gnm_agg and ipa_agg are based on the GameTracer package
(http://dags.stanford.edu/Games/gametracer.html) by Ben Blum and Christian
Shelton, which implements Govindan & Wilson's algorithms for the normal
form.
simpdiv is based on the implementation of simplicial subdivision algorithm
from GAMBIT (http://gambit.sourceforge.net/).
The GNM algorithm is outlined in a paper by Srihari Govindan and
Robert Wilson titled "A global Newton method to compute Nash
equilibria". It appeared in the Journal of Economic Theory in
2003.