Polynomial Time Algorithms for Market Equilibria

市场均衡的多项式时间算法

• 批准号: 0311541
• 负责人: Vijay Vazirani
• 金额: $ 10.2万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0311541&HistoricalAwards=false
• 关键词: Polynomial; Time; Algorithms; Market; Equilibria

New mechanism design issues, deeply rooted in algorithmic considerations, have arisen with the Internet, since distribution of limited resources among a large number of players with varying degrees of collaborative andselfish motives is an important consideration in the latter.Computational problems underlying solutions tothese issues, achieving desirable economic criteria, often turnout to be \NP-hard. It is therefore natural to apply notions fromthe area of approximation algorithms to these problems. Theconnection is made more meaningful by the fact that the two areas ofgame theory and approximation algorithms share common methodology-- both heavily use machinery from the theory of linear programming.Recent works of the PI include using approximate fixed point computations and the primal-dual schema to give a profit-maximizing pricing algorithm and a cost sharing method ensuring fairness and truth-revealing formulticast routing. Besides applying these techniques to other games,the PI would like to characterize cross-monotone methods thatform the equitable methods of Jani and Vazirani.

深深植根于算法考虑的新机制设计问题随着互联网的出现而出现，因为在具有不同程度的协作和自私动机的大量参与者之间分配有限的资源是后者的一个重要考虑因素。这些问题的解决方案背后的计算问题，达到理想的经济标准，往往是\NP-难的。因此，很自然地将近似算法领域的概念应用于这些问题。博弈论和近似算法这两个领域共享共同的方法论，这一事实使得这种联系变得更有意义——两者都大量使用线性规划理论中的机制。PI 最近的工作包括使用近似定点计算和原对偶模式给出一种利润最大化的定价算法和成本分摊方法，确保组播路由的公平性和真实性。除了将这些技术应用于其他游戏之外，PI 还希望表征形成 Jani 和 Vazirani 公平方法的交叉单调方法。