Videos

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.