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 and selfish motives is an important consideration in the latter. Computational problems underlying solutions to these issues, achieving desirable economic criteria, often turn out to be NP-hard. It is therefore natural to apply notions from the area of approximation algorithms to these problems. The connection is made more meaningful by the fact that the two areas of game 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 for multicast routing. Besides applying these techniques to other games, the PI would like to characterize cross-monotone methods that form the equitable methods of Jani and Vazirani.
