The ACM announced the 2012 Gödel Prize awardees, three seminal papers in algorithmic game theory. The prizes themselves will be presented at ICALP in Warwick in July.
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.
The first paper introduced the price of anarchy. The second applied price of anarchy to routing problems. The third applied algorithmic techniques and competitive analysis to auctions.
Congrats to all the winners.
Congratulations!
ReplyDeleteI didn't know one can award a prize to three papers, but these are the three papers that started the whole area of algorithmic game theory.
As far as I remember, the proof of 4/3 result by Roughgarden and Tardos was wrong and that's the reason that Correa, Schulz, and Stier-Moses proved it using a completely different geometric approach in Games and Economic Behavior 64 (2008) 457–469.
ReplyDeleteIf so, it seems a bit strange.
The original proof is correct. The paper you cite provides a nice alternative proof.
DeleteTypo: Worst-case equilibria was published in 1999.
ReplyDeleteThe journal version was published in 2009. The Gödel Prize is awarded to papers published in a refereed journal within the last 14 years.
DeleteSorry. I didn't know the details. I thought that only the date of the first submission was important.
Delete