ComputingComputer ScienceComputer NetworksDistributed SystemsGame TheoryAlgorithmic Game TheoryNetwork GamesNetwork OptimizationQueueing TheoryRoutingRouting AlgorithmsLinear Cost FunctionsMulti-commodity FlowNetwork PricingPriority Queueing NetworksRouting Games
We consider a priority-based selfish routing model, where agents may have different priorities on a link. An agent with a higher priority on a link can traverse it with a smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of different problems. The structural properties that lead to inefficiencies in routing choices appear different in this priority-based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority-based model; that is, selfish behaviour leads to optimal routings. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selfish routing does lead to inefficiencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Specifically, in the nonatomic case the worst-case price of anarchy is exactly (d + 1) d+1 for polynomial latency functions of degree d (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly 3+2 √ 2 in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of O(2 d d d) is also shown for polynomial cost functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games. ACM Classification: F.2.0, F.2.2 AMS Classification: 68Q25, 68M10, 90B18 Key words and phrases: selfish routing, price of anarchy
12
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Some Theoretical Aspects of Road Traffic Research
J G Wardrop · 1952 · 2.3K citations
Studies in the Economics of Transportation.
D. J. R., M. G. Beckman, Charlie McGuire et al. · OR · 1956 · 1.6K citations
Tim Roughgarden, Éva Tardos · Journal of the ACM · 2002 · 1.6K citations