Theory Seminar, February 9, 2:00pm
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.