Polynomial Time Algorithms for Market Equilibria

新的机制设计问题，深深植根于算法考虑，随着互联网的出现，因为在具有不同程度合作和自私动机的大量参与者之间分配有限的资源是后者的重要考虑。这些问题的解决方案背后的计算问题，实现理想的经济标准，往往被证明是困难的。因此，将近似算法领域的概念应用于这些问题是很自然的。这种联系因为博弈论和近似算法的两个领域共享共同的方法论--都大量使用线性规划理论中的机器。PI最近的工作包括使用近似不动点计算和原始-对偶模式来给出利润最大化的定价算法和成本分担方法，以确保公平性和揭示真相的公式化广播路由。除了将这些技术应用到其他游戏中，PI还想描述形成Jani和Vazirani的公平方法的交叉单调方法的特征。

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.