Equilibria, Fixed Points, and Complexity Classes

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; market equilibria; computing optimal strategies
  and the values of competitive games (stochastic and other games);
  stable configurations of neural networks; analysing basic stochastic
  models for evolution like branching processes and for language like
  stochastic context-free grammars; and models that incorporate the
  basic primitives of probability and recursion like recursive Markov
  chains.  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
  2-player normal form games, and (mixed) Nash equilibria in normal
  form games with 3 (or more) players.  This paper reviews the
  underlying computational principles and the corresponding classes.