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.
The project resulted in several advances in the computational theory and algorithms for equilibria and fixed points, and applications to the computational analysis of several types of basic stochastic models that are used in a variety of fields. In the area of computation of market equilibria, the project resolved the longstanding open problem of determining the complexity of CES (constant elasticity of substitution) markets. Furthermore, a general notion of non-monotone utilities was introduced, which covers a wide variety of utility functions in economic theory (including CES, Leontief, piecewise linear), and which was shown to lead to computational hardness. An efficient algorithm was developed for the computation of the least fixed point solution of a multivariate system of monotone probabilistic polynomial equations to any desired accuracy, in time polynomial in the encoding size of the system and the number of bits of precision. As a consequence, polynomial-time algorithms were obtained to compute (to desired accuracy) the key quantities of several classical stochastic models, e.g. the extinction probability of multitype branching processes, the probability of the language generated by a stochastic context-free grammar, and the termination probability of 1-exit recursive Markov chains. The algorithm was extended to probabilistic polynomial systems that include also the max or the min operator, leading thereby to polynomial-time optimization for branching Markov decision processes and related models. Efficient algorithms were developed for some other basic problems on general stochastic context-free grammars, including the computation of the probability of a given string, and the computation of an approximately equivalent stochastic grammar in Chomsky Normal form. An algorithm was developed for the computation of the probability that a given scfg generates a string in a given regular language; the algorithm runs in polynomial time for a broad class of grammars, including those constructed by the standard inside-outside (EM) algorithm. Polynomial-time algorithms were developed for the analysis of Quasi-birth-death processes, including for quantitative model checking with respect to general omega-regular properties. A comprehensive study of Boolean programs (a popular domain for static-analysis-based software model checking) was performed, involving new algorithms and lower bounds, characterizing the effects that different features of the programs have on the complexity of basic model checking problems. The complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting was resolved, i.e., the optimal item pricing problem when the buyer's values for the items are independent.
