Triangle Computer Science Distinguished Lecturer Series

Porting the Computer Science Toolbox to Game Theory and Economics

Speaker:Tim Roughgarden
Stanford University
Date: Monday, September 10, 2012
Time: 4:00pm - 5:00pm
Location: 130A North Building, Duke


Theoretical computer science has brought new ideas and techniques to game and economic theory. A primary signature of the computer science approach is {em approximation} --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. We explain two of our recent contributions in this area, one motivated by networks and one by auctions.

We first discuss the "price of anarchy": how well does decentralized (or "selfish") behavior approximates centralized optimization? This concept has been analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. We highlight a new theory of robust price of anarchy bounds, which apply even to systems that are not in equilibrium.

Second, we consider auction design: for example, what selling procedure should be used to maximize the revenue of a seller? On the analysis side, we highlight a new framework that explicitly connects average-case (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worst-case analysis approach common in computer science. On the design side, we provide a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the distribution-specific optimal auction.


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 awards include the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003 Tucker Prize, a 2007 PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society, the 2009 ACM Grace Murray Hopper Award, and the 2012 EATCS-SIGACT Godel Prize. He recently developed a free online course on the design and analysis of algorithms, enrolling tens of thousands of students.

Hosted by:
Duke: Vince Conitzer