Efficiency Loss in a Network Resource Allocation Game
The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. We also consider extensions to a network context, where users submit individual payments for each link in the network they may wish to use. In this network model, we again show that the selfish behavior of the users leads to an aggregate utility that is no worse than 3/4 of the maximum possible aggregate utility. We also show that the same analysis extends to a wide class of resource allocation systems where end users simultaneously require multiple scarce resources. These results form part of a growing literature on the “price of anarchy,” i.e., the extent to which selfish behavior affects system efficiency.
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
Rate control for communication networks: shadow prices, proportional fairness and stability
Kelly, F. P., Maulloo, A. K., & Tan, D. K. H. (1998) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2600523 · Cited by 5,021
Monderer, D., & Shapley, L. S. (1996) · Games and Economic Behavior · doi:10.1006/game.1996.0044 · Cited by 3,543
Charging and rate control for elastic traffic
Kelly, F. (1997) · European Transactions on Telecommunications · doi:10.1002/ett.4460080106 · Cited by 2,936
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
Self-citationExistence and Uniqueness of Equilibrium Points for Concave N-Person Games
Rosen, J. B. (1965) · Econometrica · doi:10.2307/1911749 · Cited by 2,686
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
Koutsoupias, E., & Papadimitriou, C. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49116-3_38 · Cited by 1,806
Roughgarden, T., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/506147.506153 · Cited by 1,608
Fundamental design issues for the future Internet
Shenker, S. (1995) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.414637 · Cited by 1,097
Algorithms, games, and the internet
Papadimitriou, C. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380883 · Cited by 1,085
Resource pricing and the evolution of congestion control
Gibbens, R. J., & Kelly, F. P. (1999) · Automatica · doi:10.1016/s0005-1098(99)00135-1 · Cited by 544
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
Vetta, A. R. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181966 · Cited by 411
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
Paris metro pricing for the internet
Odlyzko, A. M. (1999) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/336992.337030 · Cited by 371
A proportional share resource allocation algorithm for real-time, time-shared systems
Stoica, I. G., Abdel-Wahab, H., Kevin Jeffay, B., Baruah, S., Gehrke, J. E., & Plaxton, C. G. (2002) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.1996.563725 · Cited by 343
Pumpkin Pies and Public Goods: The Raffle Fundraising Strategy
Duncan, B. (2002) · Public Choice · doi:10.1023/a:1015133126932 · Cited by 28
Farrell, M. P. (1996) · Journal of Government Information · doi:10.1016/s1352-0237(97)89749-3 · Cited by 14
Cited by
Multiagent systems: algorithmic, game-theoretic, and logical foundations
(2009) · Choice Reviews Online · doi:10.5860/choice.46-5662 · Cited by 1,756
Bertsimas, D., Farias, V. F., & Trichakis, N. (2011) · Operations Research · doi:10.1287/opre.1100.0865 · Cited by 656
Selfish Routing and the Price of Anarchy
(2016) · Twenty Lectures on Algorithmic Game Theory · doi:10.1017/cbo9781316779309.012 · Cited by 647
Auction-Based Spectrum Sharing
Huang, J., Berry, R. A., & Honig, M. L. (2006) · Mobile Networks and Applications · doi:10.1007/s11036-006-5192-y · Cited by 615
Yi, P., Hong, Y., & Liu, F. (2016) · Automatica · doi:10.1016/j.automatica.2016.08.007 · Cited by 478
Metadata
- Authors
- Johari, R., & Tsitsiklis, J. N.
- Venue
- Mathematics of Operations Research
- Published
- 2004-08
- Volume
- 29
- Issue
- 3
- Pages
- 407-435
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2167217653
- Cited by
- 537
- References
- 18
- FWCI
- 54.49
- Type
- journal article
- 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.