
Abstract
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 averagecase (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worstcase analysis approach common in computer science. On the design side, we provide a distributionindependent auction that performs, for a wide class of input distributions, almost as well as the distributionspecific optimal auction.
Biography
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 coedited 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 EATCSSIGACT Godel Prize. He recently developed a free online course on the design and analysis of algorithms, enrolling tens of thousands of students.