Title: When is selfish routing bad? The price of anarchy in light and heavy traffic,
Abstract: 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
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),
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.