Mihalis Yannakakis
Columbia University
Time: Friday, April 27th, 2012, 2:30 pm
Location: CEWIT 200

Computational Aspects of Equilibria

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; price equilibria in markets; optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysis of recursive models and stochastic processes, like branching processes, stochastic context-free grammars, and recursive Markov chains. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles, the relevant algorithmic and complexity issues, and their relationship with other open questions in computation.