Intrinsic Robustness of the Price of Anarchy

Time
1:30 – 2:20pm, Tuesday, October 6, 2009
Place
CSE 503
Speaker
Tim Roughgarden, Stanford

Abstract

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.