Journal Article

When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

Mertikopoulos, Panayotis, Scarsini, Marco, Cominetti, Roberto, Colini-Baldeschi, Riccardo

2020

Overview

In highly congested networks, is selfishness the problem? Empirical studies in road networks reveal a fairly surprising property of congestion: when there is too much (or too little) traffic in the network, there is no difference between the best and the fairest traffic allocations (i.e., between the traffic assignment that optimizes the commuters' average travel time versus the one that no commuter would have any incentive to deviate from). In “When is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic”, the authors give a theoretical justification to this empirical observation: for a large class of traffic inflow patterns and cost functions (including all polynomials), the gap between social optimality and equilibrium—the network’s price of anarchy—converges to 1 in both heavy and light traffic, irrespective of the network topology and the number of origin/destination pairs in the network. This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network’s cost functions are polynomials.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Contextual Areas / Convergence / Cost function / games/group decisions: non-atomic / heavy traffic / Inflow / Jones, Jacqueline / light traffic / Management research / Management science / Mathematical research / Mathematics / Network topologies / networks/graphs: multicommodity / nonatomic congestion games / Operations research / Optimization and Control / Polynomials / price of anarchy / Prices / regular variation / Traffic accidents & safety / Traffic congestion / Transportation