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

AF：小：市场、均衡和不动点的计算方面

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

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.

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