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.

新的机制设计问题，深深植根于算法的考虑，已经出现了与互联网，因为有限的资源分配之间的大量球员有不同程度的合作和自私的动机是一个重要的考虑，在后者。计算问题的基础解决这些问题，实现理想的经济标准，往往是\N P困难。因此，将近似算法领域的概念应用于这些问题是很自然的。这种联系是更有意义的事实，这两个领域的博弈论和近似算法共享共同的方法-都大量使用机器从理论的线性programming.Recent作品的PI包括使用近似不动点计算和原始-对偶模式，以获得利润最大化的定价算法和成本分摊方法，确保公平性和真理揭示formulticast路由。除了将这些技术应用于其他游戏之外，PI还希望描述Jani和Vazirani的公平方法的交叉单调方法。