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 <filename>: 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.