Game Theory: GameTracer

Ben Blum, Daphne Koller, Christian Shelton

GameTracer is an application for calculating Nash equilibria in normal-form games. It implements the global Newton method of Govindan and Wilson (2001), as well as their iterative polymatrix approximation algorithm, a faster method without any theoretical guarantee of convergence. GameTracer is released under the GNU license, and can be compiled under Linux or Solaris. Unpack the archive into a directory and read the README for installation instructions.

NOTE: GameTracer has been updated to compile with GCC version 3.2.2 in Linux and will no longer be tested under Solaris.


gametracer-0.2.tar.gz Instructions for Download
Create a directory in which you wish to install GameTracer. You do not need root privileges to install this program. Place gametracer-0.2.tar.gz in the directory you have created, and unpack it with the command
tar -xzf gametracer-0.2.tar.gz
Follow the instructions in the README file to compile GameTracer.

contact information

For questions regarding GameTracer, write to Christian Shelton at


This work was funded under Air Force contract F30602-00-2-0598 under DARPA's TASK program and ONR contract N00014-00-1-0637 under the MURI program "Decision Making under Uncertainty"

The GNM algorithm is outlined in a paper by Srihari Govindan and Robert Wilson titled A global Newton method to compute Nash equilibria. It will appear in the Journal of Economic Theory in 2003.

The IPA algorithm is outlined in a companion to the above paper, also by Govindan and Wilson, titled Computing Nash Equilibria by Iterated Polymatrix Approximation. It will appear in the Journal of Economic Dynamics and Control in 2003.

For information about similar results for extensive form games, please refer to the following paper by Govindan and Wilson:
Structure theorems for game trees. Govindan, S., and Wilson, R. Proceedings of the National Academy of Sciences, 2002. Vol. 99, Issue 13: 9077-9080