Mihalis Yannakakis (Columbia University)
Many models from a variety of areas involve the computation of an equilibrium or stable configuration 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; analyzing basic stochastic models for evolution like branching processes, and many others. Often the sought objects can be described mathematically as the fixed points of an equation x=F(x). In this talk we will discuss several types of equilibria and fixed point computation problems, their complexity, and some of the common principles that connect them.