LFCS Seminar

Game Over! The end of the line for NASH

Paul Goldberg

Department of Computer Science
University of Warwick

4pm Tuesday 13th December 2005
Room 2511, JCMB, King's Buildings

---

Abstract

In 1951, Nash proved his classical result that every game admits mixed strategies that are optimal with respect to each other. Such a set of strategies is known as a Nash equilibrium. The proof is non-constructive, and the computational problem of constructing Nash equilibria has subsequently attracted considerable attention within the algorithmics community.

In this talk we review a sequence of recent papers which have culminated in the answer to this central question of algorithmic game theory. Namely, two-player games are as computationally hard to solve as other multi-player games. Moreover, these problems are all equivalent to the problem of finding generic Brouwer or Kakutani fixpoints.