The Gödel Prize 2012 - Laudatio

The Gödel Prize 2012 for outstanding papers in theoretical computer science is awarded jointly to the following three papers:

Elias Koutsoupias and Christos H. Papadimitriou: Worst-case equilibria,Computer Science Review, 3(2): 65-69, 2009.
Tim Roughgarden and Éva Tardos: How Bad Is Selfish Routing?,Journal of the ACM, 49(2): 236-259, 2002.
Noam Nisan and Amir Ronen: Algorithmic Mechanism Design,Games and Economic Behavior 35: 166-196, 2001.
(pdf)

These three papers, appearing in their conference versions around the turn of the millennium, contributed highly influential concepts and results that laid the foundation for an explosive growth in algorithmic game theory, a transdisciplinary combination of the theory of algorithms and the theory of games that has greatly enriched both fields.

All three papers aimed to improve our understanding of the behavior of the internet and other complex computational systems, when users and service providers in those systems act selfishly. The paper by Koutsoupias and Papadimitriou introduced what is today known as the “price of anarchy“, the first quantitative measure of the degree of inefficiency of equilibria in games, formally defined as the worst-case ratio between the social cost of a Nash equilibrium and the optimal social cost. The paper by Roughgarden and Tardos revealed the power and depth of the “price of anarchy” concept, providing striking and remarkably complete results on the relationship between centralized optimization and “selfish routing” in network traffic. Finally, the paper by Nisan and Ronen introduced a whole new range of applications of the theory of mechanism design within computer science, in the process also transforming and significantly enriching the theory of mechanism design by introducing algorithmic resource bounds as well as notions of approximate optimality.

Gödel committee 2012:

Sanjeev Arora ( Princeton University)

Josep Díaz (Universitat Politecnica de Catalunya)

Giuseppe Italiano (Università di Roma Tor Vergata)

Mogens Nielsen (Aarhus University)

Daniel Spielman (Yale University)

Eli Upfal (Brown University)