Polynomial Time Algorithms for 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.