Corelab Seminar
2010-2011
Antonis Antonopoulos
Equilibria, Fixed Points and Complexity Classes (Survey Paper by M.Yannakakis)
Abstract.
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind.
Examples include Nash equilibria in games, computing optimal strategies and the values of competitive games,
stable configurations of neural networks, analysing basic stochastic models for evolution like branching processes and for
language-like context-free grammars.
It is not known whether these problems can be solved in polynomial time.
There are certain common computational principles underlying different types of
equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP.
Representative complete problems for these classes are, respectively, pure Nash equilibria in games where
they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games,
and (mixed) Nash equilibria in normal form games with three (or more) players.
In this lecture we will review the underlying computational principles, and the corresponding classes!