Game Over! The end of the line for NASH

Photograph of Paul Goldberg

Paul Goldberg


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.
Tuesday 25th April 2006, 14:00
Robert Recorde Room
Department of Computer Science