The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
How bad is selfish routing?
Abstract
We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times-the total latency-is minimized. In many settings, including the Internet and other large-scale communication networks, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance. We quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and non-decreasing in the edge congestion.
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
Bertsekas, D. P., & Gallager, R. G. (1987) · Cited by 5,561
Existence and Uniqueness of Equilibrium Points for Concave N-Person Games
Rosen, J. B. (1965) · Econometrica · doi:10.2307/1911749 · Cited by 2,686
Urban transportation networks: Equilibrium analysis with mathematical programming methods
(1986) · Transportation Research Part A: General · doi:10.1016/0191-2607(86)90023-3 · Cited by 2,349
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
Koutsoupias, E., & Papadimitriou, C. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49116-3_38 · Cited by 1,806
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
Studies 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
Recommendations on Queue Management and Congestion Avoidance in the Internet
Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., et al. (1998) · doi:10.17487/rfc2309 · Cited by 1,318
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
Traffic Equilibrium and Variational Inequalities
Dafermos, S. (1980) · Transportation Science · doi:10.1287/trsc.14.1.42 · Cited by 926
Über ein Paradoxon aus der Verkehrsplanung
Braess, D. (1968) · Unternehmensforschung Operations Research - Recherche Opérationnelle · doi:10.1007/bf01918335 · Cited by 911
The existence, uniqueness and stability of traffic equilibria
Smith, M. J. (1979) · Transportation Research Part B: Methodological · doi:10.1016/0191-2615(79)90022-5 · Cited by 857
Bertsekas, D. P., & Gallager, R. G. (1992) · Prentice-Hall, Inc eBooks · Cited by 852
Speed is as powerful as clairvoyance
Kalyanasundaram, B., & Pruhs, K. (2000) · Journal of the ACM · doi:10.1145/347476.347479 · Cited by 561
The Mathematics of Nonlinear Programming
Peressini, A. L., Uhl, J. J., & Sullivan, F. E. (1988) · Undergraduate Texts in Mathematics · doi:10.1007/978-1-4612-1025-2 · Cited by 374
On the relationship between Nash—Cournot and Wardrop equilibria
Haurie, A. B., & Marcotte, P. (1985) · Networks · doi:10.1002/net.3230150303 · Cited by 329
Equilibria on a Congested Transportation Network
Aashtiani, H. Z., & Magnanti, T. L. (1981) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0602024 · Cited by 263
Braess's paradox of traffic flow
Murchland, J. D. (1970) · Transportation Research · doi:10.1016/0041-1647(70)90196-6 · Cited by 210
Mavronicolas, M., & Spirakis, P. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380846 · Cited by 183
Stackelberg scheduling strategies
Roughgarden, T. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380783 · Cited by 139
Self-citationFrank, M. (1981) · Mathematical Programming · doi:10.1007/bf01589354 · Cited by 139
Designing networks for selfish users is hard
Roughgarden, T. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959923 · Cited by 123
Self-citationNonlinear cost network models in transportation analysis
Florian, M. (1986) · Mathematical programming studies · doi:10.1007/bfb0121092 · Cited by 100
Mowbray, A. (1969) · Medical Entomology and Zoology · Cited by 48
Stable Flows in Transportation Networks
Nesterov, Y. E. (1999) · Cited by 6
Research works printed but not linked: 17
- 10.1680/ipeds.1952.11362 · doi:10.1680/ipeds.1952.11362
- 10.1287/trsc.17.3.301 · doi:10.1287/trsc.17.3.301
- 10.1287/trsc.22.4.231 · doi:10.1287/trsc.22.4.231
- 10.1287/trsc.12.3.208 · doi:10.1287/trsc.12.3.208
- 10.2307/1884592 · doi:10.2307/1884592
- kn�del, 1969, Graphentheoretische Methoden und ihre Anwendungen, 10.1007/978-3-642-95121-3 · doi:10.1007/978-3-642-95121-3
- 10.1109/9.557575 · doi:10.1109/9.557575
- korlis, 1999, Avoiding the Braess paradox in noncooperative networks, Journal of Applied Probability, 42, 309
- 10.1109/90.650145 · doi:10.1109/90.650145
- roughgarden, 0, How bad is selfish routing?
- 10.2307/3214558 · doi:10.2307/3214558
- 10.1287/moor.11.1.1 · doi:10.1287/moor.11.1.1
- 10.6028/jres.073B.010 · doi:10.6028/jres.073b.010
- 10.1016/0191-2615(79)90023-7 · doi:10.1016/0191-2615(79)90023-7
- nesterov, 2000, Stable dynamics in transportation systems, CORE Discussion paper
- owen, 1995, Game Theory
- 10.1109/90.251910 · doi:10.1109/90.251910
Cited by
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
Nash equilibria of packet forwarding strategies in wireless ad hoc networks
Felegyhazi, M., Hubaux, J.-P., & Buttyan, L. (2006) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2006.68 · Cited by 321
Classical Paradigm of Transportation Modeling
Teknomo, K. (2026) · Lecture Notes in Intelligent Transportation and Infrastructure · doi:10.1007/978-981-95-4727-2_2
Metadata
- Authors
- Roughgarden, T., & Tardos, E.
- Venue
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-08
- Pages
- 93-102
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2149497768
- Cited by
- 277
- References
- 25
- FWCI
- 28.77
- 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.