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. We introduce "smoothness arguments" and show that they give bounds on the price of anarchy that are "intrinsically robust" in a precise sense. We describe recent applications to the analysis of Bayes-Nash equilibria of mechanisms without dominant strategies, and a “local” refinement of the proof framework that yields tight bounds on the price of anarchy in atomic splittable congestion games.
Copyright. All Rights Reserved.