Journal
JOURNAL OF THE ACM
Volume 62, Issue 5, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2806883
Keywords
Theory; Economics Equilibria; price of anarchy; games; approximation
Categories
Funding
- NSF [CCF-0448664, CCF-1016885]
- AFOSR MURI grant
- ONR Young Investigator Award
- ONR PECASE Award
- Alfred P. Sloan Fellowship
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1524062, 1215965] Funding Source: National Science Foundation
Ask authors/readers for more resources
The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains. However, such bounds are meaningful only if a game's participants successfully reach a Nash equilibrium. This drawback motivates inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash equilibria and correlated equilibria, and to sequences of outcomes generated by natural experimentation strategies, such as successive best responses and simultaneous regret-minimization. We establish a general and fundamental connection between the price of anarchy and its seemingly more general relatives. First, we identify a canonical sufficient condition for an upper bound on the price of anarchy of pure Nash equilibria, which we call a smoothness argument. Second, we prove an extension theorem: every bound on the price of anarchy that is derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of every outcome sequence generated by no-regret learners. Smoothness arguments also have automatic implications for the inefficiency of approximate equilibria, for bicriteria bounds, and, under additional assumptions, for polynomial-length best-response sequences. Third, we prove that in congestion games, smoothness arguments are complete in a proof-theoretic sense: despite their automatic generality, they are guaranteed to produce optimal worst-case upper bounds on the price of anarchy.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available