Loading Events

« All Events

  • This event has passed.

Fishbowl teleseminar: Porting the Computer Science Toolbox to Game Theory and Economics

April 11, 2013 @ 4:00 am - 5:00 pm

Prof. Tim Roughgarden
Stanford University


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

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
significant 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-ACM-SIGACT Godel Prize.


April 11, 2013
4:00 am - 5:00 pm