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.
Turing's Invisible Hand 
Regarding Schaefer’s talks:
As far as I understood, due to Green-Laffont theorem, it is impossible to achieve Budget Balance + Efficiency. So we have to compromise on one of these two. Moulin mechanisms are budget balanced but we need to design appropriate cross monotonic cost sharing functions. And because of computational issues, we cannot design cross monotonic functions which are budget balanced. But then we can do beta budget balanced mechanisms. Scaefer proposed incremental mechanisms which are not group strategyproof as Moulin. However, they have better beta budget balanced properties.
Regarding Christos Papadimitriou’s talk:
I would like to add that he explained important steps in showing NASH is PPAD complete. He talked about computing Nash equilibria in sparse games or games which has succinct representations. He also explained that, if agents are not expected utility maximizers, in many cases, we cannot guarantee existence of Nash equilibrium.
[…] seen a multitude of worshops, and schools on AGT throughout the year, from Bertinoro to Lisbon to Saarbrucken, from Tehran to Shanghai, with more coming next year from LA to […]