The Anarchy-Stability Tradeoff in Congestion Games

This work focuses on the design of incentive mechanisms in congestion games, a commonly studied model for competitive resource sharing. While the majority of the existing literature on this topic focuses on unilaterally optimizing the worst case performance (i.e., price of anarchy), in this manuscript we investigate whether optimizing for the worst case has consequences on the best case performance (i.e., price of stability). Perhaps surprisingly, our results show that there is a fundamental tradeoff between these two measures of performance. Our main result provides a characterization of this tradeoff in terms of upper and lower bounds on the Pareto frontier between the price of anarchy and the price of stability. Interestingly, we demonstrate that the mechanism that optimizes the price of anarchy inherits a matching price of stability, thereby implying that the best equilibrium is not necessarily any better than the worst equilibrium for such a design choice. Our results also establish that, in several well-studied cases, the unincentivized setting does not even lie on the Pareto frontier, and that any incentive with price of stability equal to 1 incurs a much higher price of anarchy.