Events Calendar

GTHB Seminar

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 worst-case ratio between the welfare of a Nash equilibrium and that of an optimal (first-best) 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 worst-case price of anarchy for pure Nash equilibria *necessarily* implies the exact same worst-case 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 regret-minimization).

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 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, 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