AF: Small: Computational Aspects of Markets, Equilibria, and Fixed Points

本项目的总体目标是推进平衡点和不动点的计算理论和算法。来自不同领域的许多问题可以表示为计算适当函数F的不动点的问题。例如，博弈的纳什均衡的计算、市场中的价格均衡、随机和其他动态博弈的价值和最优策略、在许多领域中出现的各种基本随机模型(分支过程、随机上下文无关文法、递归马尔可夫链等)的分析。在某些情况下(例如，纳什和市场均衡)，人们希望计算任何不动点，而在其他几种情况(例如，随机模型和博弈)中，函数F是单调的，并且希望计算特定的不动点，即最小不动点。该项目将以最近的进展为基础，在两个方面推进理论和算法：市场均衡和最小不动点问题。在第一个领域，它将寻求开发一种更系统的方法并展示一般性结果，以表征哪些特征使市场均衡问题变得困难，哪些特征使市场均衡问题变得容易；它将促进我们对均衡计算的理解，无论是在难度方面还是在算法方面；它将试图解决关于特定市场类型和价格调整方案的限制的公开问题。在第二个领域，项目将利用最近强大的积极成果，以统一的方式解决和解决随机上下文无关文法、拟生灭过程和其他需要求解更一般类型的单调不动点方程的随机模型的基本问题。本项目研究的问题和模型是各个学科(包括经济学、博弈论、生物学和计算机科学的各个领域，如验证和自然语言处理)的基础，它们已经被研究和广泛使用。该项目的研究将对根本的基本问题提供系统、统一的处理，并将产生在各个相关领域有用的算法和见解。

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.