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

AF：小：平衡、不动点和近似的研究

• 批准号: 1017955
• 负责人: Mihalis Yannakakis
• 金额: $ 50万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017955&HistoricalAwards=false
• 关键词: AF; Small; Research; Equilibria; Fixed

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.

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