Intrinsic Robustness of the Price of Anarchy

Speaker  Tim Roughgarden

Host  Adam

Affiliation  Stanford

Duration  00:57:39

Date recorded  20 May 2009

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.

©2009 Microsoft Corporation. All rights reserved.
> Intrinsic Robustness of the Price of Anarchy