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.

互联网上出现了新的机制设计问题，它根深蒂固地植根于互联网上，因为在多种协作和泼妇动机的大量参与者中分配有限的资源是后者的重要考虑因素，这是解决方案的基础问题中的一个重要考虑因素，这些问题是解决所需的经济标准的问题，通常会达到理想的经济标准。因此，自然要将近似算法区域的概念应用于这些问题。通过与线性编程理论相互使用的两个领域的理论和近似算法共享共同方法的事实，这一事实具有更有意义。除了将这些技术应用于其他游戏之外，PI还希望表征横孔酮方法，以形成Jani和Vazirani的公平方法。