The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Intrinsic robustness of the price of anarchy
Abstract
The price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. This measure implicitly assumes that players successfully reach some Nash equilibrium. This drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. We prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. First, we identify a "canonical sufficient condition" for an upper bound of the POA for pure Nash equilibria, which we call a smoothness argument. Second, we show that every bound 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 regret-minimizing players (or "price of total anarchy"). Smoothness arguments also have automatic implications for the inefficiency of approximate and Bayesian-Nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. We also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the POA, even for the smallest set of interest (pure Nash equilibria). Byproducts of our proof of this result include the first tight bounds on the POA in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the POA.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Subjectivity and Correlation in Randomized Strategies
Aumann, R. J. (1974) · Journal of Mathematical Economics · doi:10.1016/0304-4068(74)90037-8 · Cited by 1,630
Cited by
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Distributed Seeking of Nash Equilibria With Applications to Mobile Sensor Networks
Stankovic, M. S., Johansson, K. H., & Stipanovic, D. M. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2174678 · Cited by 358
Roughgarden, T. (2010) · Communications of the ACM · doi:10.1145/1785414.1785439 · Cited by 288
Self-citationCycles in adversarial regularized learning
Mertikopoulos, P., Papadimitriou, C., & Piliouras, G. (2018) · Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611975031.172 · Cited by 122
Metadata
- Authors
- Roughgarden, T.
- Venue
- Proceedings of the forty-first annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2009-05-31
- Pages
- 513-522
- OpenAlex
- W2133243407
- Cited by
- 319
- References
- 1
- FWCI
- 56.38
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Intrinsic robustness of the price of anarchy. https://app.cochat.ai/papers/10.1145/1536414.1536485
- The paper
- Roughgarden, T. (2009). Intrinsic robustness of the price of anarchy. Proceedings of the forty-first annual ACM symposium on Theory of computing. https://doi.org/10.1145/1536414.1536485
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.