The overall goal of this project is to advance the computational theory and algorithms for equilibria and fixed points. Many problems from different areas can be formulated as the problem of computing a fixed point of a suitable function F. Examples include the computation of Nash equilibria of games, price equilibria in markets, the value and optimal strategies for stochastic and other dynamic games, the analysis of various basic stochastic models (branching processes, stochastic context-free grammars, recursive Markov chains, and others) that arise in many areas. In some cases (e.g., Nash and market equilibria) one wishes to compute any fixed point, while in several others (e.g., stochastic models and games), the function F is monotone and one wishes to compute a specific fixed point, the least fixed point.
The project will build on recent progress to advance the theory and algorithms on two fronts: market equilibria, and least fixed point problems. In the first area, it will seek to develop a more systematic methodology and show general results that characterize what features make the market equilibrium problem hard and what features make it easy; it will advance our understanding of the computation of equilibria, both on the hardness side and on the algorithmic side; and it will try to resolve open questions regarding specific types of markets, and limitations of price adjustment schemes. In the second area, the project will leverage recent powerful positive results to address and solve in a unified way basic problems on stochastic context-free grammars, quasi-birth-death processes, and other stochastic models that require the solution of more general classes of monotone fixed point equations.
The problems and models studied in this project are fundamental in various disciplines (including economics, game theory, biology, and various areas of computer science such as verification and natural language processing), and they have been studied and are used extensively. The research of the project will provide a systematic, unified treatment of the underlying fundamental questions, and will result in algorithms and insights that are useful in the various relevant areas.
