2010 has seen the field of Algorithmic Game Theory and Economics continue its process of maturing. I can not point out any breakthroughs this year, conceptual or technical, but we have seen a significant widening in scope, in points of view, in ways of analysis, in application areas, as well as an increase in technical depth.
Interest in Computational Social Choice is rising, and the dividing line between it and Algorithmic Mechanism Design is blurring. Among the topics of interest are various notions of approximation, notions of fairness, and positive results without quasi-linearity.
In Algorithmic Mechanism Design, computer scientists are slowly graduating from the basic “private-value dominant-strategy quasilinear” settings and paying more attention to into more sophisticated, problematic, and realistic Bayesean models, correlated values, and other complications. On the basic open problem of AMD, that of reconciling computational complexity with incentives, there has been some progress, but the basic challenge still seems beyond our powers.
The more applied world of research into ad auctions is also widening, with most interest now going beyond the basic multi-slot “adwords auction“, to the more sophisticated types of challenges raised by display auctions, ad-exchanges, privacy issues, social networks, and such.
On the core algorithmic/complexity questions of the computational difficulty of finding equilibria in games and markets we have seen only little progress, mostly for some market variants. There was some commotion regrading the complexity of correlated equilibria in concise games, but that was soon settled.
The extremely influential “price of anarchy” line of work seems to be getting closer to being exhausted. Its point of view of analyzing the loss due to rationality constraints using a competitive ratio framework seems to still rule, but now this would be just one ingredient in a research effort rather than the effort itself.
Beyond the growing set of AGT conferences, and the growing place of AGT within other fields, we have seen a multitude of worshops, and schools on AGT throughout the year, from Bertinoro to Lisbon to Saarbrucken to Aarhus and from Tehran to Shanghai to Auckland, with more coming next year from LA to Jerusalem.
As far as I can see, as “Algorithmic Game Theory/Economics” is getting larger and wider, it is also getting more fragmented and I have an acute feeling that my point of view is restricted. Comments from readers adding their point of view are highly encouraged.
Happy New year!