
GTHB Seminar
Tue, Nov 16, 2010 @ 12:00 PM  02:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Tim Roughgarden, Stanford University
Talk Title: Intrinsic Robustness of the Price of Anarchy
Abstract: The price of anarchy is a measure of the inefficiency of selfish behavior that has been successfully analyzed in many applications, including network routing, resource allocation, network formation, and even models of basketball. It is defined as the worstcase ratio between the welfare of a Nash equilibrium and that of an optimal (firstbest) solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach some Nash equilibrium. Our main result is that for many of the classes of games in which the price of anarchy has been studied, results are "intrinsically robust" in the following sense: a bound on the worstcase price of anarchy for pure Nash equilibria *necessarily* implies the exact same worstcase bound for a much larger sets of outcomes, including mixed Nash equilibria, correlated equilibria, and sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regretminimization).
Biography: Tim Roughgarden received his PhD from Cornell University in 2002 and joined the Stanford CS faculty in 2004. His research interests lie 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 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.
Host: GTHB
Location: James H. Zumberge Hall Of Science (ZHS)  159
Audiences: Everyone Is Invited
Contact: Kanak Agrawal