(Warwick)

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.

Robert Recorde Room

Department of Computer Science