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

该项目的总体目标是发展平衡点和不动点的计算理论和算法。来自不同领域的许多模型都涉及某种平衡点或固定点的计算。例子包括博弈纳什均衡的计算；市场价格均衡；竞争动态博弈（如随机博弈）的最优策略和值的计算；分析进化的基本随机模型，如分支过程，以及语言的随机上下文无关语法；以及包含概率和递归基本要素的模型，比如递归马尔可夫链。这些模型已经被不同的社区研究了很长时间，导致了丰富的理论发展。然而，基本的算法问题仍然悬而未决。最近的工作已经发现了贯穿其中几个问题的共同线索，并确定了作为其中一些问题基础的通用算法原则，并通过适当的复杂性类和完备性结果进行了形式化。该项目将沿着几个方向发展不动点和平衡的计算理论。一方面，该项目将通过统一问题和识别当前类别未充分捕获的范式，以及通过调查不同类别和范式之间的关系来推进一般理论。另一方面，该项目将调查特定的模型和问题（例如，市场平衡的计算、动态市场调整计划、随机游戏和概率递归模型），寻求制定有效的解决方案或确定阻止这种解决方案的内在障碍。这个项目的智力价值和目标是发现新的统一的原则和方法，适用于不同领域的中心问题。它将利用计算的思维方式来建立联系，并大大提高我们对许多重要挑战性问题的认识。预计该项目将对各个领域产生更广泛的影响。所研究的概念和模型是各个学科（包括经济学、博弈论、生物学和计算机科学的各个领域）的基础，它们已经被广泛研究和使用。识别不同问题之间的共同计算原理和联系，有助于不同领域之间思想和方法的交叉施肥。在可能的情况下，为这些问题的解决提供有效的算法，将对相关领域大有裨益。该项目将包括培训一名研究生，并编写综合该领域知识的说明性调查文章，这些文章将有助于教学和培训。研究结果将通过在会议和大学的演讲以及学术出版物广泛传播。

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.