Intrinsic Robustness of the Price of Anarchy
Tim Roughgarden, Stanford University
Abstract. The price of anarchy is a measure of the inefficiency of decentralized behavior that has been successfully analyzed in many systems. It is defined as the worst-case ratio between the welfare of an equilibrium and that of an optimal solution. Seemingly, a bound on the price of anarchy is meaningful in a game-theoretic context only if players successfully reach an equilibrium. Our main result is 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: a bound on the worst-case price of anarchy for equilibria *necessarily* implies the exact same worst-case bound for a much larger set of outcomes, such as the possible sequences generated by no-regret learners.