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.