Towards a Black-box Solver for Finite Games: The Gambit System

Tuesday, October 24, 2006 - 10:50am - 11:40am
EE/CS 3-180
Theodore Turocy (Texas A & M University)
An intriguing fact about the celebrated Nash equilibrium concept in
games is that it can be expressed mathematically in a variety of ways:
as a fixed point, a solution to a complementarity program, a (global)
minimizer, or a solution to a system of polynomial equations and
As a result, there are general-purpose algorithms to compute Nash
on finite games. Many of these algorithms relate specifically to
well-studied areas of numerical programming, including linear
homotopy path-following, and solving polynomial systems.
Game theory appears in a broad range of disciplines, and is taught
at the undergraduate level. Students and practitioners alike need a
to specify and analyze games without needing to worry about the
details of finding equilibria. The Gambit system is an Open Source
set of software tools for specifying and analyzing games, with the goal
of packaging quality implementations of numerical codes from experts in
a convenient form for general use. This talk will introduce the Gambit
system and outline current implementations of algorithms for computing
equilibrium, with special emphasis on the role of a method for computing
all equilibria which uses the PHCPACK system as a backend.
MSC Code: