Swaprava Nath sent me a short summary that he wrote about the 11th Max Planck Advanced Courseon the Foundations of Computer Science on Approximation Algorithms and Algorithmic Game Theory that he recently attended in Saarbrücken, Germany:
The setting for this series of lectures were to discuss the computational issues involved in finding Nash Equilibrium and the hardness results. Given the hardness of the problems, approximation algorithms that are developed to address different relaxation of these problems were the focus of the talks. The speakers identified one area of these algorithmic issues.
The first one by Christos Papadimitriou addressed the general complexity classes and their interrelationships. The examples of the new complexity classes of PPAD, PPADS, PPA, PPP etc were shown with examples and showing that some of them implies some other were part of our exercises.
The second problem of Market Modeling and pricing of objects were addressed by Vijay Vazirani. In his lectures, the main focus was on Fisher’s linear market model and the Eisenberg Gale linear program which in the optimal solution gives a market clearing allocation and pricing (the allocation ensures that each bidder gets an optimal bundle of products and the pricing ensures that all products are sold and nobody has any surplus money).
The third problem of Cost sharing and approximation algorithms was addressed by Guido Schaefer. In his talks, he initially introduced the mechanism design framework and the reason for Incentive Compatibity. He discussed Moulin Mechanisms which under the assumption of ‘cross monotonic’ cost sharing functions can be shown to be group strategyproof and budget balanced. Note that all these frameworks work on a strong notion of Dominant Strategies. When more desirable properties of efficiency come into the play, because of the impossibility results of Green and Laffont, this calls for an approximation algorithm. The workaround in this setting is via approximating the budget balance and the total value. He analyzed these approximation algorithms with the example of Steiner Tree.
All the speakers concluded with some new directions in these fields and the current shape of the research. The lecture notes are available in the website.