The DOI matches its Crossref record; 44 of the 44 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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Equilibrium points in n -person games
Nash, J. F. (1950) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.36.1.48 · Cited by 7,560
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Monderer, D., & Shapley, L. S. (1996) · Games and Economic Behavior · doi:10.1006/game.1996.0044 · Cited by 3,543
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
A class of games possessing pure-strategy Nash equilibria
Rosenthal, R. W. (1973) · International Journal of Game Theory · doi:10.1007/bf01737559 · Cited by 2,008
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
Correlated Equilibrium as an Expression of Bayesian Rationality
Aumann, R. J. (1987) · Econometrica · doi:10.2307/1911154 · Cited by 1,613
Studies in the Economics of Transportation.
R., D. J., Beckman, M., McGuire, C. B., Winsten, C. B., & Koopmans, T. (1956) · OR · doi:10.2307/3007560 · Cited by 1,613
Roughgarden, T., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/506147.506153 · Cited by 1,608
Self-citationStudies in the Economics of Transportation.
Smeed, R. J., Beckmann, M., McGuire, C. B., Winsten, C. B., & Koopmans, T. C. (1957) · The Economic Journal · doi:10.2307/2227641 · Cited by 1,488
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Hart, S., & Mas-Colell, A. (2000) · Econometrica · doi:10.1111/1468-0262.00153 · Cited by 1,088
The Complexity of Computing a Nash Equilibrium
Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2009) · SIAM Journal on Computing · doi:10.1137/070699652 · Cited by 921
Koutsoupias, E., & Papadimitriou, C. H. (2009) · Computer Science Review · doi:10.1016/j.cosrev.2009.04.003 · Cited by 687
The complexity of pure Nash equilibria
Fabrikant, A., Papadimitriou, C., & Talwar, K. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007445 · Cited by 650
Strategic Learning and its Limits
Young, H. P. (2004) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199269181.001.0001 · Cited by 605
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C. H., & Shenker, S. J. (2003) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/872035.872088 · Cited by 523
Settling the Complexity of Two-Player Nash Equilibrium
Chen, X., & Deng, X. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.69 · Cited by 486
Nash and correlated equilibria: Some complexity considerations
Gilboa, I., & Zemel, E. (1989) · Games and Economic Behavior · doi:10.1016/0899-8256(89)90006-7 · Cited by 406
Selfish Routing in Capacitated Networks
Correa, J., Schulz, A. S., & Stier‐Moses, N. E. (2004) · Mathematics of Operations Research · doi:10.1287/moor.1040.0098 · Cited by 398
The price of anarchy is independent of the network topology
Roughgarden, T. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00044-8 · Cited by 398
Self-citationCalibrated Learning and Correlated Equilibrium
Foster, D. P., & Vohra, R. V. (1997) · Games and Economic Behavior · doi:10.1006/game.1997.0595 · Cited by 365
Vetta, A. R. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181966 · Cited by 320
Computing correlated equilibria in multi-player games
Papadimitriou, C. H., & Roughgarden, T. (2008) · Journal of the ACM · doi:10.1145/1379759.1379762 · Cited by 311
Self-citationBounding the inefficiency of equilibria in nonatomic congestion games
Roughgarden, T., & Tardos, É. (2004) · Games and Economic Behavior · doi:10.1016/j.geb.2003.06.004 · Cited by 298
Self-citationOn the Complexity of Nash Equilibria and Other Fixed Points
Etessami, K., & Yannakakis, M. (2010) · SIAM Journal on Computing · doi:10.1137/080720826 · Cited by 249
Moulin, H., & Vial, J. P. (1978) · International Journal of Game Theory · doi:10.1007/bf01769190 · Cited by 227
Strong Equilibrium in Congestion Games
Holzman, R., & Law-yone, N. (1997) · Games and Economic Behavior · doi:10.1006/game.1997.0592 · Cited by 198
Learning, Regret Minimization, and Equilibria
Blum, A., & Mansour, Y. (2007) · Algorithmic Game Theory · doi:10.1017/cbo9780511800481.006 · Cited by 180
Bayesian Combinatorial Auctions
Christodoulou, G., Kovács, A., & Schapira, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_67 · Cited by 167
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,,
Christodoulou, G., & Koutsoupias, E. (2005) · Lecture notes in computer science · doi:10.1007/11561071_8 · Cited by 163
P, A. W. (1922) · The Library · doi:10.1093/library/s4-iii.1.66 · Cited by 163
Multiplicative updates outperform generic no-regret learning in congestion games
Kleinberg, R., Piliouras, G., & Eva Tardos, D. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536487 · Cited by 133
Moscibroda, T., Schmid, S., & Wattenhofer, R. P. (2006) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1146381.1146391 · Cited by 120
Market sharing games applied to content distribution in ad hoc networks
Goemans, M. X., Li, L., Mirrokni, V., & Thottan, M. (2006) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2006.872884 · Cited by 116
Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction
Leme, R. P., & Eva Tardos, D. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.75 · Cited by 107
Convergence Issues in Competitive Games
Mirrokni, V., & Vetta, A. R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27821-4_17 · Cited by 104
Exact Price of Anarchy for Polynomial Congestion Games
Aland, S., Dumrauf, D., Gairing, M., Monien, B., & Schoppmann, F. (2006) · Lecture notes in computer science · doi:10.1007/11672142_17 · Cited by 103
The “Price of Anarchy” Under Nonlinear and Asymmetric Costs
Perakis, G. (2007) · Mathematics of Operations Research · doi:10.1287/moor.1070.0258 · Cited by 94
On the efficiency of equilibria in generalized second price auctions
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2011) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1993574.1993588 · Cited by 86
Strong equilibrium in cost sharing connection games
Epstein, A., Feldman, M., & Mansour, Y. (2008) · Games and Economic Behavior · doi:10.1016/j.geb.2008.07.002 · Cited by 78
Generalized Efficiency Bounds in Distributed Resource Allocation
Marden, J. R., & Roughgarden, T. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2301613 · Cited by 65
Self-citationItai Ashlagi, A., Monderer, D., & Tennenholtz, M. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2588 · Cited by 42
The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds
Nadav, U., & Roughgarden, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17572-5_26 · Cited by 31
Self-citationBradonjić, M., Ercal, G., Meyerson, A., & Roytman, A. (2009) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1566374.1566419 · Cited by 10
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
- 44
- 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
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.