权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Medium: New Frontiers in Equilibrium Computation

AF：中：平衡计算的新领域

基本信息

批准号：
1703925
负责人：
Mihalis Yannakakis
金额：
$ 119.95万
依托单位：
Columbia University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-05-01 至 2022-04-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1703925&HistoricalAwards=false
关键词：
AF Medium New Frontiers Equilibrium

项目摘要

Concepts and methodologies from economics and social sciences have found numerous applications in the study of the Internet and e-commerce. At the core of many such applications lies the notion of equilibria, which has been widely studied by game theorists and economists to model and predict the strategic behavior of selfish yet rational agents. During the past decade, the computation of equilibria in both games and markets has been studied intensively and many of the exciting developments have brought new insights towards a much better understanding of equilibria. At the same time, they opened up a window to many new research challenges. The goal of the project is to explore some of the important directions and problems that have emerged in the new frontiers of equilibrium computation. Research along directions pursued in the project will complement the already extensive literature in economics and social sciences on equilibria, by offering new perspectives through the lens of algorithms, approximation, and computational complexity. In addition to curriculum development, mentoring PhD students, and involving undergraduate students in accessible projects, the PIs will actively pursue outreach activities and broadly disseminate results obtained in the project.Some of the research directions that the PIs plan to explore include the following: 1) Deepen our understanding of the new exponential-time hypothesis for fixed-point computation employed by Rubinstein in his recent breakthrough, by exploring its connections with other natural conjectures on the exact complexity of fundamental equilibrium computation problems. 2) Explore connections between two problems that have been studied intensively in the literature, the problem of finding an approximate Nash equilibrium in an anonymous game with a polynomial precision and that in a two-player game with a constant precision. 3) Study the computation of equilibria in games and markets with a unique equilibrium. Equilibrium as a prediction tool is more meaningful when a unique equilibrium exists. 4) Work towards a dichotomy theorem for Arrow-Debreu market equilibria that aims to classify every family of utilities into those that are easy to solve and those that are intractable.

经济学和社会科学的概念和方法在互联网和电子商务的研究中得到了大量的应用。许多此类应用的核心是均衡的概念，博弈论者和经济学家对此进行了广泛的研究，以建模和预测自私但理性的代理人的战略行为。在过去的十年里，对博弈和市场中均衡的计算进行了深入的研究，许多令人兴奋的发展为更好地理解均衡带来了新的见解。与此同时，他们为许多新的研究挑战打开了一扇窗。该项目的目标是探索平衡计算新领域中出现的一些重要方向和问题。沿着该项目所追求的方向进行的研究将通过算法、近似性和计算复杂性的视角提供新的视角，从而补充经济学和社会科学中关于均衡的已经广泛的文献。除了课程开发、指导博士学生和让本科生参与可理解的项目外，个人调查还将积极开展外展活动，并广泛传播项目中取得的成果。个人调查计划探索的一些研究方向包括：1)通过探索与其他关于基本平衡计算问题精确复杂性的自然猜想之间的联系，加深我们对鲁宾斯坦在其最近的突破中采用的定点计算的新指数时间假说的理解。2)探讨了文献中研究较多的两个问题之间的联系，即在精度为多项式的匿名对策中寻找近似纳什均衡的问题和在精度为常数的两人对策中寻找近似纳什均衡的问题。3)研究具有唯一均衡的博弈和市场均衡的计算。当存在唯一均衡时，均衡作为一种预测工具更有意义。4)致力于建立Arrow-Debreu市场均衡的二分法定理，旨在将每一类公用事业分为容易解决的和难以解决的。

项目成果

期刊论文数量（67）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Hedging in games: Faster convergence of external and swap regrets

博弈中的对冲：外部遗憾和互换遗憾的更快收敛

DOI：
发表时间：
2020
期刊：
Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020
影响因子：
0
作者：
Chen, Xi;Peng, Binghui
通讯作者：
Peng, Binghui

Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis

摩擦接触被动静平衡及其在抓取稳定性分析中的应用

DOI：
10.15607/rss.2018.xiv.064
发表时间：
2018
期刊：
Robotics: Science and Systems XIV
影响因子：
0
作者：
Haas-Heger, Maximilian;Papadimitriou, Christos;Yannakakis, Mihalis;Iyengar, Garud;Ciocarlie, Matei
通讯作者：
Ciocarlie, Matei

Doubly Balanced Connected Graph Partitioning

双平衡连通图划分