Action Graph Game Solver
Albert Xin Jiang and Kevin Leyton-Brown
Based on the GameTracer package
(http://dags.stanford.edu/Games/gametracer.html) by Ben Blum, Christian Shelton
CONTENTS
1.Introduction
2.Installation
3.Usage
4.Acknowledgments
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
-coffee Generate a coffee shop game
-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 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. Acknowledgments
Kevin Leyton-Brown is the supervisor of this project.
gnm_agg is 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.