Intrinsic Robustness of the Price of Anarchy


May 20, 2009


Tim Roughgarden




The price of anarchy, the most popular measure of the
inefficiency of selfish behavior, assumes that players successfully reach
some Nash equilibrium. We prove that for most of the classes of games in
which the price of anarchy has been studied, results are “intrinsically
robust” in the following sense: an upper bound on the worst-case price of
anarchy for pure Nash equilibria *necessarily* implies the exact same
worst-case upper 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). Byproducts of our work
include several new results for the inefficiency of equilibria in
congestion games.


Tim Roughgarden

Tim Roughgarden received his BS and MS degrees from Stanford University in 1997 and 1998. He completed his PhD in May 2002 at Cornell University, where he continues to work as a postdoctoral researcher.

Dr. Roughgarden’s research interests lie on the interface of combinatorial optimization and game theory. In his PhD work, he developed techniques for quantifying the degradation in network performance due to noncooperative behavior by network users, together with methods for building and managing networks so that selfish behavior leads to a socially desirable outcome.

Dr. Roughgarden received an NSF Graduate Fellowship in 1998 and the Danny Lewin Best Student Paper Award at the STOC 2002 conference. He has recently given invited talks at MIT, Princeton, the Institute for Advanced Studies, the University of Pennsylvania, and Lucent Bell Labs.