How Bad Is Selfish Routing?¶
Roughgarden, T., & Tardos, É. (2002). How Bad Is Selfish Routing?. Journal of the ACM, 49(2), 236-259.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Braess's Paradox
- Communication networks — added capacity in a selfishly-routed packet network can degrade end-to-end performance, studied formally under the "price of anarchy."
This sourceFormalizes the price of anarchy of selfish routing, the framework under which Braess effects in communication and traffic networks are studied.
Supported in partVerified against the publisher's abstract
The abstract quantifies the loss from unregulated selfish routing (at most 4/3 of optimal for linear latencies), i.e. the price-of-anarchy framework, but never states that added capacity degrades performance.
“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.”
- Communication networks — added capacity in a selfishly-routed packet network can degrade end-to-end performance, studied formally under the "price of anarchy."
- Price of Anarchy
- The ratio is finite for some game classes (linear-cost routing has price of anarchy at most 4/3) and unbounded for others.
This sourceProves the price of anarchy of selfish routing is at most 4/3 for linear latency functions, with the bound a property of the cost-function class.
SupportedVerified against the publisher's abstract
Roughgarden and Tardos prove that when each edge's latency is a linear function of its congestion, the total latency of selfishly chosen routes “is at most 4/3 times the minimum possible total latency”, and that when latency functions are merely continuous and nondecreasing the selfish total “may be arbitrarily larger than the minimum possible total latency”. Those two routing classes are the bounded and unbounded cases the sentence contrasts. The work states these bounds for selfish routing without using the term price of anarchy.
“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 nondecreasing in the edge congestion. …”
- The ratio is finite for some game classes (linear-cost routing has price of anarchy at most 4/3) and unbounded for others.
Mechanisms¶
- User Equilibrium vs System Optimum Analysis
- Its strength is that it produces a portable, comparable measure of how much room misalignment has to do harm — a network's price of anarchy — which lets an organization triage where equilibrium-aware governance is worth the effort and where ordinary scaling is safe.
This sourceQuantifies the performance loss caused by selfish routing by comparing equilibrium total latency with the coordinated system optimum.
- Its strength is that it produces a portable, comparable measure of how much room misalignment has to do harm — a network's price of anarchy — which lets an organization triage where equilibrium-aware governance is worth the effort and where ordinary scaling is safe.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 3 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:c626fd56e5fd · see in the full table