Porting the Computer Science Toolbox to Game Theory and Economics

Monday, January 30, 2012 - 10:15am


Monday, March 5, 2012
3:30 – 4:30 PM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Subhash Suri

SPEAKER: Tim Roughgarden
Computer Science, Stanford University

Title: Porting the Computer Science Toolbox to Game Theory and Economics


Theoretical computer science has brought new ideas and techniques to
game and economic theory. A primary signature of the computer science
approach is 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


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, 2007
PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society,
and the 2009 ACM Grace Murray Hopper Award. He’s currently developing a
free online course on the design and analysis of algorithms, which has
over 50,000 students.