1 Introduction

Nonatomic routing games provide a model for the distribution of traffic over networks with a large number of drivers, each one representing a negligible fraction of the total demand. The model is based on a directed graph with one or more (OD) pairs, and the costs are identified with the delays incurred to go from origin to destination. The delay on an edge is a nondecreasing function of the load of players on that edge, and the delay of a path is additive over its edges. The standard solution concept for such nonatomic games is the Wardrop equilibrium, according to which the traffic in each OD pair travels along paths of minimum delay. The aggregate social cost experienced by the whole traffic is therefore the product of these minimal delays multiplied by the corresponding traffic demands, summed over all OD pairs.

Equilibria are known to be inefficient, so that a social planner would be able to reduce the social cost by redirecting flows along the network. The most common measure of inefficiency is the  price of anarchy (PoA), that is, the ratio of the social cost at equilibrium over the minimum social cost. For nonatomic congestion games with affine costs, the value of the PoA is bounded above by 4/3, and this bound is known to be sharp [32]. On the other hand, for a large class of cost functions, including all polynomials, the PoA converges to 1 as the traffic demand goes either to 0 or to infinity. In other words, equilibria tend to perfect efficiency both in light and heavy traffic [3, 39].

Fig. 1
figure 1

Oscillations of the price of anarchy

Full size image

Empirical studies have shown that in real networks, and for intermediate levels of the demand, the PoA tends to oscillate and often does not reach the worst case bounds. Figure 1 shows a typical profile of the PoA as a function of the traffic demand. It starts at 1 for low levels of traffic, then it exhibits some oscillations with a number of nonsmooth spikes, and eventually it decreases smoothly back to 1 in the highly congested regime. The shape and number of these oscillations and spikes is the object of this paper.

1.1 Our contribution

We consider nonatomic routing games over a network with a single OD, and we study the behavior of the price of anarchy as a function of the traffic demand.

To achieve our goal, we need some general results on the continuity and monotonicity of the equilibrium costs and flows. We resort to the classical result in [2] according to which a Wardrop equilibrium is a solution of a convex optimization program. We show that the optimal value of this program is convex and continuously differentiable as a function of the demand, and its derivative is precisely the equilibrium cost. A similar result is established for the minimum social cost.

When the costs have a strictly positive derivative, we show that the equilibrium loads and the PoA are in fact \(C^1\) at each demand level that is regular, in the sense that all the optimal paths carry a strictly positive flow. This regularity fails in particular at the so-called \(\widehat{\mathcal {E}}\)-break points, which are demand levels at which the set of shortest paths at equilibrium changes.

For affine costs we bypass regularity and we show directly that the equilibrium cost is piecewise linear and differentiable except at \(\widehat{\mathcal {E}}\)-break points. The crucial property is that if the set of shortest paths is the same at two demand levels, then this set remains optimal in between. From here it follows that the number of \(\widehat{\mathcal {E}}\)-break points is finite, though it can be exponentially large. It also follows that between \(\widehat{\mathcal {E}}\)-break points the PoA is differentiable and either is monotone, or is first decreasing and then increasing, so it has a unique minimum in the interior of the interval. From this we conclude that the maximum of the PoA is attained at an \(\widehat{\mathcal {E}}\)-break point.

We finally present several examples showing how these properties might fail for general costs.

1.2 Related work

The standard solution concept in nonatomic routing games is due to Wardrop [37]. Its mathematical properties were first studied in [2]; early algorithms for computing equilibria were proposed in [36] for affine costs, and in [12] for general convex costs. For historical surveys on the topic we refer to [10, 16].

Several papers have considered the sensitivity of the equilibrium flows and costs with respect to variations of the traffic demand. Hall [19] showed that an increase in the demand of one OD pair always increases the equilibrium cost for that pair, whereas [15] observed that the cost on a different OD could be reduced. These questions were further explored in [11]. In a different direction, Patriksson [28] characterized the existence of directional derivatives for the equilibrium and [20] proved that equilibrium costs are always directionally differentiable, whereas equilibrium edge loads not always are. Takalloo and Kwon [14] showed that there exist single OD network games where an \(\varepsilon \)-increase in the traffic demand produces a global migration of traffic from one set of equilibrium paths to a disjoint set of paths, but, nevertheless, the load on each edge changes at most by \(\varepsilon \). Moreover, if the cost functions are polynomials of degree at most d, then the equilibrium costs increase at most of a multiplicative factor \((1+\varepsilon )^{d}\). [35] extended this last result to games with multiple OD pairs.

The recognition that selfish behavior produces social inefficiency goes back at least to Pigou [29]. A measure to quantify this inefficiency was proposed in [23], by considering the ratio of the social cost of the worst equilibrium over the optimum social cost. It was termed price of anarchy in [27]. A PoA close to one indicates efficiency of the equilibria of the game, whereas a high PoA implies that, in the worst scenario, strategic behavior can lead to significant social inefficiency. Most of the subsequent literature established sharp bounds for the PoA for specific classes of games, notably for congestion games and in particular for routing games. Roughgarden and Tardos [32] showed that in every nonatomic congestion game with affine costs the PoA is bounded above by 4/3. Moreover, this bound is sharp and attained in a traffic game with a simple two-edge parallel network. Roughgarden [31] generalized this result to polynomial functions of maximum degree d showing that the PoA grows as \(\varTheta (d/\log d)\). Dumrauf and Gairing [13] refined the result when the cost functions are sums of monomials whose degrees are between q and d. Roughgarden and Tardos [33] extended the analysis to all differentiable cost function c such that xc(x) is convex. Less regular costs and different optimizing criteria for the social cost were studied in [7,8,9].

Some papers took a more applied view and studied the actual value of the PoA in real networks. Youn et al. [40, 41] dealt with traffic in Boston, London, and New York, and noted that the PoA exhibits a similar pattern in the three cities: it is 1 when traffic is light, it oscillates in the central region and then goes back to 1 when traffic increases. A similar behavior was observed by O’Hare et al. [26], who—taking an approach that relates to the one in this paper—showed how an expansion and/or retraction of the routes used at equilibrium affects the behavior of the PoA. Experimentally, [25] studied the commuting behavior of a large number of Singaporean students and concluded that the PoA is overall low and far from the worst case scenarios.

An analytical justification for the asymptotic efficiency of the PoA in light and heavy traffic was presented in [3, 4, 39]. Colini-Baldeschi et al. [4] considered the case of single OD parallel networks and proved that, in heavy traffic, the PoA converges to one when the cost functions are regularly varying. These results were extended in various directions in [3], considering general networks and analyzing both the light and heavy traffic asymptotics. A different technique, called scalability, was used in [39] to study the case of heavy traffic.

Wu and Möhring [38] considered issues that are quite close to the ones examined here. They defined a metric on the space of nonatomic congestion games that share the same network, commodities, and strategies, but differ in terms of demands and cost functions. Using this metric they showed that the PoA is a continuous function of both the demand and the costs. Then they performed a sensitivity analysis of the PoA with respect to variations of the game in terms of this metric.

In a very interesting recent paper Klimm and Warode [22, 21, see also the conference version] considered nonatomic routing games with piecewise linear costs and provided algorithms to track the full path of Wardrop equilibria when the demands vary proportionally along a fixed direction. These algorithms are based on (positive or negative) electrical flows on undirected graphs and are then suitably adapted to positive flows on directed graphs. The connection between their paper and ours will be discussed in Sect. 4.

The behavior of the PoA as a function of a different parameter was studied in [6]. In that case the parameter of interest is the probability that players actually take part in the game. Colini-Baldeschi et al. [5] studied the possibility of achieving efficiency in routing games via the use of tolls, when the demand can vary, whereas [18] analyzed the income inequality effects of reducing the PoA via tolls.

1.3 Organization of the paper

In Sect. 2 we recall the model of nonatomic routing games, and we set the notations and the standing assumptions. Section 3 investigates the smoothness of the equilibrium costs and of the PoA as a function of the demand, for general nondecreasing smooth costs. The behavior of the PoA for affine costs is studied in Sect. 4. Section 5 presents various examples.

2 The nonatomic congestion model

We consider a nonatomic routing game with a single origin-destination pair. The network is described by a directed multigraph \(\mathcal {G}=(\mathcal {V},\mathcal {E})\) with vertex set \(\mathcal {V}\), edge set \(\mathcal {E}\), an origin \(\mathsf {O}\in \mathcal {V}\), and a destination \(\mathsf {D}\in \mathcal {V}\). The traffic demand is given by a positive real number \(\mu > 0\), interpreted as vehicles per hour, which has to be routed along a set \(\mathcal {P}\) of simple paths from \(\mathsf {O}\) to \(\mathsf {D}\). The nonatomic hypothesis means that each vehicle controls a negligible fraction of the total traffic, and consequently the traffic flows are treated as continuous variables.

The traffic flow on path p is denoted by \(f_{p}\) and the set of feasible flow profiles is

$$\begin{aligned} \mathcal {F}_{\mu }=\left\{ \varvec{f}=(f_{p})_{p\in \mathcal {P}} :f_{p}\ge 0 \text { and }\sum _{p\in \mathcal {P}} f_{p}=\mu \right\} . \end{aligned}$$
(2.1)

Each flow profile \(\varvec{f}\in \mathcal {F}_{\mu }\) induces a load profile \(\varvec{x}=(x_{e})_{e\in \mathcal {E}}\) with \(x_{e}=\sum _{p\ni e} f_{p}\) representing the aggregate traffic over the edge e. We call \(\mathcal {X}_{\mu }\) the set of all such load profiles. Note that different flow profiles may induce the same edge loads so this correspondence is not bijective.

Every edge \(e\in \mathcal {E}\) has a continuous nondecreasing cost function \(c_{e} :[0,+\infty )\rightarrow [0,+\infty )\), where \(c_{e}(x_{e})\) represents the travel time (or unit cost) of traversing the edge when the load is \(x_{e}\). When the traffic is distributed according to \(\varvec{f}=(f_{p})_{p\in \mathcal {P}}\) with induced load profile \(\varvec{x}=(x_{e})_{e\in \mathcal {E}}\), the cost experienced by traveling on a path \(p\in \mathcal {P}\) is given by

$$\begin{aligned} c_{p}\left( \varvec{f}\right) :=\sum _{e\in p} c_{e}\left( {\sum _{p'\ni e}f_{p'}}\right) =\sum _{e\in p} c_{e}(x_{e}). \end{aligned}$$
(2.2)

With a slight abuse of notation, we use the same symbol c for the cost function over paths and over edges. The meaning should be clear from the context.

2.1 Wardrop equilibrium

A feasible flow profile is called a Wardrop equilibrium if the paths that are actually used have minimum cost. Formally, \(\varvec{f}^{*}\in \mathcal {F}_{\mu }\) is an equilibrium iff there exists \(\lambda \in \mathbb {R}\) such that

$$\begin{aligned} {\left\{ \begin{array}{ll} c_{p}(\varvec{f}^{*})=\lambda &{} \text {for each }p\in \mathcal {P}\text { such that }f^{*}_{p}>0,\\ c_{p}(\varvec{f}^{*})\ge \lambda &{} \text {for each }p\in \mathcal {P}\text { such that }f^{*}_{p}=0. \end{array}\right. } \end{aligned}$$
(2.3)

The quantity \(\lambda \) is called the equilibrium cost, and is a function of \(\mu \).

As noted in [2], Wardrop equilibria coincide with the optimal solutions of the convex minimization problem

$$\begin{aligned} V(\mu ):=\min _{\varvec{f}\in \mathcal {F}_{\mu }} \sum _{e\in \mathcal {E}} C_{e}\left( {\sum _{p'\ni e}f_{p'}}\right) =\min _{x\in \mathcal {X}_{\mu }}\sum _{e\in \mathcal {E}}C_{e}(x_{e}), \end{aligned}$$
(2.4)

where \(C_{e}(\,\cdot \,)\) is the primitive of the edge cost \(c_{e}(\,\cdot \,)\), that is,

$$\begin{aligned} C_{e}(x_{e})=\int _{0}^{x_{e}} c_{e}(z)\ d z. \end{aligned}$$
(2.5)

This follows by noting that (2.3) are the optimality conditions for \(V(\mu )\), with the equilibrium cost \(\lambda \) playing the role of a Lagrange multiplier for the constraint \(\sum _{p} f_{p}=\mu \). It follows that, for each fixed demand \(\mu \) an equilibrium flow \(\varvec{f}^{*}\) always exists.

Although Wardrop equilibria are not always unique, all of them induce the same edge costs \(\tau _{e}(\mu ):=c_{e}(x^{*}_{e})\). In particular they have the same equilibrium cost \(\lambda =\lambda (\mu )\), which is simply the shortest \(\mathsf {O}\)-\(\mathsf {D}\) distance:

$$\begin{aligned} \lambda (\mu )=\min _{p\in \mathcal {P}}\sum _{e\in p}\tau _{e}(\mu ). \end{aligned}$$
(2.6)

As a matter of fact, as proved in [17], the equilibrium edge costs \(\tau _{e}=\tau _{e}(\mu )\) are the unique optimal solution of the strictly convex dual program

$$\begin{aligned} \min _{\tau }\sum _{e\in \mathcal {E}}C_e^*(\tau _{e}) - \mu \,\min _{p\in \mathcal {P}}\sum _{e\in p}\tau _{e} \end{aligned}$$
(2.7)

where \(C_e^*(\,\cdot \,)\) is the Fenchel conjugate of \(C_e(\,\cdot \,)\), which is strictly convex.

2.2 Social optimum and efficiency of equilibria

The total cost experienced by all users traveling across the network is called the social cost and is denoted by

$$\begin{aligned} {{\,\mathrm{\mathsf{SC}}\,}}(\varvec{f}):=\sum _{p\in \mathcal {P}}f_{p}\, c_{p}(\varvec{f})=\sum _{e\in \mathcal {E}}x_{e}\, c_{e}(x_{e}). \end{aligned}$$
(2.8)

Since in equilibrium all the paths that carry flow have the same cost \(\lambda (\mu )\), it follows that all equilibria have the same social cost, that is,

$$\begin{aligned} {{\,\mathrm{\mathsf{SC}}\,}}(\varvec{f}^{*})=\sum _{p\in \mathcal {P}}f^{*}_{p}\,c_{p}(\varvec{f}^{*}) =\sum _{p\in \mathcal {P}}f^{*}_{p}\,\lambda (\mu ) = \mu \,\lambda (\mu ). \end{aligned}$$
(2.9)

A feasible flow \(\widetilde{\varvec{f}}\in \mathcal {F}_{\mu }\) is called an optimum flow if it minimizes the social cost, that is, \(\widetilde{\varvec{f}}\) is an optimal solution of

$$\begin{aligned} \widetilde{V}(\mu ):=\min _{\varvec{f}\in \mathcal {F}_{\mu }} {{\,\mathrm{\mathsf{SC}}\,}}(\varvec{f}) =\min _{\varvec{f}\in \mathcal {F}_{\mu }} \sum _{e\in \mathcal {E}}\widetilde{C}_{e}\left( {\sum _{p'\ni e}f_{p'}}\right) , \end{aligned}$$
(2.10)

where \(\widetilde{C}_{e}(x_{e})=x_{e}\, c_{e}(x_{e})\). The price of anarchy (PoA) is then defined as the ratio between the social cost at equilibrium \( \mu \,\lambda (\mu )\) and the minimum social cost \(\widetilde{V}(\mu )\):

$$\begin{aligned} {{\,\mathrm{\mathsf {PoA}}\,}}(\mu )= \frac{ \mu \,\lambda (\mu )}{\widetilde{V}(\mu )}. \end{aligned}$$
(2.11)

Our main goal is to investigate the smoothness of the function \(\mu \mapsto {{\,\mathrm{\mathsf {PoA}}\,}}(\mu )\) and to understand the kinks and monotonicity properties observed in the example of Fig. 1b. To this end, Sect. 3 presents some preliminary results on the differentiability of equilibria as a function of the demand \(\mu \). More precise results will be discussed in Sect. 4 for the case with affine costs.

3 Differentiability of equilibria and price of anarchy

In order to study the smoothness of the PoA, we begin by establishing some preliminary facts on the differentiability of the optimal value function \(\mu \mapsto V(\mu )\) and the smoothness of the equilibrium loads \(\mu \mapsto x^{*}_{e}(\mu )\). These results follow from general convex duality and sensitivity analysis of parametric optimization problems. The following property does not seem to have been stated earlier in the literature, at least in this generality.

Proposition 3.1

The map \(\mu \mapsto V(\mu )\) is convex and \(C^1\) on \((0,\infty )\) with \(V'(\mu )=\lambda (\mu )\) continuous and nondecreasing. Moreover, the equilibrium costs \(\tau _{e}(\mu )\) are uniquely defined and continuous.

Proof

This is a consequence of the convex duality theorem. Indeed, consider the perturbation function \(\varphi _{\mu }: \mathbb {R}^{|\mathcal {P}|}\times \mathbb {R}\rightarrow \mathbb {R}\cup \{+\infty \}\), given by

$$\begin{aligned} \varphi _{\mu }(\varvec{f},z) = {\left\{ \begin{array}{ll} \sum _{e\in \mathcal {E}}C_{e}{{(}{\sum _{p'\ni e}f_{p'}}{)}} &{} \text {if } \varvec{f}\ge \varvec{0},\ \sum _{p}f_{p}=\mu +z\\ +\infty &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$
(3.1)

Clearly \(\varphi _{\mu }\) is a proper closed convex function [30, page 24]. Calling

$$\begin{aligned} v_{\mu }(z)=\inf _{\varvec{f}}\varphi _{\mu }(\varvec{f},z), \end{aligned}$$
(3.2)

we have \(V(\mu +z)=v_{\mu }(z)\) and in particular \(V(\mu )=v_{\mu }(0)\) which we consider as the primal problem \((\mathsf {P}_{\mu })\). From general convex duality, we have that \(z\mapsto v_{\mu }(z)=V(\mu +z)\) is a convex function, from which we deduce that \(V(\,\cdot \,)\) is convex. Moreover, the perturbation function \(\varphi _{\mu }\) yields a corresponding dual

$$\begin{aligned} (\mathsf {D}_{\mu })\quad \min _{\lambda \in \mathbb {R}}\varphi _{\mu }^{*}(\varvec{0},\lambda ), \end{aligned}$$
(3.3)

where \(\varphi _{\mu }^{*}\) is the Fenchel conjugate function, that is,

$$\begin{aligned} \varphi _{\mu }^{*}(\varvec{0},\lambda )&=\sup _{\varvec{f},z}~\langle \varvec{0},\varvec{f}\rangle +\lambda z-\varphi _{\mu }(\varvec{f},z)\\&=\sup _{\varvec{f}\ge \varvec{0}}\lambda \left( {\sum _{p} f_{p}-\mu }\right) -\sum _{e\in \mathcal {E}}C_{e}\left( {\sum _{p'\ni e}f_{p'}}\right) . \end{aligned}$$

Since \(V(\mu ')\) is finite for all \(\mu '\in (0,\infty )\), it follows that \(v_{\mu }(z)=V(\mu +z)\) is finite for z in some interval around 0, and then the convex duality theorem implies that there is no duality gap and the subdifferential \(\partial v_{\mu }(0)\) at \(z=0\) coincides with the optimal solution set \(\mathsf {S}(\mathsf {D}_{\mu })\) of the dual problem, that is, \(\partial V(\mu )=\partial v_{\mu }(0)=\mathsf {S}(\mathsf {D}_{\mu })\).

We claim that the dual problem has a unique solution, which is exactly the equilibrium cost \(\lambda (\mu )\). Indeed, fix an optimal solution \(\varvec{f}^{*}\) for \(v_{\mu }(0) =V(\mu )\) and recall that this is just a Wardrop equilibrium. The dual optimal solutions are precisely the \(\lambda \)’s such that

$$\begin{aligned} \varphi _{\mu }(\varvec{f}^{*},0)+\varphi _{\mu }^{*}(\varvec{0},\lambda )=0. \end{aligned}$$

This equation can be written explicitly as

$$\begin{aligned} \sum _{e\in \mathcal {E}}C_{e}\left( {\sum _{p\ni e}f^{*}_{p}}\right) +\sup _{\varvec{f}\ge \varvec{0}}~\lambda \left( {\sum _{p} f_{p}-\mu }\right) -\sum _{e\in \mathcal {E}}C_{e}\left( {\sum _{p'\ni e}f_{p'}}\right) =0, \end{aligned}$$

from which it follows that \(\varvec{f}=\varvec{f}^{*}\) is an optimal solution in the latter supremum. The corresponding optimality conditions are

$$\begin{aligned} \lambda -\sum _{e\in p}c_{e}\left( {\sum _{p'\ni e} f^{*}_{p'}}\right) =0,&\quad \text { if }f^{*}_{p}>0,\\ \lambda -\sum _{e\in p}c_{e}\left( {\sum _{p'\ni e} f^{*}_{p'}}\right) \le 0,&\quad \text { if }f^{*}_{p}=0, \end{aligned}$$

which imply that \(\lambda \) is the equilibrium cost for the Wardrop equilibrium, that is, \(\lambda =\lambda (\mu )\). It follows that \(\partial V(\mu )=\{\lambda (\mu )\}\) so that \(\mu \mapsto V(\mu )\) is not only convex but also differentiable with \(V'(\mu )=\lambda (\mu )\). The conclusion follows by noting that every convex differentiable function is automatically of class \(C^{1}\), with \(V'(\mu )\) nondecreasing.

The continuity of the equilibrium edge costs \(\tau _{e}=\tau _{e}(\mu )\) is a consequence of Berge’s maximum theorem [see, e.g., [1], Section 17.5]. Indeed, the equilibrium edge costs are optimal solutions for the dual program in (2.7). Since the objective function is jointly continuous in \((\tau ,\mu )\), Berge’s theorem implies that the optimal solution correspondence is upper-semicontinous. However, in this case the optimal solution is unique, so that the optimal correspondence is single-valued, and, as a consequence, the equilibrium edge costs \(\tau _{e}(\mu )\) are continuous. \(\square \)

As an immediate consequence of Proposition 3.1 we obtain the following result:

Corollary 3.2

If the costs \(c_{e}(\,\cdot \,)\) are strictly increasing and continuous, the equilibrium loads \(x^{*}_{e}(\mu )=c_{e}^{-1}(\tau _{e}(\mu ))\) are unique and continuous.

For multiple origin-destination networks with continuous and strictly increasing costs, the continuity of the equilibrium loads \(x^{*}_e\) as a function of the demands was already proved in [19, Theorem 1]. On the other hand, [19, Theorem 2] proved the continuity of the equilibrium costs provided that all paths carry a strictly positive flow, whereas [19, Theorem 3] showed that the equilibrium cost of each OD increases with the corresponding demand. As shown in Proposition 3.1, for a single origin-destination the continuity and monotonicity of the equilibrium cost requires neither that costs be strictly increasing nor that all paths carry a strictly positive flow. Although this might be considered a minor improvement, allowing for nondecreasing costs and particularly constant costs is a convenient extension.

For the analysis of the PoA, the most relevant part of Proposition 3.1 is the smoothness of \(V(\,\cdot \,)\) and the characterization of its derivative \(V'(\mu )=\lambda (\mu )\). In particular, considering the social optimum problem (2.10) we get the following direct consequence:

Proposition 3.3

Let the costs \(c_{e}(\,\cdot \,)\) be \(C^{1}\) and nondecreasing with \(x_{e}\mapsto x_{e}\,c_{e}(x_{e})\) convex. Then the optimal social cost \(\mu \mapsto \widetilde{V}(\mu )\) is convex and \(C^{1}\). Moreover, \(\mu \mapsto {{\,\mathrm{\mathsf {PoA}}\,}}(\mu )\) is continuous in \((0,+\infty )\) and differentiable at every \(\mu \) where the equilibrium cost \(\lambda (\mu )\) is differentiable.

Proof

The assumptions on \(c_{e}(\,\cdot \,)\) imply that the marginal costs

$$\begin{aligned} \widetilde{c}_{e}(x_{e}):=\widetilde{C}_{e}'(x_{e}) =c_{e}(x_{e})+x_{e} \,c_{e}'(x_{e}) \end{aligned}$$
(3.4)

are continuous and nondecreasing. It follows that the optimal flows are the Wardrop equilibria for these marginal costs, and the smoothness of \(\widetilde{V}(\mu )\) follows from Proposition 3.1. For the PoA it suffices to observe that \(\lambda (\mu )\) is continuous and then use the equality (2.11). \(\square \)

Wu and Mohring [38] recently established a very general result on the continuity of the PoA with respect to the demands and also with respect to perturbations of the cost functions. However, differentiability was not addressed in their paper.

3.1 Differentiability of equilibrium costs

In order to use Proposition 3.3 it is convenient to find conditions that ensure the differentiability of the equilibrium cost \(\lambda (\mu )\). In this section we present one such result, which also guarantees the differentiability of the resource loads \(x^{*}_{e}(\mu )\). This follows from the implicit function theorem applied to the system of first order optimality conditions for (2.4). Given a vertex \(v \in \mathcal {V}\), call \(\mathcal {N}^{+}(v )\) and \(\mathcal {N}^{-}(v )\) the sets of out-edges and in-edges of v, respectively, and \(\mathcal {P}(\mathsf {O},v )\) the set of all paths from \(\mathsf {O}\) to v.

Moreover, call \(\mathcal {E}{{(}{v ,w }{)}}\) the set of all edges \(e\in \mathcal {E}\) that go from v to w. Then, an equilibrium load profile \({{(}{x^{*}_{e}}{)}}_{e\in \mathcal {E}}\) for a total demand \(\mu \) is characterized as a solution of

$$\begin{aligned}&x_{e}\ge 0 ~\text { for all }~e\in \mathcal {E}, \end{aligned}$$
(3.5)
$$\begin{aligned}&\sum _{e\in \mathcal {N}^{+}(v )}x_{e}-\sum _{e\in \mathcal {N}^{-}(v )}x_{e}= {\left\{ \begin{array}{ll} ~~0 &{} \text { if }v \ne \mathsf {O},\mathsf {D},\\ ~~\mu &{} \text { if }v =\mathsf {O},\\ -\mu &{} \text { if }v =\mathsf {D}, \end{array}\right. } \quad \text {for all }v \in \mathcal {V}, \end{aligned}$$
(3.6)
$$\begin{aligned}&T_{\mathsf {O}}=0~\text { and }~T_{w }\le T_{v } +\tau _{e}~\text { for all }~ e\in \mathcal {E}(v ,w ), \end{aligned}$$
(3.7)
$$\begin{aligned}&x_{e}\cdot (T_{w }-T_{v }-\tau _{e})=0~\text { for all }~e\in \mathcal {E}(v ,w ), \end{aligned}$$
(3.8)
$$\begin{aligned}&\tau _{e}=c_{e}(x_{e})~\text { for all }~e\in \mathcal {E}, \end{aligned}$$
(3.9)

where \(\tau _{e}\) is the equilibrium cost of the edge e and

$$\begin{aligned} T_{v }:=\min _{p\in \mathcal {P}(\mathsf {O},v )}\sum _{e\in p}\tau _{e} \end{aligned}$$
(3.10)

is the equilibrium cost of a shortest path from the origin \(\mathsf {O}\) to vertex v.

For the subsequent analysis we define the active network as the set of all edges that lie on some shortest path. We also consider the demand levels at which this set changes.

Definition 3.4

For each \(\mu >0\) we let \(\mathcal {P}(\mu )\) be the set of all shortest paths from the source \(\mathsf {O}\) to the sink \(\mathsf {D}\) with cost at equilibrium equal to \(\lambda (\mu )\), and we define the active network \(\widehat{\mathcal {E}}(\mu )\) as the union of the edges on all these paths \(p\in \mathcal {P}(\mu )\).

The active network is said to be locally constant at \(\mu _{0}\) if there exists \(\varepsilon >0\) such that \(\widehat{\mathcal {E}}(\mu )\) is the same for all \(\mu \in [\mu _{0}-\varepsilon ,\mu _{0}+\varepsilon ]\).

The demand \(\mu _{0}\) is called an \(\widehat{\mathcal {E}}\)-break point if there exists \(\varepsilon >0\) such that \(\widehat{\mathcal {E}}(\mu )\) is constant over each of the intervals \([\mu _{0}-\varepsilon ,\mu _{0})\) and \((\mu _{0},\mu _{0}+\varepsilon ]\), with \(\widehat{\mathcal {E}}(\mu _{0}-\varepsilon )\ne \widehat{\mathcal {E}}(\mu _{0}+\varepsilon )\).

Remark 3.5

Since the equilibrium costs \(\tau _{e}=\tau _{e}(\mu )\) and \(\lambda (\mu )\) are unique for each \(\mu \), it follows that both \(\mathcal {P}(\mu )\) and \(\widehat{\mathcal {E}}(\mu )\) are also uniquely determined. Moreover, the continuity of \(\tau _{e}(\mu )\) implies that an edge \(e\not \in \widehat{\mathcal {E}}(\mu _{0})\) that is inactive at \(\mu _{0}\) remains inactive for \(\mu \) near \(\mu _{0}\), that is to say \(\widehat{\mathcal {E}}(\mu _{0})^c\subseteq \widehat{\mathcal {E}}(\mu )^c\).

Figure 2 shows the evolution of the active network at different demand levels for the game in Fig. 1a, with five \(\widehat{\mathcal {E}}\)-break points at \(\mu =1,2,3,4,7\). Notice the correspondence with the break points in the price of anarchy in Fig. 1b.

Fig. 2
figure 2

The active network for the graph on Fig. 1, with \(\widehat{\mathcal {E}}\)-break points at \(\mu =1,2,3,4,7\)

Full size image

Although in general there can be infinitely many \(\widehat{\mathcal {E}}\)-break points (see Proposition 5.5 and Remark 5.6), their number is finite for series-parallel networks (cf. Proposition 3.12) and also for general networks with affine costs (cf. Proposition 4.2). In both cases, once an active network changes, it may never occur again at higher demand levels.

An edge carrying a strictly positive flow at equilibrium must be on some optimal path, and, as a consequence, belongs to the active network. However, the converse may fail when a path becomes active but carries no flow. In order to prove the smoothness of the equilibrium flows we need to avoid this situation, which leads to the following definition of a regular demand.

Definition 3.6

A demand \(\mu >0\) is called regular if there is an equilibrium with \(x_{e}>0\) for all \(e\in \widehat{\mathcal {E}}(\mu )\).

Regularity is just strict complementarity. Indeed, the complementarity condition (3.8) imposes that for each \(e\in \mathcal {E}\) either \(x_{e}\) or \((T_{w }-T_{v }-\tau _{e})\) is zero, whereas strict complementarity requires exactly one of these expressions to be zero. As shown next, when the costs are strictly increasing this implies that the active network is locally constant, so that a regular demand cannot be an \(\widehat{\mathcal {E}}\)-break point. We note however that there can be nonregular demands at which the active network is still locally constant (see Example 5.2).

Lemma 3.7

Suppose that the costs \(c_{e}(\,\cdot \,)\) are strictly increasing and continuous. If \(\mu _{0}\) is a regular demand then the active network \(\widehat{\mathcal {E}}(\mu )\) is locally constant at \(\mu _{0}\).

Proof

From regularity all active edges \(e\in \widehat{\mathcal {E}}(\mu _{0})\) satisfy \(x^{*}_{e}(\mu _{0})>0\). By Proposition 3.1 the maps \(x^{*}_{e}(\,\cdot \,)\) are continuous, so these strict inequalities are preserved for \(\mu \) near \(\mu _{0}\), and therefore \(\widehat{\mathcal {E}}(\mu _{0})\subseteq \widehat{\mathcal {E}}(\mu )\). This, combined with Remark 3.5, yields \(\widehat{\mathcal {E}}(\mu )= \widehat{\mathcal {E}}(\mu _{0})\) for \(\mu \) close to \(\mu _{0}\). \(\square \)

We are now ready to establish the smoothness of the equilibrium.

Proposition 3.8

Assume that the costs \(c_{e}(\,\cdot \,)\) are \(C^1\) with strictly positive derivative. If \(\mu _{0}\) is a regular demand then \(\mu \mapsto (\varvec{x}^{*}(\mu ),\varvec{\tau }(\mu ),\varvec{T}(\mu ))\) is continuously differentiable in a neighborhood of \(\mu _{0}\). In particular the equilibrium cost \(\mu \mapsto \lambda (\mu )\) is \(C^1\) near \(\mu _{0}\).

Proof

From Proposition 3.1 and Corollary 3.2, the equilibrium costs \(\tau _{e}(\mu )\) and loads \(x^{*}_{e}(\mu )\) are uniquely defined and continuous in \(\mu \). Hence, the equilibrium cost \(T_v (\mu )\) of a shortest path to any vertex v is also continuous. These functions \(x^{*}_{e}, \tau _{e}\) and \(T_v \) satisfy in particular (3.6), (3.8), and (3.9).

Now, since \(\mu _{0}\) is regular, the active network is locally constant. Let \(\widehat{\mathcal {E}}_{0}=\widehat{\mathcal {E}}(\mu _{0})\) be this active network and \(\mathcal {V}_{0}\) the corresponding vertices. Moreover, call \(\widehat{\mathcal {E}}_{0}{{(}{v ,w }{)}}\) the set of all edges \(e\in \widehat{\mathcal {E}}_{0}\) that go from v to w. For \(\mu \) near \(\mu _{0}\) we have \(x^{*}_{e}(\mu )=0\) for all \(e\not \in \widehat{\mathcal {E}}_{0}\); hence, these functions are trivially differentiable. Also for \(w \not \in \mathcal {V}_{0}\) we can take \(v \in \mathcal {V}_{0}\) the last vertex on a shortest path from \(\mathsf {O}\) to w, so that \(T_w (\mu )=T_v (\mu )+\varDelta _{v ,w }\) where \(\varDelta _{v ,w }\) is a constant travel time from v to w. Hence it suffices to establish the smoothness of \(x^{*}_{e}(\mu )\) for \(e\in \widehat{\mathcal {E}}_{0}\) and \(T_v (\mu )\) for \(v \in \mathcal {V}_{0}\). To this end, consider (3.6), (3.8), and (3.9) restricted to the edges in \(\widehat{\mathcal {E}}_{0}\), together with the equation \(T_{\mathsf {O}}=0\), which gives the following system:

$$\begin{aligned}&\sum _{e\in \mathcal {N}^{+}(v )\cap \widehat{\mathcal {E}}_{0}}x_{e}-\sum _{e\in \mathcal {N}^{-}(v )\cap \widehat{\mathcal {E}}_{0}}x_{e}= {\left\{ \begin{array}{ll} 0\text { if }v \ne \mathsf {O},\mathsf {D},\\ \mu \text { if }v =\mathsf {O}, \end{array}\right. } \quad \text {for all }v \in \mathcal {V}_{0}, \end{aligned}$$
(3.11)
$$\begin{aligned}&x_{e}\cdot (T_{w }-T_{v }-\tau _{e})=0\quad \text {for all }e\in \widehat{\mathcal {E}}_{0}(v ,w ), \end{aligned}$$
(3.12)
$$\begin{aligned}&\tau _{e}=c_{e}(x_{e}), \end{aligned}$$
(3.13)
$$\begin{aligned}&T_{\mathsf {O}}=0. \end{aligned}$$
(3.14)

To apply the implicit function theorem to this reduced system, we must check that the associated linearized system has a unique solution. Let \(u_{e}\), \(\delta _{v }\) and \(s_{e}\) be respectively the increments in the variables \(x_{e}\), \(T_v \) and \(\tau _{e}\) for each \(e\in \widehat{\mathcal {E}}_{0}\) and \(v \in \mathcal {V}_{0}\). The homogeneous linear system obtained from (3.11), (3.12), (3.13), and (3.14) is:

$$\begin{aligned}&\sum _{e\in \mathcal {N}^{+}(v )\cap \widehat{\mathcal {E}}_{0}}u_{e}-\sum _{e\in \mathcal {N}^{-}(v )\cap \widehat{\mathcal {E}}_{0}}u_{e}= 0 \quad \text {for all }v \in \mathcal {V}_{0}, \end{aligned}$$
(3.15)
$$\begin{aligned}&x_{e}(\delta _{w }-\delta _{v }-s_{e})+u_{e}(T_w -T_v -\tau _{e})=0\quad \text {for all }e\in \widehat{\mathcal {E}}_{0}(v ,w ), \end{aligned}$$
(3.16)
$$\begin{aligned}&s_{e}=c_{e}'(x_{e})u_{e}, \end{aligned}$$
(3.17)
$$\begin{aligned}&\delta _{\mathsf {O}}=0. \end{aligned}$$
(3.18)

Strict complementarity on an active link implies that (3.16) is equivalent to

$$\begin{aligned} \delta _{w }=\delta _{v }+s_{e}\qquad \text {for all }e\in \widehat{\mathcal {E}}_{0}(v ,w ), \end{aligned}$$
(3.19)

which, together with (3.17), gives

$$\begin{aligned} \delta _{w }=\delta _{v }+c'_{e} (x_{e})u_{e}\qquad \text {for all }e\in \widehat{\mathcal {E}}_{0}(v ,w ). \end{aligned}$$
(3.20)

These equations are the stationarity conditions for the strongly convex (since \(c'_{e}(x_{e})>0\)) quadratic program

figure a

under the constraints (3.15). Indeed, associating a Lagrange multiplier to each of those constraints, we get the Lagrangian

$$\begin{aligned} \mathcal {L}(\varvec{u},\varvec{\delta })=\sum _{e\in \widehat{\mathcal {E}}_{0}}\frac{1}{2} c'_{e}(x_{e})u_{e}^{2}+\sum _{v \in \mathcal {V}_{0}}\delta _{v }\left( \sum _{e\in \mathcal {N}^{+}(v )\cap \widehat{\mathcal {E}}_{0}}u_{e}-\sum _{e\in \mathcal {N}^{-}(v )\cap \widehat{\mathcal {E}}_{0}}u_{e} \right) \end{aligned}$$

and the equation \(\partial \mathcal {L}/\partial u_{e}=0\) is precisely equivalent to (3.20). Hence, every solution of (3.15), (3.16), (3.17), and (3.18) corresponds to an optimal solution of (\(\mathsf {P}\)). Since \(u_{e}=0\) for all \(e\in \widehat{\mathcal {E}}_{0}\) is feasible, it is also the unique optimal solution. Then (3.17) yields \(s_{e}=0\) for all \(e\in \widehat{\mathcal {E}}_{0}\), and from (3.19) and (3.18) we also get \(\delta _{v }=0\) for all \(v \in \mathcal {V}_{0}\).

Since the linear system (3.15), (3.16), (3.17), and (3.18) has only the trivial solution, the Jacobian of (3.11), (3.12), (3.13), and (3.14) with respect to \(\varvec{x},\varvec{\tau },\varvec{T}\) is invertible and the implicit function theorem implies the smoothness of the solution. In particular \(\lambda (\mu )=T_\mathsf {D}(\mu )\) is continuously differentiable. \(\square \)

Remark 3.9

The directional differentiability of the equilibrium loads with respect to parameters was investigated by [20, 28], though it can also be derived from [34, Theorem 5.1]. Theorem 10 in [28] shows that differentiability holds provided that the edge loads in the linearized system are unique (this is what is done in the proof above) and assuming in addition that all the route flows corresponding to the solutions of the linearized system satisfy an additional vanishing condition. Our Proposition 3.8 is more straightforward as it follows directly from the implicit function theorem, which gives in addition the continuity of the derivatives. It is also easier to apply and to interpret: it just requires to check that all active links carry a positive flow. In other words, smoothness can only fail at critical values of the demand where a new link becomes active but is not yet carrying flow. This simpler sufficient condition is all that is needed hereafter.

Combining Propositions 3.3 and 3.8 we obtain the following result on the differentiability of the price of anarchy.

Theorem 3.10

Suppose that \(c_{e}(\,\cdot \,)\) are \(C^{1}\) with strictly positive derivative and \(x_{e}\,c_{e}(x_{e})\) convex. Then PoA \((\,\cdot \,)\) is continuously differentiable at each regular demand level \(\mu _{0}\).

While all \(\widehat{\mathcal {E}}\)-break points are nonregular, there might exist other nonregular points that are not \(\widehat{\mathcal {E}}\)-break points (see Example 5.2). We do not know if differentiability of \({{\,\mathrm{\mathsf {PoA}}\,}}(\,\cdot \,)\) can fail at such additional nonregular points. In the next section we will show that for affine costs, nonsmoothness can only occur at \(\widehat{\mathcal {E}}\)-break points and that there are finitely many of them. In contrast, for general networks and nonlinear costs the number of \(\widehat{\mathcal {E}}\)-break points can be unbounded. In this regard, it is worth noting that for networks with a series-parallel topology (which excludes the Wheatstone network), the active network increases monotonically with the demand, which yields a sharp bound on the number of different active networks and \(\widehat{\mathcal {E}}\)-break points that can occur as the demand grows from 0 to \(+\infty \).

Definition 3.11

The class of series-parallel (SP) networks can be constructed as follows:

  • A network with two vertices \(\mathsf {O}, \mathsf {D}\) and one edge \((\mathsf {O},\mathsf {D})\) connecting them is SP.

  • A network obtained by joining in series two SP networks by merging \(\mathsf {D}_{1}\) with \(\mathsf {O}_{2}\) is SP.

  • A network obtained by joining in parallel two SP networks by merging \(\mathsf {O}_{1}\) with \(\mathsf {O}_{2}\) and \(\mathsf {D}_{1}\) with \(\mathsf {D}_{2}\) is SP.

Proposition 3.12

Let \(\mathcal {G}\) be a series-parallel network. Then there exist equilibrium load profiles \(\varvec{x}(\mu )\) whose components \(x_{e}(\mu )\) are nondecreasing functions of the demand \(\mu \). Moreover, the active network \(\widehat{\mathcal {E}}(\mu )\) is also nondecreasing with respect to inclusion so that the number of \(\widehat{\mathcal {E}}\)-break points is bounded by the minimum between the number of paths and the number of edges.

Proof

The result clearly holds for the network with only two vertices and a single link.

Let \(\mathcal {G}^{1}\) and \(\mathcal {G}^{2}\) be two series-parallel networks for which the result is true, and fix two nondecreasing equilibrium loads \({\varvec{x}}^{1}(\mu )\) and \({\varvec{x}}^{2}(\mu )\), with their corresponding equilibrium costs \(\lambda ^{1}(\mu )\) and \(\lambda ^{2}(\mu )\) and active networks \(\mathcal {E}^{1}(\mu )\) and \(\mathcal {E}^{2}(\mu )\).

If \(\mathcal {G}^{1}\) and \(\mathcal {G}^{2}\) are connected in series, then an equilibrium is given by the coupling \(\varvec{x}(\mu )=(\varvec{x}^{1}(\mu ),\varvec{x}^{2}(\mu ))\) with active network \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}^{1}(\mu )\cup \mathcal {E}^{2}(\mu )\), all of which are nondecreasing with \(\mu \).

The case in which \(\mathcal {G}^{1}\) and \(\mathcal {G}^{2}\) are joined in parallel, is slightly more involved. Here an equilibrium splits as \({\varvec{x}}(\mu )=(\varvec{x}^{1}(\mu ^{1}),\varvec{x}^{2}(\mu ^{2}))\) where \(\mu ^{1}+\mu ^{2}=\mu \) with \(\mu ^{2}=0\) if \(\lambda ^{1}(\mu )<\lambda ^{2}(0)\), \(\mu ^{1}=0\) if \(\lambda ^{2}(\mu )<\lambda ^{1}(0)\), and \(\lambda ^{1}(\mu ^{1})=\lambda ^{2}(\mu ^{2})\) otherwise. More explicitly, if we let \(g(\mu )=\inf \{x\in [0,\mu ]: \lambda ^{1}(x)\ge \lambda ^{2}(\mu -x)\}\), with \(g(\mu )=\mu \) when the latter set is empty, then both \(\mu ^{1}=g(\mu )\) and \(\mu ^{2}=\mu -g(\mu )\) turn out to be nondecreasing and therefore \(\varvec{x}(\mu )=(\varvec{x}^{1}(g(\mu )),\varvec{x}^{2}(\mu -g(\mu )))\) is a nondecreasing equilibrium. The monotonicity of the active network \(\widehat{\mathcal {E}}(\mu )\) is similar. We have \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}^{1}(\mu )\) if \(\lambda ^{1}(\mu )<\lambda ^{2}(0)\), \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}^{2}(\mu )\) when \(\lambda ^{2}(\mu )<\lambda ^{1}(0)\), and \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}^{1}(g(\mu ))\cup \mathcal {E}^{2}(\mu -g(\mu ))\) otherwise, and in all three cases the active network is nondecreasing. \(\square \)

Remark 3.13

A related result was obtained in [24] for undirected networks. His Lemma 2 shows that in a series-parallel network there exists some path whose edge loads are increasing in the total traffic demand. Proposition 3.12 proves that there exists an equilibrium in which this monotonicity holds for all edges and paths.

Concerned about complexity of computing parametric mincost flows, [22, Corollary 4] also proved monotonicity of the output flows on the edges when costs are piecewise linear.

4 Networks with affine cost functions

4.1 Equilibrium flows

In this section we consider the case of affine cost functions

$$\begin{aligned} c_{e}(x) =a_{e}\cdot x+b_{e}, \end{aligned}$$
(4.1)

with \(a_{e},b_{e}\ge 0\) for each \(e\in \mathcal {E}\). We recall that in this case we have a scaling law that relates the equilibrium and optimum flows.

Lemma 4.1

(Roughgarden and Tardos [32, Lemma 2.3]) Suppose \(c_{e}\) is affine for all \(e\in \mathcal {E}\). Let \(\varvec{f}^{*}(\mu )\) be an equilibrium flow with corresponding load \(\varvec{x}^{*}(\mu )\). Then \(\widetilde{\varvec{f}}(\mu )=\frac{1}{2}\varvec{f}^{*}(2\mu )\) is a socially optimal flow with load \(\widetilde{\varvec{x}}(\mu )=\frac{1}{2}\varvec{x}^{*}(2\mu )\).

From this it follows directly that for affine costs the \(\widehat{\mathcal {E}}\)-break points for the optimum are in one-to-one correspondence with the \(\widehat{\mathcal {E}}\)-break points for the equilibrium, that is,

$$\begin{aligned} \widetilde{\mu }_{0}=\frac{1}{2}\mu _{0}. \end{aligned}$$
(4.2)

[26, Theorem 3.5] established a similar scaling law when all the edge costs are \({{\,\mathrm{\mathsf {BPR}}\,}}\) functions of the same degree.

We now describe the behavior of the equilibrium and the price of anarchy. We first show that any given subset of edges \(\widehat{\mathcal {E}}_{0}\subseteq \mathcal {E}\) can only be an active network over an interval. In other words, once a given active network changes, it will never become active again. This implies that the number of \(\widehat{\mathcal {E}}\)-break points is finite. Moreover, we show that between \(\widehat{\mathcal {E}}\)-break points the equilibrium cost is affine with nonnegative slope and intersect.

Proposition 4.2

Suppose that the costs \(c_{e}(\,\cdot \,)\) are affine. Let \(\mathcal {E}_{0}\subseteq \mathcal {E}\) and suppose that \(\mu ^1<\mu ^2\) are such that \(\widehat{\mathcal {E}}(\mu ^1)=\widehat{\mathcal {E}}(\mu ^2)=\mathcal {E}_{0}\). Then, for every \(\mu \in [\mu ^1,\mu ^2]\) we have \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}_{0}\) and we can select an equilibrium flow \(\varvec{f}(\mu )\) that is affine in \(\mu \), so that the equilibrium cost \(\lambda (\mu )\) is also affine on \([\mu ^1,\mu ^2]\). More precisely \(\lambda (\mu )=\alpha +\beta \mu \) with nonnegative coefficients \(\alpha \ge 0\) and \(\beta \ge 0\).

Proof

Let \(\varvec{f}^1\) and \(\varvec{f}^2\) be equilibrium profiles for \(\mu ^1\) and \(\mu ^2\), and consider the following affine interpolation with \(\theta =\theta (\mu ):=(\mu -\mu ^1)/(\mu ^2-\mu ^1)\in [0,1]\)

$$\begin{aligned} \varvec{f}(\mu )=(1-\theta )\varvec{f}^1+\theta \varvec{f}^2\in \mathcal {F}_{\mu }. \end{aligned}$$
(4.3)

The corresponding load profile is given by \(\varvec{x}(\mu )=(1-\theta )\varvec{x}^1+\theta \varvec{x}^2\) and, since the costs are affine, it follows that \(c_{e}(x_{e}(\mu ))=(1-\theta )c_{e}(x_{e}^{1})+\theta c_{e}(x_{e}^{2})\). Hence, the same affine behavior holds for the path costs \(c_{p}(\varvec{f}(\mu ))=(1-\theta )c_{p}(\varvec{f}^{1})+\theta c_{p}(\varvec{f}^{2})\). Now, since \(\widehat{\mathcal {E}}(\mu ^1)=\widehat{\mathcal {E}}(\mu ^2)=\mathcal {E}_{0}\), the optimal paths are the same for \(\mu ^1\) and \(\mu ^2\). Thus, if p is an optimal path and \(p'\) is not optimal, we have

$$\begin{aligned} c_{p}(\varvec{f}^1)&=\lambda (\mu ^1)<c_{p'}(\varvec{f}^1)\\ c_{p}(\varvec{f}^2)&=\lambda (\mu ^2)<c_{p'}(\varvec{f}^2) \end{aligned}$$

and taking a convex combination of these inequalities we get

$$\begin{aligned} c_{p}(\varvec{f}(\mu ))=(1-\theta )\lambda (\mu ^1)+\theta \lambda (\mu ^2)<c_{p'}(\varvec{f}(\mu )). \end{aligned}$$

This implies that the paths p and \(p'\) remain respectively optimal and nonoptimal for \(\mu \). It follows that \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}_{0}\) and also that \(\varvec{f}(\mu )\) is an equilibrium with \(\lambda (\mu )=(1-\theta )\lambda (\mu ^1)+\theta \lambda (\mu ^2)\).

This shows that the equilibrium cost is affine over the interval \([\mu ^1,\mu ^2]\), that is, \(\lambda (\mu )=\alpha +\beta \mu \). From Proposition 3.1 we know that \(\lambda (\mu )\) is nondecreasing so that \(\beta \ge 0\), and therefore it remains to show that \(\alpha \ge 0\). We rewrite the interpolated flow as \(\varvec{f}(\mu )=\mu \varvec{w} +\varvec{z}\) with

$$\begin{aligned} \varvec{w}&=\frac{\varvec{f}^2-\varvec{f}^1}{\mu ^2-\mu ^1}, \end{aligned}$$
(4.4)
$$\begin{aligned} \varvec{z}&=\frac{\mu ^2\varvec{f}^1-\mu ^1\varvec{f}^2}{\mu ^2-\mu ^1}. \end{aligned}$$
(4.5)

Let \(\mathcal {P}_{0}\) be the set of all the \(\mathsf {O}\)-\(\mathsf {D}\) shortest paths included in \(\mathcal {E}_{0}\). We observe that \(\varvec{z}_{p}=0\) for every \(p\not \in \mathcal {P}_{0}\), and also that \(\sum _{p\in \mathcal {P}}\varvec{z}_{e}=0\). On the other hand, since \(\varvec{f}(\mu )\) is an equilibrium we have \(c_{p}(\varvec{f}(\mu ))=\lambda (\mu )\) for all \(p\in \mathcal {P}_{0}\), so that \(\langle c(\varvec{f}(\mu )),\varvec{z}\rangle =0\) and, as a consequence,

$$\begin{aligned} \mu \lambda (\mu )={{\langle }{c(\varvec{f}(\mu )),\varvec{f}(\mu )}{\rangle }} ={{\langle }{c(\varvec{f}(\mu )),\mu \varvec{w}+\varvec{z}}{\rangle }} =\mu {{\langle }{c(\varvec{f}(\mu )),\varvec{w}}{\rangle }}. \end{aligned}$$
(4.6)

Defining

$$\begin{aligned} A=Z^{\top }\varGamma Z \quad \text {and}\quad \varvec{d}=Z^{\top }\varvec{b}, \end{aligned}$$
(4.7)

with Z the edge-path incidence matrix, \(\varGamma ={{\,\mathrm{diag}\,}}[(a_{e})_{e\in \mathcal {E}}]\), and \(\varvec{b}=(b_{e})_{e\in \mathcal {E}}\), the vector of path costs can be expressed as

$$\begin{aligned} c(\varvec{f}(\mu ))=A\varvec{f}(\mu )+\varvec{d}=\mu A\varvec{w}+A\varvec{z}+\varvec{d}, \end{aligned}$$
(4.8)

so that

$$\begin{aligned} \lambda (\mu )={{\langle }{c(\varvec{f}(\mu )),\varvec{w}}{\rangle }} = \mu {{\langle }{A \varvec{w},\varvec{w}}{\rangle }}+{{\langle }{A \varvec{z}+\varvec{d},\varvec{w}}{\rangle }}, \end{aligned}$$
(4.9)

which yields \(\beta ={{\langle }{A \varvec{w},\varvec{w}}{\rangle }}\) and \(\alpha ={{\langle }{A\varvec{z}+\varvec{d},\varvec{w}}{\rangle }}\). Since A is positive semidefinite, we get again \(\beta \ge 0\). Now, since \(0=\langle c(\varvec{f}(\mu )),\varvec{z}\rangle =\mu \langle A\varvec{w},\varvec{z}\rangle +\langle A\varvec{z}+\varvec{d},\varvec{z}\rangle \) for all \(\mu \), it follows that \(\langle A\varvec{w},\varvec{z}\rangle =0\) so that \(\alpha ={{\langle }{\varvec{d},\varvec{w}}{\rangle }}\), and also \(\langle A\varvec{z}+\varvec{d},\varvec{z}\rangle =0\) so that \(\langle \varvec{d},\varvec{z}\rangle =-\langle A\varvec{z},\varvec{z}\rangle \le 0\). To conclude, we note that all the entries in \(\varvec{f}(\mu )\) and in \(\varvec{d}\) are nonnegative, and therefore

$$\begin{aligned} 0\le {{\langle }{\varvec{f}(\mu ),\varvec{d}}{\rangle }}=\mu {{\langle }{\varvec{w},\varvec{d}}{\rangle }}+{{\langle }{\varvec{z},\varvec{d}}{\rangle }}, \end{aligned}$$
(4.10)

from which we deduce that \(\alpha ={{\langle }{\varvec{w},\varvec{d}}{\rangle }}\ge 0\) as claimed. \(\square \)

Remark 4.3

The paper by Klimm and Warode [22] developed a homotopy method for computing the full path of Wardrop equilibria as a function of the traffic demand. The method is designed to work with piecewise linear costs and produces a piecewise linear path of equilibrium loads. The algorithm first determines the equilibrium costs and then recovers the loads by inverting the link costs. This requires the costs to be strictly increasing. In contrast, we work directly in the space of flows so we can handle nondecreasing and constant costs. However, we restrict to affine costs, which is essential for Proposition 4.2. Indeed, beyond the piecewise affine character of the equilibrium, the most relevant part of this result is the identification of the break points as the demand levels at which the active network changes. As shown in Proposition 4.2, each particular subnetwork can be active on a demand interval, and, on each of these intervals, the equilibrium varies linearly. Once an active network is abandoned, it will never occur again at higher demand levels. This property fails to hold for nonlinear or even piecewise linear costs, as shown in Proposition 5.5.

[22, Theorem 10] showed that, even for affine costs, the number of \(\widehat{\mathcal {E}}\)-break points can be exponential in the number of paths. In Sect. 5 we will use their example to show an interesting behavior of the price of anarchy.

4.2 Behavior of the price of anarchy

We now prove that the social cost at the equilibrium and at the optimum have a very similar quadratic form, from which we deduce that between \(\widehat{\mathcal {E}}\)-break points the function \(\mu \mapsto {{\,\mathrm{\mathsf {PoA}}\,}}(\mu )\) has a unique minimum and its maximum must be attained at some of the \(\widehat{\mathcal {E}}\)-break points.

Proposition 4.4

Let \(\mu _{k}\) and \(\mu _{k+1}\) be two consecutive \(\widehat{\mathcal {E}}\)-break points for the equilibrium. Then, there exist \(\alpha _{k}\ge 0\), \(\beta _{k}\ge 0\), and \(\gamma _{k}\le 0\), such that

$$\begin{aligned} {\mathsf {SC}}(\varvec{f}^{*}(\mu ))&=\alpha _{k}\mu +\beta _{k}\mu ^{2} \quad \text {when }\mu \in (\mu _{k},\mu _{k+1}), \end{aligned}$$
(4.11)
$$\begin{aligned} {\mathsf {SC}}(\widetilde{f}(\mu ))&=\gamma _{k}+\alpha _{k}\mu +\beta _{k}\mu ^{2} \quad \text { when }2\mu \in (\mu _{k},\mu _{k+1}),\text { i.e., }\mu \in (\widetilde{\mu }_{k},\widetilde{\mu }_{k+1}). \end{aligned}$$
(4.12)

Proof

Since \(\mathsf {SC}(\varvec{f}^{*}(\mu ))=\mu \,\lambda (\mu )\), the equality (4.11) follows directly from Proposition 4.2 with \(\alpha _{k}={{\langle }{A\varvec{z}+\varvec{d},\varvec{w}}{\rangle }}\) and \(\beta _{k}={{\langle }{A \varvec{w},\varvec{w}}{\rangle }}\), where \(\varvec{w}, \varvec{z}, A, \varvec{d}\) are defined as in (4.4), (4.5), and (4.7).

In order to prove (4.12), let \(\varvec{f}(\mu )=\mu \varvec{w} +\varvec{z}\) be the affine interpolated equilibria as in the proof of Proposition 4.2. When \(2\mu \in (\mu _{k},\mu _{k+1})\), Proposition 4.1 implies that an optimum flow is

$$\begin{aligned} \widetilde{\varvec{f}}(\mu )={\frac{1}{2}}\varvec{f}(2\mu )=\mu \,\varvec{w} +{\frac{1}{2}}\varvec{z}. \end{aligned}$$

Then the social cost at optimum will be a quadratic function in \(\mu \) with the same linear coefficient (\(\alpha _{k}\)) and quadratic coefficient (\(\beta _{k}\)) of the social cost at equilibrium, and constant coefficient

$$\begin{aligned} \gamma _{k}=\frac{1}{4}\langle A\varvec{z},\varvec{z}\rangle + \frac{1}{2}\langle \varvec{d},\varvec{z}\rangle , \end{aligned}$$

which is less or equal to \(\langle A\varvec{z},\varvec{z}\rangle + \langle \varvec{d},\varvec{z}\rangle =0\) since \(\langle A\varvec{z},\varvec{z}\rangle \ge 0\) and \(\langle \varvec{d},\varvec{z}\rangle \le 0\). \(\square \)

From this result it follows that the PoA between \(\widehat{\mathcal {E}}\)-break points is a quotient of quadratics. Moreover, the specific signs of the coefficients of these quadratics imply that PoA has a unique minimum between break points and that its local maxima can only occur at these break points.

Theorem 4.5

Let \(\mu _{k}\) and \(\mu _{k+1}\) be two consecutive \(\widehat{\mathcal {E}}\)-break points for the equilibrium. Then on the interval \((\mu _{k},\mu _{k+1})\) the function \(\mu \mapsto \) \( {{{\,\mathrm{\mathsf {PoA}}\,}}}(\mu )\) is smooth and it is either decreasing, or increasing, or first decreasing and then increasing with a local minimum in the interior of the interval. In particular \( {{{\,\mathrm{\mathsf {PoA}}\,}}}(\mu )\) does not attain a local maximum on \((\mu _{k},\mu _{k+1})\).

Proof

From Proposition 3.3 the optimal social cost is a \(C^1\) function of \(\mu \), so that (4.11) implies that \({{\,\mathrm{\mathsf {PoA}}\,}}(\mu )\) is smooth over the full interval \((\mu _{k},\mu _{k+1})\). Consider first the case when there is no \(\widehat{\mathcal {E}}\)-break point \(\widetilde{\mu }_{\ell }\) for the optimum in this interval. Using (4.11), and (4.12) we can express the PoA in the form

$$\begin{aligned} \mathrm{{{\,\mathrm{\mathsf {PoA}}\,}}}(\mu ) =\frac{{{\,\mathrm{\mathsf{SC}}\,}}(\varvec{f}^{*}(\mu ))}{{{\,\mathrm{\mathsf{SC}}\,}}(\widetilde{f}(\mu ))} =\frac{\alpha \mu +\beta \mu ^{2}}{\gamma +\delta \mu +\eta \mu ^{2}}, \end{aligned}$$

with \(\alpha ,\beta ,\delta ,\eta ,\ge 0\) and \(\gamma \le 0\). The derivative is given by

$$\begin{aligned} \mathrm{{{\,\mathrm{\mathsf {PoA}}\,}}'}(\mu )=\frac{1}{{{\,\mathrm{\mathsf{SC}}\,}}(\widetilde{f}(\mu ))^{2}}\cdot {[}\alpha \gamma +(2\beta \gamma )\mu +(\beta \delta -\alpha \eta )\mu ^{2}{]} \end{aligned}$$

and, since \(\alpha \gamma \le 0\) and \(2\beta \gamma \le 0\), it can have at most one positive zero, and only if \(\beta \delta -\alpha \eta >0\). Hence, either \({{\,\mathrm{\mathsf {PoA}}\,}}'(\mu )\) has a constant sign over \((\mu _{k},\mu _{k+1})\), or it changes from negative to positive if the zero lies on \((\mu _{k},\mu _{k+1})\), in which case we have a local minimum at this zero.

If the optimum has \(\widehat{\mathcal {E}}\)-break points in \((\mu _{k},\mu _{k+1})\), we can repeat the argument on each subinterval, noting that \({{\,\mathrm{\mathsf {PoA}}\,}}(\mu )\) is \(C^1\) so that the sign \({{\,\mathrm{\mathsf {PoA}}\,}}'(\mu )\) does not change at these \(\widehat{\mathcal {E}}\)-break points. \(\square \)

Proposition 4.5 shows that the typical profile of the Price of Anarchy for networks with affine costs is similar to the one shown in the example Fig. 1b. In particular, it implies:

Corollary 4.6

For networks with affine costs the maximum of the Price of Anarchy is attained at some \(\widehat{\mathcal {E}}\)-break point.

5 Examples and counter examples

In this section we present a set of examples that illustrate the results of the previous sections.

The first example shows the difference between the set of \(\widehat{\mathcal {E}}\)-break points and the demands at which the set of paths used at equilibrium changes.

Example 5.1

Given a selection of equilibrium flows \(\varvec{f}^{*}(\mu )\), the values \(\mu \) at which the set of used paths changes may be different from the \(\widehat{\mathcal {E}}\)-break points. For instance, in the network of Fig. 3, for all \(\mu \ge 2\) and for any choice of \(\eta \in [0,1]\) the flow in the flow in the following table is an equilibrium.

Path

\(\{\mathsf {O},v _{1},v _{2},\mathsf {D}\}\)

\(\{\mathsf {O},v _{1},\mathsf {D}\}\)

\(\{\mathsf {O},v _{2},\mathsf {D}\}\)

\(\{\mathsf {O},\mathsf {D} \}\)

Flow

\(1-\eta \)

\(\eta \)

\(\eta \)

\(\mu -1-\eta \)

.

By letting \(\eta \) oscillate between 0 and 1 arbitrarily often, the set of used paths might change an arbitrary number of times, whereas the active network is always the set of edges in all four paths, each of them with an equilibrium cost equal to 2.

Fig. 3
figure 3

The set of paths used in equilibrium may change arbitrarily often

Full size image

Our second example shows that in general the set of nonregular demands may be strictly larger than the set of \(\widehat{\mathcal {E}}\)-break points.

Example 5.2

Consider again Fig. 3 with the cost 2 in the lower link replaced by \(2+x\), with \(\widehat{\mathcal {E}}\)-break points at \(\mu =1\) and \(\mu =2\). Note that all the demands \(\mu <1\) and \(\mu >2\) are regular. However, for \(\mu \in (1,2)\) the active network \(\widehat{\mathcal {E}}(\mu )\) is constant and comprises all the links, so that there are no \(\widehat{\mathcal {E}}\)-break points, while the unique equilibrium sends a zero flow on the lower link and hence \(\mu \) is not regular. It is worth noting that, although the loss of regularity in the interval (1, 2) precludes the use of Proposition 3.8, in this case the costs are affine so that the equilibrium flows are piecewise affine and differentiable except at the \(\widehat{\mathcal {E}}\)-break points \(\mu =1\) and \(\mu =2\).

The next example deals with the fact that the PoA can attain the value 1 several times.

Example 5.3

In the example of Fig. 1, the price of anarchy shows an initial phase in which it is identically equal to 1, after which it oscillates and eventually goes back to 1 but only asymptotically. We will use an example taken from [22, Section 6.1.2] to show that the PoA can oscillate and go back to 1 more than once. The idea is to nest several Wheatstone networks and choose constant costs that increase exponentially as we go from the inner to the outer networks.

Figure 4a shows the version where the network is obtained by nesting with two Wheatstone networks. Figure 4b shows the graph of the corresponding PoA. The PoA is equal to 1 for small demand (\(\mu \le 1/2\)), then increases and reaches a local maximum, then it decreases back to 1 and it remains equal to 1 for the entire interval [2, 3] of demand, then reaches its maximum and, after that, decreases back to 1, where it remains indefinitely.

Below we list the paths in the network in Fig. 4a:

$$\begin{aligned} p_{1}=&~\mathsf {O}\rightarrow v _{1}\rightarrow \mathsf {D},\\ p_{2}=&~\mathsf {O}\rightarrow v _{4}\rightarrow \mathsf {D},\\ p_{3}=&~\mathsf {O}\rightarrow v _{1}\rightarrow v _{2}\rightarrow v _{4}\rightarrow \mathsf {D},\\ p_{4}=&~\mathsf {O}\rightarrow v _{1}\rightarrow v _{3}\rightarrow v _{4}\rightarrow \mathsf {D},\\ p_{5}=&~\mathsf {O}\rightarrow v _{1}\rightarrow v _{2}\rightarrow v _{3}\rightarrow v _{4}\rightarrow \mathsf {D}. \end{aligned}$$

The equilibrium flow for \(\mu \in [0,+\infty )\) is given explicitly in the following table:

Interval

Cost \(\lambda (\mu )\)

\(p_{1}\)

\(p_{2}\)

\(p_{3}\)

\(p_4\)

\(p_5\)

\(\mu \in [0,1)\)

\(4\mu \)

0

0

0

0

\(\mu \)

\(\mu \in [1,2)\)

\(2+2\mu \)

0

0

\(\mu -1\)

\(\mu -1\)

\(2-\mu \)

\(\mu \in [2,6)\)

\(\displaystyle 1 +\frac{5}{2} \mu \)

0

0

\(\displaystyle \frac{\mu }{2}\)

\(\displaystyle \frac{\mu }{2}\)

0

\(\mu \in [6,14)\)

\(\displaystyle \frac{29}{2}+\frac{\mu }{4}\)

\(\displaystyle \frac{3}{4} \mu -\frac{9}{2}\)

\(\displaystyle \frac{3}{4} \mu -\frac{9}{2}\)

\(\displaystyle \frac{9}{2}-\frac{\mu }{4}\)

\(\displaystyle \frac{9}{2}-\frac{\mu }{4}\)

0

\(\mu \in [14,15)\)

18

\(\mu -8\)

\(\mu -8\)

\(15-\mu \)

\(15-\mu \)

\(\mu -14\)

\(\mu \in [15,20)\)

\(\displaystyle 12+\frac{2}{5} \mu \)

\(\displaystyle \frac{3}{5} \mu -2\)

\(\displaystyle \frac{3}{5} \mu -2\)

0

0

\(\displaystyle 4 -\frac{\mu }{5}\)

\(\mu \ge 20\)

\(\displaystyle 10+\frac{\mu }{2}\)

\(\displaystyle \frac{\mu }{2}\)

\(\displaystyle \frac{\mu }{2}\)

0

0

0

As a consequence, the PoA is

$$\begin{aligned} {{\,\mathrm{\mathsf {PoA}}\,}}(\mu )= {\left\{ \begin{array}{ll} 1 &{}\text {if }\mu \in [0,\frac{1}{2})\\ \dfrac{8\mu ^{2}}{-1+4\mu +4\mu ^{2}} &{}\text {if }\mu \in [\frac{1}{2},1)\\ \dfrac{4+4\mu }{2+5\mu } &{}\text {if }\mu \in [1,2)\\ 1 &{}\text {if }\mu \in [2,3)\\ \dfrac{4\mu +10\mu ^{2}}{-81+58\mu +\mu ^2} &{}\text {if }\mu \in [3,6)\\ \dfrac{58\mu +\mu ^{2}}{-81+58\mu +\mu ^{2}} &{}\text {if }\mu \in [6,7)\\ \dfrac{58\mu +\mu ^2}{-130+72\mu } &{}\text {if }\mu \in [7,\frac{15}{2})\\ \dfrac{290\mu +5\mu ^2}{-200+240\mu +8\mu ^2} &{}\text {if }\mu \in [\frac{15}{2},10)\\ \dfrac{58+\mu }{40+2\mu } &{}\text {if }\mu \in [10,14)\\ \dfrac{36}{20+\mu } &{}\text {if }\mu \in [14,15)\\ \dfrac{120+4\mu }{100+5\mu } &{}\text {if }\mu \in [15,20)\\ 1 &{}\text {if }\mu \ge 20. \end{array}\right. } \end{aligned}$$
(5.1)
Fig. 4
figure 4

An example where \({{\,\mathrm{\mathsf {PoA}}\,}}\) goes back to 1 once at intermediate demands

Full size image

The case of three nested Wheatstone networks can be treated similarly (see Fig. 5). Here the PoA is 1 in the intervals \([0,\frac{1}{2}]\), [2, 3], [20, 30] and \([200,+\infty )\).

Fig. 5
figure 5

An example where \({{\,\mathrm{\mathsf {PoA}}\,}}\) goes back to 1 twice at intermediate demands

Full size image

Example 5.4

This example shows that the result in Proposition 4.5 fails for polynomials, even for the simplest network topology. Indeed, consider the two-link parallel network with cost functions

$$\begin{aligned} \begin{aligned} c_{1}(x_{1})&=x_{1}, \\ c_{2}(x_{2})&=1+x_{2}^2. \end{aligned} \end{aligned}$$
(5.2)

The equilibrium and optimum flows can be computed explicitly as in the following table:

Demand

\(x^{*}_{1}(\mu )\)

\(x^{*}_{2}(\mu )\)

\(\widetilde{x}_{1}(\mu )\)

\(\widetilde{x}_{2}(\mu )\)

\(\mu \in [0,1/2]\)

\(\mu \)

0

\(\mu \)

0

\(\mu \in [1/2,1]\)

\(\mu \)

0

\(\mu -\dfrac{-1+\sqrt{6\mu -2}}{3}\)

\(\dfrac{-1+\sqrt{6\mu -2}}{3}\)

\(\mu \in [1,+\infty )\)

\(\mu -\dfrac{-1+\sqrt{4\mu -3}}{2}\)

\(\dfrac{-1+\sqrt{4\mu -3}}{2} \)

\(\mu -\dfrac{-1+\sqrt{6\mu -2}}{3}\)

\(\dfrac{-1+\sqrt{6\mu -2}}{3}\)

Note that the sole \(\widehat{\mathcal {E}}\)-break point is at \(\mu =1\). Moreover we have \(x^{*}_{1}(3)=\widetilde{x}_{1}(3)=2\) and \(x^{*}_{2}(3)=\widetilde{x}_{2}(3)=1\) so that the equilibrium and optimal flows coincide, and \({{\,\mathrm{\mathsf {PoA}}\,}}(3)=1\). This implies that in the interval \((3,+\infty )\) the PoA has a local maximum (see Fig. 6).

Fig. 6
figure 6

Plot of the PoA on the interval [2, 40] for the parallel network with costs as in (5.2)

Full size image

When the cost functions are less regular, the set of paths used at equilibrium can have a recurring behavior, and an active network that is abandoned at some point can be reactivated at larger demands. In particular we cannot ensure that the number of \(\widehat{\mathcal {E}}\)-break points is finite.

Proposition 5.5

There exist networks and nondecreasing cost functions \(c_{e}(\,\cdot \,)\) such that a given active network \(\widehat{\mathcal {E}}(\mu )=\mathcal {E}_{0}\) can repeat itself over disjoint demand intervals defined by \(\widehat{\mathcal {E}}\)-break points.

Proof

Consider the network in Fig. 7 with the cost c(x) defined in \([0,\zeta ]\cup [\zeta +\eta ,+\infty ]\) as follows

$$\begin{aligned} c(x)={\left\{ \begin{array}{ll} a &{}\text { if }x\le \zeta \\ b &{}\text { if }x\ge \zeta +\eta , \end{array}\right. } \end{aligned}$$

with \(0<\eta<a<\zeta<\zeta +\eta <b\), and in the interval \([\zeta ,\zeta +\eta ]\) we interpolate in any way that makes c(x) continuous and nondecreasing in the whole \([0,+\infty ]\).

Fig. 7
figure 7

Wheatsone network with nonaffine costs

Full size image

Then we have the following regimes:

  1. (a)

    when \(\mu \in [0,a]\), the equilibrium flow uses only the path \(\{\mathsf {O},v _{1},v _{2},\mathsf {D}\}\), the load on the two edges \(\{\mathsf {O},v _{2}\}\), and \(\{v _{1},\mathsf {D}\}\) is zero and the equilibrium cost is \(\lambda (\mu )=2\mu \);

  2. (b)

    when \(\mu \in (a,2a)\), the equilibrium flow uses all the three paths as in the following table:

    Path

    \(\{\mathsf {O},v _{1},v _{2},\mathsf {D}\}\)

    \(\{\mathsf {O},v _{1},\mathsf {D}\}\)

    \(\{\mathsf {O},v _{2},\mathsf {D}\}\)

    Flow

    \(2a-\mu \)

    \(\mu -a\)

    \(\mu -a\)

    the load on the two edges \(\{\mathsf {O},v _{2}\}\), \(\{v _{1},\mathsf {D}\}\) is \(\mu -a<\zeta \), and the equilibrium cost is \(\lambda (\mu )=2a\);

  3. (c)

    when \(\mu \in [2a,2\zeta ]\), the equilibrium flow splits equally between the two paths \(\{\mathsf {O},v _{1},\mathsf {D}\}\), \(\{\mathsf {O},v _{2},\mathsf {D}\}\), the load on the two edges \(\{\mathsf {O},v _{2}\}\), \(\{v _{1},\mathsf {D}\}\) is \(\mu /2\le \zeta \), and the equilibrium cost is \(\lambda (\mu )=a+\mu /2\);

  4. (d)

    the regime on the demand interval \([2\zeta ,b+\zeta +\eta ]\) is complicated to describe, but this is not relevant for our purpose;

  5. (e)

    when \(\mu \in [b+\zeta +\eta ,2b)\), the equilibrium uses all three paths as in the following table:

    Path

    \(\{\mathsf {O},v _{1},v _{2},\mathsf {D}\}\)

    \(\{\mathsf {O},v _{1},\mathsf {D}\}\)

    \(\{\mathsf {O},v _{2},\mathsf {D}\}\)

    Flow

    \(2b-\mu \)

    \(\mu -b\)

    \(\mu -b\)

    the load on the two edges \(\{\mathsf {O},v _{2}\}\), \(\{v _{1},\mathsf {D}\}\) is \(\mu -b\ge \zeta +\eta \), and the equilibrium cost is \(\lambda (\mu )=2b\);

  6. (f)

    when \(\mu \ge 2b\), the equilibrium flow splits equally between the two paths \(\{\mathsf {O},v _{1},\mathsf {D}\}\), \(\{\mathsf {O},v _{2},\mathsf {D}\}\), and the load on the two edges \(\{\mathsf {O},v _{2}\}\), \(\{v _{1},\mathsf {D}\}\) is \(\mu /2>\zeta +\eta \).

This proves our claim, as in the intervals sub (c) and (f) the equilibrium uses only the two paths \(\{\mathsf {O},v _{1},\mathsf {D}\}\) and \(\{\mathsf {O},v _{2},\mathsf {D}\}\), while in the interval sub (b) and (e) it uses all three paths. \(\square \)

Remark 5.6

Note that in the same way one can construct examples of networks with an infinite number of \(\widehat{\mathcal {E}}\)-break points for the equilibrium. Furthermore, one can make the increasing sequence of such \(\widehat{\mathcal {E}}\)-break points to be convergent. Indeed, one could chose infinite sequences \((\eta _{i})_{i\in \mathbb {N}}\), \((a_{i})_{i\in \mathbb {N}}\), \((\zeta _{i})_{i\in \mathbb {N}}\), \((b_{i})_{i\in \mathbb {N}}\) with

$$\begin{aligned} 0<\eta _{i}<a_{i}<\zeta _{i}<\zeta _{i}+\eta _{i}<b_{i} <a_{i+1}\quad \text {for every }i\in \mathbb {N}. \end{aligned}$$
(5.3)

Then we set the cost function c(x) to be

$$\begin{aligned} c(x)= {\left\{ \begin{array}{ll} a_{1} &{}\text { if }x\le \zeta _{1}\\ b_{i} &{}\text { if }\zeta _{i}+\eta _{i}\le x\le \dfrac{a_{i+1}-b_{i}}{2}\\ a_{i+1} &{}\text { if }a_{i+1}\le x\le \zeta _{i+1}, \end{array}\right. } \end{aligned}$$

and in the intervals \([\zeta _{i},\zeta _{i}+\eta ]\), \([(a_{i+1}-b_{i})/2,a_{i+1}]\) we interpolate in any way that makes c(x) continuous and nondecreasing in the whole \([0,+\infty ]\). With this choice of c(x), the situation is similar to the one of Proposition 5.5, repeated infinitely many times. Furthermore, since the \(\eta _{i}\) can be as small as we want, we can choose the sequences \((a_{i})_{i\in \mathbb {N}}\), \((\zeta _{i})_{i\in \mathbb {N}}\), \((b_{i})_{i\in \mathbb {N}}\) to be convergent to the same limit.

Remark 5.7

Repetition of an active network can happen for cost functions that are smooth or piecewise affine, as in [22]. We know that this cannot happen for affine cost functions, but, so far we have not been able to characterize the class of cost functions for which repetitions of active networks are impossible.