Action Graph Games

Action graph games (AGGs) are a graphical representation of simultaneous-move games. AGGs can compatcly represent games with structured utility functions. Furthermore, computation of solution concepts like Nash equilbrium on AGGs can be exponentially faster compared to normal-form based algorithms. For more information on AGGs, the following paper gives a comprehensive discussion.

For incomplete-information settings, the NIPS'10 paper by Albert Xin Jiang and Kevin Leyton-Brown proposes Bayesian Action-Graph Games (BAGGs), an extension of AGGs that compactly represents Bayesian games.

For temporal settings, the UAI'09 paper by Albert Xin Jiang, Kevin Leyton-Brown and Avi Pfeffer proposes Temporal Action-Graph Games (TAGGs), an extension of AGGs that compactly represents dynamic games.

For an application of AGGs to ad auctions, see the EC'09 paper by David Thompson and Kevin Leyton-Brown, which uses AGGs to model and efficiently compute equilibria for several different position auction mechanisms under several preference models.

Software for AGGs and BAGGs

Here are some software packages that make use of the action-graph game (AGG) and Bayesian action-graph game (BAGG) representations. These include a solver for computing Nash equilibria of games represented as AGGs, a graphical user interface for creating, editing and visualizing AGGs, and game generators that generate AGG instances.

AGG file format

These software packages can read/write a description of an AGG from/into a text file. The format of the AGG descrption file is specified here. (Updated May 2013: for compatibility with GAMBIT, please put "#AGG" as the first line of the file.)

Example: a simple 2-player 2-action symmetric game

BAGG file format

The BAGG file format is described here.

Gambit-AGG

We are currently working on incorporating AGG functionality into Gambit, a collection of software tools for game theory. A version of Gambit with AGG integration is available at Gambit's Github repository, and will be soon released as Gambit 14.0.0.

If you are interested in contributing, please contact Ted Turocy or Albert Xin Jiang. See also project idea descriptions at the Gambit website.

AGG/BAGG Solver

Our AGG/BAGG solver reads in a description of the AGG/BAGG in the above formats, and then computes one or more Nash equilibria using either Govindan & Wilson's Global Newton Method (GNM) or van der Laan, Talman & van der Heyden's simplicial subdivision algorithm.

It is written in C++ by Albert Xin Jiang and Kevin Leyton-Brown, and makes use of the GameTracer package (an implementation of Govindan & Wilson's algorithm), and GAMBIT's implementation of the simplicial subdivision algorithm. It has been tested on Windows and Linux systems, but should work on other UNIX systems as well.

Current version: 3.1 (May, 2013): Bugfixes
Download source code
Download README
Version 3.0 (November, 2011): Added new solvers based on GNM that compute symmetric (Bayes) Nash equilibria for symmetric (B)AGGs.

Version 2.0 (October, 2010)
The main new feature is the ability to solve BAGGs, using Govindan & Wilson's GNM algorithm or the simplicial subdivision algorithm.
Download source code
Download README

Older versions
AGG Solver version 1.0 (AGG only)
Download source code

AGG Graphical User Interface

AGGUI is a graphical user interface developed by Damien Bargiacchi, Albert Xin Jiang and Kevin Leyton-Brown. It allows users to create and edit AGGs, read in existing AGGs, and visualize strategy profiles (e.g. Nash equilibria) as a density map the action graph. It is written in Java and runs on any platform that supports Java.

Download AGGUI
Download README

Examples of visualizations of Nash equilibria produced by AGGUI:

AGG generators in GAMUT

GAMUT is a suite of generators of different types of games. We (Albert Xin Jiang and Kevin Leyton-Brown) have extended GAMUT with generators of AGG instances.

Download GAMUT with AGG generators (Updated June 2013: now outputs "#AGG" as the first line of the file, for compatibility with GAMBIT.)
Download README

This web site is maintained by Albert Xin Jiang.