AF: Small: Research on Equilibria, Fixed Points, and Approximation

Columbia University, New York NY

Investigators

Abstract

The overall goal of this project is the development of the computational theory and algorithms for equilibria and fixed points. Many models from a wide variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include the computation of Nash equilibria of games; price equilibria in markets; computation of optimal strategies and values of competitive, dynamic games (e.g., stochastic games); analysis of basic stochastic models for evolution like branching processes, and for language like stochastic context-free grammars; and models that incorporate the fundamental primitives of probability and recursion like recursive Markov chains. These models have been studied for a long time by different communities, leading to the development of rich theories. However, basic algorithmic questions have remained open. Recent work has discovered common threads that run through several of these problems, and has identified common algorithmic principles that underlie some of these problems, formalized through appropriate complexity classes and completeness results. The project will develop the computational theory of fixed points and equilibria along several directions. On the one hand the project will advance the general theory by unifying problems and identifying paradigms that are not adequately captured by the current classes, and by investigating the relationships between the different classes and paradigms. On the other hand, the project will investigate particular models and problems (e.g., computation of market equilibria, dynamic market adjustment schemes, stochastic games, and probabilistic recursive models) seeking to develop efficient solutions or to identify the intrinsic obstacles that prevent such solutions. The intellectual merit and goal of this project is to discover new unifying principles and methods that apply to central problems from different fields. It will leverage the computational way of thinking to establish connections and advance greatly our knowledge on a number of important challenging problems. The project is expected to have broader impact on a variety of fields. The concepts and models under investigation are fundamental in various disciplines (including economics, game theory, biology, and various areas of computer science), and they have been studied and are used extensively. Identifying the common computational principles and connections between the different problems facilitates the cross-fertilization of ideas and methods among the different areas. Providing efficient algorithms for their solution, whenever possible, will be greatly beneficial to the relevant areas. The project will include the training of a graduate student, and the preparation of expository survey articles that synthesize the knowledge in the field and which will be useful for teaching and training. The results will be broadly disseminated with presentations at conferences and universities, and with scholarly publications.