Towards a Black-box Solver for Finite Games: The Gambit System
Presenter
October 24, 2006
Keywords:
- Nash functions
MSC:
- 14P20
Abstract
An intriguing fact about the celebrated Nash equilibrium concept in
finite
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
inequalities.
As a result, there are general-purpose algorithms to compute Nash
equilibria
on finite games. Many of these algorithms relate specifically to
well-studied areas of numerical programming, including linear
programming,
homotopy path-following, and solving polynomial systems.
Game theory appears in a broad range of disciplines, and is taught
broadly
at the undergraduate level. Students and practitioners alike need a
tool
to specify and analyze games without needing to worry about the
computational
details of finding equilibria. The Gambit system is an Open Source
(GPL)
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.