Riccardo Colini-Baldeschi

Roberto Cominetti

PANAYOTIS MERTIKOPOULOS § Marco Scarsini

WHEN IS SELFISH ROUTING BAD? THE PRICE OF ANARCHY IN LIGHT AND HEAVY TRAFFIC

This paper examines the behavior of the price of anarchy as a function of the tra c in ow 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 tra c, thus raising the question: can these observations be justi ed theoretically? We rst 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 tra c in ow, 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 tra c, 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.

"Tra c congestion is caused by vehicles, not by people in themselves."

I

Almost every commuter in a major metropolitan area has experienced the frustration of being stuck in tra c. At best, this might mean being late for dinner; at worst, it means more accidents and altercations, not to mention the vastly increased damage to the environment caused by huge numbers of idling engines.

To name but an infamous example, China's G110 tra c jam in August 2010 brought to a standstill thousands of vehicles for 100 kilometers between Hebei and Inner Mongolia. . E-mail addresses: rickuz@fb.com, roberto.cominetti@uai.cl, panayotis.mertikopoulos@imag.fr, marco.scarsini@luiss.it.

2010 Mathematics Subject Classi cation. Primary 91A13; secondary 91A43, 91A80. Key words and phrases. Nonatomic congestion games; price of anarchy; light tra c; heavy tra c; regular variation.

We thank an anonymous reviewer of an earlier conference version of this paper for suggesting one of the examples with variable in ows in Section 6.

This research bene ted from the support of the FMJH Program PGMO under grant HEAVY.NET and from the support of EDF, Thales, and Orange. R. Colini-Baldeschi and M. Scarsini are members of GNAMPA-INdAM. R. Cominetti and P. Mertikopoulos gratefully acknowledge the support and hospitality of LUISS during a visit in which this research was initiated. R. Cominetti's research is also supported by FONDECYT 1130564 and Núcleo Milenio ICM/FIC RC130003 "Información y Coordinación en Redes. " P. Mertikopoulos was partially supported by the ECOS/CONICYT Grant C15E03 and the Huawei HIRP Flagship project ULTRON. P. Mertikopoulos and M. Scarsini also gratefully acknowledge the support and hospitality of FONDECYT 1130564 and Núcleo Milenio "Información y Coordinación en Redes. "

The snarl-up lasted twelve days and resulted in drivers being unable to move for more than 1 kilometer per day, reportedly spending up to ve days trapped in the jam. Not caused by weather or a natural disaster, this massive 10-day tie-up was instead laid at the feet of a bevy of trucks swarming on the shortest route to Beijing, thus clogging the highway to a halt (while ironically carrying supplies for construction work to ease congestion). This, therefore, raises the question: how much better would things have been if all tra c had been routed by a social planner who could calculate (and enforce) the optimum tra c assignment?

In game-theoretic terms, this question boils down to the ine ciency of Nash equilibria that are not Pareto optimal. The most widely used quantitative measure of this ine ciency is the so-called price of anarchy (PoA): introduced by [START_REF] Koutsoupias | Worst-case equilibria[END_REF] and so dubbed by [START_REF] Papadimitriou | Algorithms, games, and the Internet[END_REF], the price of anarchy is simply the ratio of the social cost of the least e cient Nash equilibrium divided by the minimum achievable social cost. By virtue of this straightforward de nition, deriving worst-case bounds for the price of anarchy has given rise to a vigorous literature at the interface of operations research, economics and computer science, often leading to surprising and counter-intuitive results.

In the context of network congestion, [START_REF] Pigou | The Economics of Welfare[END_REF] was probably the rst to note the ine ciency of sel sh routing, and his elementary two-road example with a PoA of 4/3 is one of the two prototypical examples thereof. The other example is due to [START_REF] Braess | über ein Paradoxon aus der Verkehrsplanung[END_REF], and consists of a four-road network where the addition of a zero-cost segment makes things just as bad as in the Pigou case. These two examples were the starting point for [START_REF] Roughgarden | How bad is sel sh routing?[END_REF] who showed that the price of anarchy in (nonatomic) routing games with a ne costs may not exceed 4/3. On the other hand, if the network's cost functions are polynomials of degree at most d, the price of anarchy may become as high as Θ(d/log d), implying that sel sh routing can become arbitrarily bad in networks with polynomial costs [START_REF] Roughgarden | The price of anarchy is independent of the network topology[END_REF].

By this token, and given the typically nonlinear relation between tra c loads and travel times, the intervention of a central planner seems necessary in order to regain some degree of e ciency. At the same time however, these worst-case instances are typically realized in networks with delicately tuned tra c loads and costs: if a network operates beyond this regime, it is not clear whether the price of anarchy remains high. In view of this, our aim in this paper is to examine the asymptotic behavior of the price of anarchy at both ends of the congestion spectrum: light and heavy tra c.

Using both analytical and numerical methods, a very recent study by [START_REF] O'hare | Mechanisms that govern how the price of anarchy varies with travel demand[END_REF] suggests that the price of anarchy is usually close to 1 for both high and low tra c, and it uctuates in the intermediate regime (typically exhibiting multiple local maxima). In a similar setting, [START_REF] Monnot | How bad is sel sh routing in practice?[END_REF] used a huge dataset on commuting students in Singapore to estimate the so-called "stress of catastrophe": this majorant of the ordinary price of anarchy was estimated to a value between 1.11 and 1.22, suggesting that the actual value of the price of anarchy in Singapore is lower (and de nitely below the 4/3 worst-case bound of the Pigou/Braess examples).

All this leads to the following natural questions: a) Under what conditions does the price of anarchy converge to 1 in light/heavy trafc? b) Do these conditions depend on the network topology, its cost functions, or both? c) Can general results be obtained for networks with multiple origin-destination (O/D) pairs? d) When these conditions are satis ed, how fast is this convergence?

O D c 1 (x ) = [1 + 1/2 sin(log x )] x 2 c 2 (x ) = x 2 c 3 (x ) = [1 + 1/2 cos(log x )] x 2
1.1. Our contributions. Our rst result is a cautionary tale: we show that the price of anarchy may oscillate between two bounds strictly greater than 1 for all values of the tra c in ow, even in simple parallel-link networks with a single O/D pair (cf. Fig. 1).

The cost functions in our example are convex and di erentiable, so neither convexity nor smoothness seem to play a major role in the e ciency of sel sh routing. Moreover, our construction only involves a three-link network, so such phenomena may arise in any network containing such a three-link component.

Heuristically, the reason for this irregular -and, perhaps, counter-intuitive -behavior is that the growth rate of the network's cost functions exhibits higher-order oscillations which persist at any scale, in both light and heavy tra c. To dispense with such pathologies, we focus on networks whose cost functions c e (x) are asymptotically comparable to a benchmark function c(x) which is itself assumed to be regularly varying (cf. De nition 4.1). In so doing, we obtain a classi cation of the network's edges, paths, and O/D pairs as fast, slow or tight relative to the chosen benchmark. Then, thanks to this classication, we obtain the following general result: If the routing cost of the "most costly" O/D pair in the network behaves like the benchmark, the network's price of anarchy converges to 1 in both light and heavy tra c.

Polynomial cost functions satisfy all of the above requirements, leading to the comprehensive asymptotic principle:

In networks with polynomial costs, the price of anarchy becomes 1 under both light and heavy tra c.

In other words, a benevolent social planner with full control of tra c assignment would not do any better than sel sh agents in conditions of high or low congestion. In particular, only if the tra c falls in an intermediate regime can there be a substantial gap between optimum and equilibrium states.

To assess how wide this intermediate regime might be in practice, we also examine the speed at which the price of anarchy converges to 1 as a function of the tra c in ow. Specializing to networks with polynomial costs, we nd that in both regimes the convergence follows a power law with respect to the total tra c in ow, and we derive explicit sharp estimates for the corresponding rates.

1.2. Related work. Establishing worst-case bounds for the price of anarchy under different conditions has been a staple of the literature on congestion games ever since the seminal result of [START_REF] Roughgarden | How bad is sel sh routing?[END_REF]. In words, this result states that in networks with a ne costs the price of anarchy is no higher than 4/3, independently of the network topology and/or the number of O/D pairs in the network. Furthermore, this bound is sharp in that, for every M > 0, there exists a network with tra c in ow M and a ne costs such that the price of anarchy is exactly equal to 4/3. Importantly, our analysis shows that the order of the quanti ers in the above statement cannot be exchanged: in any network with a ne costs, the price of anarchy gets arbitrarily close to 1 if the tra c in ow is su ciently large or small.

Worst-case bounds for the price of anarchy have been obtained for larger classes of cost functions. For polynomial costs with degree at most d, [START_REF] Roughgarden | The price of anarchy is independent of the network topology[END_REF] showed that the worst possible instance grows as Θ(d/log d) while [START_REF] Dumrauf | Price of anarchy for polynomial Wardrop games[END_REF] provided sharper bounds for monomials of maximum degree d and minimum degree q. Extending the above results, [START_REF] Roughgarden | Bounding the ine ciency of equilibria in nonatomic congestion games[END_REF] provided a unifying result for costs that are di erentiable with xc(x) convex, while [START_REF] Correa | Sel sh routing in capacitated networks[END_REF][START_REF] Correa | A geometric approach to the price of anarchy in nonatomic congestion games[END_REF] considered less regular classes of cost functions. [START_REF] Correa | Fast, fair, and e cient ows in networks[END_REF] also studied the price of anarchy when the goal is to minimize the maximum -rather than the average -latency in the network. For a survey, the reader is referred to [START_REF] Roughgarden | Routing games[END_REF].

In a more practical setting, [START_REF] Youn | Price of anarchy in transportation networks: E ciency and optimality control[END_REF] studied the di erence between optimal and actual system performance in real transportation networks, focusing in particular on Boston's road network. They observed that the price of anarchy depends crucially on the total tra c in ow: it starts at 1, it then grows with some oscillations, and ultimately returns to 1 as the ow increases. González [START_REF] Vayá | On the price of being sel sh in large populations of plug-in electric vehicles[END_REF] studied optimal scheduling for the electricity demand of a eet of plug-in electric vehicles: without using the term, they showed that the price of anarchy goes to 1 as the number of vehicles grows. [START_REF] Cole | Large market games with near optimal e ciency[END_REF] showed that in large Walrasian auctions and in large Fisher markets the price of anarchy goes to one as the market size increases. Finally, [START_REF] Feldman | The price of anarchy in large games[END_REF] took a di erent asymptotic approach and considered atomic games where the number of players grows to in nity. Applying the notion of (λ, µ)-smoothness to the resulting sequence of atomic games, they showed that the price of anarchy converges to the corresponding nonatomic limit.

From an analytic standpoint, the closest antecedent to our paper is the recent work of [START_REF] Colini-Baldeschi | On the price of anarchy of highly congested nonatomic network games[END_REF] who studied the heavy tra c limit of the price of anarchy in parallel networks with a single O/D pair. Their analysis identi ed that regular variation plays an important role in this setting; however, it o ered no insights into non-parallel networks with multiple O/D pairs or the light tra c regime. Our paper provides an indepth answer to these questions: we show that (a) regular variation yields asymptotic e ciency under both light and heavy tra c conditions; (b) the topology of the network doesn't matter; and (c) the existence of several O/D pairs doesn't matter as long as they admit a common benchmark (which is always the case if the network's cost functions are polynomial).

Building on a previous unpublished version of the present paper, [START_REF] Wu | Sel shness need not be bad[END_REF] introduced a class of congestion games, called scalable, whose price of anarchy converges to 1 as the total demand diverges. They also computed the rate of convergence of the price of anarchy for the special case of BPR cost functions of the same degree. [START_REF] Stidham | The price of anarchy for a network of queues in heavy tra c[END_REF] also studied the behavior of the price of anarchy for queueing networks in heavy tra c under various assumptions on the structure of the network and on the stochastic properties of the queues. His results can be used for the analysis of network routing models with capacity constraints.

Our work should also be compared to that of [START_REF] Monnot | How bad is sel sh routing in practice?[END_REF] who performed an empirical study of the price of anarchy based on data from thousands of commuting students in Singapore. Focusing on the network's "stress of catastrophe" (an empirical majorant of the network's price of anarchy), they showed that routing choices are nearoptimal and the incurred price of anarchy is much lower than what traditional worst-case bounds suggest. Interestingly, the study of [START_REF] Monnot | How bad is sel sh routing in practice?[END_REF] also suggests that the Singapore road network is often lightly congested: as such, their results can be seen as a practical validation of the light tra c results presented here (and, conversely, our results provide a theoretical justi cation for their empirical observations).

1.3. Outline of the paper. The paper is organized as follows. In Section 2, we introduce the basic model and concepts that will be used in the rest of the paper. Section 3 provides two motivating examples for the analysis to follow. In Section 4, we treat networks with a single O/D pair, whereas Section 5 examines networks with multiple O/D pairs. The more complicated case of variable relative in ows is treated in Section 6. Finally, in Section 7, we study the rate of convergence of the price of anarchy in light and heavy tra c. To streamline our presentation, the proofs of our main results have been relegated to a series of appendices at the end of the paper.

M

2.1. Network model. Following [START_REF] Beckmann | Studies in the Economics of Transportation[END_REF] and [START_REF] Roughgarden | How bad is sel sh routing?[END_REF], the basic component of our model will be a directed multi-graph G ≡ G(V, E) with vertex set V and edge set E (both nite). We further assume that there is a nite set of origin-destination (O/D) pairs indexed by i ∈ I, each with an individual tra c demand m i ≥ 0 that is to be routed from the pair's origin node O i ∈ V to its destination D i ∈ V.

To route this tra c, the i-th O/D pair employs a set P i of paths joining O i to D i , with each path p ∈ P i comprising a sequence of edges that meet head-to-tail in the usual way; speci cally, we do not assume that P i is necessarily the set of all paths joining O i to D i , but only some subset thereof. 1 For bookkeeping reasons, we will also make the following standing assumptions throughout our paper:

a) The total in ow rate M = i ∈I m i is positive (so there is a nonzero amount of tra c in the network). b) The path sets P i are disjoint (which in particular holds trivially if all pairs (O i , D i ) are distinct). Now, writing P ≡ i ∈I P i for the union of all such paths, the set of feasible routing ows f = (f p ) p ∈P in the network is de ned as

F = f ∈ P + : p ∈P i f p = m i for all i ∈ I . (2.1)
In turn, a routing ow f ∈ F induces a load on each edge e ∈ E as

x e = p e f p , (2.2)
and we write x = (x e ) e ∈E for the corresponding load pro le on the network. Given all this, the delay (or latency) experienced by an in nitesimal tra c element traversing edge e is determined by a nondecreasing continuous cost function c e : [0, ∞) → [0, ∞): more precisely, if x = (x e ) e ∈E is the load pro le induced by a feasible routing ow f = (f p ) p ∈P , the incurred delay on edge e ∈ E is c e (x e ). Hence, with a slight abuse of notation, the associated cost of path p ∈ P will be given by

c p (f ) = e ∈p
c e (x e ).

(2.3)

Putting together all of the above, the tuple Γ = (G, I, {m i } i ∈I , {P i } i ∈I , {c e } e ∈E ) will be referred to as a (nonatomic) routing game. When we want to explicitly keep track of the total in ow rate M = i m i , we write Γ M instead of Γ; also, when there is a single O/D pair, we will drop all reference to i and I altogether.

2.2. Equilibrium, optimality, and the price of anarchy. In routing games, the notion of Nash equilibrium is captured by Wardrop's rst principle: at equilibrium, the delays along utilized paths are equal and no higher than those that would be experienced by an in nitesimal tra c element going through an unused route [START_REF] Wardrop | Some theoretical aspects of road tra c research[END_REF].

Formally, a routing ow f * is said to be a

f p c p (f p ), subject to f ∈ F . (SO)
By a simple rearrangement of terms, the objective function of (SO) can be rewritten as L(x) = e ∈E x e c e (x e ), so the value of the above problem can be expressed equivalently (and somewhat more concisely) as

Opt(Γ) = min x ∈X L(x),
(2.5)

where X = {x ∈ E + : x e = p e f p , f ∈ F } denotes the set of all load pro les of the form (2.2). Thus, to quantify the gap between solutions to (WE) and (SO), let

Eq(Γ) = L(x * ) (2.6)
where x * is the load pro le induced by a Wardrop equilibrium f * of Γ (by a standard result of [START_REF] Beckmann | Studies in the Economics of Transportation[END_REF], all such ows incur the same total cost). The game's price of anarchy (PoA) is then de ned as PoA(Γ) = Eq(Γ) Opt(Γ) .

(2.7)

For this ratio to be well-de ned, we must have Opt(Γ) > 0; otherwise, if this is not the case, we will vacuously set PoA(Γ) = 1. To avoid such technicalities, we will tacitly assume that Opt(Γ) > 0 throughout. (a) The Sioux Falls road network. Of course, PoA(Γ) ≥ 1 with equality if and only if Wardrop equilibria are also socially e cient. Our main objective in what follows will be to study the asymptotic behavior of this ratio when M → 0 or M → ∞.

○ ○○○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○○ ○○ ○○○ ○○○○ ○○○○○○ ○○○○○○○○○○○○○○○○ ○○○○ � � � � � �

F

3.1. Sioux Falls: a representative case study. To motivate our analysis, we begin by examining the behavior of the price of anarchy in the road network of Sioux Falls, a standard case study in the transportation literature. For concreteness, the network's (twoway) arterial roads are shown in Fig. 2 1). To analyze the network's price of anarchy as a function of the total tra c in ow, we considered all 528 O/D pairs with nonzero in ow, and for each O/D pair i ∈ I, we restricted P i to contain only the ve shortest paths in terms of free-ow travel time (i.e., the time taken to traverse a path when empty). We then scaled up or down these in ows preserving the ratios between di erent O/D pairs and we plotted the network's price of anarchy for various values of the total in ow M.

As can be seen from Fig. 2(b), the network's price of anarchy is identically equal to 1 when the total in ow is small enough (approximately up to 3.7 × 10 4 trips per hour); for intermediate values of M, the price of anarchy becomes strictly greater than 1, and, ultimately, it decreases monotonically to 1 in the heavy tra c limit. Interestingly, [START_REF] Leblanc | An e cient approach to solving the road network equilibrium tra c assignment problem[END_REF] report a value of M avg ≈ 3.6 × 10 5 trips/hour for the network's median tra c in ow; this value is well within the range where the price of anarchy decreases monotonically to 1 and, indeed, the observed value is approximately equal to 1.005, indicating a 0.5% di erence between socially optimum and equilibrium ows under median tra c conditions.

Similar conclusions have been drawn in the literature from empirical studies in London, New York and Boston [START_REF] Youn | Price of anarchy in transportation networks: E ciency and optimality control[END_REF], as well as Sioux Falls with di erent subsets of O/D pairs and connecting paths per pair [START_REF] O'hare | Mechanisms that govern how the price of anarchy varies with travel demand[END_REF]. In particular, in all cases, it was observed that there is an initial interval of values of M for which the price of anarchy is identically equal to 1; our rst result shows that this is not mere happenstance: Proposition 3.1. If the network's cost functions are of the form (3.1) with a e , b e > 0 and d e ≡ d for all e ∈ E, we have PoA(Γ M ) = 1 for all su ciently small M.

In fact, as the following result shows, this behavior arises whenever each O/D pair admits a single "best" path under zero in ow: Proposition 3.2. Let P i min = arg min p ∈P i c p (0) denote the set of minimal cost paths of the i-th O/D pair under zero in ow. If P i min is a singleton for all i ∈ I, we have PoA(Γ M ) = 1 for all su ciently small M.

The above results (both proven in Appendix A) provide a reasonable theoretical justication for the light tra c behavior of the price of anarchy that is observed in Fig. 2 (the heavy tra c limit is discussed in detail in the next sections). At the same time however, the BPR and "unique best path" assumptions in Propositions 3.1 and 3.2 respectively suggest that there is a ner mechanism at play which becomes apparent when the total cost at low tra c depends more delicately on the distribution of tra c in the network. We make this precise in the following section where we provide an example of a three-link network where the price of anarchy oscillates between two values strictly greater than 1, for all values of the tra c in ow.

3.2.

A network where sel sh routing is always ine cient. To construct an example of an "always ine cient" network, our approach will be to take a network with a certain degree of periodicity, obtain an explicit handle for its price of anarchy over a compact interval, and then tessellate this behavior over the entire tra c spectrum (0, ∞). To carry this out, let Γ M be a nonatomic routing game consisting of a single O/D pair with tra c in ow M. This tra c is to be routed over the three-link parallel graph of Fig. 1 with cost functions

c 1 (x 1 ) = x d 1 1 + 1 2 sin(log x 1 ) , (3.2a) c 2 (x 2 ) = x d 2 , (3.2b) c 3 (x 3 ) = x d 3 1 + 1 2 cos(log x 3 ) , (3.2c)
where d is a positive integer. It is easy to see that these cost functions are increasing, strictly convex and smooth on [0, ∞) for all d ≥ 2, and they all grow as Θ(x d ) at both tra c limits (x → 0 and x → ∞). Furthermore, the functions x e c e (x e ) are strictly convex, so the optimum tra c allocation problem (SO) admits a unique solution. Hence, the only way for the game's price of anarchy to be equal to 1 is when the game's (also unique) Wardrop equilibrium coincides with the network's socially optimum ow.

As we show in Appendix A, the equations determining the network's equilibrium and optimum ows never admit a common solution, so the price of anarchy is strictly greater than 1 over any compact interval (showing in this way that the conclusion of Propositions 3.1 and 3.2 already fails for this example). Moreover, the trigonometric terms in (3.2) imply that these equations are periodic in a logarithmic scale (i.e., in log M). Hence, combining these two properties, we obtain: Proposition 3.3. In the three-link parallel network de ned above, PoA(Γ M ) is periodic in log M and oscillates between two values strictly greater than 1. [START_REF] Colini-Baldeschi | On the price of anarchy of highly congested nonatomic network games[END_REF] already provided examples of networks where lim sup M →∞ PoA(Γ M ) > 1 but the cost functions involved were fairly irregular and the lim inf of the price of anarchy was still 1 (i.e., sel sh routing was still e cient in nitely often). By contrast, in the above example, the price of anarchy is bounded away from 1 for all possible demands, and this despite the fact that the network's cost functions are smooth, strictly convex and grow as Θ(x d ) at both ends of the congestion spectrum. This is a considerable sharpening of the example of [START_REF] Colini-Baldeschi | On the price of anarchy of highly congested nonatomic network games[END_REF] as it shows that there are cases where e ciency is never achieved at equilibrium -not even asymptotically.

N O/D

Despite the highly smooth and convex structure of the example network of Proposition 3.3, closer inspection reveals that the growth rate of its cost functions exhibits persistent oscillations at both 0 and ∞. This naturally leads to the following question: Does sel sh routing remain bad for "reasonable" cost functions that do not behave irregularly in the limit?

To quantify -and discard -such irregularities, we will employ the seminal notion of regular variation (recalled below). For clarity and concision, we will focus for now on networks with a single O/D pair; the case of multiple O/D pairs will be discussed in detail later, in Sections 5 and 6. 4.1. Regular variation and edge classi cation. To present a uni ed perspective, we will tackle both ends of the congestion spectrum simultaneously by introducing the tra c limit indicator ω ∈ {0, ∞}: letting M → ω gives the light tra c limit for ω = 0 and the heavy tra c limit for ω = ∞. Regular variation at either limit is then de ned as follows:

De nition 4.1. A function : (0, ∞) → (0, ∞) is said to be regularly varying at ω if lim t →ω (tx) (t)
is nite and nonzero for all x > 0.

(4.1)

In words, regular variation means that (t) grows at the same rate when viewed at di erent scales (determined here by x). The concept itself dates back to [START_REF] Karamata | Sur un mode de croissance régulière des fonctions[END_REF][START_REF] Karamata | Sur un mode de croissance régulière. Théorèmes fondamentaux[END_REF] and has been used extensively in functional analysis, probability, and large deviations theory (see e.g., [START_REF] De Haan | Extreme Value Theory[END_REF][START_REF] Jessen | Regularly varying functions[END_REF][START_REF] Resnick | Heavy-Tail Phenomena[END_REF]; for a comprehensive survey we refer the reader to [START_REF] Bingham | Regular Variation[END_REF].

Standard examples of regularly varying functions include all a ne functions, polynomials, logarithms, and, more generally, all analytic functions (barring those with an essential singularity at ω = ∞).2 On the other hand, despite being bounded from above and below as Θ(x d ), the oscillatory cost functions (3.2) used in the counterexample of Section 3 are not regularly varying. Indeed, at either ω = 0 or ω = ∞, the limit lim

t →ω c 1 (tx) c 1 (t) = lim t →ω 1 + 1 2 sin(log t + log x) 1 + 1 2 sin(log t) x d (4.2)
does not exist in (0, ∞) unless log x = kπ for some k ∈ (and likewise for c 3 ). In this way, regular variation provides a much ner view than polynomial growth.

With all this at hand, we will dispose of growth irregularities like the above by positing that the network's cost functions can be compared asymptotically to some regularly varying function c(x). Speci cally, given an ensemble of cost functions C = {c e } e ∈E , we will say that a regularly varying function c : (0, ∞) → (0, ∞) is a benchmark for C at ω if the following (possibly in nite) limit exists for all e ∈ E α e = lim (4.3) This limit will be called the index of edge e at ω, and e will be called fast, slow, or tight (relative to c at ω) if α e is respectively 0, ∞, or in-between. In particular, when e is tight, c e (x) is also regularly varying and exhibits the same asymptotic behavior as the benchmark function c(x) at ω; if e is fast, then c e (x) = o(c(x)); and, nally, if e is slow, then c(x) = o(c e (x)). As such, a benchmark function groups the network's edges into three equivalence classes that exhibit the same qualitative behavior with respect to c(x).

Of course, this partition depends on the chosen benchmark and the tra c limit (light or heavy): for instance, x 2 is fast with respect to x at 0, but it is slow at ∞. For concision, we will not keep track of this dependence explicitly and instead rely on the context to resolve any ambiguities. However, it will be important to keep in mind that the classi cation of fast and slow edges could be ipped when transitioning from heavy to light tra c and vice versa. Now, since bottlenecks along a path are caused by its slowest edges, we also de ne the index of a path p ∈ P as

α p = max e ∈p α e , (4.4)
and we say that p is fast, slow, or tight based on whether α p is 0, ∞, or in-between. Finally, given that tra c will tend to be routed along the fastest paths in the network, we de ne the index of the network as α = min

p ∈P α p , (4.5)
and we say that the network is itself tight if 0 < α < ∞. In words, a path is fast (resp. tight/slow) if its slowest edge is fast (resp. tight/slow), and a network is tight if its fastest path is tight. De ned this way, tightness guarantees that the network admits a path whose cost behaves asymptotically as a (positive) multiple of the benchmark function c(x). The importance of this requirement is again illustrated by the cost model (3.2) of the previous section: if we only assumed that the network admits a path whose cost behaves as Θ(c(x)), then we would not be able to rule out the pathological oscillations of the example in Section 3. 4.2. The light tra c limit. Thanks to the above legwork, we are in a position to state our main result for lightly congested networks with a single O/D pair: Theorem 4.2. Let Γ M be a nonatomic routing game with a single O/D pair. If the network is tight under light tra c (ω = 0), then

lim M →0 PoA(Γ M ) = 1. (4.6)
In words, Theorem 4.2 simply states that if the cost of the network's fastest path is regularly varying at 0, sel sh routing becomes e cient in light tra c. To streamline our presentation, Theorem 4.2 is proved in Appendix B as a special case of a much more general statement. Here, we focus on some immediate corollaries thereof: Corollary 4.3. Suppose that, for every edge e ∈ E, the limit lim x →0 c e (x)/x q e is nite and nonzero for some q e ≥ 0. Then, PoA(Γ M ) → 1 as M → 0.

Proof. Referring to q e as the order of e, de ne the order of a path p ∈ P as q p = min e ∈p q e and that of the network as q = max p ∈P q p . Clearly, lim x →0 c e (x)/x q = 0 if and only if q e > q; lim x →0 c e (x)/x q = ∞ if and only if q e < q; and lim x →0 c e (x)/x q ∈ (0, ∞) if and only if q e = q. This shows that the network is tight with respect to c(x) = x q at 0, so Theorem 4.2 applies.

(Γ M ) → 1 as M → 0. Proof. If c e (x) = ∞ k =0 c k,e
x k for small enough x, we have lim x →∞ c e (x)/x q e ∈ (0, ∞) for q e = min{k ∈ : c k,e 0}. Our claim then follows from Corollary 4.3. Of the above results, Corollaries 4.4 and 4.5 are of special practical interest because most latency models that have been proposed in the literature are polynomial or analytic at 0. In urban networks, the golden standard is the Bureau of Public Roads (BPR) quartic model c e (x) = a e + b e x 4 , while basically all of the established queueing models used in the theory of packet-switched networks (M/M/1, M/G/k, M/M/c, etc.) are analytic at 0 [START_REF] Bertsekas | Data Networks[END_REF].

Despite appearances, the very wide applicability of Theorem 4.2 and its corollaries is fairly surprising. Indeed, at rst sight, one would expect that when M → 0, tra c is so light that it doesn't really matter how it is routed. This is indeed the case if, for instance, all paths in the network exhibit di erent positive costs when M = 0 (cf. Proposition 3.2). However, if the cost of an empty path is zero, this is no longer the case: the optimum and equilibrium tra c assignments could be fairly di erent (even when the network is lightly congested), so there is no a priori reason for the price of anarchy to converge to 1 as M → 0 (the example of Section 3 clearly illustrates this phenomenon). Theorem 4.2 shows that all that is needed for this to occur is for the network's cost functions to be faithfully represented by a common benchmark function: when this condition is met, optimum and equilibrium costs no longer uctuate but, instead, they converge to the same value. 4.3. The heavy tra c limit. Our main result for highly congested networks with a single O/D pair is as follows:

Theorem 4.6. Let Γ M be a nonatomic routing game with a single O/D pair. If the network is tight under heavy tra c (ω = ∞), then

lim M →∞ PoA(Γ M ) = 1. (4.7)
In words, Theorem 4.6 simply states that if the cost of the network's fastest path is regularly varying at ∞, sel sh routing becomes e cient in heavy tra c. To compare and contrast the light and heavy tra c regimes, we relegate the proof of Theorem 4.6 to Appendix B and only focus here on some immediate corollaries thereof: Corollary 4.7. Suppose there exists a path p ∈ P with bounded costs, that is,

lim x →∞ c e (x) < ∞ for all e ∈ p. Then, PoA(Γ M ) → 1 as M → ∞.
Proof. Taking c(x) = 1, we get α e = lim x →∞ c e (x) ∈ (0, ∞] for all e ∈ E. By assumption, there exists a path such that 0 < α p < ∞, so Theorem 4.6 applies.

Corollary 4.8. Suppose that the limit lim x →∞ c e (x)/x q e is nite and nonzero for some q e ≥ 0 and all e ∈ E. Then, PoA(Γ M ) → 1 as M → ∞.

Proof. Shadowing the proof of Corollary 4.3, let q p = max e ∈p q e and q = min p ∈P q p (but note the reversal of the max and min operators). Clearly, lim x →∞ c e (x)/x q = 0 if and only if q e < q; lim x →∞ c e (x)/x q = ∞ if and only if q e > q; nally, lim x →∞ c e (x)/x q ∈ (0, ∞) if and only if q e = q. This shows that the network is tight with respect to c(x) = x q at ∞, so Theorem 4.6 applies.

Corollary 4.9. In a single O/D-network with polynomial costs we have PoA(Γ M ) → 1 as M → ∞.

In a certain, precise sense, Theorems 4.2 and 4.6 show that the high and low congestion regimes can be seen as di erent sides of the same coin. By excluding pathological oscillations at either end of the congestion spectrum, regular variation ensures asymptotic regularity and guarantees that sel sh routing becomes e cient in the limit: speci cally, tightness at 0 guarantees e ciency in light tra c while tightness at ∞ guarantees eciency in heavy tra c. By this token, taking Corollaries 4.5 and 4.9 in tandem implies that sel sh routing becomes e cient under both light and heavy tra c in networks with polynomial costs and a single O/D pair.

That being said, there are still important, quantitative di erences between the light and heavy tra c limits. For instance, even though Corollaries 4.8 and 4.9 are direct analogues of their light tra c counterparts, the conclusion of Corollary 4.7 is false in light tra c (the three-link network of Section 3 serves again as a counterexample). In fact, even in the case of polynomial costs (Corollary 4.5 vs. Corollary 4.9), there is an important reversal of roles that takes place between fast and slow edges. Speci cally, edges that are fast in light tra c typically become slow under heavy tra c and vice versa (importantly however, tight edges are not re-classi ed under this regime change). Nevertheless, despite this reversal, the price of anarchy still goes to 1 in both cases.

N O/D

We now extend our analysis to networks with multiple O/D pairs. In this case, if the in ow rate of the i-th O/D pair is m i , the total tra c in ow in the network is given by

M = i ∈I m i ,
(5.1) and we write

λ i = m i M (5.2)
for the relative in ow rate of the i-th O/D pair -i.e., the fraction of the total tra c generated by the pair in question. In the rest of this section, we will assume that the relative in ow of every O/D pair i ∈ I is a xed positive constant that does not depend on M; the case of variable in ow rates will be discussed in detail in Section 6.

The key di erence with the single-pair setting is that routing costs for di erent O/D pairs may exhibit completely di erent asymptotic behaviors in the limit. As a result, in the presence of multiple O/D pairs, the de nition of the network's index (and the related notion of tightness) must be re-examined. To do so, given that the tra c generated by an O/D pair will tend to be routed along the pair's fastest path, we rst de ne the index of an O/D pair i ∈ I as

α i = min p ∈P i α p .
(5.3)

Just like edges and paths, this index can be used to classify O/D pairs as fast, slow or tight depending on whether α i is respectively 0, ∞, or in-between. The index of the network is then de ned as

α = max i ∈I α i , (5.4)
and we say that the network is tight if 0 < α < ∞. Heuristically, this de nition simply captures the fact that the leading contribution to congestion is due to the "costliest" O/D pairs in the network; obviously, if there is but a single O/D pair, this last point is moot and (5.4) reduces to (4.5).

O 1 D 1 O 2 D 2 c 1 (x) = x c 2 (x) = x 2 c 3 (x) = log(1 + x) c 4 (x) = 1 + √ x c 5 (x) = e x
Example 5.1. To illustrate the above concepts, consider a Wheatstone network with two O/D pairs and cost functions as in Fig. 3. Focusing rst on the heavy tra c limit, the benchmark c(x) = x would classify edge 1 as tight, edges 2 and 5 as slow, and edges 3 and 4 as fast. Accordingly, the rst O/D pair would be classi ed as tight while the second O/D pair would be classi ed as fast; since no pair is slow and at least one pair is not fast, the network is itself tight. In the light tra c limit, the same benchmark would classify edges 1 and 3 as tight, edges 4 and 5 as slow, and edge 2 as fast. Under this classi cation, the rst O/D pair would again be tight, but the second O/D pair would now be classi ed as slow (because all its paths contain a slow edge), so the network would no longer be tight. A moment's re ection shows that the reason for this is that the benchmark function c(x) = x is not well-suited for the second O/D pair. Instead, if we take the benchmark c(x) = 1, the rst O/D pair would be classi ed as fast (because it has a fast path, namely edge 1) and the second pair would be classi ed as tight, so the network would now be tight. For a systematized version of this benchmark selection procedure, see the proof of Corollary 5.2 below.

With all this at hand, our next result states that if the costliest O/D pair in the network admits a tight path, sel sh routing becomes asymptotically e cient in the limit: Theorem 5.1. Let Γ M be a nonatomic routing game. If the network is tight in the limit as M → ω, then lim

M →ω
PoA(Γ M ) = 1.

(5.5)

In words, if (a) every O/D pair has a path which is not slow, and (b) the fastest path of the slowest O/D pair has a regularly varying cost, sel sh routing becomes e cient in the limit. Motivated by the strong connection between Theorems 4.2 and 4.6, Theorem 5.1 has been stated in a way that does not discriminate between the light and heavy tra c regimes. The reason for this is to highlight the role of the tightness assumption: tightness at 0 guarantees e ciency in light tra c (ω = 0) while tightness at ∞ guarantees e ciency in heavy tra c (ω = ∞).

Of course, both Theorems 4.2 and 4.6 follow as corollaries of Theorem 5.1 by taking respectively ω = 0 or ∞ and specializing to a single O/D pair (in which case Eqs. (4.5) and (5.4) coincide). Other than that, however, the same caveats apply regarding the passage from light to heavy tra c: the classi cation of fast and slow edges could be reversed, the equilibrium/socially optimum ows could be drastically di erent in the two regimes, etc. To illustrate all this, we proceed with some further corollaries of Theorem 5.1 (which we prove in Appendix B):

Corollary 5.2. If the network's costs are regularly varying at ω and the (possibly in nite) limit α e,e = lim Proof. De ne a total preorder among the network's edges by setting e e if and only if α e,e ≤ 1. For each path p ∈ P, choose a maximal element e p of p, i.e., an edge e p ∈ p such that e e p for all e ∈ p. Then, for each O/D pair i ∈ I, choose a path p i for which e p i is minimal, i.e., e p i e p for all p ∈ P i . Finally, pick an O/D pair i ∈ I such that e p i is maximal, i.e., e p j e p i for all j ∈ I. Setting e * = e p i and taking c(x) ≡ c e * (x) as a benchmark, it is easy to verify that the network is tight at ω, so Theorem 5.1 applies.

The proof of Corollary 5.2 shows that the "comparison index" α e,e induces a preference relation which re nes the coarser classi cation of the network's edges into fast, slow and tight. Of course, this ordering could be reversed when passing from light to heavy tra c, but the existence thereof (along with regular variation) guarantees that the price of anarchy is asymptotically equal to 1 in both cases.

In addition to the above, Corollary 5.2 also gives an alternative way to prove the following analogue of Corollaries 4.3 and 4.8:

Corollary 5.3. Suppose that the limit lim x →ω c e (x)/x q e is nite and nonzero for some q e ≥ 0 and all e ∈ E. Then, PoA(Γ M ) → 1 as M → ω.

Proof. Observe that c e (x) c e (x) = c e (x)

x q e

x q e x q e

x q e c e (x) , (5.7) so lim x →ω c e (x)/c e (x) exists for all e ∈ E. Our claim then follows from Corollary 5.2.

We thus obtain the following important corollary for polynomial cost functions:

Corollary 5.4. In networks with polynomial costs, PoA(Γ M ) → 1 as M → ω.

In words, Corollary 5.4 yields the general principle that we stated in the introduction:

In networks with polynomial costs, the price of anarchy becomes 1 under both light and heavy tra c.

We nd this principle particularly appealing as it indicates that the price of anarchy may attain high values only in an intermediate regime (where the tra c is neither light nor heavy).

N

An important assumption in the analysis of the previous section is that the relative in ow rate λ i = m i /M of each O/D pair i ∈ I does not uctuate in the limit -i.e., all pairs are assumed to generate a constant fraction of the overall tra c. In general however, this assumption need not hold: for instance, in an urban road network, central O/D pairs generate disproportionately more tra c during rush hour than peripheral, suburban destinations, so it is not reasonable to assume that tra c scales up maintaining a constant tra c ratio between di erent O/D pairs.

To understand the impact of this variability, consider two independent links, e 1 and e 2 , with corresponding cost functions c 1 (x) = x and c 2 (x) = x 2 . Suppose further that these links are joining two uncoupled O/D pairs with in ow rates m 1 and m 2 and total in ow M = m 1 + m 2 . If both in ows scale in the limit as Θ(M), the cost of the rst pair will scale as Θ(M) while that of the second pair will scale as Θ(M 2 ). As such, the leading contribution to congestion will be that of the rst O/D pair in light tra c, and that of the second pair in heavy tra c. If, however, the in ow of the rst pair scales as Θ(M) but that of the second pair scales as Θ(M 1/3 ), the induced costs will scale respectively as Θ(M) and Θ(M 2/3 ); consequently, the most costly O/D pair will now be the second one in light tra c and the rst one in heavy tra c.

This reversal of roles shows that the asymptotic behavior of the relative in ow rates λ i = m i /M could end up painting a completely di erent picture in the limit. In particular, if these relative rates oscillate wildly in the limit, the price of anarchy may exhibit a likewise irregular asymptotic behavior, even if the underlying network is well-behaved (for instance, even if it is tight; cf. Example 6.2 below). As a result, special care must be taken to de ne and study the asymptotic regime in networks with variable tra c demands.

To that end, let Γ n be a sequence of nonatomic routing games with total in ow M n = i ∈I m i n induced by a sequence of in ow rates m i n for each O/D pair i ∈ I. The light and heavy tra c limits are obviously recovered depending on whether the total in ow M n converges respectively to ω = 0 or ω = ∞ as n → ∞. However, the relative in ow rates λ i n = m i n /M n could now exhibit very di erent behaviors as n → ∞: in particular, as discussed above, the relative in ow of an O/D pair could oscillate -or even vanish -in the limit. To capture such phenomena, we introduce below the notion of salience: De nition 6.1. Let Γ n be a sequence of nonatomic routing games with relative in ow rates λ i n , i ∈ I. We say that a subset

I ⊆ I of O/D pairs is salient if lim inf n→∞ i ∈I λ i n > 0, ( 6.1)
i.e., if the total fraction of the tra c generated by the O/D pairs in I is non-negligible in the limit.

Obviously, if the sequence of relative in ow vectors λ n = (λ i n ) i ∈I converges to a wellde ned limit, I will be salient if and only if some O/D pair of I is itself salient -i.e., if and only if lim inf n→∞ λ i n > 0 for some i ∈ I . However, if this is not the case, a set of O/D pairs may be salient even if none of its constituent pairs is salient: for instance, if there are two O/D pairs, "+" and "-", with relative in ows λ ± n = (1 ± (-1) n )/2, neither pair is salient but their union is (since λ + n + λ - n = 1 for all n). Thus, the notion of salience does not rule out uctuations in the relative in ows of individual O/D pairs; it only posits that the set of O/D pairs in question carries enough tra c in the limit.

Bearing all this in mind, our main result for networks with variable in ow rates is as follows:

Theorem 6.2. Let Γ n be a sequence of nonatomic routing games with in ow rates m i n and total in ow M n = i ∈I m i n . Suppose further that: (a) Tra c is either light or heavy in the limit, i.e., lim n→∞ M n = ω ∈ {0, ∞}. (b) Every O/D pair has a path which is not slow, i.e., α i < ∞ for all i ∈ I. (c) The set of tight O/D pairs is salient, i.e., lim inf n→∞ i: In view of all this, Theorem 6.2 can be seen as a direct extension of our " xed-rate" analysis in Sections 4 and 5: indeed, in the case of constant (positive) relative in ows, salience boils down to asking that the network admits at least one tight O/D pair, so Theorem 5.1 can be obtained as a special case of Theorem 6.2. Below, we provide some further corollaries of Theorem 6.2 along these lines: On the other hand, it is worth noting that if salience fails, we can draw no de nitive conclusions for the price of anarchy. We illustrate the main reasons for this via two examples below:

α i >0 λ i n > 0. Then, PoA(Γ n ) → 1 as n → ∞. O 1 D 1 O 2 D 2 c 1 (x ) = 1 c 2 (x ) = x c 3 (x ) = 0
Example 6.1 (E ciency without salience). Consider the simple network of Fig. 4, where two "uncoupled" O/D pairs respectively encounter a standard Pigou network and an independent link with zero cost. In heavy tra c, the benchmark function c(x) = 1 classi es the O/D pair i = 1 as tight and the pair i = 2 as fast, so the network is itself tight. Note also that the second O/D pair does not a ect the network's price of anarchy because it has a single routing option and its cost is identically equal to 0; however, it still a ects the de nition of relative in ows.

If we take the in ow sequence

m 1 n = √ n and m 2 n = n, we get M n = n + √ n → ∞ and λ 1
n → 0 as n → ∞, so the rst O/D pair is not salient. Since the second O/D pair is not tight, Condition (c) fails; nevertheless, if we apply Theorem 4.6 to the rst O/D pair by itself, we obtain lim M →∞ PoA(Γ M ) = 1 (recall here that the second pair does not a ect the network's PoA). In other words, Condition (c) is not necessary for sel sh routing to be asymptotically e cient. Example 6.2 (Ine ciency without salience). Consider the same network as above but take the periodically oscillating in ow sequence m 1 n = 1 for n odd, 1 + 2n for n even, and m 2 n = 2n for n odd, 0 for n even. (6.2)

We then have M n = 2n + 1 → ∞ and lim inf n→∞ λ 1 n = 0 so, again, Condition (c) fails (but in a di erent way). This time, whenever n is odd, the network's price of anarchy is equal to that of a Pigou network with in ow 1 (because the second O/D pair is costless). Thus, for n odd, we get PoA(Γ n ) = 4/3, which is the worst-case value for networks with a ne costs; as such, the conclusion of Theorem 6.2 does not hold in general if we just drop the salience condition.

O D c 1 (x ) = x d 1 c 2 (x ) = x d 2
The above examples suggest that there is a ner mechanism at work which is not captured by the intersection of tightness and salience. At a high level, the crucial component of this mechanism seems to be that asymptotic e ciency is guaranteed if the network remains tight after suitably modifying the network's cost functions to take into account the scaling of the in ow of each O/D pair. However, getting an exact statement at this level of generality is fairly cumbersome, so we do not attempt it here.

R

The analysis of the previous sections provides a wide range of su cient conditions guaranteeing that sel sh routing becomes e cient in the limit; however, it does not provide any indication for the rate at which the network's price of anarchy converges to 1. In this section, we derive such rates (including subleading terms) for networks with polynomial costs of the form where all coe cients are assumed nonnegative (c e,k ≥ 0) and q e and d e respectively denote the smallest and largest powers present (so c e,q e , c e,d e > 0); by convention, we also take q e = ∞ and d e = 0 when c e (x) ≡ 0.3 This model covers in particular the BPR "constant plus monomial" model (3.1) but also extends more easily to networks with more intricate cost functions.

In contrast to our qualitative analysis, the two tra c limits (light and heavy) exhibit di erent quantitative behaviors, so we treat them separately.

7.1. The light tra c case. We begin with the light tra c limit (ω = 0). To motivate our analysis, we start with a simple example of a Pigou network with monomial costs as shown in Fig. 5: for d 1 , d 2 > 0, the zero-ow travel time of both links is zero, so Proposition 3.2 does not apply. Instead, as we show below, the network's price of anarchy decays to 1 following a power law: Proposition 7.1. Consider a two-link parallel network with cost functions c 1 (x) = x d 1 and c 2 (x) = x d 2 , 0 < d 1 < d 2 , and a single O/D pair with in ow M. Then

PoA(Γ M ) = 1 + bM a + o(M a ) (7.2)
where

a = d 2 /d 1 -1, (7.3) ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ ○ ��=�� ��=� □ ��=�� ��=� ◇ ��=�� ��=� △ ��=�� ��=� �� -� �� -� ����� ����� ����� � �� -�� �� -� �� -� �� -� ����� ������ (�) ���-� ����� �� ������� �� � �������� �� ������ (����� �������) ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ ○ ��=�� ��=� □ ��=�� ��=� ◇ ��=�� ��=� △ ��=�� ��=� �� -� �� -� ����� ����� ����� � ���� ���� ���� � ����� ������ (�) � -� (���-�)

���������� ����� �� ������� �� � �������� �� ������ (����� �������)

Figure 6. The rate of convergence of the price of anarchy in a lightly congested Pigou network as in Fig. 5. The gure on the left shows the price of anarchy as a function of the total tra c in ow M for di erent values of the exponents d 1 and d 2 . In the gure to the right, the price of anarchy has been rescaled by M -a with a = d 2 /d 1 -1, showing that PoA(Γ M ) ∼ 1 + bM a for some b > 0; the horizontal asymptotes correspond precisely to the expression (7.4) for b.

and b = d 1 1 + d 2 1 + d 1 1+1/d 1 -d 2 > 0. (7.4)
In words, Proposition 7.1 shows that the rate of convergence of the price of anarchy is controlled by the ratio d 2 /d 1 : the largest the ratio of degrees, the fastest the decay of the price of anarchy (for a numerical illustration, see Fig. 6). This behavior is consistent with Proposition 3.2 which predicts that PoA(Γ M ) ≡ 1 if M is small enough and d 1 = 0. Indeed, taking d 1 → 0 in (7.2) shows that PoA(Γ M ) = 1 + O(M a ) for any a > 0, suggesting in turn that the rate of decay of PoA(Γ M ) is qualitatively di erent in this case.

Another case worth noting is when d 1 = d 2 , i.e., when both links are equivalent in terms of performance. In this case, PoA(Γ M ) is identically equal to 1 for all values of M (Proposition 3.1 already guarantees as much when M is not large). However, (7.2) would seem to suggest that the price of anarchy can remain large as M → 0 (since a = 1 -1 = 0 when d 1 = d 2 ). The solution of this apparent paradox is provided by looking at the multiplicative constant b: when d 1 = d 2 , we also have b = 0, so the resulting contribution to the price of anarchy is 0 -not Ω(1).

The above highlights the importance of the relative rate of decay of the network's edge costs as a function of the in ow. Since monomials with lower exponents are more costly in the low tra c limit, this rate is dominated by the smallest power in (7.1). Thus, motivated by the index machinery of Sections 4 and 5, we respectively de ne the order of an edge e ∈ E, that of a path p ∈ P, of an O/D pair i ∈ I, and that of the network itself as q e = min{k : c e,k > 0} (7.5a)

q p = min e ∈p
q e , (7.5b)

q i = max p ∈P i q p , (7.5c) q = min i ∈I q i . (7.5d) ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ ○ ��=�� ��=� □ ��=�� ��=� ◇ ��=�� ��=� △ ��=�� ��=� ��� �� � �� � �� -� �� -� �� -� �� -� ����� ����� ����� ����� ������ (�) ���-� ����� �� ������� �� � �������� �� ������ (����� �������) ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ◇ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ △ ○ ��=�� ��=� □ ��=�� ��=� ◇ ��=�� ��=� △ ��=�� ��=� ��� �� � �� � ���� ���� ���� ���� ���� ���� ����� ������ (�) � � (���-�)

���������� ����� �� ������� �� � �������� �� ������ (����� �������)

Figure 7. The rate of convergence of the price of anarchy in a heavily congested Pigou network as in Fig. 5. The gure on the left shows the price of anarchy as a function of the total tra c in ow M for di erent values of the exponents d 1 and d 2 . In the gure to the right, the price of anarchy has been rescaled by M a with a = 1 -d 1 /d 2 , showing that PoA(Γ M ) ∼ 1 +b/M a for some b > 0; the horizontal asymptotes correspond precisely to the expression (7.11) for b.

In view of the above, the network is tight with respect to the benchmark function c(x) = x q , and an edge e ∈ E is fast when q e > q, tight when q e = q, and slow if q e < q. We then denote the set of the network's slow edges as

E slow = {e ∈ E : q e < q}, (7.6)
and we write q slow = max e ∈E slow q e (7.7)

for the order of the fastest edge in E slow (again employing the standard convention that max = -∞, so q slow = -∞ when there are no slow edges).

Building on the intuition gained from Proposition 7.1, our main quantitative result for low tra c is that the network's PoA decays to 1 following a power law that depends only on the ratio between the order of the network (q) and that of its fastest slow edge (q slow ): Theorem 7.2. Let Γ M be a nonatomic routing game with polynomial costs, total in ow M, and xed relative in ows. Then, there exist non-negative constants

K 1 ≥ 0 and K a ≥ 0 such that PoA(Γ M ) ≤ 1 + K 1 M + K a M a , (7.8)
where a = q/q slow -1 and K a = 0 whenever E slow = .

Theorem 7.2 was stated for networks with xed relative in ows for simplicity only: in Appendix C, we state and prove a more general result for networks with variable relative in ows as in Section 5. In terms of intuition, we only note here that Theorem 7.2 complements the insights gained from Propositions 3.1 and 3.2 in an important way: when there is no single "best path" under zero in ow, the network's price of anarchy is no longer identically equal to 1 for small in ows but instead behaves as a power law. 7.2. The heavy tra c case. We now turn to the heavy tra c limit (ω = ∞). As in the light tra c case, we start with a simple -but illuminating -example of a two-link Pigou network where precise results can be obtained:

= d 2 1 + d 1 1 + d 2 1+1/d 2 -d 1 > 0. (7.11)
For illustration purposes, we plotted in Fig. 7 the asymptotic behavior of the network's price of anarchy for di erent values of d 1 and d 2 . In the same vein as in the light tra c limit, two special cases that are of interest here are when d 2 = ∞ and when d 1 = d 2 . In the former (d 2 = ∞), Eq. ( 7.10) gives a = 1, indicating a convergence rate of the order of O(1/M): since a < 1 for all nite d 2 , this is the best possible rate that can be achieved in the heavy tra c limit. For the latter (d 1 = d 2 ), Eq. ( 7.10) gives a = 0, suggesting that the price of anarchy can remain large as M → ∞. This seems to be inconsistent with the fact that the network's price of anarchy is identically equal to 1 when d 1 = d 2 but a closer look reveals that the multiplicative constant b of (7.11) is also 0 when d 1 = d 2 , thus reconciling the two results. Now, even though the above result does not apply to more general networks with polynomial costs, it still highlights the main mechanism at play. Speci cally, for large edge loads x, the dominant term in (7.1) is the one with highest degree d e . As we've discussed before, this indicates a complete reversal of roles between light and heavy tra c: for d 1 < d 2 , x d 1 is slower than x d 2 when x → 0, but faster when x → ∞. Thus, with an obvious adaptation of what we did for light tra c, we de ne the order of an edge e ∈ E, that of a path p ∈ P, of an O/D pair i ∈ I, and of the network itself as d e = max{k : c e,k > 0} (7.12a)

d p = max e ∈p d e , (7.12b)
d i = min p ∈P i d p , (7.12c)
d = max i ∈I d i . (7.12d)
With all this at hand, we see that the network is tight with respect to the benchmark c(x) = x d , so an edge e ∈ E is fast when d e < d, tight when d e = d, and slow if d e > d.

The set of the network's slow edges is then denoted as for the order of the fastest edge in E slow (again employing the standard convention that min = ∞, so d slow = ∞ when there are no slow edges). Mutatis mutandis, this de nition is the same as in light tra c except for a reversal of the max/min operators. Our main result for heavily congested networks con rms this intuition:

E slow = {e ∈ E : d e > d }, (7.13
Theorem 7.4. Let Γ M be a nonatomic routing game with polynomial costs, total in ow M, and xed relative in ows. Then, there exist non-negative constants K 1 ≥ 0 and K a ≥ 0 such that

PoA(Γ M ) ≤ 1 + K 1 M + K a M a , (7.15)
where a = 1 -d/d slow and K a = 0 whenever E slow = .

Remark 7.1. As in the light tra c case, if the costs are monomials of the same degree, then K 1 = K a = 0 and PoA(Γ M ) ≡ 1 for all M > 0.

In words, given that a < 1 when there is at least one slow edge in the network (a = 1 and K a = 0 otherwise), Theorem 7.4 states the network's price of anarchy converges to 1 as O(1/M a ) with an O(1/M) subleading term. In particular, in the presence of a single slow edge with d e > d, the convergence exponent a in (7.15) can become as small as 1/(d + 1), thus pointing to a slower convergence rate in networks with routing costs of high degree and a small gap between the degree of tight and slow edges. On the other hand, if there are no slow edges we have E slow = and we get an O(1/M) rate of convergence.

On this issue, [START_REF] Wu | Sel shness need not be bad[END_REF] recently showed that if all the network's cost functions are of the BPR type c e (x) = a e +b e x d with the same degree d, then PoA(Γ M ) = 1+O(M -d ) as M → ∞. In this special case, the rate of convergence is faster than the prediction of Theorem 7.4, a gap which points to a sharp discontinuity that occurs when all costs have the same degree. To see this in a concrete example, consider again the two-link Pigou network of Fig. 5. By symmetry, if d 1 = d 2 , the fraction of tra c routed on edge 1 at optimum and at equilibrium coincide (7.16) implying in turn that PoA(Γ M ) is identically equal to 1. On the other hand, when d 1 < d 2 , both fractions ˜ 1 and * 1 converge to 1 as M → ∞. Proposition 7.3 shows that the rate of convergence of the price of anarchy in this case is exactly of order Θ(1/M a ) and cannot be improved.

˜ 1 = * 1 = 1 2 for all M > 0,
Put di erently, Proposition 7.3 shows that the slightest di erence in edge degrees causes the rate of convergence of the price of anarchy to drop abruptly to Θ(M -a ); in fact, Eq. (7.11) even provides an explicit expression for the proportionality constant in the high congestion rate Θ(M -a ). By this token, the bounds provided by Theorem 7.4 are tight and cannot be improved in general, even in the class of two-link parallel networks with monomial costs.

D

Most of the literature on the price of anarchy -for congestion games and not onlyhas traditionally focused on worst-case upper bounds for di erent classes of networks, cost functions, and/or types of players. Several of these results have become milestones in the eld and have had a signi cant impact in practical considerations for tra c networks. However, real-world situations involve a xed network and tra c ows that are not necessarily close to these worst-case scenarios. Thus, in addition to determining how bad can sel sh routing become, it is also important to determine when these cases are relevant.

Our goal in this paper was to provide an answer to this question by examining the behavior of the price of anarchy at each end of the congestion spectrum. Under fairly mild assumptions (that always include networks with polynomial costs), we found that the PoA goes to 1 in both cases, independently of the network's topology, and even when there are multiple O/D pairs. What we nd appealing about this result is that it is essentially independent of the underlying graph and/or the distribution of O/D pairs in the network. Especially in the heavy tra c limit, this means that sel sh routing is not the real cause of increased delays: from a social planner's point of view, sophisticated tolling/rerouting schemes that target the optimum tra c assignment will not yield considerable gains over a "laissez-faire" approach where each tra c element takes the fastest available path.

A

A. P S 3

We start this appendix with the proofs of Propositions 3.1 and 3.2. To that end, we rst establish the following result: Lemma A.1. For su ciently small M, equilibrium and optimum tra c allocations only employ paths in P i min = arg min p ∈P i c p (0). Proof. In a slight abuse of notation, let c p (M) = e ∈p c e (M) denote the cost of the path p if all its edges carry load equal to the total in ow M. Clearly, if M is small enough, we have c p (0) > c p (M) for all p ∈ P i min and all p ∈ P i \ P i min . Hence, for an equilibrium ow f * , we have

c p (f * ) ≥ c p (0) > c p (M) ≥ c p (f * ), (A.1)
implying in turn that f * p = 0. Likewise, since an optimal ow f is an equilibrium for the marginal costs ce (x) = c e (x) + x c e (x) and cp (0) > cp (M), similar considerations show that an optimum ow pro le cannot route any tra c along a path p ∈ P i \ P i min . To proceed, it is more convenient to start with Proposition 3.2:

Proof of Proposition 3.2. By Lemma A.1, when M is small enough, both the equilibrium and the optimum must route the total in ow m i along the unique path in P i min . Hence the equilibrium and optimal ows coincide and therefore the price of anarchy is equal to 1.

With this result at hand, we have:

Proof of Proposition 3.1. If P i
min is a singleton for all i ∈ I, our claim follows from Proposition 3.2. Otherwise, by Lemma A.1, if M is small enough, for every i ∈ I, only paths in P i min are used in equilibrium. Moreover, if p, p ∈ P i min , then, for M small enough, we have Comparing (A.3) and (A.5), we see that the two equations are satis ed by the same loads. Therefore, for M small enough, there exist an equilibrium and an optimum having the same ows. Uniqueness of the equilibrium and optimum costs provides the result.

We now present the proof of the counterexample with an oscillating PoA of Section 3.2:

Proof of Proposition 3.3. Since an unused edge has a cost of zero under (3.2), all three edges must be used at equilibrium. Hence, for a given value of the total in ow

M = x 1 + x 2 + x 3 , the load pro le x = (x 1 , x 2 , x 3 ) is a Wardrop equilibrium if and only if c 1 (x 1 ) = c 2 (x 2 ) = c 3 (x 3 ).
In that case, the normalized pro le z = x/M satis es

z d 1 1 + 1 2 sin(log Mz 1 ) = z d 2 = z d 3 1 + 1 2 cos(log Mz 3 ) . (A.6)
Likewise, after di erentiating and rearranging, the conditions for the network's socially optimum ow are

z d 1 1 + 1 2 sin(log Mz 1 ) + 1 2(d +1) cos(log Mz 1 ) = z d 2 = z d 3 1 + 1 2 cos(log Mz 3 ) -1 2(d
, k 3 ∈ such that log Mz 1 = k 1 π + π 2 , log Mz 3 = k 3 π . (A.9)
This implies that sin(log Mz 1 ) = ±1 and cos(log Mz 3 ) = ±1, leading to the following cases:

Case 1: sin(log Mz 1 ) = 1, cos(log Mz 3 ) = 1. Substituting in (A.6) we get z d 1 = z d 3 so (A.9) gives .10) This gives k 3 -k 1 = 1/2, which cannot hold for integer values of k 1 and k 3 .

k 1 π + π 2 = k 3 π . (A
Case 2: sin(log Mz 1 ) = 1, cos(log Mz 3 ) = -1. As above, from (A.6) we get 3z d 1 = z d 3 , so (A.9) gives 1 .11) This yields log 3

d log 3 + k 1 π + π 2 = k 3 π . (A
π = d(k 3 -k 1 -1 2 )
, which again cannot hold for k 1 , k 3 , d ∈ . The remaining two cases lead to a contradiction in the same way, implying that the game's Wardrop equilibrium and socially optimum ows cannot coincide for any value of M. Since Eqs. (A.6) and (A.7) are periodic in log M, it follows that the game's price of anarchy oscillates periodically at a logarithmic scale. Thus, focusing on the period 1 ≤ M ≤ e 2π , we conclude that The following asymptotic approximation result provides the heavy lifting for the proof of Theorem 6.2: Lemma B.3. Consider a network with nondecreasing cost functions e , with e (0) = 0 for e ∈ E, and suppose that it admits a benchmark function at ω, which is ρ-regularly varying with ρ > 0. Consider also a sequence of in ow vectors m n = M n λ n such that: a) M n → ω and the vector of relative in ows λ n converges to some λ ∈ ∆(I). b) Every O/D pair has a path which is not slow (relative to ). c ) There exists an O/D pair i ∈ I which is tight (relative to ) and has λ i > 0.

Then, the optimal allocation problem and, by convention, we have set α e z ρ e = 0 if α e = ∞ and z e = 0. Moreover, if ˆ n is a sequence of optimal solutions of G n , every limit point of ˆ n solves V ρ (λ).

G n = min
Proof. The arguments in the proof are similar to the line of reasoning in epi-convergence arguments as in [START_REF] Attouch | Variational Convergence for Functions and Operators[END_REF]. To streamline the presentation, we break up the proof in ve steps as follows:

Step 1: V ρ (λ) < ∞. By Condition (b), each O/D pair admits a path that is not slow; therefore, routing all tra c through said path gives a nite value for the objective of (B.11), implying in turn that V ρ (λ) < ∞. More precisely, for every i ∈ I, take a tra c allocation i ∈ Y i that assigns zero weight to the slow paths P i slow of i. Then, for every slow edge e ∈ E slow , we have z Step 2: V ρ (λ) > 0. By Condition (c), there exists a tight O/D pair i ∈ I tight such that λ i > 0. For every ∈ Y we have p ∈P i p = 1, so there exists some route p ∈ P i with

α e λ i /|P i | ρ ≥ α i λ i /|P i | ρ > 0. (B.13)
Minimizing over ∈ Y then yields V ρ (λ) > 0, as claimed.

Step 3: .11). By the niteness of V ρ (λ), we have ζ e ( ˆ , λ) = 0 for every slow edge e ∈ E slow (i.e., when α e = ∞). If λ i > 0, this implies that z i e ( ˆ ) = 0. Otherwise, if λ i = 0, the objective function of (B.11) does not depend on i , so every i with z i e ( ) = 0 is also optimal. Hence we can choose the solution ˆ of (B.11) so that all tra c is routed along edges that are not slow. Now, from optimality we have (B.17)

lim sup n→∞ G n / (M n ) ≤ V ρ (λ). Fix an optimal solution ˆ ∈ Y of (B
G n (M n ) ≤ 1 (M n ) e ∈E e (
Step 4: lim inf n→∞ G n / (M n ) ≥ V ρ (λ). Passing to a subsequence if necessary, we may assume that lim inf n→∞ G n / (M n ) is attained as a limit. Thus, letting ˆ n be a sequence of solutions of G n , and taking a further subsequence if necessary, we may assume that ˆ n converges to some ˆ ∈ Y. To proceed, we will show that ζ e ( ˆ , λ) = 0 for every slow edge. Indeed, if this were not the case, we could nd some ε > 0 such that ζ e ( ˆ n , λ n ) > ε for all su ciently large n. With e nondecreasing, we then get (B.20) in contradiction to Steps 1 and 3 above. From all this, it follows that

G n (M n ) ≥ e (M n ζ e ( ˆ n , λ n )) (M n ) ≥ e (M n ε) (M n ) = e (M n ε) (M n ε) (M n ε) (M n ) → α e ε ρ = ∞,
lim inf n→∞ G n (M n ) ≥ e ∈E α e ζ e ( ˆ , λ) ρ ≥ V ρ (λ). (B.21)
Step 5: Optimality of limit points. As above, let ˆ n be a sequence of optimal solutions of (B.9) and, by descending to a subsequence if necessary, assume that it converges to some ˆ ∈ Y. From the previous steps we have G n / (M n ) → V ρ (λ) so, proceeding as in Step 4, we get B.22) showing that ˆ solves (B.11).

V ρ (λ) = lim n→∞ G n (M n ) ≥ e ∈E α e ζ e ( ˆ , λ) ρ ≥ V ρ (λ), (
Armed with Lemma B.3, we are nally in a position to prove Theorem 6.2:

Proof of Theorem 6.2. To begin with, express the objective function of (SO) in terms of the normalized ow variables as

L n ( ) = e ∈E
x e ( , m n ) c e (x e ( , m n )).

(B.23)

Now, let * n , ˜ n be the normalized tra c allocation pro les of a Wardrop equilibrium and a socially optimum ow, respectively. Then, the network's price of anarchy may be expressed as

PoA(Γ n ) = Eq(Γ n ) Opt(Γ n ) = L n ( * n ) L n ( ˜ n ) . (B.24)
Notice that Opt(Γ n ) > 0 thanks to Assumptions (b) and (c).

In order to prove that PoA(Γ n ) → 1 it su ces to take a subsequence Γ n k realizing the lim sup n→∞ PoA(Γ n ) as a limit and to prove that PoA(Γ n k ) → 1. Relabeling indices and extracting a further subsequence if necessary, we may assume without loss of generality that: (a) the limit lim n→∞ PoA(Γ n ) exists; (b) the sequence λ n of relative in ows converges to some λ ∈ ∆(I); and (c) the sequences * n and ˜ n converge to some * , ˜ ∈ Y respectively. With all this, we will use Lemma B.3 to derive the asymptotic behavior of Opt(Γ n ) and Eq(Γ n ).

First, for Opt(Γ n ), combining Lemma B.1 with Proposition 1.5.1 of [START_REF] Bingham | Regular Variation[END_REF] and the fact that the network's cost functions are nondecreasing, we immediately see that the network's benchmark function c is β-regularly varying for some β ≥ 0. Then, letting e (x) = xc e (x) and (x) = xc(x), we also get that is ρ-regularly varying with ρ = 1 + β > 0 and lim x →ω e (x)/ (x) = lim x →ω c e (x)/c(x) = α e . This means that the hypotheses of Lemma B.3 are all satis ed, implying in turn that

L n ( ˜ n ) = Opt(Γ n ) ∼ V ρ (λ) (M n ) as n → ∞, (B.25)
with the notation "f n ∼ n " meaning here that lim n→∞ f n / n = 1. In view of this, and since 0

< V ρ (λ) < ∞, it remains to show that L n ( * n ) ∼ V ρ (λ) (M n ).
To that end, we rst analyze the asymptotic behavior of the convex minimization problem

W (Γ n ) = min ∈Y e ∈E C e (x e ( , m n )) (B.26)
by applying Lemma B.3 to the primitives C e and C of c e and c respectively. By a standard result (Bingham et al., 1989, Theorem 1.5.11), C is ρ-regularly varying with ρ = 1 + β; moreover, by L'Hôpital's rule we also have lim

x →ω C e (x)/C(x) = lim x →ω c e (x)/c(x) = α e . By Lemma B.3, it follows that W (Γ n )/C(M n ) → V ρ (λ).
In addition, since the Wardrop equilibrium tra c allocations * n are solutions of W (Γ n ), the limit * of * n is optimal for V ρ (λ) by Lemma B.3.

Noting that x

e ( * n , m n ) = M n ζ e ( * n , λ n ), we obtain L n ( * n ) (M n ) = e ∈E e M n ζ e ( * n , λ n ) (M n ) . (B.27)
By Lemma B.2, we also have the following limit for every non-slow edge e ∈ E \ E slow :

e M n ζ e ( * n , λ n ) (M n ) → α e ζ e ( * , λ) ρ . (B.28)
To establish a similar limiting result when e is slow, we rst claim that there exists a constant B ≥ 0 such that

e M n ζ e ( * n , λ n ) ≤ B ζ e ( * n , λ n ) (M n ) (B.29)
This is trivially satis ed when ζ e ( * n , λ n ) = 0, so it su ces to consider the case ζ e ( * n , λ n ) > 0. The above inequality is then equivalent to asking that

c e M n ζ e ( * n , λ n ) ≤ B c(M n ) (B.30)
Now, ζ e ( * n , λ n ) > 0 implies that the edge e receives some equilibrium tra c from at least one O/D pair i ∈ I, so it must belong to a path p ∈ P i with minimal cost. Thus, if we consider an alternative path p ∈ P i all of whose edges are tight or fast, we have B.34) as was to be shown.

c e (M n ζ e ( * n , λ n )) ≤ e ∈p c e (M n ζ e ( * n , λ n )) ≤
L n ( * n )/ (M n ) → e ∈E α e ζ e ( * , λ) ρ = V ρ (λ), (

A C. S

In this appendix, we provide the proofs of the results presented in Section 7.

C.1. Rates in the light tra c regime. First we present the proof of Proposition 7.1 on the light tra c rates in the case of a Pigou network.

Proof of Proposition 7.1. Let x denote the ow on edge e 1 . At equilibrium, the costs on both edges must be equal so that (x * )

d 1 = (M -x * ) d 2 , which is equivalent to x * + (x * ) d 1 /d 2 = M.
Since M tends to 0 it follows that x * will be small and since d 1 < d 2 the term (x * ) d 1 /d 2 dominates the right hand side. Therefore

x * = M d 2 /d 1 (1 + o(1)) (C.
+ 1 k + 1 + k -q k + 1 c e,k • (x * e,n ) k +1 = (q + 1) e ∈E C e (x * e,n ) + e ∈E d e k =q e k -q k + 1 c e,k • (x * e,n ) k +1 ≤ (q + 1) e ∈E C e ( xe,n ) + e ∈E d e k =q+1 k -q k + 1 c e,k • (x * e,n ) k+1 (C.10)
where C e is the primitive of c e and for the last inequality we used the fact that x * e,n minimizes the rst sum, and in the double sum we dropped the negative terms with k ≤ q. Now, the rst sum in (C.10) can be further bounded as

(q + 1) e ∈E C e ( xe,n ) = e ∈E d e k =q e q + 1 k + 1 c e,k • ( xe,n ) k+1 = e ∈E d e k =q e c e,k • ( xe,n ) k +1 + e ∈E d e k=q e q -k k + 1 c e,k • ( xe,n ) k +1 ≤ Opt(Γ n ) + e ∈E slow q-1 k=q e q -k k + 1 c e,k • ( xe,n ) k +1
where we used the optimality of xn in the rst double sum, and we dropped the negative terms in the second. Note that in the latter only the slow edges with q e < q are relevant.

Combining these estimates we get

L n ( * n ) ≤ Opt(Γ n )+ e ∈E slow q-1 k =q e q -k k + 1 c e,k • ( xe,n ) k +1 + e ∈E d e k =q+1 k -q k + 1 c e,k • (x * e,n ) k +1 (C.11)
Let us call L I n the rst double sum in (C.11) and L II n the second. In order to bound L II n we assume that n is large enough so that M n ≤ 1. This assumption is done for convenience and it only a ects the value of the constants K 1 and K a : by rede ning them appropriately, the bound (C.9) will hold for all n. Then by setting C.12) and noting that x * e,n ≤ M n , we get

G = e ∈E d e k=q+1 k -q k + 1 c e,k , (
L II n ≤ e ∈E d e k =q+1 k -q k + 1 c e,k • M k +1 n ≤ GM q+2 n . (C.13)
In order to bound L I n we note that this term vanishes when E slow is empty. Otherwise, consider any edge e ∈ E slow that contributes to the sum with xe,n > 0. We note that the optimum ow ˜ n is an equilibrium for the marginal cost functions ce (x) = c e (x) + x c e (x) = The edge e must therefore belong to an optimal path p ∈ P i (w.r.t. the costs ce (x)) for some i ∈ I. Hence, taking any alternative path p ∈ P i which is not slow, i.e., with q e ≥ q for all e ∈ p , and denoting In particular, letting c0 = min e ∈E slow (q e + 1)c e,q e we have c0 • xe,n q e ≤ (q e + 1)c e,q e • xe,n q e ≤ ce ( xe,n ) ≤ BM q n . (C.17)

B = e E slow
Now, for n large we have BM q n / c0 ≤ 1 and since q e ≤ q slow we obtain xe,n ≤ BM q n / c0 1/q slow .

Combining this latter bound with (C.16), and denoting D = B (B/ c0 ) 1/q slow |E slow |, we deduce for all e ∈ p. For n large we may assume that M n κε ≤ 1 and, since the path p contains at least one edge e ∈ p with q e ≤ q, setting H = H (κε) q+1 we get Opt(Γ n ) ≥ H (M n κε) q e +1 ≥ H M q+1 n .

L I n = e ∈E slow q-1 k =q e q -k k + 1 c e,k • ( xe,n ) k +1 ≤ e ∈E slow q-1 k =q e (k + 1)c e,k
(C.21)

This lower bound, combined with (C.19), yields (C.9) with K 1 = G/ H and K a = D/ H . We conclude by noting that when E slow = we have L I n = 0 and therefore we may take K a = 0. C.2. Rates in the heavy tra c regime. We proceed with the proof of Proposition 7.3 on the heavy tra c rates in the case of a Pigou network.

Proof of Proposition 7.3. Let x denote the ow on edge e 2 . At equilibrium, the costs on both edges must be equal so

d 2 +1 = M d 1 +1 -(d 1 + 1)M d 1 (θM) d 1 /d 2 + (θM) d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ) = M d 1 +1 -θ d 1 /d 2 [(d 1 + 1) -θ d 1 ]M d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ), (C.27) = M d 1 +1 -(b + d 1 )M d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ), (C.28)
where b is de ned as in (7.11).

Combining the previous expressions, we then get C.30) which establishes the rst part of Proposition 7.3. Finally, the positivity of b > 0, follows again from the fact that (1 -/x) x increased with x when > 0.

PoA(Γ M ) = Opt(Γ M ) + bM d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ) Opt(Γ M ) (C.29) = 1 + bM d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ) M d 1 +1 + o(M d 1 +1 ) = 1 + bM -a + o(M -a ), (
The following more general result subsumes Theorem 7.4.

Theorem C.2. Let Γ n be a sequence of nonatomic routing games satisfying the assumptions of Theorem 6.2, with M n → ∞. Suppose further that the edge costs are polynomials as in (7.1), and let a = 1 -d/d slow with d and d slow given by (7.12d) and (7.14). Then there exist non-negative constants K 1 ≥ 0 and K a ≥ 0 such that

PoA(Γ n ) ≤ 1 + K 1 M n + K a M a n (C.31)
with K a = 0 whenever E slow = .

Proof where in the last inequality we used the fact that x * e,n minimizes the rst sum, while in the double sum we dropped the edges e E slow since (k -d)/(k + 1) ≤ 0 for all k ≤ d e ≤ d, and we used the inequality (k -d)/(k + 1) ≤ 1 to bound the remaining terms e ∈ E slow by factoring out x * e,n and using the expression (7.1) for c e (x). Now, the rst sum in (C.32) can be further bounded as In order to bound L II n we note that this term vanishes whenever E slow is empty. Otherwise, consider any edge e ∈ E slow that contributes to the sum with x * e,n > 0. Since * n is an equilibrium, the edge e must belong to a path p ∈ P i with minimal cost for some i ∈ I. Hence, taking any alternative path p ∈ P i which is not slow, and denoting This lower bound, combined with (C.40), yields (C.31) with K 1 = G/ H and K a = D/ H . We conclude by noting that when E slow = we have L II n = 0 and therefore we may take K a = 0.

(d + 1)
B = e E slow

Figure 1 .

 1 Figure1. A network where sel sh routing remains ine cient for both light and heavy tra c.

  and e ciency in Sioux Falls.

Figure 2 .

 2 Figure 2. The price of anarchy in the Sioux Falls metropolitan area as a function of the tra c in ow.

  (a) and their delay functions are taken to be of the BPR (Bureau of Public Roads) type c e (x) = a e + b e x d e (3.1) with coe cients a e , b e and degrees d e (typically d e = 4) taken from the standard reference work of LeBlanc et al. (1975, Table

  Corollary 4.4. In a single O/D-network with analytic costs we have PoA

  Corollary 4.5. In a single O/D-network with polynomial costs we have PoA(Γ M ) → 1 as M → 0.

Figure 3 .

 3 Figure 3. A Wheatstone network with two O/D pairs (cf. Example 5.1 below).In heavy tra c, the network is tight relative to the benchmark function c(x) = x; in light tra c, the network is tight relative to the benchmark c(x) = 1.

  e, e ∈ E, then PoA(Γ M ) → 1 as M → ω.

Figure 4 .

 4 Figure 4. A simple network with two uncoupled O/D pairs. Heuristically, Condition (a) above simply indicates the tra c regime under study (light or heavy), whereas Condition (b) guarantees that the network's benchmark function correctly classi es the paths that are not too costly in each O/D pair. Finally, Condition (c) guarantees that tight O/D pairs are indeed relevant in terms of tra c, i.e., they account for a non-negligible fraction of the total in ow.In view of all this, Theorem 6.2 can be seen as a direct extension of our " xed-rate" analysis in Sections 4 and 5: indeed, in the case of constant (positive) relative in ows, salience boils down to asking that the network admits at least one tight O/D pair, so Theorem 5.1 can be obtained as a special case of Theorem 6.2. Below, we provide some further corollaries of Theorem 6.2 along these lines:

Corollary 6. 3 .

 3 If every O/D pair in the network is tight, then PoA(Γ n ) → 1. Corollary 6.4. If the network is tight and every O/D pair is salient, then PoA(Γ n ) → 1.

Figure 5 .

 5 Figure 5. A two-link Pigou network with monomial costs.

  Proposition 7.3. Consider a two-link parallel network with cost functions c 1 (x) = x d 1 and c 2 (x) = x d 2 , 0 < d 1 < d 2 , and a single O/D pair with in ow M. Then PoA(Γ M ) = 1 + bM -a + o(M -a )

  Lemma A.1, if M is small enough, for every i ∈ I, only paths in P i min are used at the optimum. If p, p ∈ P i min , then, for M small enough, we have 1)b e xd e = e ∈p = (d + 1)b e xd e . (A.5)

  ., the Wardrop equilibria of the network in Fig.1remain strictly ine cient under both light and heavy tra c. and we denote respectively the normalized and total load on edge e ∈ E asζ e ( , λ) = i ∈I λ i z i e () and x e ( , m) = M ζ e ( , λ) on the index framework of Sections 4 and 5, we will respectively denote the set of the network's fast, tight and slow edges asE fast = {e ∈ E : α e = 0}, (B.8a) E tight = {e ∈ E : 0 < α e < ∞}, (B.8b) E slow = {e ∈ E : α e = ∞}, (B.8c)and, in obvious notation, we will write e.g., P slow for the set of the network's slow paths, I tight for the set of tight O/D pairs, etc.

  where V ρ (λ) ∈ (0, ∞) is the solution value of the problemV ρ (λ) = min ∈Y e ∈E α e ζ e ( , λ) ρ (B.11)

  i e ( ) = 0 and, a fortiori, ζ e ( , λ) = 0; hence V ρ (λ) ≤ e:α e <∞ α e ζ e ( , λ) ρ < ∞.(B.12)

  M n ζ e ( ˆ , λ n )). (B.14) Using Lemma B.2, for every non-slow edge e ∈ E \ E slow (i.e., α e < ∞), we get lim n→∞ e(M n ζ e ( ˆ , λ n )) (M n ) = α e ζ e ( ˆ , λ) ρ . (B.15) Otherwise, if e ∈ E slow is slow (i.e., α e = ∞), we have ζ e ( ˆ , λ n ) = 0; thus, since e (0) α e ζ e ( ˆ , λ) ρ . n ζ e ( ˆ , λ n )) (M n ) = e ∈Eα e ζ e ( ˆ , λ) ρ = V ρ (λ).

  e ∈p c e (M n ζ e ( * n , λ n )). (B.31) Using the trivial bound M n ζ e ( * n , λ n ) ≤ M n , we further get c e (M n ζ e ( * n , λ n )) ≤ e ∈p c e (M n ) ≤ e :α e <∞ c e (M n ). (B.32) However, for every non-slow edge e ∈ E \ E slow , the sequence c e (M n )/c(M n ) converges to α e so we can nd a constant B e such that c e (M n )/c(M n ) ≤ B e for all n ∈ ; consequently, (B.30) follows by taking B = e :α e <∞ B e . Thus, given that * is optimal for V ρ (λ), we get ζ e ( * n , λ n ) → ζ e ( * , λ) = 0, and hence e (M n ζ e ( * n , λ n )) (M n ) ≤ B ζ e ( * n , λ n ) → 0 = α e ζ e ( * , λ) ρ . (B.33) Combining (B.28), (B.33) and (B.27), we then get

  1)c e,k x k . (C.14)

  bound (recall that M n ≤ 1) ce ( xe,n ) ≤ e ∈p ce ( xe,n ) ≤ e ∈p ce ( xe,n ) ≤ e ∈p ce (M n ) ≤ BM q n .(C.16)

  Opt(Γ n ) = e ∈E xe,n • c e ( xe,n ) ≥ H e ∈E ( xe,n ) q e +1 .(C.20)We claim that the latter is of order at least O(M q+1 n ). Indeed, let us take ε > 0 with i ∈I tight λ i n ≥ ε for su ciently large n. For each n ∈ we may nd i ∈ I tight such that λ i n ≥ ε/|I tight | and, similarly, there exists a path p ∈ P i with ˜ p,n ≥ 1/|P i | ≥ 1/|P |. Then, setting κ = 1/(|I tight | × |P |) we have ζ e ( ˜ n , λ n ) ≥ κε and therefore xe,n ≥ M n κε

  (x * ) d 2 = (M -x * ) d 1 , which is equivalent to x * + (x * ) d 2 /d 1 = M. It thus follows that x * = M d 1 /d 2 (1 + o(1)), (C.22)implying in turn that the equilibrium cost Eq(ΓM ) = M • c 2 (x * ) = M • c 1 (M -x * ) scales as Eq(Γ M ) = M • M -M d 1 /d 2 (1 + o(1)) d 1 = M 1+d 1 -d 1 M d 1 +d 1 /d 2 + o(M d 1 +d 1 /d 2 ). (C.23)Similarly, if x is the optimal ow on edge e 2 , both edges have the same marginal cost, namely(1 + d 2 ) xd 2 = (1 + d 1 )(Mx) d 1 , optimal social cost scales as Opt(Γ M ) = (Mx) • c 1 (Mx) + x • c 2 ( x) = M -(θM) d 1 /d 2 (1 + o(1)) d 1 +1 + (θM) d 1 /d 2 (1 + o(1))

.

  The proof follows a similar pattern as the one of Theorem C.1. Let again * n , ˜ n ∈ Y be an equilibrium and an optimum for Γ n , respectively. Denote x * e,n = M n ζ e ( * n , λ n ) and xe,n = M n ζ e ( ˜ n , λ n ) the corresponding induced edge ows. As before, the social cost of * n can be estimated asL n ( * n ) = e ∈Ex * e,n c e (x * e,n ) =

  k • ( xe,n ) k+1 ,where in the inequality we used the optimality of xn for the rst sum and we dropped the negative terms in the second sum. Putting all this together we obtain the boundL n ( * n ) ≤ Opt(Γ n ) + L In the rst double sum and L II n the last sum in (C.33). In order to bound L I n we assume that n is large enough so that M n ≥ 1. Then, denotingG = e ∈E d -1 k =q e dk k + 1 c e,k(C.34) and using the fact that xe,n ≤ M n , we can bound L I n as

  e (M n ) ≤ BM d n . (C.37) In particular, letting c 0 = min e ∈E slow c e,d e we have c 0 • x * e,n d e ≤ c e,d e • x * e,n d e ≤ c e (x * e,n ) ≤ BM d n . (C.38) Now, for n large we have BM d n /c 0 ≥ 1 and since d e ≥ d slow we get x * e,n ≤ BM d n /c 0 1/d slow . Combining this latter bound with (C.37), and denoting D = B (B/c 0 ) 1/d slow |E slow |, we deduce 35) and (C.39) into (C.33) we get PoA(Γ n ) = L n ( * n ) Opt(Γ n ) ≤ Opt(Γ n ) + GM d n + DM d +d /d slow n Opt(Γ n ) . (C.40)Now, if we set H = min e ∈E c e,d e , we have the following lower bound for the optimal costOpt(Γ n ) = e ∈E xe,n • c e ( xe,n ) ≥ H e ∈E ( xe,n ) d e +1 .(C.41)We claim that the latter is of order at least O(M d +1 n ). Indeed, let us take ε > 0 with i ∈I tight λ i n ≥ ε for su ciently large n. For each n ∈ we may nd i ∈ I tight such thatλ i n ≥ ε/|I tight |and, similarly, there exists a path p ∈ P i with ˜ p,n ≥ 1/|P i | ≥ 1/|P |. Then, setting κ = 1/(|I tight | × |P |) we have ζ e ( ˜ n , λ n ) ≥ κε and therefore xe,n ≥ M n κε for all e ∈ p. For n large we may assume that M n κε ≥ 1 and, since the path p contains at least one edge e ∈ p with d e ≥ d, setting H = H (κε) d +1 we get Opt(Γ n ) ≥ H (M n κε) d e +1 ≥ H M d +1 n . (C.42)

  Wardrop equilibrium (WE) of Γ if, for all i ∈ I, we have c p (f * ) ≤ c p (f * ) for all p, p ∈ P i such that f *

			p > 0.	(2.4)
	From the work of Beckmann et al. (1956), it is known that Wardrop equilibria coincide
	with the solutions of the (convex) minimization problem
	minimize	C e (x e ),
	e ∈E subject to x e =	f p , f ∈ F,	(WE)
		p e
	where C e (x e ) = (SO) ows are de ned as solutions of the total cost minimization problem ∫ x e 0 c e (w) dw denotes the primitive of c e . Analogously, socially optimum
	minimize
		p ∈P

  +1) sin(log Mz 3 ) .

		(A.7)
	We now show that Eqs. (A.6) and (A.7) never admit a common solution. Indeed, this can
	occur if and only if
	cos(log Mz 1 ) = 0 = sin(log Mz 3 ),	(A.8)
	i.e., if and only if there exist integers k 1

  Proof. Let * n , ˜ n ∈ Y be an equilibrium and an optimum ow for Γ n with induced edge ows x * e,n = M n ζ e ( * n , λ n ) and xe,n = M n ζ e ( ˜ n , λ n ). The social cost of *

				n can be esti-
	mated as
				d e
	L n ( * n ) =	x * e,n c e (x * e,n ) =	c e,k • (x * e,n ) k +1
	e ∈E		e ∈E	k=q e
	=	d e	q
	e ∈E	k =q e

1)

  Now, if we set H = min e ∈E c e,q e , we have the following lower bound for the optimal cost

				xe,n ce ( xe,n )
		e ∈E slow
		≤			BM	q n / c0	1/q slow BM	q n
		e ∈E slow
		≤ DM	q+q/q slow n	.	(C.18)
	Plugging (C.18) and (C.13) into (C.11) we get
	PoA(Γ n ) =	L n ( * n ) Opt(Γ n )	≤	Opt(Γ n ) + GM Opt(Γ n ) q+2 n + DM	q+q/q slow n	.	(C.19)

• ( xe,n ) k +1 ≤

This distinction is particularly relevant for packet-switched networks (such as the Internet) where only paths with a low hop count are typically employed.

Recall here that a function (x ) is analytic on a domain U if it is equal to its Taylor series on U .

This follows the standard -if somewhat surprising at rst -convention that sup = -∞, inf = ∞.

A B. C

We now prove Theorem 6.2; Theorems 4.2, 4.6 and 5.1 will then follow as special cases of this more general result. To that end, we begin with two auxiliary lemmas concerning the asymptotic behavior of regularly varying functions: Lemma B.1 [START_REF] Karamata | Sur un mode de croissance régulière. Théorèmes fondamentaux[END_REF]. If is regularly varying at ω, there exists some ρ ∈ such that lim t →ω (tx) (t) = x ρ for all x > 0. (B.1) Lemma B.1 is a classical result in the theory of regularly varying functions and gives rise to the term "ρ-regularly varying" for functions satisfying (B.1); for a proof, see, e.g., [START_REF] Bingham | Regular Variation[END_REF].

The second lemma is a more technical asymptotic comparison result allowing us to replace a ρ-regularly varying function by a monomial of degree ρ in the limit: Lemma B.2. Let ω ∈ {0, ∞} and consider two functions f , : (0, ∞) → (0, ∞) such that:

(1) f is nondecreasing.

(2) is ρ-regularly varying at ω for some ρ > 0.

(3) lim

Proof. We rst consider the case ω = ∞. If z > 0, the sequence x n = M n z n diverges to in nity, so our claim follows from Theorem 1.5.2 in [START_REF] Bingham | Regular Variation[END_REF] by writing

If z = 0, then, for all ε > 0, we have z n ≤ ε if n is su ciently large. Then, using the monotonicity of f and the previous argument, we get

The case ω = 0 is even simpler. Indeed, we now have that x n = M n z n tends to 0, so that the result follows using (B.3) and invoking Theorem 1.5.2 in [START_REF] Bingham | Regular Variation[END_REF]. Now, to proceed with the proof of Theorem 6.2, we will require some additional notation. First, x some in ow vector m = (m i ) i ∈I with total in ow M = i ∈I m i and relative in ows λ = (λ i ) i ∈I . Instead of working directly with the ow variables f ∈ F, it will be more convenient to introduce the normalized tra c allocation variables i = ( i p ) p ∈P i de ned as i p = f p /m i for all p ∈ P i , i ∈ I.

(B.5)

We clearly have p ∈P i i p = 1 for all i ∈ I; we will also write Y i = ∆(P i ) for the simplex of tra c allocations of i ∈ I and Y = × i ∈I Y i for the product thereof. Moreover, descending to the edge level, we de ne the normalized load induced by the i-th O/D pair on e ∈ E as

Similarly, if x is the optimal ow on edge e 1 , both edges have the same marginal cost

Therefore, if we let

we get ρ x + xd 1 /d 2 = ρM as before, and hence

It follows that the optimal cost scales as

where the last equality follows from the identity

Combining the previous expressions we get

(C.7)

To complete our proof, it remains to show that b > 0. After a small rearrangement, this is equivalent to establishing the inequality

which itself follows from the fact that the function (1 + /x) x is increasing in x whenever is positive. Now we prove the following more general version of Theorem 7.2.

Theorem C.1. Let Γ n be a sequence of nonatomic routing games satisfying the assumptions of Theorem 6.2, with M n → 0. Suppose further that the edge costs are polynomials as in (7.1), and let a = q/q slow -1 with q and q slow given by (7.5d) and (7.7) respectively. Then, there exist non-negative constants K 1 ≥ 0 and K a ≥ 0 such that

with K a = 0 whenever E slow = .