Warren Weaver Hall, Room 312

Smoothness arguments and the price of anarchy

Tim Roughgarden, Stanford University

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 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. We also describe recent applications to the analysis of Bayes-

Nash equilibria in (non-truthful) mechanisms, and a “local” refinement of the framework that yields tight bounds

on the price of anarchy in atomic splittable congestion games.