The 2012 Gödel Prize, which recognizes outstanding papers in theoretical computer science published over the past 14 years, has just been announced. This year it recognizes three prominent papers that helped to launch the field of Algorithmic Game Theory, and these papers’ six authors: Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen. Quoting from the ACM’s official citation (editing slightly to improve readability):
In their paper “Worst-case Equilibira,” Koutsoupias and Papadimitriou introduced the “price of anarchy” concept, a measure of the extent to which competition approximates cooperation. It quantifies how much performance is lost due to selfish behaviors in systems like the Internet, which operates without a system designer or monitor striving to achieve the “social optimum.” Their answer, surprisingly often, is “not that much.”
Roughgarden and Tardos revealed the power and depth of the “price of anarchy” concept as it applies to routing traffic in large-scale communications networks to optimize the performance of a congested network. Their paper “How Bad Is Selfish Routing?” revisits an old conundrum in transportation science known as “Braess’s paradox,” and provides remarkably complete results on the relationship between centralized optimization and selfish routing in network traffic.
Nisan and Ronen coined the term “algorithmic mechanism design” in their paper of the same title, presenting a whole new range of applications of the theory of mechanism design within computer science. Combining ideas from economics and game theory with concepts and techniques from computer science, they enriched both mechanism design and the theories of algorithms and complexity.
It’s great to see this level of recognition of the importance of algorithmic game theory in general, and these influential papers in particular, by the broader TCS community. Congratulations to all the winners! (I should note that half the winners—one from each paper—are contributors to this blog: Elias Koutsoupias, Noam Nisan and Tim Roughgarden. They would surely have been too modest to post this announcement themselves, but congratulations to them anyway. :-))