Network Characterizations for Excluding Braess’s Paradox

Abstract

Braess’s paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve the overall network performance. Under the model of nonatomic selfish routing, we characterize the topologies of k-commodity undirected and directed networks in which Braess’s paradox never occurs. Our results strengthen Milchtaich’s series-parallel characterization (Milchtaich, Games Econom. Behav. 57(2), 321–346 (2006)) for the single-commodity undirected case.

1 Introduction

A basic task of network management is routing traffic to achieve the best possible network performance, e.g., to minimize the maximum latency. However, it is usually difficult or even impossible to implement centralized optimal routing in large network systems where a number of network users (players) are playing selfish routing games [8, 16, 23]. In these games, players choose routes in the networks for traveling from their origins to their destinations. These route choices are selfish in the sense that the players only aim to minimize their own latencies. It is well known that Nash equilibria of selfish routing games might not be socially optimal [17]. A dazzling example is Braess’s paradox [4], which exposes the seemingly counterintuitive phenomenon that less route options for the players lead to shorter travel time at the equilibrium – subnetworks have better performance under the selfish behaviors. The natural question arises as to which topologies of networks are immune to the inefficiency due to the occurrence of Braess’s paradox. The characterization of network topologies, which model fixed infrastructures, is independent of the changeable latency functions and traffic demands. Once such a paradox-free network is established, no matter how the latency functions and traffic demands change, the entire network remains a good venue for selfish players. The goal of this paper is to characterize paradox-free network topologies for nonatomic players each routing a negligible portion of the overall traffic, where the nonatomic routing can be viewed as a mathematical idealization of a very large population of individuals.

1.1 Noatomic Selfish Routing

We are concerned with both undirected and directed networks, and model them by multigraph or multidigraph G = (V, E) with vertex set V and link set E. Loops are not allowed, while more than one links can join the same pair of vertices. Each link e ∈ E is associated with a nonnegative, continuous, nondecreasing latency function ℓ _e (⋅), which specifies the time needed to traverse e as a function of the link congestion on e. We call G a graph with edge set E if it is undirected and a digraph with arc set E if it is directed.¹ Throughout the paper, by a path we mean a simple one, i.e., it contains no repeated vertices; by a path (or a cycle) in a digraph we mean a directed one. For any u, v ∈ V, a path in G from u to v is called a u-v path. For convenience, graphs and digraphs are collectively referred to as (di)graphs.

Let k ≥ 1 be a positive integer. We write [k] for the set {1,…,k} of positive integers smaller than or equal to k. Given k distinct origin-destination pairs of vertices (s _i , t _i ) in G, we call G a k-commodity network if for each i ∈ [k], s _i ≠ t _i and G contains at least an s _i - t _i path. Given a traffic demand (vector) $\mathbf {r}=(r_{i})_{i=1}^{k}$, the traffic in G comprises k flows, each for one commodity. For every i ∈ [k], the flow of commodity i has an amount of r _i ; it is formed by an infinite number of players traveling from s _i to t _i . Each player selects a single path from his origin to his destination that has a minimum latency, given the congestion imposed by the rest of the players. Assuming a continuum of players, the choice of each individual player has a negligible impact on the experiences of others.

Formally, let the triple (G, r, ℓ) denote a k-commodity selfish routing instance, where latency functions ℓ _e (⋅), e ∈ E, are collectively represented by ℓ. The routing instance is sometimes written as $(G,(s_{i},t_{i})_{i=1}^{k},\mathbf {r},\ell )$ in order to explicitly specify the origin-destination pairs. For each i ∈ [k], let $\mathcal {P}_{i}$ be the set of s _i - t _i paths in G; a flow of commodity i is a nonnegative vector $\mathbf {f}_{i}=(f_{i}(P))_{P\in \mathcal {P}_{i}}$ satisfying ${\sum }_{P\in \mathcal {P}_{i}}f_{i}(P)=r_{i}$. The combination of f ₁,…,f _k gives rise to a k-commodity flow $\mathbf {f}=(\mathbf {f}_{i})^{k}_{i=1}$ for routing instance (G, r, ℓ). Under f, each link e that is contained by some path in $\mathcal {P}=\cup _{i=1}^{k}\mathcal {P}_{i}$ experiences a congestion $f(e)={\sum }_{i=1}^{k}{\sum }_{P\in \mathcal {P}_{i}:e\in P}f_{i}(P)$, and thus a link latency ℓ _e (f(e)). Accordingly, each path P contained by $\cup _{Q\in \mathcal {P}}Q$ and any player traveling through P suffer from a path latency $\ell _{P}(\mathbf {f})={\sum }_{e\in P}\ell _{e}(f(e))$. In this nonatomic routing game, a Nash equilibrium is characterized by Wardrop’s principle [28] in a way that all players travel only on the minimum latency paths from their own origins to their own destinations.

Definition 1.1

A k-commodity flow f in (G, r, ℓ) is called a Nash equilibrium (NE) of (G, r, ℓ) if for each i ∈ [k] and each $P\in \mathcal {P}_{i}$ with f _i (P) > 0, it holds that $\ell _{P}(\mathbf {f})=\min _{Q\in \mathcal {P}_{i}}\ell _{Q}(\mathbf {f})$.

By the classical result of Beckmann et al. [2] (see also [17, 23]), the NE of (G, r, ℓ) exist, and are essentially unique in the sense that each link experiences the same latency under all NE of (G, r, ℓ). Thus, for each i ∈ [k], the common latency experienced by all players traveling from s _i to t _i in any NE of (G, r, ℓ) has the same value, which we denote by ℓ _i (G, r), and refer to as the equilibrium latency of commodity i for (G, r, ℓ).

1.2 Braess’s Paradox

The formal definition of Braess’s paradox involves the specific meaning of subnetworks. Let $(G,(s_{i},t_{i})_{i=1}^{k},\mathbf {r},\ell )$ be a k-commodity selfish routing instance. For any index set k ⊆ [k], a subgraph or subdigraph H of G is referred to as a subnetwork of (G, k) if H is a |k|-commodity network with origin-destination pairs (s _i , t _i ) _{i ∈ k} , Following [17], a subnetwork of (G,[k]) is simply called a subnetwork of G.

Given routing instance (G, r, ℓ), it is natural to ignore the commodities of zero demands, and focus on k(r) = {i ∈ [k]:r _i > 0}. Let H be a subnetwork of (G, k(r)), and ℓ ^′ be the restriction of ℓ to the link set of H. In a mild abuse of notation, we use (H, r, ℓ) to denote the selfish routing instance (H,(r _i ) _{i ∈ k(r)}, ℓ ^′), and, for each i ∈ [k], use ℓ _i (H, r) to denote the equilibrium latency of commodity i for (H, r, ℓ). For simplicity, in case of single-commodity, i.e., k = 1, we often write r as r (the traffic demand from the single origin to the single destination), and drop the subscript 1 in notions $s_{1},t_{1},\mathcal {P}_{1}$, and ℓ ₁(⋅,r) in our discussions. When r is an all-one vector we often write it as 1.

Definition 1.2

We say that Braess’s paradox occurs in (G, r, ℓ) if there exists subnetwork H of (G, k(r)) and h ∈ k(r) such that ℓ _h (H, r) < ℓ _h (G, r) and ℓ _i (H, r) ≤ ℓ _i (G, r) for all i ∈ k(r)−{h}. A k-commodity network G is said to be Braess’s paradox free, or paradox-free for short, if for any nonnegative traffic demand vector r and any nonnegative, continuous, nondecreasing latency functions ℓ, Braess’s paradox does not occur in (G, r, ℓ). A k-commodity network that is not Braess’s paradox free is called Braess’s paradox ridden, or paradox-ridden for short.

We remark that the definition of paradox-ridden network here is a substantial relaxation of the ones given by Roughgarden [22] and Fotakis et al. [12], which admit instances suffering from the most severe performance loss in terms of Braess’s paradox.

For example, Braess’s paradox occurs in the routing instances (a) and (b) depicted in Fig. 1a and b, respectively, where one unit flow is to be routed from each origin to its corresponding destination. The latency function ℓ _e (x) on arc e of network G _a (a.k.a. directed Wheatstone network) or network G _b is either x or a constant 0, 1 or 2 as represented by the symbol beside the arc in the figure. In instance (a) (resp. (b)), the subnetwork H _a (resp. H _b ) is obtained from G _a (resp. G _b ) by deleting the dotted arc. It is easy to see that, in the single-commodity case (a), at the NE of (G _a ,1,ℓ) all players go through the path suvt, while at the NE of (H _a ,1,ℓ) half of players go through path sut and the other half go through path svt; this gives ℓ(H _a ,1)=1.5 < 2 = ℓ(G _a ,1). Similarly, in the 2-commodity case (b), at the NE of (G _b , 1, ℓ) no player uses arc (s ₁, t ₁) (which has a constant latency 2 regardless of any congestion), while at the NE of (H _b , 1, ℓ) the flows of commodities 1 and 2 use disjoint paths s ₁ t ₁ and s ₂ t ₂, respectively; it follows that ℓ ₁(H _b , 1) = 2 = ℓ ₁(G _b , 1) and ℓ ₂(H _b , 1) = 1 < 2 = ℓ ₂(G _b , 1). Hence, both network G _a and G _b are paradox-ridden. In contrast, the 3-commodity network G _c depicted in Fig. 1c is paradox-free, as our main result (Theorem 1.6) below guarantees.

Fig. 1

Braess’s paradox in nonatomic selfish routing

A nice hereditary property implied by Definition 1.2 is that every paradox-free k-commodity network with origin-destination pairs (s _i , t _i ) _{i ∈ [k]} must be a paradox-free |I|-commodity network with origin-destination pairs (s _i , t _i ) _{i ∈ I} for any nonempty I ⊆ [k] (see Lemma 2.4). This property would have been lost if one modified the definition by requiring the existence of a subnetwork H of (G, r) instead of (G, k(r)). Take the digraph G in Fig. 2 as an example. When G being considered as a 3-commodity network in (a), for any demand r, every subnetwork of (G, r) contains the path s ₁ s ₂ t ₂, which would imply that G is paradox-free if one adopted the modified definition. However, G as a 2-commodity network in (b) is still paradox-ridden under the modified definition.

Fig. 2

The hereditary property of paradox-freeness

1.3 Our Contributions on Paradox-Free Networks

Considering a k-commodity network G with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$, it would be convenient to think of G being irredundant in the sense that each link and each vertex of G are contained in at least an s _i - t _i path for some i ∈ [k].

Milchtaich [20] established a series-parallel characterization for excluding Braess’s paradox in irredundant single-commodity undirected networks. The nice characterization confirms an unproven assertion of Murchland [21], and partially solved the open question of characterizing paradox-free networks, proposed by Roughgarden [22]. In this paper, we complete the solution by characterizing all irredundant k-commodity undirected and directed networks with the series-parallel and coincident conditions (see Theorem 1.6). In particular, our results on multicommodity networks answer the open question raised by Milchtaich [20]. The theoretical results imply polynomial time algorithms for recognizing paradox-free k-commodity undirected networks and paradox-free k-commodity planar directed networks.

Single-Commodity Networks

The paradox-freeness of irredundant single-commodity networks is characterized in [20] for the undirected case and in this paper for the directed case (see Theorem 1.4 below), using the notion of two-terminal series-parallel networks.

Definition 1.3

An irredundant single-commodity network G with origin-destination pair (s, t) is said to be two-terminal series-parallel, or s-t series-parallel to be more specific, if one of the following conditions holds.

• (i) G is undirected, and there do not exist two s-t paths in G that pass a common edge in opposite directions.

• (ii) G is directed, and its underlying graph is s-t series-parallel.

Theorem 1.4

An irredundant single-commodity network is paradox-free if and only if it is two-terminal series-parallel.

Given the result by Milchtaich [20] for undirected networks, intuitively, one might expect a graphical characterization less restrictive than the two-terminal series-parallel one for directed networks, where players lose the flexibility to traverse a link in either direction, and Braess’s paradox might have fewer chances to occur. However, the intuition is disproved by our result on directed networks.

Despite the similarity of the necessary and sufficient condition for graphs and that for digraphs in Theorem 1.4, the necessity proof for digraphs constitutes our first technical contribution. Milchtaich’s model for single-commodity undirected network [20] allows a class of latency functions wider than ours (which is useful for proving the sufficiency). However the model does preclude predetermined directionality (which is a common feature of many real networks and modeled by digraphs [3]). Milchtaich’s wider class of latency functions does not contribute the necessity proof of the characterization for directed networks. Neither the results nor their proofs in [20] can imply the necessity in the directed case. In the half-page necessity proof for graphs [20], given any undirected network that is not s-t series-parallel, Milchtaich derived a Braess’s paradox by finding a special pair of vertices in the network whose existence relies on the property that the graph has two s-t paths which go through an edge in opposite directions. Such a property is lost when considering digraphs. This is the main hurdle to extending Milchtaich’s proof to digraphs. New ideas and approaches are required to overcome the difficulty due to more complicated structures of digraphs.

• We use the existence of cycles in digraphs to obtain these special pairs of vertices (see Lemma 3.1), which in turn lead us to Braess’s paradoxes (see Lemmas 3.4 and 3.3).

• We translate edge traverses in opposite directions in graphs into the existences of s-t paths through reversed arcs in digraphs. Instead of relying on special pairs of vertices as Milchtaich did, we derive Braess’s paradox directly in acyclic digraphs that are not s-t series-parallel using an inductive argument that carefully exploits the properties of digraphs (see Theorem 3.5).

Multicommodity Networks

To characterize paradox-free multicommodity network, we need the concept of block (see e.g., [26]). Let H be a (di)graph. We say that H is 2-connected if it is connected and has no cut-vertices. A block of H is a maximal 2-connected sub(di)graph of H. If H is two-terminal series-parallel, then each block B of H is also two-terminal series-parallel, where the terminals of B are uniquely determined by the structure of H (see Lemma 2.8), and are referred to as the terminals of B in H.

For each i ∈ [k], let G _i = (V _i , E _i ) be the maximum (in terms of the number of links) irredundant subnetwork of (G,{i}). Then G _i , consisting of all s _i - t _i paths in G, is an irredundant single-commodity network with origin-destination pair (s _i , t _i ). We call s _i and t _i the terminals of G _i .

Definition 1.5

If G _i and G _j (possibly i = j) are two-terminal series-parallel, B is a block of both G _i and G _j , and the set of terminals of B in G _i and that in G _j are the same, then B is called a coincident block of G _i and G _j .

In Definition 1.5, the orders of terminals (which is the origin and which is the destination) of B in G _i and G _j do not have to be the same. A common block B of G _i and G _j is coincident if G is directed, but it is not necessarily coincident if G is undirected, as in the undirected case the terminal sets of B in G _i and G _j might be different. In addition, the order of a coincident block’s terminals makes a difference between directed and undirected networks. Given a coincident block B of G _i and G _j , in the directed case, the order of B’s terminals is unique; while in the undirected case, it is possible that the origin (resp. destination) of B in G _i is the destination (resp. origin) of B in G _j . An example of such different orders can be seen from G ₁ and G ₂ for G = G _c in Fig. 1c.

The next theorem summarizes the main results of this paper, which concern both the directed and undirected case.

Theorem 1.6 (Main result)

An irredundant k-commodity network G is paradox-free if and only if G satisfies the following conditions:

• (i) Series-parallel Condition: for each i ∈ [k], G _i = (V _i , E _i ) is an s _i - t _i series-parallel network; and

• (ii) Coincident Condition: for any i, j ∈ [k], either E _i ∩ E _j = ∅ or the (di)graph induced by E _i ∩ E _j consists of all coincident blocks of G _i and G _j .

The theorem clearly generalizes Theorems 1.4. This generalization is by no means straightforward. Indeed, the coincident condition specifies the interactions of players with different origins and destinations, capturing in the context of paradox-freeness a key property of asymmetric nonatomic selfish routing, which, to the best of our knowledge, was not studied previously.

The configurations depicted in Figs. 1b and 3 give visualizations of how Braess’s paradox occurs in multicommodity directed networks and undirected networks, respectively, where $\mathbb {u}(G_{b})$ in Fig. 3a is the underlying graph of G _b in Fig. 1b.

Fig. 3

Braess’s paradoxes in 2-commodity instance (G, r, ℓ), where for $G\in \{\mathbb {u}(G_{b}),G_{d}\}$ and H = G∖e it holds that ℓ ₁(H, 1) = 2 = ℓ ₁(G, 1) and ℓ ₂(H, 1) = 1 < 2 = ℓ ₂(G, 1)

Moreover, we show in Section 4 that the three configurations are typically all the forbidden structures for paradox-free multicommodity networks. This complements the result that Wheatstone network (G _a in Fig. 1a and its underlying graph) is the only forbidden configuration for paradox-free single-commodity networks.

The proofs for the necessity of the coincident condition constitute our second technical contribution. In undirected networks, coping with the nonidentical sets of terminals for a common block of G _i and G _j turns out to be the key for obtaining the paradox configurations in Fig. 3.

• In connecting the different pairs of terminals, careful path selections to avoid unnecessary intersections, which involve techniques from graph connectivity theory, reveal the essence of the problem.

In directed networks, the difficulty lies on the fact that pure graph theory cannot enforce two intersecting blocks to be identical as it does for undirected networks.

• A more elaborate inductive method is applied to reduce the proof to smaller networks obtained by arc deletion and contraction. As arc contractions might create Braess’s paradox which is not possessed by the original network, the challenging task is to guarantee that the selected arc contraction does not destroy the paradox-freeness (see the proof outline in Section 4.2 for more details).

Our results imply polynomial time algorithms for recognizing paradox-free k-commodity undirected networks and planar directed networks (see Corollary 5.2). In our proofs, the constructions of Braess’s paradoxes only use linear latency functions of form ℓ _e (x) = a _e x + b _e for constants a _e , b _e ≥ 0. An immediate corollary is that our results all hold even if the paradox-freeness is defined with respect to this kind of linear latency functions.

Our characterizations for paradox-free (paradox-ridden) networks show that the multicommodity cases are natural and nontrivial extensions from their single-commodity counterparts, which stands in contrast to the dichotomy between single- and 2-commodity networks in terms of severity of Braess’s paradox [17, 22]. It is known that Braess’s paradox can be dramatically more severe for multicommondity networks than single-commodity ones. More importantly, the characterization for paradox-free networks in the multicommodity case differs significantly from the single commodity case. Braess’s paradox can occur in the multicommodity case even in simple series-parallel networks. An example is the 2-commodity network G _b in Fig. 1b that is paradox-ridden and series parallel.

1.4 Related Work

Most literature on characterizing network topologies for various properties of NE in selfish routing is restricted to the single-commodity case. The most related work is the aforementioned two-terminal series-parallel characterization by Milchtaich [20] for paradox-free undirected networks in nonatomic selfish routing. Recently, Cenciarelli et al. [5] obtained an equivalent characterization using the conception of “homeomorphic” from [20]. The authors proved that a single-commodity directed network is paradox-ridden if and only if it contains a subgraph homeomorphic to G _a in Fig. 1a. This work is independent from ours. The characterization with forbidden structure is valuable, and it is also verified by our results in Section 3. In [20], Milchtaich proved that the networks which guarantee all NE to be weakly Pareto efficient are exactly those with linearly independent routes, meaning that every s-t path has at least an edge that does not belong to any other s-t path. The linear route independence was also shown to be a characterization for paradox-free single-commodity undirected networks with heterogeneous players, meaning that the latency functions are player-specific: the same link under the same congestion might give different latencies to different players using it. (Note that the linear independence result can not be extended to digraphs as shown by the paradox-ridden network G _a in Fig. 1a, where each of the three s-t paths has a unique arc that is not used by any other s-t path.) For the nonatomic routing with heterogeneous players, Milchtaich [18] characterized undirected networks such that, given any strictly increasing latency functions, each player’s latency is the same at all NE. These networks are either nearly parallel or consist of two or more nearly parallel networks connected in series. In contrast to nonatomic routing, an atomic routing game has only a finite number of players, each controlling a noneligible portion of traffic, The most studied scenarios are unsplittable routing where each player routes his flow through a single path from his origin to his destination, and routing with unit demands where each player controls a unit of flow. Milchtaich [19] identified some sufficient conditions for directed network topologies that guarantee the existence of at least one pure NE in unsplittable atomic routing with unit demands for either player-specific latency functions or weighted players. The series connection of some small digraphs was shown to be sufficient for the existence of a pure NE.

As far as multicommodity networks are concerned, Holzman and Monderer [14] studied the unsplittable atomic routing game with unit demands that is played on a directed network with two distinguished vertices u and v, where every arc belongs to at least one u-v path. Note that such a constraint of networks is much stronger than ours of irredundant networks (defined at the beginning of Section 1.3); we only discard links never used by any player. Under this topological constraint, Holzman and Monderer [14] proved that the class of extension-parallel networks is exactly the one guaranteeing the existence of a strong equilibrium. This is a generalization of the previous result on the single-commodity case [15]. Epstein et al. [10] characterized the so-called efficient undirected networks in which all NE of each unsplittable routing instance with unit demands are socially optimal, i.e., they are among routings that minimize the maximum path latency between any origin-destination pair. It was shown that the efficient multicommodity networks are either trees or two vertices joined by parallel edges, while the efficient single-commodity networks are exactly those with linearly independent routes. The authors [10] also obtained characterizations of efficient undirected networks for the routing game where both individual players and the network (society) wish to minimize their own maximum edge latencies. Recently, Fujishige et al. [13] considered general nonatomic congestion games and gave a characterization of the maximal combinatorial property of strategy spaces for which Braess paradox does not occur. In a nutshell, bases of matroids are exactly this maximal structure.

Since its discovery [4] in 1968, Braess paradox has been a subject of considerable research on transportation networks [25], communication and computation systems [23], electrical circuits [6], and more general scientific context; see [22] for an overview. In analyzing the worst-case severity of Braess’s paradox in selfish routing games, Lin et al. [17] defined the Brasses ratio of a k-commodity instance (G, r, ℓ) as the maximum of $\min _{i=1}^{k}\ell _{i}(G,\mathbf {r})/\ell _{i}(H,\mathbf {r})$ over all subnetworks H of G. For nonatomic routing in single-commodity directed networks with n ≥ 2 vertices, Roughgarden [22] established a tight upper bound ⌊n/2⌋ on the Braess ratio. The upper bound was generalized by Lin et al. [17] who showed that removing a set S of arcs from a single-commodity directed network G with origin-destination pair (s, t) can only decrease the equilibrium latency at most by a factor of 1 + c, where c is the maximum number of arcs in S that form a matching of G∖{s, t}. In contrast to the linear upper bound for the single-commodity case, Lin et al. [17] proved an exponential lower bound on the Braess ratio for nonatomic routing in 2-commodity directed networks, and this bound is surprisingly attained by a one-arc removal.

Braess’s paradox indicates the inefficiency of NE, which is usually measured by the price of anarchy (PoA), i.e., the worst-case ratio between the system objective value (of the maximum path latency between any origin-destination pair) at a NE and that of an optimal flow (which minimizes the maximum path latency). Strengthening the observation that the PoA is bounded below by the Braess ratio, Lin et al. [17] proved that the PoA of nonatomic routing is n−1 for single-commodity directed network with n vertices, and 2^{O(min{kn, m logn})} for k-commodity directed network with n vertices and m arcs. A natural network design problem motivated by Braess’s paradox is, given an nonatomic k-commodity routing instance (G, r, ℓ) on directed network G with n vertices, to find a subnetwork H of (G, k(r)) such that maxi ∈ k(r)ℓ _i (H, r) is minimized. Assuming P ≠ N P, the problem was shown to have very strong inaproximability. When k = 1 the best-possible approximation ratio for the problem is ⌊n/2⌋, implying the impossibility of detecting Braess’s paradox (even in its worst manifestations) efficiently in directed single-commodity networks [22]. When k ≥ 2 no polynomial time algorithm for the problem can achieve an approximation ratio 2^o(n), showing exponential inapproximability for detecting Braess’s paradox in directed multicommodity networks [17]. In case of single commodity, the trivial algorithm that outputs the entire digraph G turns out to give the best possible approximation ratio (up to a constant factor) for the single-commodity case [22]; if, in addition, all latencies are linear, then the trivial algorithm guarantees a (4/3)-approximation [22, 23]. Similar network design problems were later investigated for unsplittable atomic routing by Azar and Epstein [1] and for nonatomic single-commodity routing by Fotakis [12], where the efficiency was measured by the total latency [1] or the maximum link latency [12] of all players.

Organization

The rest of the paper is organized as follows: In Section 2, we introduce notations and present preliminaries. In Sections 3 and 4, we characterize paradox-free single-commodity networks and paradox-free multicommodity networks, respectively. In Section 5, we give a wrap-up of the proof for our main result (Theorem 1.6), and then discuss its corollaries on recognition of paradox-free networks and the relations between the paradox-freeness of a network and that of its underlying graph or orientations. In Section 6, we conclude with remarks on directions of future research.

2 Preliminaries

We begin by introducing graph-theoretic notations used in the paper. Let G = (V, E) be a (di)graph without loops that may possibly contain parallel links. As usual, G is said to be acyclic if G contains no cycle. If G is directed, we use $\mathbb {u}(G)$ to denote the underlying (undirected) graph of G.

We often write H ⊆ G to mean that H is a sub(di)graph of G. We use V(H) and E(H) to denote the vertex set and link set of H, respectively. For u ∈ V(H) ∪ E(H), we often write u ∈ H if it is clear from the context that u is a vertex or it is a link.

Let G ₁, G ₂ ⊆ G. By G ₁ ∪ G ₂, we mean the sub(di)graph of G with vertex set V(G ₁) ∪ V(G ₂) and link set E(G ₁) ∪ E(G ₂). If G ₁ and G ₂ have at least one vertex in common, by G ₁ ∩ G ₂, we mean the sub(di)graph of G with vertex set V(G ₁) ∩ V(G ₂) and link set E(G ₁) ∩ E(G ₂). If V(G ₁) ∩ V(G ₂) = ∅, we often use short natation G ₁ ∩ G ₂ = ∅. If G ₁ ⊆ G ₂ and G ₂ ⊆ G ₁, we write G ₁ = G ₂.

Let U ⊆ V ∪ E. The sub(di)graph of G obtained from G by removing elements in U is denoted by G∖U. In case of U consisting of a singleton u, we write G∖u instead of G∖{u}. If G is undirected, we write an edge of G with end-vertices u, v as uv. If G is directed, we write an arc of G with tail u and head v as (u, v).

Let P = v ₁ v ₂…v _h be a v ₁- v _h path in G.² For any 1 ≤ i < j ≤ h, we say that v _i precedes v _j in P, or equivalently v _j follows v _i in P; such a relation is written as v _i ≺ _P v _j . If 1 ≤ i ≤ j ≤ h, we write v _i ≼ _P v _j , and use P[v _i , v _j ] to denote the subpath of P from v _i to v _j . For convenience, we set P(v _i , v _j ] = P[v _i , v _j ]∖v _i , P[v _i , v _j ) = P[v _i , v _j ]∖v _j and P(v _i , v _j ) = P[v _i , v _j ]∖{v _i , v _j }. Let u, v ∈ V, and Q be a u-v path in G. We say that P and Q are internally vertex-disjoint if V(P) ∩ V(Q) ⊆ {v ₁, v _h }∩{u, v}.

Lemma 2.1

Let G=(V,E) be an acyclic digraph. If u, v, w ∈ V, and P and Q are u-v path and v-w path in G, respectively, then P ∪ Q is a u-w path in G.

Consider graph G. For any X, Y, Z ⊆ V, we call a path in G between a vertex in X and a vertex in Y an X-Y path. We say that vertices in Z separate X from Y if G∖Z does not contains any X-Y path.

Theorem 2.2 (Menger’s theorem)

If G=(V,E) is a graph and X,Y ⊆ V, then the minimum number of vertices that separate X from Y in G is equal to the maximum number of vertex-disjoint X-Y paths in G.

Corollary 2.3

Let G = (V,E) be a 2-connected graph with u, v, w, x, y ∈ V. If u ≠ v, w ≠ x and wx ∈ E, then (i) G contains a u-v path going through wx, and (ii) G contains a u-v path going through y.

Proof

Since G is 2-connected, no single vertex in V can separate {u, v} from {w, x}. It follows from Theorem 2.2 that there are two vertex-disjoint {u, v}- {w, x} paths P and Q in G. Note that P ∪ w x ∪ Q is a u-v path containing wx. Thus (i) holds. It is clear that (ii) follows from (i). □

Lemma 2.4

Let G be a k-commodity network (directed or undirected) with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$ . If G is paradox-free, then for any nonempty I ⊆ [k], each |I|-commodity network G ^′ (⊆G) with origin-destination pairs (s _i ,t _i ) _{i ∈ I} is paradox-free.

Proof

Suppose on the contrary that there exist I ⊆ [k] and |I|-commodity network G ^′ with origin-destination pairs (s _i , t _i ) _{i ∈ I} such that Braess’s paradox occurs in (G ^′, r ^′, ℓ ^′) for some r ^′=(r _i ) _{i ∈ I} and ℓ ^′. We construct an instance (G, r, ℓ) by defining r and ℓ as follows:

• $r_{i}=r^{\prime }_{i}$ for all i ∈ I, and r _i =0 for all i ∈ [k]−I;

• $\ell _{e}(x)=\ell ^{\prime }_{e}(x)$ for each e ∈ E(G ^′), and ℓ _e (⋅) = ∞ for each e ∈ E(G)−E(G ^′).

It is easy to see that k(r) = k(r ^′), (G, r, ℓ) and (G ^′, r ^′, ℓ ^′) have the same NE flow (in a way of ignoring the commodities with zero demands), and $\ell _{i}(G,\mathbf {r})=\ell ^{\prime }_{i}(G^{\prime },\mathbf {r}^{\prime })$ for all i ∈ k(r). As Braess’s paradox occurs in (G ^′, r ^′, ℓ), there exist H ⊆ G ^′ ⊆ G and h ∈ k(r ^′) = k(r) such that $\ell _{h}(H,\mathbf {r})=\ell ^{\prime }_{h}(H,\mathbf {r}^{\prime })<\ell ^{\prime }_{h}(G^{\prime },\mathbf {r}^{\prime })=\ell _{h}(G,\mathbf {r})$ and $\ell _{i}(H,\mathbf {r})=\ell ^{\prime }_{i}(H,\mathbf {r}^{\prime })\le \ell ^{\prime }_{i}(G^{\prime },\mathbf {r}^{\prime })=\ell _{i}(G,\mathbf {r})$ for all i ∈ k(r ^′)−{h} = k(r)−{h}, showing that Braess’s paradox occurs in (G, r, ℓ). The contradiction to paradox-freeness of G proves the lemma. □

The remainder of this section is devoted to the discussion on two-terminal series-parallel (di)graphs. The way of defining the series-parallel property [20] in terms of link traverse directions (see Definition 1.3(i)) is valid only for (undirected) graphs. It can not be extended to digraphs. On the other hand, the series-parallel property can be uniformly defined for both graphs and digraphs in the following recursive way.

Definition 2.5

A single-commodity network G with origin-destination pair (s, t) is two-terminal series-parallel or s-t series-parallel if

• (i) G has a single link with ends s and t; or

• (ii) G is obtained by connecting two smaller o _i - d _i series-parallel networks H _i , i = 1,2, in series – identifying d ₁ and o ₂, and naming o ₁ as s, and d ₂ as t; or

• (iii) G is obtained by connecting two smaller o _i - d _i series-parallel networks H _i , i = 1,2, in parallel – identifying o ₁ and o ₂ to form s and identifying d ₁ and d ₂ to form t.

In the above definition, the vertices s and t are called the terminals of the series-parallel (di)graph G. The equivalence of Definitions 2.5 and Definition 1.3 was proved by Milchtaich [20].³ The above recursive definition implies polynomial time recognition algorithms for recognizing two-terminal series-parallel (di)graphs [27]. It is well-known that each series-parallel graph of at least two edges has either a degree 2 vertex or a pair of parallel edges. The following observation on two-terminal series-parallel digraphs will be useful in our proofs.

Lemma 2.6

Let G be a two-terminal series-parallel digraph with at least two arcs. Then G contains either a pair of parallel arcs or a vertex whose indegree and outdegree are both one.

Proof

We prove the lemma by induction on the number m of arcs in G. The base case where G has exactly two arcs is trivial. We assume that m ≥ 3 and the lemma holds for all two-terminal series-parallel networks with at least 2 and at most m−1 arcs. Since m ≥ 2, there exist two smaller two-terminal series-parallel digraphs H ₁ and H ₂ whose connection in series or in parallel gives G. Suppose without loss of generality that H ₁ has at least two arcs. It follows that H ₁ satisfies our lemma, because H ₁ has fewer edge than G. Clearly, any pair of parallel arcs of H ₁ is the one in G. Moreover, if a vertex v has exactly one in-neighbor and exactly one out-neighbor in H ₁, then v cannot be a terminal of H ₁, and therefore cannot have any neighbors in H ₂. Thus G satisfies the lemma. □

Corollary 2.7

Let G=(V,E) be an irredundant single-commodity undirected network with origin-destination pair (s,t). For any distinct vertexes u, v ∈ V, G contains two vertex-disjoint {s,t}- {u,v} paths.

Proof

Since u ≠ v, and each of u and v is contained in an s-t path of G, it is easy to see that no single vertex of G can sperate {s, t} from {u, v}. The conclusion is instant from Theorem 2.2. □

For any s-t series-parallel (di)graph G, let U(G) denote the set of its cut-vertices, and $\mathcal {B}(G)$ the set of its blocks. Let s-t block graph of G be defnined as a graph with vertex set $\{s.t\}\cup U(G)\cup \mathcal {B}(G)$ and edge set $\{vB:v\in B,v\in \{s,t\}\cup U(G),B\in \mathcal {B}(G)\}$. Note that the definition of s-t block graphs here is slightly different from that of standard block graphs in textbook (see, e.g., page 56 of [9]). The next observation concerns with the block-chain structure of two-terminal series-parallel (di)graphs. See Fig. 4 for an illustration of the directed case. (The undirected case is visualized by ignoring the arc directions.)

Fig. 4

The block structures of two-terminal series-parallel networks

Lemma 2.8

Let G is an s-t series-parallel (di)graph. If $p=|\mathcal {B}(G)|$ , then the s-t block graph of G is a path of form v ₁ B ₁ v ₂ …v _i B _i v _i+1 …v _p B _p v _p+1 such that the following hold:

• (i) v ₁ = s, v _p+1 = t, and U(G) = {v ₂ ,…,v _p } if and only if U(G) ≠ ∅ if and only if p ≥ 2;

• (ii) each s-t path in G goes through v ₁, v ₂ ,…,v _p in this order;

• (iii) $\mathcal {B}(G)=\{B_{1},\ldots ,B_{p}\}$;

• (iv) for each i ∈ [p], B _i is a v _i - v _i+1 series-parallel (di)graph; and

• (v) for each i ∈ [p] and each v _i - v _i+1 path P, either B _i is a link or B _i contains a v _i - v _i+1 path Q such that P and Q are internally disjoint.

Proof

By Definition 2.5, it suffices to consider G obtained by connecting two smaller o _i - d _i series-parallel networks H _i (i = 1,2) in series or in parallel. In the former case, the result follows from applying inductions on H ₁ and H ₂. In the latter case, G is 2-connected, $\mathcal {B}(G)$ is G itself, and the statements (i)–(iv) are trivially true. To see (v), suppose without loss of generality that P ⊆ H ₁. Then we may take Q to be any o ₂- d ₂ path, i.e., s-t path, in H ₂. □

3 Single-Commodity Networks

In view of Milchtaich’s characterization for undirected networks [20], in this section we mainly focus on single-commodity directed networks, while leaving a brief discussion on the undirected case to the end of this section.

We study single-commodity directed network G = (V, E) with origin-destination pair (s, t). Without loss of generality, we may assume that G is irredundant, which particularly implies that G is connected. We will characterize paradox-freeness of G with s-t series-parallel property. Our efforts are mainly devoted to proving the necessity of the property.

In Milchtaich’s proof for undirected networks (Proposition 1 of [20]), the embedding of $\mathbb {u}(G_{a})$ (see Fig. 1a for G _a ) in a single-commodity undirected network implies the network is paradox-ridden, while such an embedding is implied by a special pair of distinct vertices u, v such that u precedes v in an s-t path and follows v in another s-t path of the network. To derive such u, v, Milchtaich used the property that the graph has two s-t paths which go through an edge in opposite directions. Such a property is lost when considering digraphs. This is the main hurdle to extending Milchtaich’s proof to digraphs.

To get around the difficulty, our first step is to use the existence of a cycle to derive that of a special pair of vertices in G (Lemma 3.1), which in turn gives the occurrence of Braess’s paradox (Lemmas 3.3 and 3.4). Our second step is to derive Braess’s paradox in acyclic G that is not s-t series-parallel. We translate edge traverses in opposite directions in graphs into the existences of s-t paths through reversed arcs in digraphs; instead of relying on the special pair of vertices, we derive Braess’s paradox directly using an inductive argument that carefully exploits the properties of digraphs (Theorem 3.5).

Lemma 3.1

If there is a cycle in G, then there exist s-t paths $P,Q\in \mathcal {P}$ and distinct vertices u,v ∈ V(P)∩V(Q) such that u precedes v in P and u follows v in Q, i.e., u≺ _P v and v≺ _Q u.

Proof

Assume on the contrary that no such P, Q and u, v stated in the lemma exist. Let C = v ₁ v ₂…v _m v ₁ be a cycle in G. For each 2 ≤ i ≤ m, let C[v ₁, v _i ] stand for the unique v ₁- v _i path in the directed cycle C. Since G is an irredundant network, every arc (v _i , v _i+1) of C is contained in some s-t path $Q_{i}\in \mathcal {P}$, i = 1,2,…,m, where (v _m , v _m+1)=(v _m , v ₁).

If Q ₁[s, v ₂) and Q ₂(v ₂, t] have some vertex in common, say u, then our contradiction assumption is violated by $u\prec _{Q_{1}}v_{2}$ and $v_{2}\prec _{Q_{2}} u$. Hence Q ₁[s, v ₂] and Q ₂[v ₂, t] intersect only at vertex v ₂, and their concatenation forms an s-t path Q ₁[s, v ₂] ∪ Q ₂[v ₂, t] containing C[v ₁, v ₃], which we write as Q _1,2. Then we consider Q _1,2[s, v ₃] and Q ₃[v ₃, t]. They, by our contradiction assumption, intersect only at v ₃ (otherwise $u\prec _{Q_{1,2}}v_{3}$ and $v_{3}\prec _{Q_{3}} u$ for some vertex u ∈ Q _1,2[s, v ₃) ∩ Q ₃(v ₃, t]), and their concatenation forms an s-t path Q _1,2,3: = Q _1,2[s, v ₃] ∪ Q ₃[v ₃, t] containing C[v ₁, v ₄]. Continuing this way, we concatenate Q _1,2,…,i [s, v _i+1] and Q _i+1[v _i+1, t] to obtain an s-t path Q _1,2,…,i+1 containing C[v ₁, v _i+2] for i = 1,2,…,m−2 inductively. In particular Q _{1,2,…,m−1} contains C[v ₁, v _m ], implying that v ₁ precedes v _m in $Q_{1,2,\ldots ,m-1}\in \mathcal {P}$. However v ₁ follows v _m in $Q_{m}\in \mathcal {P}$. The contradiction to our assumption establishes the lemma. □

Definition 3.2

We call G an s-t paradox if G = P ₁ ∪ P ₂ ∪ P ₃ is the union of three paths P ₁, P ₂ and P ₃ with the following properties:

• (i) P ₁ is an s-t path going through distinct vertices a, u, v, b in this order, i.e., $s\preceq _{P_{1}} a\prec _{P_{1}}u\prec _{P_{1}}v\prec _{P_{1}}b\preceq _{P_{1}} t$;

• (ii) P ₂ is an a-v path with V(P ₂) ∩ V(P ₁)={a, v};

• (iii) P ₃ is a u-b path with V(P ₃) ∩ V(P ₁)={u, b} and V(P ₃) ∩ V(P ₂) = ∅.

The s-t paradox defined above is often denoted as (P ₁, P ₂, P ₃). As illustrated in Fig. 5, P ₂ and P ₃ are vertex-disjoint, and they intersect with P ₁ only at their ends. Observe that G _a in Fig. 1a is an s-t paradox (s u v t, s v, u t) with s = a and t = b.

Fig. 5

An s-t paradox (P ₁, P ₂, P ₃)

Lemma 3.3

If G contains an s-t paradox, then G is paradox-ridden.

Proof

Let G ^′=(V ^′, E ^′) = P ₁ ∪ P ₂ ∪ P ₃ be an s-t paradox (P ₁, P ₂, P ₃) contained in G = (V, E). In the subdigraph G ^′, let e ₁ and e ₂ be the two outgoing arcs from a with e ₁ ∈ P ₁ and e ₂ ∈ P ₂, and let e ₃ and e ₄ be the two incoming arcs to b with e ₃ ∈ P ₁ and e ₄ ∈ P ₃. We define routing instance (G,1,ℓ) by ℓ _e (x) = x if e ∈ {e ₁, e ₃}, ℓ _e (x) = 1 if e ∈ {e ₂, e ₄}, ℓ _e (x) = 0 if e ∈ E ^′−{e ₁, e ₂, e ₃, e ₄}, and ℓ _e (x) = ∞ if e ∈ E−E ^′. See Fig. 5 for an illustration. The unique NE in (G,1,ℓ) sends the one-unit flow all through path P ₁ and suffers from a latency $\ell (G,1)=\ell _{e_{1}}(1)+\ell _{e_{3}}(1)=2$. Let subnetwork H of G be obtained from G by removing an arc e on P ₁[u, v]. Then the unique NE in (H,1,ℓ) splits the one-unit flow equally at vertex a, sending a half via path P ₂[a, v] ∪ P ₁[v, t] and the other half via path P ₁[a, u] ∪ P ₃[u, b] ∪ P ₁[b, t]. This incurs a latency ℓ(H, 1) = 1 + 0.5 = 1.5, showing a Braess’s paradox. □

Lemma 3.4

If there is a cycle in G, then G contains an s-t paradox.

Proof

By Lemma 3.1, there exist s-t paths $P,Q\in \mathcal {P}$ and distinct vertices u, v ∈ V(P) ∩ V(Q) such that u precedes v in P and u follows v in Q. Let such P, Q, u, v be taken such that Q[v, u] is as long as possible. It follows from the maximality of Q[v, u] that

• (i) Q[s, v) and P[u, t] are vertex-disjoint.

Suppose otherwise Q[s, v) and P[u, t] have a common vertex w. Note from u ∈ Q(v, t] that w ≠ u. It follows that we should have chosen P, Q, u, w instead of P, Q, u, v because Q[w, u] properly contains Q[v, u]. So (i) holds. A symmetric argument shows the following,

• (ii) Q(u, t] and P[s, v] are vertex-disjoint.

Consider a traverse of Q from s to t. Let a be the last vertex on Q[s, v) with a ∈ P, meaning Q(a, v) ∩ P = ∅; let b be the first vertex on Q(u, t] with b ∈ P, meaning Q(u, b) ∩ P = ∅. It follows from (i) that a ∈ P[s, u), and from (ii) that b ∈ P(v, t] (See Fig. 5 for an illustration with P ₁ = P, P ₂ = Q[a, v] and P ₃ = Q[u, b]). It can be seen from the choices and positions of a and b that P, Q(a, v) and Q(u, b) are pairwise vertex-disjoint, implying that P ∪ Q[a, v] ∪ Q[u, b] is an s-t paradox (P, Q[a, v],Q[u, b]) contained in G. □

For any arc subset K ⊆ E, let G〈K〉 be the digraph obtained from G by reversing the directions of all arcs in K. The set of reversed arcs is written as $\bar K$.

Theorem 3.5

If G does not contain any s-t paradox, then G is s-t series-parallel.

Proof

As G contains no s-t paradox, it follows from Lemma 3.4 that G is acyclic. Therefore by Lemma 2.1, we have

• (i) for any u, v, w ∈ V and any u-v path P _{u v} and v-w path P _{v w} in G, P _{u v} ∪ P _{v w} is a u-w path in G.

By Definition 1.3, digraph G is s-t series-parallel if and only if its underlying graph $\mathbb {u}(G)$ has no pair of s-t paths which go through some edge in opposite directions. Recall that each arc of G is contained in some s-t path in G. To justify the theorem, it suffices to prove the equivalent statement that for any nonempty subset K of E, there is no s-t path in G〈K〉 going through some arc in $\bar K$.

By contradiction, we assume on the contrary that there is ∅ ≠ K ⊆ E with minimum |K| such that G〈K〉 contains an s-t path P going through some arc in $\bar K$. The minimality of K implies that $\bar K\subseteq P$, and $\bar K$ induces a number of, say m, subpaths of P from v _i to w _i , i = 1,2,…,m, where v _i ≺ _P w _i ≺ _P v _i+1≺ _P w _i+1 for all i = 1,2,…,m−1. Notice that

• (ii) the reverse of P[v _i , w _i ] is a path $\bar P[w_{i},v_{i}]=(V_{i},E_{i})$ in G for each i ∈ [m];

• (iii) K is the disjoint union of E ₁, E ₂,…,E _m ;

• (iv) P[w _i , v _i+1], i = 0,1,…,m are paths in G, where w ₀ = s and v _m+1 = t;

• (v) for any i ∈ [m], there exists a v _i - v ₁ path Q _i in G.

Statements (ii)–(iv) are straightforward observations. See Fig. 6 for an illustration. We prove (v) by induction on i. The base case i = 1 is trivial. Suppose that 2 ≤ i ≤ m and there is a v _h - v ₁ path Q _h in G for each h ∈ [i−1].

Fig. 6

The path P in G〈K〉, where arcs in G and K are drawn as solid and dotted ones, respectively

Since G is an irredundant network, it contains a v _i -t path Q. If Q and P[s, v _i ) are vertex-disjoint, then P[s, v _i ] ∪ Q is an s-t path in $G\langle \cup _{h=1}^{i-1}E_{i}\rangle$ going through $\cup _{h=1}^{i-1}\bar E_{h}$. However $\emptyset \ne \cup _{h=1}^{i-1}E_{h}\varsubsetneq \cup _{h=1}^{m}E_{h}$ and (iii) imply a contradiction to the minimality of K. Hence

• P(s, v _i ) and Q(v _i , t) have some vertex in common, say c.

Observe from (iv) and (i) that P[w _i−1, v _i ] ∪ Q is a path in G, implying that P[w _i−1, v _i ) and Q are vertex-disjoint, and

• c ∈ P(s, w _i−1) ∩ Q(v _i , t).

Note that c ∈ P[w _h−1, w _h ) for some h ≤ i−1. By (iv) and (ii), the subdigraph $P[w_{h-1},v_{h}]\cup \bar P[w_{h},v_{h}]$ of G contains a c- v _h path, written as R. Consider the concatenation of R and the v _h - v ₁ path Q _h (whose existence is guaranteed by the inductive hypothesis). We see from (i) that R ∪ Q _h is a c- v ₁ path in G. In turn we concatenate the v _i -c path Q[v _i , c] and the c- v ₁ path R ∪ Q _h into a v _i - v ₁ path in G, which establishes (v).

Applying (ii) and (v) with i = m, we deduce from (i) that $S_{w_{m}v_{1}}=\bar P[w_{m},v_{m}]\cup Q_{m}$ is a w _m - v ₁ path in G. Since G is an irredundant network, it contains an s- w _m path $S_{sw_{m}}$ and a v ₁-t path $S_{v_{1}t}$. By (i), $S=S_{sw_{m}}\cup S_{w_{m}v_{1}}\cup S_{v_{1}t}$ is an s-t path in G satisfying s≺ _S w _m ≺ _S v ₁≺ _S t. Observe that w _m , v ₁ ∈ P ∩ S. This enables us to take distinct vertices u, v ∈ P ∩ S such that

• u≺ _S v and v≺ _P u,

• P[v ₁, w _m ] ⊆ P[v, u], and

• P[v, u] is as long as possible.

Notice from s≼ _S u≺ _S v≼ _S t that v ≠ s and u ≠ t. Recall from (iv) that P[s, v ₁] ∪ P[w _m , t] = P[w ₀, v ₁] ∪ P[w _m , v _m+1] ⊆ G. From P[v ₁, w _m ] ⊆ P[v, u], we derive

• (vi) P[s, v] ∪ P[u, t] ⊆ G.

The maximality of P[v, u] enforces that

• (vii) P[s, v) ∩ S[u, t] = ∅ and P(u, t] ∩ S[s, v] = ∅.

Otherwise we should have taken v to be some vertex v ^′ ∈ P[s, v) ∩ S(u, t), or u to be some vertex u ^′ ∈ P(u, t] ∩ S(s, v). See Fig. 6 for the positions of the contradictory v ^′ and u ^′ on P.

Consider a traverse of P from s to t. Let a be the last vertex of P[s, v) with a ∈ S, meaning that P(a, v) ∩ S = ∅ (such a vertex a exists because s ∈ P[s, v) ∩ S as v ≠ s). Let b be the first vertex of P(u, t] with b ∈ S, meaning P(u, b) ∩ S = ∅ (such a vertex b exists because t ∈ P(u, t] ∩ S as u ≠ t). It follows from (vii) that a ∈ S[s, u) and b ∈ S(v, t], giving a≺ _S u≺ _S v≺ _S b. Thus, by (vi), we see that (S, P[a, v],P[u, b]) is an s-t paradox in G. The contradiction completes the proof of the theorem. □

We are now ready to prove the directed case of Theorem 1.4, restated as follows.

Theorem 3.6

An irredundant single-commodity directed network G is paradox-free if and only if it is two-terminal series-parallel.

Proof

If G is paradox-free, then, by Lemma 3.3, G contains no s-t paradox, which along with Theorem 3.5 implies that G is s-t series-parallel.

Conversely, if G is s-t series-parallel, then $\mathbb {u}(G)$ is s-t series-parallel by Definition 1.3. It can be seen from the definition that $\{\mathbb {u}(P):P\in \mathcal {P}\}$ is exactly the set of s-t paths in $\mathbb {u}(G)$. Suppose for a contradiction that there exist H ⊆ G, traffic demand r and nonnegative, continuous, nondecreasing latency functions ℓ _e , e ∈ E such that ℓ(H, r) < ℓ(G, r). For each edge e of $\mathbb {u}(G)$, set $\underline {\ell }_{e}(\cdot )=\ell _{e^{\prime }}(\cdot )$ where e is the underlying edge of the arc e ^′∈E. Then $\underline {\ell }(\mathbb {u}(H), r)=\ell (H, r)<\ell (G, r)=\underline {\ell }(\mathbb {u}(G),r)$, exhibiting a Braess’s paradox in $\mathbb {u}(G)$. We deduce from the undirected case of Theorem 1.4 that $\mathbb {u}(G)$ is not s-t series-parallel. The contradiction proves the theorem. □

The sufficiency stated in the above theorem has an alternative proof based on Milchtaich’s work [20]. Milchtaich’s model for single-commodity undirected network allows a class of latency functions wider than ours; in particular, two (different) functions are defined for each edge e, one specifying the latency of passing e from its end u to its end v and the other specifying the latency of passing e from v to u. This class of latency functions brings a kind of directionality into Milchtaich’s model – Regardless of how the edges in a two-terminal series-parallel undirected network are directed and their latencies are defined, Braess’s paradox does not occur. To be more specific, given any routing instance in a single-commodity directed network G, let us consider its corresponding instance in the underlying graph $\mathbb {u}(G)$ under Milchtaich’s model. For each edge of $\mathbb {u}(G)$, the latency function of its corresponding arc is associated with passing the edge in the direction the same as the arc, and an infinite latency function is given to passing the edge in the opposite direction. Then Braess’s paradox occurs in the routing instance in $\mathbb {u}(G)$ if and only if so does in the routing instance in G. If G is two-terminal series-parallel, then so is $\mathbb {u}(G)$. Milchtaich’s result [20] implies that the undirected instance does not admit any Braess’s paradox, and we derive the same for the directed instance.

A Remark on Single-Commodity Undirected Networks

As mentioned above, the class of latency functions investigated in Milchtaich’s paper [20] is wider than the one in this paper. Milchtaich defined Braess’s paradox free undirected networks with respect to this wider class of functions, and characterized these networks with the two-terminal series-parallel property. While the sufficiency of Theorem 1.4 (the undirected case) is immediate from Milchtaich’s original theorem (Theorem 1 of [20]), the necessity can only follow from Milchtaich’s proof, where only our class of latency functions (i.e., nonnegative, continuous, and nondecreasing ones) was used for constructing Braess’s paradox.

4 Multicommodity Networks

In this section we study k-commodity network G = (V, E) with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$, where k ≥ 2. For convenience, we assume that G is an irredundant network. We are to prove that the series-parallel condition and coincident condition (see Theorem 1.6) are necessary and sufficient for G to be paradox-free.

By virtue of the block chain structure of series-parallel (di)graphs, the sufficiency proof, which builds on the result for single-commodity (Theorem 1.4), turns out to be easier than the necessity part.

Theorem 4.1

Let G be an irredundant multicommodity network. If G satisfies the series-parallel condition and the coincident condition, then G is paradox-free.

Proof

Given any nonnegative traffic demand vector $\mathbf {r}=(r_{i})_{i=1}^{k}$ and nonnegative, continuous and nondecreasing latency functions ℓ, suppose that H is a subnetwork of (G, k(r)). Let $\mathbf {g}=(\mathbf {g}_{i})_{i=1}^{k}$ and $\mathbf {h}=(\mathbf {h}_{i})_{i=1}^{k}$ be the NE of (G, r, ℓ) and (H, r, ℓ), respectively.

Consider an arbitrary commodity i ∈ k(r). Since G _i is s _i - t _i series-parallel, by Lemma 2.8, we suppose that the s _i - t _i block graph of G _i is v ₁ B ₁ v ₂…v _p B _p v _p+1, where s _i = v ₁ and t _i = v _p+1.

For each q ∈ [p], recall from Lemma 2.8(iv) that B _q is a v _q - v _q+1 series-parallel (di)graph. We consider it as a single-commodity network with origin-destination pair (v _q , v _q+1). Set traffic demand $r^{(q)}={\sum }_{j:B_{q}\subseteq G_{j}}r_{j}$. Let ℓ ^(q) denote the restriction of ℓ to the links in B _q . Since H is a subnetwork of (G, k(r)), it contains at least an s _i - t _i path. Every such s _i - t _i path intersects B _q with a v _q - v _q+1 path, implying that H _q = B _q ∩ H is nonempty. Furthermore, it follows from the coincidence condition that H _q contains all v _q - v _q+1 paths in H. Since g is the NE for (G, r, ℓ), its restriction to B _q , denoted as g ^(q), is the NE for (B _q , r ^(q), ℓ ^(q)), where $g^{(q)}(P)={\sum }_{j:P\subseteq G_{j}}{\sum }_{Q:P\subseteq Q\in \mathcal {P}_{j}}g_{j}(Q)$ for each v _q - v _q+1 path in B _q . Similarly, the restriction of h to H _q , denoted as h ^(q), is the NE for (H _q , r ^(q), ℓ ^(q)), where $h^{(q)}(P)={\sum }_{j:P\subseteq G_{j}}{\sum }_{Q:P\subseteq Q\in \mathcal {P}_{j},Q\subseteq H}h_{j}(Q)$ for each v _q - v _q+1 path in H _q . As B _q is v _q - v _q+1 series-parallel, it follows from Theorem 1.4 that B _q is paradox-free, giving $\ell ^{(q)}_{P}(\mathbf {g}^{(q)})=\ell _{i}(B_{q},r^{(q)})\leq \ell _{i}(H_{q},r^{(q)})=\ell _{Q}^{(q)}(\mathbf {h}^{(q)})$ for any v _q - v _q+1 paths P, Q with g ^(q)(P) > 0 and h ^(q)(Q) > 0.

Now we have $\ell _{i}(G,\mathbf {r})= {\sum }_{q\in [p]} \ell ^{(q)}(B_{q},r^{(q)})\le {\sum }_{q\in [p]}\ell ^{(q)}(H_{q},r^{(q)})= \ell _{i}(H,\mathbf {r})$. By the arbitrary choice of i ∈ k(r), we deduce that G is paradox-free. □

For the necessity proof, we have the following observation, which provides us with series-parallel structure of each individual G _i , i ∈ [k] for further study on the coincident condition.

Corollary 4.2

If G is paradox-free, then G satisfies the series-parallel condition.

Proof

It is straightforward from Lemma 2.4 that all G _i (i ∈ [k]) are paradox-free, and then by Theorem 1.4, they all are two-terminal series-parallel. □

The rest of this section is devoted to the proof of paradox-freeness implying the coincident condition. In view of Lemma 2.4, we may focus on 2-commodity networks: the undirected ones are investigated in Section 4.1, while the directed ones are discussed in Section 4.2. In both undirected and directed cases, we derive Braess’s paradox assuming the coincident condition fails.

4.1 The Undirected Case

In this subsection, we investigate irredundant 2-commodity undirected network G. The following Lemma 4.3 plays an important role in our proof. It helps to verify the fact that the intersecting blocks of G ₁ and G ₂ are their common blocks. Then we cope with the different terminal sets of G ₁ and G ₂ by connecting them via carefully selected paths, and use these paths to construct Braess’s paradox as desired.

Lemma 4.3

For any i ∈ [2] and any distinct vertices u, v ∈ V _i , all u-v paths of G are contained in G _i .

Proof

By contradiction, let u-v path P be a counterexample to the lemma with a minimum number of edges. Then all vertices of P(u, v) are outside G _i . Recall from Corollary 2.7 that G _i contains vertex-disjoint {s _i , t _i }- {u, v} paths Q ₁ and Q ₂ with u ∈ Q ₁ and v ∈ Q ₂. It follows that Q ₁ ∪ P ∪ Q ₂ is an s _i - t _i path in G. Thus Q ₁ ∪ P ∪ Q ₂ ⊆ G _i by the definition of G _i . This gives a contradiction to the fact that P and G _i are arc-disjoint. □

Theorem 4.4

Let G be an irredundant 2-commodity undirected network. If G is paradox-free, then it satisfies the coincident condition.

Proof

Notice from Corollary 4.2 that G _i is an s _i - t _i series-parallel network for i = 1, 2. Suppose that E ₁ ∩ E ₂ ≠ ∅. Then we have an edge u v ∈ E ₁ ∩ E ₂, a block B ₁ of G ₁ with terminals a, b and a block B ₂ of G ₂ with terminals c, d such that u v ∈ B ₁ ∩ B ₂. Since B ₁ is 2-connected, by Corollary 2.3(i), each edge of B ₁ is on some u-v path of B ₁. Thus Lemma 4.3 enforces that B ₁ ⊆ G ₂. As B ₁ is 2-connected and have common edge uv with block B ₂ of G ₂, we have B ₁ ⊆ B ₂. A symmetric argument gives B ₂ ⊆ B ₁, implying B ₁ = B ₂. It remains to prove that {a, b}={c, d}. Assume the contrary that {a, b} ≠ {c, d}, which particularly implies that B ₁ = B ₂ is not an edge. We distinguish between two cases depending on whether there exist an a-b path and a c-d path with one containing the other. We derive contradictions in both cases by constructing Braess’s paradoxes.

Case 1

There are an a-b path and a c-d path in B ₁ such that one contains the other. Suppose without loss of generality that B ₁ contains an a-b path P with c, d ∈ P. As B ₁ is not an edge ab, it follows from Lemma 2.8(v) that there is an a-b path Q in B ₁ which is internally disjoint from P, i.e., P ∪ Q is a cycle.

Take an arbitrary edge e ₁ ∈ P[c, d] and an arbitrary edge e ₂ ∈ Q. Let latency functions ℓ be defined as follows: $\ell _{e_{1}}(x)=x$, $\ell _{e_{2}}(x)=2$, ℓ _e (x) = 3 for all edges e inside B ₁ but outside P ∪ Q, and ℓ _e (x) = 0 for edges e outside B ₁ and all edges e inside (P ∪ Q)∖{e ₁, e ₂}. See Fig. 7a for an illustration. Define r by r ₁ = r ₂=1.

Fig. 7

Braess’s paradoxes in 2-commodity undirected networks

On one hand, in the NE for (G, r, ℓ), when restricted to B ₁ = B ₂, commodity 1 only uses path P and commodity 2 only uses path P[c, d]. It follows that ℓ ₁(G, r) = ℓ ₂(G, r) = 2. On the other hand, consider the subgraph H obtained from G by removing an edge e ₃ inside P but outside P[c, d] (such an edge does exist because {a, b} ≠ {c, d}). Since e ₃ belongs to the cycle P ∪ Q ⊆ G, it can be seen that H = G∖e ₃ is a subnetwork of G. Observe that in any NE for (H, r, ℓ), when restricted to B ₁ ∩ H = B ₂ ∩ H, commodity 1 only uses path Q and commodity 2 only uses path P[c, d]. It follows that ℓ ₁(G, r) = 2 and ℓ ₂(G, r) = 1, showing the occurrence of Braess’s paradox in (G, r, ℓ).

Case 2

No a-b path in B ₁ contains any c-d path and no c-d path in B ₁ contains any a-b path. It follows that no a-b path in B ₁ contains {c, d} and no c-d path in B ₁ contains {a, b}. If a = d, then by Corollary 2.3(ii), there is an a-b path in B ₁ that passes through c, and this a-b path clearly contains a c-d path, a contradiction to the hypothesis of Case 2. Therefore a ≠ d, and symmetric arguments provide {a, b}∩{c, d} = ∅. Moreover, by Corollary 2.3(ii), we may take P to be an a-b path in B ₁ containing c and Q to be an a-b path in B ₁ containing d.

Consider a traverse of P from a to b. Let u denote the last common vertex of P[a, c) and Q, and v denote the first common vertex of P(c, b] and Q. Obviously u ≠ v, c ∈ P[u, v], and P[u, v] ∩ Q contains only two vertices u and v. Swapping u and v if necessary, we obtain

• (i) There exist distinct vertices u, v ∈ P ∩ Q such that a≼ _Q u≼ _Q v≼ _Q b, c ∈ P(u, v) and P[u, v] ∩ Q contains only u and v

See Fig. 7b for an illustration. Since no a-b path in B ₁ contains {c, d}, statement (i) enforces

• (ii) d ∈ Q(u, v).

By (i) and (ii), we may take edge e ₁ ∈ Q[u, d] and edge e ₂ ∈ P[c, v]. Let latency functions ℓ be defined as follows: $\ell _{e_{1}}(x)=x$, $\ell _{e_{2}}(x)=2$, ℓ _e (x) = 3 for all edges e inside B ₁ but outside P[u, v] ∪ Q, and ℓ _e (x) = 0 for edges e outside B ₁ and all edges e inside (P[u, v] ∪ Q)∖{e ₁, e ₂}. Define r by r ₁ = r ₂=1. Then in the NE for (G, r, ℓ), when restricted to B ₁ = B ₂, commodity 1 only uses the a-b path Q, and commodity 2 only uses the c-d path P[c, u] ∪ Q[u, d]. It follows that ℓ ₁(G, r) = ℓ ₂(G, r) = 2. On the other hand, consider the subgraph H obtained from G by removing an edge e ₃ ∈ Q[d, v] (such an edge does exist because of (ii)). It can be seen that H is a subnetwork of G, and in the NE for (H, r, ℓ), when restricted to B ₁ ∩ H = B ₂ ∩ H, commodity 1 only uses path Q[a, u) ∪ P[u, v] ∪ Q(v, b] and commodity 2 only uses path P[c, u] ∪ Q[u, d]. It follows that ℓ ₁(G, r) = 2 and ℓ ₂(G, r) = 1, showing the occurrence of Braess’s paradox in (G, r, ℓ). □

Remark 4.5

Suppose that G ₁ and G ₂ are both two-terminal series-parallel networks, and E ₁ ∩ E ₂ induces all coincident blocks of G ₁ and G ₂. It is easy to prove that these coincident blocks must be consecutive in the sequence of blocks of G ₁ (resp. G ₂) ordered according to the s ₁- t ₁ block graph of G ₁ (resp. the s ₂- t ₂ block graph of G ₂).

4.2 The Directed Case

In this subsection, we prove that paradox-freeness implies the coincident condition for irredundant 2-commodity directed network G. If G ₁ and G ₂ are two-terminal series-parallel, then, due to the directionality of G, coincident blocks of G ₁ and G ₂ are exactly their common blocks, because each block of G _i (i = 1,2) has a unique source, which must be its origin, and a unique sink, which must be its destination. In the proof of Theorem 4.4, Lemma 4.3 helps to obtain a quick proof for B ₁ = B ₂. As the lemma does not extend to digraphs, more elaborative operations of arc deletion and contraction will be employed in directed networks for reaching the conclusion of B ₁ = B ₂ (i.e., its failure implies occurrence of Baress’s paradox).

Given a 2-commodity network D (not necessarily irredundant), we use D _i (i = 1,2) to denote the maximum irredundant subnetwork of (D,{i}). The maximum irredundant subnetwork of D is D ₁ ∪ D ₂. Instead of focusing on irredundant directed networks with origin-destination pairs (s _i , t _i ) _{i = 1,2}, our proof considers the set $\mathfrak C$ of 2-commodity directed networks D (not necessarily irredundant) whose maximum irredundant subnetworks D ₁ ∪ D ₂ satisfy the coincident condition: if a block B ₁ of D ₁ and a block B ₂ of D ₂ have some arc in common, then B ₁ and B ₂ are identical, i.e., B ₁ = B ₂. Our goal is to prove $G\in \mathfrak C$ provided G is paradox-free.

Our argument employs arc deletion and contraction frequently. Let D be a digraph and e an arc of D. We write D∖e and D/e for the graphs obtained from D by deleting e and contracting e, respectively. If D ^′ is a subdigraph of D∖e, then both notations D ^′∖e and D ^′/e mean D ^′ itself.

Proof Outline

To prove $G\in \mathfrak C$, we use the minimum counterexample approach. Assuming $G\not \in \mathfrak C$ is a minimum (in term of the number of arcs) counterexample, for any e ∈ E, we have G∖e and G/e belong to $\mathfrak C$ whenever they are paradox-free subnetworks of G.

• The basic idea is to derive from $G\setminus e\in \mathfrak C$ or $G/e\in \mathfrak C$ either $G\in \mathfrak C$ or a Braess’s paradox in G, contradicting the assumption that $G\not \in \mathfrak C$ and G is paradox- free.

However, not all e ∈ E can help us to fulfill this task, because G/e might have many s _i - t _i paths P (i = 1, 2) such that neither P nor P ∪ {e} is an s _i - t _i path in G, meaning that G/e might be paradox-ridden and we could not have $G/e\in \mathfrak C$. This is where the inductive series-parallel property helps; it gives us a pair of arcs e ₁, e ₂ which are in parallel or in series in G ₁ (recalling Lemma 2.6). The case of parallel e ₁, e ₂ is easy. Most of our efforts are devoted to investigating series e ₁, e ₂. The argument is divided into the following main steps to prove:

• G ₂ contains e ₁ or e ₂, say e ₁.

• e ₁ is the only incoming or outgoing arc at the common end v of e ₁ and e ₂.

• G ₁ and G ₂ have a common arc other than e ₁ (otherwise a Braess’s paradox is obtained).

• for i = 1,2, the set of s _i - t _i path in G _i /e ₁ naturally correspond the set of s _i - t _i paths in G _i , implying G/e ₁ is paradox-free and thus $G/e_{1}\in \mathfrak C$.

Then the final contradiction $G\in \mathfrak C$ is reached due to $G/e_{1}\in \mathfrak C$ and e ₁ ∈ G ₁ ∩ G ₂.

Theorem 4.6

Let G be a 2-commodity directed network. If G is paradox-free, then $G\in \mathfrak C$.

Proof

By contradiction, let $G=(V,E)\not \in \mathfrak C$ be a counterexample to the theorem with minimum |E|. (The minimality of G instantly implies that G is irredundant.) Hence there exist a block B _i of G _i = (V _i , E _i ), i = 1,2 such that B ₁ and B ₂ have some arc e ^∗ in common, but B ₁ ≠ B ₂. It can be assumed without loss of generality that

$$B_{1} \nsubseteq B_{2} ,$$

which implies |E(B ₁)| ≥ 2 because e ^∗ ∈ B ₁ ∩ B ₂. Since G is paradox-free, it follows from Corollary 4.2 that both G ₁ and G ₂ are two-terminal series-parallel. In turn, Lemma 2.8(iv) says that both B ₁ and B ₂ are two-terminal series-parallel. We break our proof into a sequence of claims.

Claim 1

$B_{1} \nsubseteq G_{2}$.

Otherwise, B ₁ is contained by some block of G ₂. This block must be B ₂ because e ^∗ ∈ B ₁ and B ₂ is the (unique) block of G ₂ that contains e ^∗. However B ₁ ⊆ B ₂ gives a contradiction to $B_{1} \nsubseteq B_{2}$,

Claim 2

G∖e is paradox-free for any e ∈ E.

If there exists e ∈ E such that Braess’s paradox occurs in (G∖e, r, ℓ) for some r and ℓ. Extending ℓ by ℓ _e (x) = ∞, Braess’s paradox occurs in (G, r, ℓ), a contradiction to the assumption that G is paradox-free.

Claim 3

There exist distinct vertices u, v, w, and arcs e ₁ = (u, v), e ₂ = (v, w) in B ₁ such that e ₁ is the only incoming arc at v in G ₁, and e ₂ is the only outgoing arc from v in G ₁.

If it were not the case, then Lemma 2.6 applies to the two-terminal series-parallel network B ₁ with at least two arcs, and enforces that B ₁ contains a pair of parallel arcs e ₁ and e ₂. Switching e ₁ and e ₂ if necessary, we may assume e ₁ ≠ e ^∗. Clearly, D = G∖e ₁ is a 2-commodity network with origin-destination pairs (s _i , t _i ) _{i = 1,2}. Since D is paradox-free by Claim 2, we deduce from the minimality of $G\not \in \mathfrak C$ that $D\in \mathfrak C$. Therefore B ₁∖e ₁ and B ₂∖e ₁ are identical because they are blocks of D ₁ and D ₂, respectively, and both contain e ^∗. Notice from e ₂ ∈ B ₁∖e ₁ = B ₂∖e ₁ that e ₁ ∈ B ₂. Now e ₁ ∈ B ₁ ∩ B ₂ combined with B ₁∖e ₁ = B ₂∖e ₁ implies B ₁ = B ₂. The contradiction to $B_{1} \nsubseteq B_{2}$ justifies Claim 3.

Claim 4

B ₁/e _i is 2-connected for i = 1, 2.

The claim is an immediate corollary of Claim 3 and the 2-connectivity of B ₁.

Claim 5

G ₂ contains either e ₁ or e ₂.

Assuming the contrary, let D be obtained from G∖{e ₁, e ₂} by adding a new arc e ₀ = (u, w). It is clear that D is still a 2-commodity network with origin-destination pairs (s _i , t _i ) _{i = 1,2}, D ₁ = G ₁∖{e ₁, e ₂} ∪ {e ₀}, B ₁∖{e ₁, e ₂} ∪ {e ₀} is the block of D ₁ that contains e ^∗ (note that e ^∗∉{e ₁, e ₂}) and B ₂ ⊆ D ₂.

If Braess’s paradox occurs in some routing instance (D, r, ℓ ^′), then Braess’s paradox occurs in (G, r, ℓ), where $\ell _{e_{i}}(x)=\ell ^{\prime }_{e_{0}}(x)/2$ for i = 1,2 and $\ell _{e}(x)=\ell ^{\prime }_{e}(x)$ for all e ∈ E−{e ₁, e ₂}. The paradox-freeness of G implies that D is paradox-free, and the minimality of $G\not \in \mathfrak C$ implies $D\in \mathfrak C$. It follows from e ^∗ ∈ B ₂ ⊆ D ₂ that B ₁∖{e ₁, e ₂} ∪ {e ₀} ⊆ D ₂.

As e ₀ ∈ D ₂, there is an s ₂- t ₂ path P in D ₂ with e ₀ ∈ P. If v ∈ P[s ₂, u] or v ∈ P[w, t ₂], then, correspondingly, P[s ₂, v]∪(v w) ∪ P[w, t ₂] or P[s ₂, u]∪(u v) ∪ P[v, t ₂] is an s ₂- t ₂ path in G containing e ₂ or e ₁, showing a contradiction to our assumption that e ₁, e ₂∉G ₂. So v∉P and P∖e ₀ ∪ {e ₁, e ₂} = P[s ₂, u]∪(u v w) ∪ P[w, t ₂] is an s ₂- t ₂ path in G, again a contradiction to e ₁, e ₂∉G ₂. Thus Claim 5 holds.

Reversing the directions of all arcs if necessary, we may assume without loss of generality that e ₁ ∈ G ₂. Since v is incident with both an incoming arc e ₁ ∈ E ₁ ∩ E ₂ and an outgoing arc e ₂ ∈ E ₁, we see that

$$ v\not\in\{s_{1},t_{1},s_{2}\}. $$

(1)

Claim 6

e ₁ is the only incoming arc at v in G.

Assume on the contrary that there exists an arc e ₀ ∈ E−{e ₁} which is incoming at v. Since G = G ₁ ∪ G ₂, it follows from Claim 3 that e ₀ ∈ G ₂. Note that e ₀∉G ₁. As e ₁ ∈ G ₂, we consider an s ₂- t ₂ path in G ₂ that passes through e ₁. This path clearly avoids e ₀; it is thus an s ₂- t ₂ path in D = G∖e ₀. It follows that D is a 2-commodity network with origin-destination pairs (s _i , t _i ) _{i = 1,2}, and e ₁ ∈ D ₂. Since D is paradox-free by Claim 2, and it has fewer arcs than G, we have $D\in \mathfrak C$. Note that D ₁ = G ₁, D ₂ ⊆ G ₂∖e ₀, and B ₁ is the block of D ₁ containing e ₁. We deduce from $D\in \mathfrak C$ and e ₁ ∈ D ₂ that B ₁ is the block of D ₂ which contains e ₁. It follows that B ₁ ⊆ D ₂ ⊆ G ₂∖e ₀ ⊆ G ₂, a contradiction to Claim 1. Hence Claim 6 holds.

Claim 7

E(B ₁) ∩ E(G ₂) ≠ {e ₁}.

Suppose on the contrary that E(B ₁) ∩ E(G ₂)={e ₁}. We construct routing instance (G, r, ℓ) in which Braess’s paradox occurs. Recall that B ₁ is a two-terminal series-parallel network with at least two arcs. Let a and b be the origin and destination of B ₁, respectively. It follows from Lemma 2.8(v) that B ₁ contains two internally-disjoint a-b paths P and Q such that e ₁ ∈ P. By Claim 3, we have e ₂ ∈ P. Take e ₃ to be an arbitrary arc in Q. Let R be an s ₂- t ₂ path in G ₂ that goes through e ₁. Let latency functions ℓ be defined as follows (see Fig. 8):

• $\ell _{e_{1}}(x)=x$,

• $\ell _{e_{3}}(x)=2$,

• ℓ _e (x) = 0 for all arcs e ∈ P ∪ Q ∪ R∖{e ₁, e ₃},

• ℓ _e (x) = ∞ for all arcs e ∈ B ₁∖E(P ∪ Q), and

• ℓ _e (x) = 2 for all arcs e ∈ G∖E(R ∪ B ₁).

Fig. 8

A Braess’s paradox in 2-commodity directed network

Note that the latencies of arcs outside B ₁ are constants, either 0 or 2. Thinking of them as arc lengths, let α and β denote the length of a shortest s ₁-a path in G ₁∖E(B ₁) and that of a shortest b- t ₁ path in G ₁∖E(B ₁), respectively.

Let the demand vector be defined as r = (1,1). In the NE of (G, r, ℓ), commodity 1 chooses path P in B ₁ and chooses an s ₁-a path of latency α and a b- t ₁ path of latency β outside B ₁; commodity 2 chooses path R. We have ℓ ₁(G, r) = α+2 + β and ℓ ₂(G, r) = 2. Now consider the subdigraph H = G∖e ₂. In the NE of (H, r, ℓ), commodity 1 chooses Q in B ₁, giving ℓ ₁(H, r) = α+2 + β; commodity 2 chooses R, giving ℓ ₂(H, r) = 1. This shows that Braess’s paradox occurs in (G, r, ℓ). The contradiction to the condition that G is paradox-free verifies Claim 7.

Instantly, e ₁ ∈ G ₂ and Claims 6 and 7 imply that either u ≠ s ₂ or v ≠ t ₂. It follows that D = G/e ₁ is a 2-commodity network with origin-destination pairs (s _i , t _i ) _{i = 1,2}. For i = 1,2, let $\mathcal {Q}_{i}$ denote the set of s _i - t _i paths in D. By abuse of notation, we shall identify a digraph with its arc set. Claim 6 enables us to construct for i = 1,2 a 1-1 correspondence φ _i between $\mathcal {Q}_{i}$ and $\mathcal {P}_{i}$ as follows: For any $Q\in \mathcal {Q}_{i}$.

$$\varphi_{i}(Q)=\left\{\begin{array}{ll}Q&\text{if }Q\in\mathcal{P}_{i};\\ Q\cup\{e_{1}\}&\text{otherwise.} \end{array} \right. $$

(2)

Claim 8

For i = 1, 2, φ _i is a 1-1 correspondence between $\mathcal {Q}_{i}$ and $\mathcal {P}_{i}$.

To see φ _i is a mapping from $\mathcal {Q}_{i}$ and $\mathcal {P}_{i}$, it suffices to consider the case where $Q\not \in \mathcal {P}_{i}$ for some $Q\in \mathcal {Q}_{i}$. From D = G/e ₁, we deduce that Q (as a subset of E) consists of two vertex disjoint paths Q[s _i , u ^′] and Q[v ^′, t _i ] in G, where {u ^′, v ^′}={u, v}. If u ^′ = v, then v∉{s ₁, s ₂} in (1) implies that v = u ^′ has an incoming arc on Q[s _i , u ^′] which is different from e ₁, a contradiction to Claim 6. So it must be the case that u ^′ = u and v ^′ = v, giving $Q\cup \{e_{1}\}\in \mathcal {P}_{i}$.

It is clear that φ _i is injective. To see it is also surjective, we consider an arbitrary $P\in \mathcal {P}_{i}$. In case of e ₁∉P, Claim 6 and (1) imply v∉P. Therefore $P\in \mathcal {Q}_{i}$, and φ _i (P) = P. In case of e ₁ ∈ P, we have $P/e_{1}\in \mathcal {Q}_{i}$, and φ _i (P/e ₁) = P. This proves Claim 8.

For i = 1,2, the above proof also gives the inverse of φ _i as follows: For any $P\in \mathcal {P}_{i}$.

$$\begin{array}{@{}rcl@{}} \varphi_{i}^{-1}(P)=\left\{\begin{array}{ll}P&\text{if }e_{1}\not\in P;\\ P/e_{1}&\text{otherwise.} \end{array} \right. \end{array} $$

(3)

Claim 9

D = G/e ₁ is paradox-free.

Suppose on the contrary that Braess’s paradox occurs in (D, r, ℓ ^′) for some r and ℓ ^′, i.e., there exists a subnetwork F of (D, k(r)) and {g, h}={1,2} such that

$$ \ell^{\prime}_{g}(F,\mathbf{r})<\ell^{\prime}_{g}(D,\mathbf{r})\; \text{and}\; \ell^{\prime}_{h}(F,\mathbf{r})\le\ell^{\prime}_{h}(D,\mathbf{r}). $$

(4)

Define $\ell _{e_{1}}(x)=0$ and $\ell _{e}(x)=\ell _{e}^{\prime }(x)$ for every e ∈ E−{e ₁}. It is clear that r is not a zero vector. We show that Braess’s paradox occurs in (G, r, ℓ).

For each subnetwork X of (D, k(r)), we write φ(X) for the subdigraph $\cup _{i=1,2}(\cup _{Q\subseteq X,Q\in \mathcal {Q}_{i}}\varphi _{i}(Q))$ of G (recalling Claim 8). Since G is an irredundant network, we have φ(X) = G if and only if X = D. Given any flow x = (x ₁, x ₂) for (X, r, ℓ ^′), let φ(x) be the flow y = (y ₁, y ₂) for (φ(X),r, ℓ) defined by: y _i (φ(Q)) = x _i (Q), i = 1,2, for each $Q\in \mathcal {Q}_{i}$ with Q ⊆ X. It follows from the definition of ℓ that $\ell _{\varphi (Q)}(\mathbf {y})=\ell ^{\prime }_{Q}(\mathbf {x})$ for all $Q\in \mathcal {Q}_{i}$ (i = 1,2) with Q ⊆ X. Hence, it can be seen from Definition 1.1 that φ(x) is a NE for (φ(X),r, ℓ) whenever x is a NE for (X, r, ℓ ^′).

Considering the NE flows d and f for (D, r, ℓ ^′) and (F, r, ℓ ^′), respectively, we see that φ(d) is the NE for (φ(D),r, ℓ) = (G, r, ℓ) with $\ell _{i}(G,\mathbf {r})=\ell ^{\prime }_{i}(D,\mathbf {r})$ for i = 1,2, and φ(f) is the NE for (φ(F),r, ℓ) with $\ell _{i}(\varphi (F),\mathbf {r})=\ell ^{\prime }_{i}(F,\mathbf {r})$ for i = 1, 2. It follows from (4) that Braess’s paradox occurs in (G, r, ℓ). The contradiction establishes Claim 9.

Claim 10

D _i = G _i /e ₁ for i = 1, 2.

On one hand, for each arc e of D _i , there exists $Q\in \mathcal {Q}_{i}$ such that e ∈ Q. It is clear from (2) that $e\in \varphi _{i}(Q)\in \mathcal {P}_{i}$ and e ∈ φ _i (Q)/e ₁ ⊆ G _i /e ₁. On the other hand, for each arc e of G _i /e ₁, there exists $P\in \mathcal {P}_{i}$ such that e ∈ P. Therefore $e\in \varphi ^{-1}(P) \in \mathcal {Q}_{i}$ by (3), saying e ∈ D _i . So Claim 10 holds.

The combination of Claim 9 and the minimality of $G\not \in \mathfrak C$ gives $D =G/e_{1}\in \mathfrak C$. Recall from Claim 7 that B ₁/e ₁ and G ₂/e ₁ have some arc in common. By Claim 10 it is equivalent to saying that B ₁/e ₁ and D ₂ have some arc in common.

Observe that B ₁/e ₁ is a subdigraph of G ₁/e ₁ = D ₁ (by Claim 10). Recall from Claim 4 that B ₁/e ₁ is 2-connected. So B ₁/e ₁ is contained in a block B of D ₁, which have some common arc with D ₂. It follows from $D\in \mathfrak C$ that B is a block of D ₂ = G ₂/e ₁. Now B ₁/e ₁ ⊆ G ₂/e ₁ along with e ₁ ∈ G ₂ implies B ₁ ⊆ G ₂. The contradiction to Claim 1 completes the proof of Theorem 4.6. □

Remark 4.7

Suppose that G ₁ and G ₂ are both two-terminal series-parallel directed networks and E ₁ ∩ E ₂ induces all common blocks of G ₁ and G ₂. Then the connected components of G ₁ ∩ G ₂ can be ordered as C ₁,…,C _h for some h ≥ 1 such that each s ₁- t ₁ path in G ₁ passes these components in order of C ₁,…,C _h , and each s ₂- t ₂ path in G ₂ passes these components in order of C _h ,…,C ₁. (See Fig. 9 for an illustration).

Fig. 9

An instance for Remark 4.7

5 The Unified Characterization and Corollaries

The paradox-freeness of all irredundant networks (directed, undirected, single-commodity, multicommodity) has a unified characterization, as specified in Theorem 1.6. We first complete the proof of the characterization, then discuss its corollaries.

5.1 The Wrap-Up Proof for Irredundant Networks

We now summarize the proofs for the sufficiency and necessities of series-parallel condition (i) and coincidence condition (ii) in Theorem 1.6.

(Proof of Theorem 1.6)

In view of Theorem 1.4, we assume k ≥ 2. The sufficiency of conditions (i) and (ii) and the necessity of condition (i) have been established in Theorem 4.1 and Corollary 4.2, respectively. To see the necessity of condition (ii), suppose that G is paradox-free. By Lemma 2.4, for any distinct i, j ∈ [k], G _i ∪ G _j is a paradox-free irredundant 2-commodity network. In turn Theorem 4.4 or Theorem 4.6 applies to G _i ∪ G _j , validating condition (ii). □

5.2 Polynomial Time Recognition for Paradox-Freeness

We start this subsection with the discussion on single-commodity network G = (V, E) with origin-destination pair (s, t). Without loss of generality, we may assume that G is connected. Note that Milchtaich characterized only irredundant networks [20], and the result (the undirected case of Theorem 1.4) is easily extended to all undirected single-commodity networks as follows.

Theorem 5.1

A single-commodity undirected network G is paradox-free if and only if G can be decomposed into a number of graphs $G^{\prime }_{i}=(V^{\prime }_{i},E^{\prime }_{i})$, i = 0,…, p for some p ≥ 0 such that

• (i) E is the disjoint union of $E^{\prime }_{0},\ldots , E^{\prime }_{p}$;

• (ii) $|V^{\prime }_{0}\cap V^{\prime }_{i}|=1$ for any 1 ≤ i ≤ p, and $V^{\prime }_{i}\cap V^{\prime }_{j}=\emptyset$ for any 1 ≤ i < j ≤ p;

• (iii) $G^{\prime }_{0}$ is an irredundant single-commodity network with origin-destination pair (s,t); and

• (iv) $G^{\prime }_{0}$ is s-t series-parallel.

Proof

Suppose that G admits a decomposition into $G^{\prime }_{0},\ldots , G^{\prime }_{p}$ such that (i)–(iv) hold. It is easy to see that no s-t path in G goes through any edge in $\cup _{i=1}^{p}E^{\prime }_{i}$. So G is paradox-free if and only if $G^{\prime }_{0}$ is. Indeed, by Theorem 1.4, it follows from (iii) and (iv) that $G^{\prime }_{0}$ is paradox-free, proving the sufficiency.

Suppose that G is paradox-free. Let $G^{\prime }_{0}=(V^{\prime }_{0},E^{\prime }_{0})\subseteq G$ be the maximum (in terms of the number of edges) irredundant subnetwork of G. If $E^{\prime }_{0}=E$ then let p = 0, else let $G^{\prime }_{i}=(V^{\prime }_{i},E^{\prime }_{i})$, i = 1,…,p be the connected components in $G\setminus E^{\prime }_{0}$ each of which contains at least one edge. It is obvious that (i) and (iii) hold, and the validity of (iv) is guaranteed by Theorem 1.4 because G is paradox-free. It remains to verify (ii). Notice from the definitions of $G^{\prime }_{1},\ldots ,G^{\prime }_{p}$ that $V^{\prime }_{i}\cap V^{\prime }_{j}=\emptyset$ for any 1 ≤ i < j ≤ p. If $|V^{\prime }_{0}\cap V^{\prime }_{i}|\ge 2$ for some 1 ≤ i ≤ p, then there exist distinct vertices $u,v\in V^{\prime }_{0}\cap V^{\prime }_{i}$ and u-v path P in $G^{\prime }_{i}$ such that P and $G^{\prime }_{0}$ have only u, v in common. In view of (iii) and (iv), the application of Corollary 2.7 to $G^{\prime }_{0}$ provides two vertex-disjoint {s, t}- {u, v} paths Q and R in $G^{\prime }_{0}$. From $V(P)\cap V^{\prime }_{0}=\{u,v\}$ we deduce that P ∪ Q ∪ R is an s-t path in G going through P. The maximality of $G^{\prime }_{0}$ implies $P\subseteq G^{\prime }_{0}$. However, u ≠ v says that P contains a least an edge, which belongs to $E^{\prime }_{i}$; now $E^{\prime }_{i}\cap E^{\prime }_{0}=\emptyset$ gives a contradiction. So (ii) also holds, proving the necessity. □

Recall that two-terminal series-parallel networks can be recognized in polynomial time [27]. Theorem 5.1 provides a polynomial time algorithm for the problem of determining whether a given undirected single-commodity network is paradox-free. Note that the single vertex, denoted as v _i , of $V^{\prime }_{0}\cap V^{\prime }_{i}$ for any 2 ≤ i ≤ p in Theorem 5.1 is a cut-vertex of G, and $G^{\prime }_{i}\setminus v_{i}$ consists of a number of components of G∖v _i containing neither s nor t.

Now, let G be a k-commodity network with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$, and G _i the maximum irredundant subnetwork of (G,{i}), i ∈ [k]. The first corollary of Theorem 1.6 is a polynomial time recognition algorithm for determining whether G is paradox-free or not, given that G is undirected. For each i ∈ [k], implementing Algorithm 1 with s _i in place of s and t _i in place of t, we reduce G to G _i , and obtain an answer to whether G _i is s _i - t _i series-parallel or not. If some G _i is not s _i - t _i series-parallel, then G is not paradox-free by Theorem 1.6. If G _i is s _i - t _i series-parallel for all i ∈ [k], then the s _i - t _i block graph (see Lemma 2.8) and blocks of G _i can be identified in polynomial time for all i ∈ [k], which implies a polynomial time examination to see if G ₁,…,G _k satisfy the coincident condition. If the condition is satisfied, then G is paradox-free, otherwise G is paradox-ridden.

In case of G being directed, we have no efficient algorithm for determining whether an arc (u, v) is contained by an s _i - t _i path, or equivalently for determining whether the digraph has vertex-disjoint s _i -u path and v- t _i path. The latter problem is the well-known NP-complete problem of 2-vertex-disjoint directed paths (2DDP) [11], while its special case, the 2DDP problem in planar digraphs (planar 2DDP), is polynomial time solvable [7, 24]. Suppose that G is a planar digraph. Using the algorithm for planar 2DDP [7] and that for recognizing two-terminal series-parallel digraphs [27], in polynomial time, we may identify G _i (i ∈ [k]), check whether the series-parallel and coincident conditions are satisfied by G ₁,…,G _k , and then give the answer to whether G is paradox-free or paradox-ridden.

Corollary 5.2

For any integer k ≥ 1, paradox-free k-commodity undirected networks and paradox-free k-commodity planar directed networks can be recognized in polynomial time.

5.3 Underlying Graphs v.s. Orientations

Theorem 1.6 also provides two corollaries on the relations between the paradox-freeness of a network and that of its underlying graph or orientations. Notice that if G is a directed network with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$, then its underlying graph $\mathbb {u}(G)$ is also a k-commodity network with the same origin-destination pairs.

Corollary 5.3

Let G be a k-commodity directed network. If $\mathbb {u}(G)$ is paradox-free, then so is G.

Proof

Let D be the maximum irredundant subnetwork of G with origin-destination pairs $(s_{i},t_{i})_{i=1}^{k}$. It suffices to prove that D is paradox-free. As $\mathbb {u}(D)\subseteq \mathbb {u}(G)$, it follows from Lemma 2.4 that $\mathbb {u}(D)$ is paradox-free. Theorem 1.6(i) says that each $\mathbb {u}(D)_{i}$ (i ∈ [k]) is s _i - t _i series-parallel. Note that $\mathbb {u}(D_{i})\subseteq \mathbb {u}(D)_{i}$. It is straightforward from Definition 1.3(i) that $\mathbb {u}(D_{i})$ is s _i - t _i series-parallel for i ∈ [k]. So by Definition 1.3(ii) and Lemma 2.8, we have

• (i) for each i ∈ [k], D _i is s _i - t _i series-parallel, and its s _i - t _i block graph is a path ${v^{i}_{1}}{B^{i}_{1}}{v^{i}_{2}}{\cdots } v^{i}_{p_{i}}B^{i}_{p_{i}}v^{i}_{p_{i}+1}$ with ${v^{i}_{1}}=s_{i}$ and $v^{i}_{p_{i}+1}=t_{i}$.

Next, we show that D satisfies the coincidence condition. Take arbitrary distinct i, j ∈ [k]. Suppose that $B^{i}_{*}$ is a block of D _i and $B^{j}_{*}$ is a block of D _j such that $B^{i}_{*}$ and $B^{j}_{*}$ have an arc e = (u, v) in common. We need to prove $B^{i}_{*}=B^{j}_{*}$. Notice that for each h ∈ {i, j}, uv is an edge, written as $\mathbb {u}(e)$, contained in $\mathbb {u}(B^{h}_{*})\subseteq \mathbb {u}(D_{h})\subseteq \mathbb {u}(D)_{h}$. It follows from Theorem 1.6(ii) that $\mathbb {u}(e)$ is contained in a common block $\mathbb {u}(B)$ of $\mathbb {u}(D)_{i}$ and $\mathbb {u}(D)_{j}$, where B is a 2-connected subdigraph of D. Note that $\mathbb {u}(B)$ is a two-terminal series-parallel graph that has an identical set of terminals in $\mathbb {u}(D)_{i}$ and $\mathbb {u}(D)_{j}$.

For each h ∈ {i, j}, note that $u,v\in B^{h}_{*} \cap B$. We may take m _h (resp. M _h ) to be the minimum (resp. maximum) index g ∈ [p _h ] such that ${B^{h}_{g}}\setminus v^{h}_{g+1}$ (resp. ${B^{h}_{g}}\setminus {v^{h}_{g}}$) has some common vertex, say α _h (resp. β _h ), with B. By (i), the choices of m _h and M _h particularly imply $D_{h}\cap B\subseteq \cup _{g=m_{h}}^{M_{h}} {B^{h}_{g}}$.

For each h ∈ {i, j}, considering an α _h - β _h path P in $\cup _{g=m_{h}}^{M_{h}}{B^{h}_{g}}$, we see that ${v^{h}_{g}}\in P$ for all g = m _h +1,…,M _h . Since P ∪ B is 2-connected, none of ${v^{h}_{g}}\in P$, g = m _h +1,…,M _h can be a cut-vertex of $(\cup _{g=m_{h}}^{M_{h}}{B^{h}_{g}})\cup B$. It follows from the 2-connectivity of $B^{h}_{m_{h}},B^{h}_{m_{h}+1},\ldots ,B^{h}_{M_{h}}$ and B that $(\cup _{g=m_{h}}^{M_{h}}{B^{h}_{g}})\cup B$ is 2-connected. Notice that $(\cup _{g=m_{h}}^{M_{h}}\mathbb {u}({B^{h}_{g}}))\cup \mathbb {u}(B)\subseteq \mathbb {u}(D)_{h}$ and $\mathbb {u}(B)$ is the maximum 2-connected subgraph of $\mathbb {u}(D)_{h}$ containing $\mathbb {u}(B)$. We deduce that $\cup _{g=m_{h}}^{M_{h}} {B^{h}_{g}}\subseteq B$, saying $\cup _{g=m_{h}}^{M_{h}} {B^{h}_{g}}\subseteq D_{h}\cap B$. Thus we have

• (ii) for each h ∈ {i, j}, $D_{h}\cap B=\cup _{g=m_{h}}^{M_{h}} {B^{h}_{g}}$ consists of a string of consecutive blocks of D _h , and in particular $B^{h}_{*}$ is a block of D _h ∩ B.

For each h ∈ {i, j}, denote $a_{h}=v^{h}_{m_{h}}$ and $b_{h}=v^{h}_{M_{h}}$. Let P _h be an s _h - t _h path in D _h with e ∈ P _h . By (i) and Lemma 2.8(ii), we see that P _h goes through ${v^{h}_{1}} (=s_{h}), {v^{h}_{2}},\ldots ,v^{h}_{m_{h}}(=a_{h}),\ldots ,v^{h}_{M_{h}}(=b_{h}),\ldots ,v^{h}_{p_{h}+1}(=t_{h})$ in this order. By (ii), we deduce that P _h ∩ B = P _h [a _h , b _h ] is an a _h - b _h path. On the other hand, considering $\mathbb {u}(P_{h})$ as an s _h - t _h path in $\mathbb {u}(D)_{h}$, we derive from Lemma 2.8 that $\mathbb {u}(P_{h})\cap \mathbb {u}(B)$ is a path from the origin of $\mathbb {u}(B)$ to the destination of $\mathbb {u}(B)$ in $\mathbb {u}(D)_{h}$. So it must be the case that

• (iii) for each h ∈ {i, j}, the origin and destination of $\mathbb {u}(B)$ in $\mathbb {u}(D)_{h}$ are a _h and b _h , respectively.

As $\mathbb {u}(B)$ is a coincident block of $\mathbb {u}(D)_{i}$ and $\mathbb {u}(D)_{j}$, it follows from (iii) that {a _i , b _i }={a _j , b _j } is the identical terminal set of $\mathbb {u}(B)$ in $\mathbb {u}(D)_{i}$ and $\mathbb {u}(D)_{j}$. Observe that e ∈ P _h ∩ B = P _h [a _h , b _h ] for each h ∈ {i, j}. Considering $\mathbb {u}(B)$ as an a _i - b _i series-parallel graph in $\mathbb {u}(D)_{i}$, we see that $\mathbb {u}(P_{i}[a_{i},b_{i}])$ is an a _i - b _i path in B which goes through $\mathbb {u}(e)$ in the direction from u to v.

If a _j ≠ a _i , then b _j = a _i , a _j = b _i , and we find that $\mathbb {u}(P_{j}[a_{j},b_{j}])=\mathbb {u}(P_{j}[b_{i},a_{i}])$ is an a _i - b _i path in B which goes through $\mathbb {u}(e)$ in the opposite direction from v to u. This shows a contradiction to the fact that $\mathbb {u}(B)$ is s _i - t _i series-parallel (recall Definition 1.3). Hence we have a _i = a _j and b _i = b _j .

Combining a _i = a _j and b _i = b _j with (i) and (ii), we deduce that D _i ∩ B = D _j ∩ B, and it consists of all a _i - b _i paths (i.e., a _j - b _j paths) in B. Moreover, both $B^{i}_{*}$ and $B^{j}_{*}$ are blocks of D _i ∩ B = D _j ∩ B. It follows from $e\in B^{i}_{*}\cap B^{j}_{*}$ that $B^{i}_{*}= B^{j}_{*}$, which says that D satisfies the coincident condition in Theorem 1.6. Recalling (i), we deduce that D is paradox-free, as desired. □

The reverse of Corollary 5.3 is not always true. The single-commodity directed network D in Fig. 10a is paradox-free (because its maximum irredundant subnetwork D∖(v, s) is s-t series-parallel), but $\mathbb {u}(D)$ is paradox-ridden (because it is not s-t series-parallel).

Fig. 10

Paradox-freeness concerning underlying graphs and orientations

On the other hand, observe that $\mathbb {u}(D)$ can be oriented to become the digraph G _a in Fig. 1, which is paradox-ridden. Actually, this is an example for the general property of single-commodity networks stated in the following corollary. Recall Definition 3.2 of a directed s-t paradox. An undirected s-t paradox is defined in the same way via ignoring the arc directions.

Corollary 5.4

Let G be a single-commodity undirected network with origin-destination pair (s,t). If G is paradox-ridden, then there is an orientation $\tilde G$ of G such that $\tilde G$ is a paradox-ridden single-commodity directed network with origin-destination pair (s,t).

Proof

It suffices to consider G being an irredundant network. As G is paradox-ridden, by Theorem 1.4, it is not s-t series-parallel, and thus by Proposition 1 of [20], G contains an s-t paradox (P ₁, P ₂, P ₃), where P ₁, P ₂, P ₃ satisfy (i)– (iii) of Definition 3.2 in the context of graphs. Orient P ₁, P ₂ and P ₃ into directed s-t path $\tilde P_{1}$, a-v path $\tilde P_{2}$ and u-b path $\tilde P_{3}$. respectively. Then digraph $D=\tilde P_{1}\cup \tilde P_{2}\cup \tilde P_{3}$ is an s-t paradox. Clearly D is an irredundant single-commodity network with origin-destination pairs (s, t). It follows from Lemma 3.3 that D is paradox-redden. Let $\tilde G$ be a superdigraph of D. It follows from Lemma 2.4 that $\tilde G$ is paradox-ridden. □

Corollary 5.4 does not admit multicommodity extensions, as shown by the 2-commodity undirected network G in Fig. 10b. The irredundant network G does not satisfy the coincident condition, and thus by Theorem 1.6, is paradox-ridden. Consider any orientation $\tilde G$ of G. The maximum irredundant subnetwork of $\tilde G$ consists of an s ₁- t ₁ path and an s ₂- t ₂ path, and by Theorem 1.6 is paradox-free. It follows that $\tilde G$ is paradox-free.

6 Conclusion

The main result of this paper is a graphical characterization for all irredundant networks to be paradox-free; the series-parallel and coincident conditions are shown to be sufficient and necessary for the paradox-freeness. Our work suggests several directions of future research.

As far as nonnegative traffic demands $\mathbf {r}=(r_{i})_{i=1}^{k}$, nonnegative, continuous, and nondecreasing latencies ℓ are concerned, our definition of paradox-free k-commodity networks does generalize the one for single-commodity networks [17, 20, 23]. For routing instance (G, r, ℓ), we allow some traffic demands r _i , i ∈ [k] to be zero. Clearly there is no need to consider any commodities with zero traffic demands. This is the reason why we consider the set k(r) of commodities with positive demands and subnetwork H w.r.t. the network-demand pair (G, k(r)) instead of a subnetwork defined only w.r.t. k-commodity network G itself – k(r) may be a proper subset of [k], and H is a |k(r)|-commodity network in G. By manipulating r, routing for (G, r, ℓ) can behave as an h-commodity routing inside G for any h ∈ [k]. These routings with h < k (referred to as degenerate routings) are crucial for obtaining the result that any union of G _i ’s (i ∈ [k]) is paradox-free provided G is paradox-free (see Lemma 2.4).

The assumption that $\mathbf {r}\in \mathbb R^{k}_{\ge 0}$ instead of $\mathbf {r}\in \mathbb R^{k}_{>0}$ is seemingly nature because the ratio between the largest traffic demand and the smallest one can be arbitrarily large, and the arbitrarily small traffic has arbitrarily small affect on latencies. However, one might restrict r to be positive; this requires each k-commodity routing for (G, r, ℓ) to be nondegenerate, and each subnetwork to be a k-commodity network. With this restriction of positive demands, we would lose Lemma 2.4; it is possible that the union of some G _i ’s, i ∈ [k], is paradox-ridden even if $G=\cup _{i=1}^{k}G_{i}$ is paradox-free (see the example in Fig. 2 where G ₁ ∪ G ₂ ∪ G ₃ in (a) is paradox-free, and G ₁ ∪ G ₂ in (b) is paradox-ridden). It would be an interesting and challenging task to characterize paradox-free networks for positive traffic demands.

Different from Definition 1.2, the occurrence of Braess’s paradox in a routing instance (G, r, ℓ) could have another generalization from single-commodity to multicommodities as follows: We say that strong Braess paradox occurs in (G, r, ℓ) if there exists subnetwork H of (G, k(r)) such that ℓ _i (H, r) < ℓ _i (G, r) for all i ∈ k(r). Correspondingly, we may define strong paradox-free networks. The class of strong paradox-free networks turns out to be much wider than that of paradox-free ones. Even under the undirected network model, the characterization of strong paradox-freeness might involve much more complicated interaction between network topologies and the positions of origin-destination pairs in the network.

A corollary of our main result is polynomial time recognition of k-commodity undirected networks and planar directed networks that are paradox-free (see Corollary 5.2). Unfortunately, this does not extend to general directed networks even restricted to the single-commodity case. The difficulty lies on the fact that we have no efficient algorithm for finding the maximum irredundant subnetwork for each single commodity, which is equivalent to solving the NP-complete problem of 2-vertex-disjoint paths. In view of this NP-completeness, the recognition of paradox-free directed networks is very likely to be intractable. It would be nice to identify the complexity status of the recognition problem.