Joint Colloquium Distinguished Lecture Series

Robust Guarantees in Algorithmic Game Theory

Tim Roughgarden

Wednesday, October 5, 2011
306 Soda Hall (HP Auditorium)
4:00 - 5:00 pm

Tim Roughgarden
Professor, Computer Science and Management Science and Engineering Departments, Stanford University

Downloadable pdf


Computer systems and software increasingly interact with autonomous decision-makers, and the field now known as "algorithmic game theory" has responded by formulating novel problems, goals, and design and analysis techniques relevant for these modern applications. We explain two of our recent contributions, one motivated by networks and one by auctions. Both develop unusually robust performance guarantees despite the presence of "selfish" agents.

First, the price of anarchy is a measure of the inefficiency of decentralized behavior that has been successfully analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. It is defined as the worst-case ratio between the welfare of a Nash equilibrium and that of an optimal solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach an equilibrium. We introduce "smoothness arguments", which yield performance guarantees that apply even when players fail to reach a Nash equilibrium.

Second, we define a general template for auction design that explicitly connects average-case analysis, the dominant paradigm in economics, with worst-case analysis.  Using this template, we design a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the optimal auction that is specifically tailored to the input distribution.  This framework enables, for the first time, meaningful competitive analysis for auction problems with allocation asymmetries, bidder asymmetries, and costly payments.


Tim Roughgarden received his Ph.D. from Cornell University in 2002 and joined the Stanford CS department in 2004, where he is currently an associate professor. His research interests are in theoretical computer science, especially its interfaces with game theory and networks. He wrote the book "Selfish Routing and the Price of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007). His significant awards include the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003 Tucker Prize, the 2003 INFORMS Optimization Prize for Young Researchers, speaking at the 2006 International Congress of Mathematicians, a 2007 PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society, and the 2009 ACM Grace Murray Hopper Award.

  Return to EECS Joint Colloquium