When does additional information lead to longer travel time in multi-origin–destination networks?

Xujin Chen¹¹1Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; xchen@amss.ac.cn Xiaodong Hu²²2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; xdhu@amss.ac.cn Xinqi Jing³³3Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; jingxinqi@amss.ac.cn Zhongzheng Tang⁴⁴4School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China; tangzhongzheng@amss.ac.cn

Abstract

The Informational Braess’ Paradox (IBP) illustrates a counterintuitive scenario where revelation of additional roadway segments to some self-interested travelers leads to increased travel times for these individuals. IBP extends the original Braess’ paradox by relaxing the assumption that all travelers have identical and complete information about the network. In this paper, we study the conditions under which IBP does not occur in networks with non-atomic selfish travelers and multiple origin-destination pairs. Our results completely characterize the network topologies immune to IBP, thus resolving an open question proposed by Acemoglu et al. [1].

1 Introduction

The informational Braess’ paradox (IBP), as introduced by Acemoglu et al. [1], illustrates a counterintuitive phenomenon in network traffic where disseminating supplementary information about available paths to certain travelers paradoxically results in increased travel time for these individuals. This longer travel time stems from the initial reactions of the informed travelers to the new information, and the subsequent responsive adjustments in routing by those without information extension. The IBP concept builds upon the classical Braess’ paradox (BP), which demonstrates that adding an extra link to a transport network can sometimes lead to a situation where all travelers experience a weak increase in travel times as a result of their individually rational routing decisions. The “weak increase” in this context means that travel times for travelers between one origin-destination (OD) pair strictly increase, while travel times for all others do not decrease [2, 3].

Both IBP and BP reveal the complex and counterintuitive interplay between network structure, the information possessed by self-interested travelers, and the resulting traffic flow dynamics. Though both paradoxes show similar negative effects that arise from seemingly beneficial changes, they each highlight different aspects of network dynamics and the potential unforeseen consequences when adjustments are made. (1) In BP, all travelers have access to complete information about the available routes in the network, which leads to uniform decision-making, ironically resulting in suboptimal outcomes when a new link is introduced. Conversely, IBP addresses the effects of unequal information distribution among travelers, where individual travelers act based on typically incomplete and differentiated information. In this scenario, travelers belong to different groups determined by their information types, i.e., the information sets about network edges available to them. When only one group of travelers receives additional information, their initial responses to this new data trigger a ripple effect that can ultimately impact all travelers. (2) BP requires that the introduction of an extra link causes a “uniform”, albeit weak, increase in travel times for all travelers. On the other hand, IBP only stipulates that travelers who receive additional information experience longer travel time. It is possible that some travelers with unchanged information sets might benefit from shorter travel times. As pointed out by Acemoglu et al. [1], in networks with a single OD pair, BP is identical with IBP with a single information type. The observation, however, cannot be extended to the multi-OD-pair case. The BP with two OD pairs, presented in [3], cannot be formulated as an IBP with two information types. Indeed, in the BP only one group of travelers alters their routes following the addition of an extra edge, yet their travel time does not increase. The lack of increased travel time for the route-changing group in BP departs from the expected outcome in an IBP framework, where travelers with additional choices face longer travel times after reacting to new information.

Since its introduction in the 1960s [2], BP has been extensively studied from various perspectives. Notably, for non-atomic travelers, each of whom controls an infinitesimally small fraction of the total traffic, Milchtaich [4] and Chen et al. [3] characterized topologies of networks that are immune to BP, thereby advancing our understanding of when and why the paradox does not manifest. In contrast, the investigation into IBP is still in its nascent stages. The body of research on IBP is considerably smaller, indicating a promising avenue for study to explore the nuances and implications of information asymmetry in network traffic dynamics. Acemoglu et al. [1] proved that IBP with a single OD pair does not occur if and only if the network is series of linearly independent (SLI). The result, in combination with Milchtaich’s series-parallel characterization [4], indicates that the IBP is a considerably more pervasive phenomenon than BP, as SLI networks form a subclass of series-parallel ones [1]. The conclusion aligns with the aforementioned observation [1] that IBP generalizes BP when restricted to single OD pair networks. However, as far as multiple OD pairs are concerned, the relation between IBP and BP becomes considerably more intricate, as highlighted in the preceding discussion. Can one expect a smaller class of networks for IBP-freeness than those, obtained in [3], for BP-freeness (as what has been done for the single OD pair case)? The answer is negative, as shown by Acemoglu et al. [1]. The authors provided a sufficient condition that precludes the occurrence of IBP in networks with multiple OD pairs, while also demonstrating that this condition is not necessary. They thereby posed the natural question of identifying a condition that is both sufficient and necessary. In this paper, we resolve this question by establishing a complete characterization of undirected networks with multiple OD pairs in which IBP never occurs for non-atomic travelers. The characterization might be helpful in network design to improve traffic efficiency.

1.1 Routing Game

Our basic framework is selfish routing model [5, 6, 7]. In this paradigm, travelers, acting in their own self-interest, select routes connecting their origins to their destinations within a traffic network. This network is represented by an undirected connected multigraph $G=(V,E)$ that may have parallel edges but no loops, where $V=V(G)$ is the vertex set and $E=E(G)$ is the edge set. If no confusion arises, we identify a graph with its edge set. Given $n$ pairs of origin-destination (OD) vertices $(o_{i},d_{i})_{i=1}^{n}$ in $G$ with $o_{i}\neq d_{i}$ for all $i\in[n]$ , we often call them OD pairs. There are $k$ types of non-atomic travelers, who are individually insignificant relative to the entire system. The “non-atomic” attribute means that each traveler controls an infinitesimally small fraction of the total traffic. No single non-atomic traveler’s actions can influence the overall system; their contribution to congestion is negligible. For every $j\in[k]$ , the amount of type- $j$ travelers is often referred to as their traffic rate, and denoted as $r(j)$ or $r_{j}$ (we will use these notations interchangeably throughout). Type- $j$ travelers have a common information set $E_{j}\subseteq E$ and a common terminal set $\{o_{t(j)},d_{t(j)}\}$ , where $t(\cdot)$ is a function from $[k]$ to $[n]$ . Each type- $j$ traveler travels along a path from his origin $o_{t(j)}$ to his destination $d_{t(j)}$ in $E_{j}$ , called an $o_{t(j)}$ - $d_{t(j)}$ path, or simply his OD path. Let $\mathcal{P}_{j}$ denote the set of type- $j$ travelers’ OD paths. The routing, a.k.a. traffic flow, of type- $j$ travelers is denoted by $f^{j}=(f^{j}_{P}:P\in\mathcal{P}_{j})$ , where $f^{j}_{P}\geq 0$ equals the volume of the flow (the amount of type- $j$ travelers) going through path $P\in\mathcal{P}_{j}$ , and the flow volume $\sum_{P\in\mathcal{P}_{j}}f^{j}_{P}$ equals the traffic rate $r_{j}$ . The routing of all $k$ types of travelers is represented by a flow (vector) $f=(f^{1},\ldots,f^{k})$ . For any edge $e\in E$ , let $f_{e}^{j}=\sum_{P\in\mathcal{P}_{j}:e\in P}f^{j}_{P}$ denote the flow volume of type- $j$ travelers traversing $e$ , and $f_{e}=\sum_{j\in[k]}f_{e}^{j}$ denote the flow volume of all travelers passing through $e$ . For any path $P$ in $G$ , let $f_{P}=\sum_{j\in[k]}f_{P}^{j}$ denote the flow volume of all travelers going through $P$ . Each edge $e\in E$ is associated with a nonnegative and nondecreasing latency function $\ell_{e}(\cdot)$ , which takes $f_{e}$ , the volume of flow using $e$ , as the independent variable. Under $f$ , the latency of a path $P$ is $\ell_{P}(f)=\sum_{e\in P}\ell_{e}(f_{e})$ , the sum of its edges’ latencies, and the latency of a traveler equals the latency of his OD path along which he travels. Every traveler is selfish in that he is only concerned about his own latency. Given others’ routing choices, he always chooses one of his OD paths with the lowest latency. The self-interested behaviors induce an information constrained routing game, denoted by quadruple $(G,\ell,r,\mathcal{E})$ , where $\ell=\{\ell_{e}~{}|~{}e\in E\}$ denotes the set of latency functions, and $r=(r_{1},\ldots,r_{k})$ and $\mathcal{E}=(E_{1},\ldots,E_{k})$ describe the traffic rates and information sets of all $k$ types of travelers, respectively. The Nash equilibrium of the game is often referred to as an Information-Constrained Wardrop Equilibrium (ICWE).

Definition 1 (ICWE flow).

[1] A flow $f$ is an ICWE flow if for every type- $j$ traveler and every $o_{t(j)}$ - $d_{t(j)}$ path $P\in\mathcal{P}_{j}$ with $f_{P}^{j}>0$ , it follows that $\ell_{P}(f)\leq\ell_{P^{\prime}}(f)$ for each $P^{\prime}\in\mathcal{P}_{j}$ .

The game always admits an ICWE flow, which is essentially unique: if $f$ and $\hat{f}$ are both ICWE flows, then $\ell_{e}(f_{e})=\ell_{e}(\hat{f}_{e})$ for every $e\in E$ [1]. By the definition and uniqueness, given ICWE flow $f$ , for each $j\in[k]$ , let $\ell_{j}(f)=\ell_{P}(f)$ with $f_{P}^{(j)}>0$ denote the equilibrium latency of type- $j$ travelers.

1.2 Information Braess’ Paradox

Given game $(G,\ell,r,\mathcal{E})$ , we say $\tilde{\mathcal{E}}=\{\tilde{E}_{1},\ldots,\tilde{E}_{k}\}$ is an information extension (of $\mathcal{E}$ ) if $E_{1}\subset\tilde{E}_{1}$ and $E_{j}=\tilde{E}_{j}$ for $j=2,\ldots,k$ .

Definition 2 (IBP).

[1] Let $f$ and $\tilde{f}$ be ICWE flows of games $(G,\ell,r,\mathcal{E})$ and $(G,\ell,r,\tilde{\mathcal{E}})$ , respectively. If $\ell_{1}(\tilde{f})>\ell_{1}(f)$ , then Information Braess’ Paradox (IBP) occurs, and quintuple $(G,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ is called an IBP instance.

The IBP instance encompasses two information constrained routing games $(G,\ell,r,\mathcal{E})$ and $(G,\ell,r,\tilde{\mathcal{E}})$ with $f$ and $\tilde{f}$ being their ICWE flows respectively. The only difference between $\mathcal{E}$ and $\tilde{\mathcal{E}}$ is that $E_{1}$ is properly contained in $\tilde{E}_{1}$ . By $\ell_{1}(\tilde{f})>\ell_{1}(f)$ , we see that type- $1$ travelers have their information set expanded but suffer from a higher latency, while the information sets of other travelers remain unchanged. For a network $G$ , if an IBP instance $(G,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ exists, then we say $G$ is not immune to IBP; otherwise, we call $G$ an IBP-free network.

For a network with OD pairs, we assume for convenience that each edge and each vertex of the network are contained in at least one OD path.

1.3 IBP-free Networks with a Single OD Pair

Acemoglu et al. [1] established a sufficient and necessary condition for an undirected network with a single OD pair to be IBP-free (see Theorem 1). To present their result, we need to introduce three classes of networks with a single OD pair $(o,d)$ : series-parallel networks, linearly independent networks, and series of linearly independent networks, where $\{o,d\}$ are referred to as their terminal sets. These networks provide us with important structural properties for characterizing IBP-freeness in networks with one or more OD pairs.

Definition 3 (SP network).

A network with a single OD pair is called series-parallel (SP) if any two OD paths never pass through an edge in opposite directions.

We can use recursive operations to equivalently characterize SP networks (see, e.g., [4]). By connecting two networks with a single OD pair in series, we mean joining the destination vertex of one network with the origin vertex of the other network (the origin of the first network becomes the origin of the new network, and the destination of the second network becomes the destination of the new network). By connecting two networks with a single OD pair in parallel, we mean identifying the origin vertices of two networks to form the origin of the new network and identifying the destination vertices of two networks to form the new destination of the new network.

A network with a single OD pair is SP if and only if it is a single-edge network, or a connection of two SP networks in series, or a connection of two SP networks in parallel. Another characteristic of SP networks is that the network in Figure 5 can not be embedded in a SP network [4]. SP networks are immune to BP [4] but not immune to IBP [1]. An important subclass of SP networks consists of linearly independent ones, which have been shown to be IBP-free [1].

Definition 4 (LI networks).

A network with a single OD pair is called linearly independent (LI) if each OD path has an edge that does not belong to any other OD path.

LI networks can also be characterized using recursive graphical operations [8]. A network with a single OD pair is LI if and only if it is a single-edge network, or a connection of two LI networks in parallel, or a connection of a single edge and an LI network in series. Another subclass of SP networks is obtained by connecting LI networks in series..

Definition 5 (SLI network).

A network with a single OD pair is series of linearly independent (SLI) if it is an LI network or it is a connection of two SLI networks in series.

It is worth noting that the connection of two LI networks in series may not be an LI network (see Figure 1(b)), and the connection of two SLI networks in parallel may not be an SLI network (see Figure 1(a)).

Theorem 1.

[1] A network with a single OD pair is IBP-free if and only if it is an SLI network.

A vertex in a connected graph is a cut vertex if its removal from the graph leaves the graph unconnected. A block of a graph is a maximal connected subgraph without any cut vertex. SP networks (and thus their special cases, SLI networks and LI networks) possess a structure known as block-chain. It means that an SP network can be constructed by connecting several SP blocks in series, where the OD pair of each block is uniquely determined by the OD pair of the whole SP network [3]. In particular, an SLI network is a connection of several LI blocks in series. See Figure 2 for an illustration, where the OD pair of block $B_{h}$ is $(v_{h},v_{h+1})$ , $h\in[4]$ . If a terminal (either the origin or the destination) of an LI block is not a terminal of the entire SLI network, then it is a cut vertex of the entire SLI network. For example, $v_{2},v_{3},v_{4}$ in Figure 2 are those terminals.

1.4 IBP-free Networks with Multiple OD Pairs

In this paper, we completely characterize the structure of undirected networks with multiple OD pairs that are immune to IBP (see Theorem 3), strengthening the sufficient condition by [1] (see Theorem 2) and solving an open question proposed in [1].

When network $G$ has $n\,(\geq 2)$ OD pairs $(o_{i},d_{i})_{i=1}^{n}$ , we call $G$ a network with multiple OD pairs. For every $i\in[n]$ , we reserve symbol $G_{i}$ to denote the subnetwork with terminal set $\{o_{i},d_{i}\}$ , or equivalently with a single OD pair $(o_{i},d_{i})$ , which consists of all $o_{i}$ - $d_{i}$ paths in $G$ . To characterize IBP-free networks, in view of Theorem 1, it suffices to consider the scenario in which each $G_{i}$ is an SLI network, and therefore its blocks are all LI. To investigate the mutual influence of routing in two subnetworks $G_{i}$ and $G_{j}$ , the first step is to study the structural properties of their common part $G_{i}\cap G_{j}$ .

Proposition 1.

[3] Suppose that $G_{i}$ and $G_{j}$ are SLI subnetworks of $G$ . Let $B_{i}$ and $B_{j}$ be blocks of $G_{i}$ and $G_{j}$ , respectively. If $E(B_{i})\cap E(B_{j})\neq\emptyset$ , then $B_{i}=B_{j}$ is a common block of $G_{i}$ and $G_{j}$ .

It is worth noting that a common block of $G_{i}$ and $G_{j}$ may have different terminal sets when restricted to the specific subnetworks. See Figure 3 for an illustration, where $G_{1}=G_{2}$ is a block with $\{o_{1},d_{1}\}\neq\{o_{2},d_{2}\}$ .

Definition 6.

[3] Suppose that $G_{i}$ and $G_{j}$ are SLI. A block $B$ of $G$ is called a coincident block of $G_{i}$ and $G_{j}$ if it is a common block of $G_{i}$ and $G_{j}$ , and the terminal set of $B$ in $G_{i}$ is the same as that in $G_{j}$ .

In Definition 6, 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. Combining the SLI condition for IBP-free networks with a single OD pair (see Theorem 1) and the coincident condition for characterizing BP-freeness [3], Acemoglu et al. [1] established the following sufficient condition for excluding IBP in networks with multiple OD pairs.

Theorem 2.

[1] Let $G$ to be a network with $n$ OD pairs. For every $i\in[n]$ , let $G_{i}$ be the subnetwork of $G$ with terminal set $\{o_{i},d_{i}\}$ . Then $G$ is IBP-free if $G$ satisfies the following conditions:

•

SLI condition: for every $i\in[n]$ , $G_{i}$ is SLI.
•

Coincident condition: for any $i,j\in[n]$ with $i\neq j$ , either $E(G_{i})\cap E(G_{j})=\emptyset$ or the graph induced by $E(G_{i})\cap E(G_{j})$ consists of all coincident blocks of $G_{i}$ and $G_{j}$ .

The coincident condition is not necessary, as shown by the cycle network $G$ with three vertices and two OD pairs depicted in Figure 3. Although $G=G_{1}=G_{2}$ is a non-coincident block, Acemoglu et al. [1] proved that $G$ is IBP-free.

The next theorem represents our main contribution. Building on the results of [1], we establish the following necessary and sufficient condition, showing that cycle networks are the sole exception not covered by the coincident condition.

Theorem 3 (Main Result).

Let $G$ to be a network with $n$ OD pairs. For every $i\in[n]$ , let $G_{i}=(V_{i},E_{i})$ be the subnetwork with terminal set $\{o_{i},d_{i}\}$ . Then $G$ is IBP-free if and only if $G$ satisfies the following conditions:

•

SLI condition: for every $i\in[n]$ , $G_{i}$ is SLI.
•

Common block condition: for any $i,j\in[n]$ with $i\neq j$ , either $E(G_{i})\cap E(G_{j})=\emptyset$ or the graph induced by $E(G_{i})\cap E(G_{j})$ consists of all common blocks of $G_{i}$ and $G_{j}$ , where each common block is either a coincident block or a cycle.

Our technical contributions primarily lie in the following two aspects: (1) We identified IBP instances for non-coincident blocks that are not cycles. (2) We proved that cycle networks are IBP-free. The analysis for both aspects requires a thorough understanding of the interaction between network structures, selfish routing games, and the mechanisms of IBP. It involves disentangling and reducing the complex interweaving of intricate structures and routing dynamics.

While Roman and Turrini [9] asserted to have proven the IBP-freeness of cycle networks, their proof contained irremediable flaws. Specifically, Proposition 3 in [9], intended to mirror Lemma 1(b) of [1], claimed that in a cycle network, after the information extension, there must exist a type of travelers whose latency does not increase. However, the authors [9] did not provide a complete proof for the general case. Furthermore, the proof of their main theorem (Theorem 3 in [9]) is flawed, as detailed in Appendix A. The issues remain unresolved in Roman’s thesis [10]. Given these shortcomings, we present a novel approach to prove the IBP-freeness of cycle networks. The proofs, which constitute the most technical part of our paper, are elaborated in Section 4 and Appendix B. Our method is completely different from that of Roman and Turrini, offering a complete analysis of the problem.

1.5 Related Work

The most related work for IBP-free networks, which has been discussed in Subsections 1.3 and 1.4, includes the SLI characterization by [1] for the case of a single OD pair, and the sufficient conditions of [1, 9] for the case of multiple OD pairs.

The study of the counterintuitive phenomenon in routing games was started by Braess in 1968 [2]. Milchtaich [4] introduced a series-parallel characterization for excluding BP in undirected networks with a single OD pair. Chen et al. [3] extended this solution by providing a complete characterization for all undirected and directed networks with multiple OD pairs that are immune to BP, incorporating the series-parallel and coincident conditions. BP appears not only in traffic networks, but also in communication networks [11, 12, 13, 14], mechanical systems and electrical circuits [15, 16]. In addition, BP serves as the motivation for a network design problem: determining which edges should be removed from a given network to achieve the optimal flow at equilibrium. Roughgarden [17] provided optimal inapproximability results and proposed approximation algorithms for tackling this network design problem.

Traveler heterogeneity has garnered significant research attention. Milchtaich [18] studied the situation that different travelers may have different latency functions. Cole et al. [19] focused on the routing games where diversity emerges from the trade-off between two criteria and characterized the topology of networks for which diversity is never harmful. Meir and Parkes [20] proposed a routing game model in which travelers face uncertainty regarding the paths chosen by others. Sekar et al. [21] considered the selfish routing game in which travelers may overestimate or underestimate their traffic latencies. Wu et al. [22] studied the equilibrium route choices and traffic latencies within a heterogeneous information system, considering an uncertain state that impacts the latencies of edges in the network.

Organization.

The rest of the paper is organized as follows: Section 2 introduces additional notations and presents preliminaries. Sections 3 is dedicated to proving the “only if” part of our characterization for IBP-free networks, which asserts that under the SLI condition, non-coincident blocks are either cycles or admit IBP. Section 4 establishes the “if” part of our characterization, showing that all cycle networks with multiple OD pairs are IBP-free. Section 5 concludes the paper with remarks on possible directions of future research. Due to space limitations, some proofs are omitted from the main body and provided in the Appendix.

2 Preliminaries

Given an information constrained routing game $(G,\ell,r,\mathcal{E})$ that is IBP-free, we can decompose the game into several local games based on the block-chain structure of $G$ . By Theorem 1, we assume that network $G$ satisfies the SLI condition in Theorem 3. Thus each subnetwork $G_{i}$ processes a block-chain structure (recall Figure 2). Furthermore, using Proposition 1, we can decompose the network $G$ into a number of LI blocks $B_{1},B_{2},\ldots,B_{l}$ , each of which is a common block of several $G_{i}$ ’s. For ease of presentation, if $B_{s}\subseteq G_{i}$ , i.e., $B_{s}$ is a block of $G_{i}$ , we denote the OD pair of $B_{s}$ in the block-chain of $G_{i}$ as $(o_{i},d_{i})$ . In this way, we may consider a local game $(B_{s},\ell_{B_{s}},r_{B_{s}},\mathcal{E}_{B_{s}})$ restricted to $B_{s}$ , where $\ell_{B_{s}}$ is the restriction of $\ell$ to $B_{s}$ , $\mathcal{E}_{B_{s}}$ is the restriction of $\mathcal{E}$ to $B_{s}$ , and the traffic rates are consistent with those in $G$ , i.e.,

$r_{B_{s}}(j)=r_{j}$ if $B_{s}\subseteq G_{t(j)}$ , and $r_{B_{s}}(j)=0$ otherwise.

Note that although the real participants of the game are only travelers whose OD paths pass some edges in $B_{s}$ , i.e., type- $j$ travelers with $G_{t(j)}\supseteq B_{s}$ , for notational convenience, we consider the other travelers (if any) as dummy participants of the game with traffic rate 0 for which we do not need to specify OD pairs or information sets. Let $f_{s}$ be an ICWE flow of $(B_{s},\ell_{B_{s}},r_{B_{s}},\mathcal{E}_{B_{s}})$ and $\ell_{j}(f_{s})$ be the ICWE latency of type- $j$ travelers in network $B_{s}$ ; if $r_{B_{s}}(j)=0$ , then we set $\ell_{j}(f_{s})=0$ . Let $f$ be an ICWE flow of $(G,\ell,r,\mathcal{E})$ . It is easy to see that the equilibrium latency of a traveler in $G$ is the sum of his equilibrium latency in all local games.

Proposition 2.

For every $j\in[k]$ , $\ell_{j}(f)=\sum_{s=1}^{l}\ell_{j}(f_{s})$ .

Proof.

Let $f_{B_{s}}$ denote the restriction of $f$ on $B_{s}$ . For every $B_{s}\subseteq G_{t(j)}$ , it is clear that $f_{B_{s}}$ is an ICWE flow of $(B_{s},\ell_{B_{s}},r_{B_{s}},\mathcal{E}_{B_{s}})$ and $\ell_{j}(f_{B_{s}})=\ell_{j}(f_{s})$ by the uniqueness of ICWE. Because $G_{t(j)}$ is the connection of its blocks in series, we have $\ell_{j}(f)=\sum_{B_{s}\subseteq G_{t(j)}}\ell_{j}(f_{B_{s}})=\sum_{B_{s}\subseteq G_{t(j)}}\ell_{j}(f_{s})=\sum_{s=1}^{l}\ell_{j}(f_{s})$ , where the last equality is implied by the setting that $\ell_{j}(f_{s})=0$ whenever $B_{s}\nsubseteq G_{t(j)}$ . ∎

Lemma 1.

Let $G$ be a network with multiple OD pairs that satisfies the SLI condition. Let $B_{1},B_{2},\ldots,B_{l}$ be the blocks of $G$ , each of which is an LI network with the OD pairs determined by $G$ and $G$ ’s OD pairs. Then $G$ is an IBP-free network if and only if $B_{s}$ is an IBP-free network for every $s\in[l]$ .

Proof.

To see the sufficiency, suppose that $(G,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ is an IBP instance. Let $f$ be an ICWE flow of $(G,\ell,r,\mathcal{E})$ and $\tilde{f}$ be an ICWE flow of $(G,\ell,r,\tilde{\mathcal{E}})$ . By Proposition 2, we have $\ell_{1}(f)=\sum_{s=1}^{l}\ell_{1}(f_{s})$ and $\ell_{1}(\tilde{f})=\sum_{s=1}^{l}\ell_{1}(\tilde{f_{s}})$ . Since $\ell_{1}(f)<\ell_{1}(\tilde{f})$ , there must be an $s\in[l]$ such that $\ell_{1}(f_{s})<\ell_{1}(\tilde{f_{s}})$ . It follows that $(B_{s},\ell_{B_{s}},r_{B_{s}},\mathcal{E}_{B_{s}},\tilde{\mathcal{E}}_{B_{s}})$ is an IBP instance.

To see the necessity, suppose that $(B_{s^{*}},\ell_{B_{s^{*}}},r_{B_{s^{*}}},$ $\mathcal{E}_{B_{s^{*}}},\tilde{\mathcal{E}}_{B_{s^{*}}})$ with $\ell_{1}(f_{s^{*}})<\ell_{1}(\tilde{f}_{s^{*}})$ is an IBP instance for some ${s^{*}}\in[l]$ . We construct an IBP instance $(G,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ as follows. Let $\ell_{e}\equiv 0$ for every edge $e\in E(G)-E(B_{s^{*}})$ . For type- $j$ travelers in $G$ , let their traffic rates be consistent with $r_{B_{s^{*}}}$ , let their information set before (resp. after) information expansion when restricted to $B_{s^{*}}$ be as in $\mathcal{E}_{B_{s^{*}}}$ (resp. $\tilde{\mathcal{E}}_{B_{s^{*}}}$ ), and let their information sets (before and after information expansion) when restricted to $B_{u}$ (with $u\neq s^{*}$ and $B_{u}\subseteq G_{t(j)}$ ) be $E(B_{u})$ . Let $f$ and $\tilde{f}$ be ICWE flows of $(G,\ell,r,\mathcal{E})$ and $(G,\ell,r,\tilde{\mathcal{E}})$ , respectively. By Proposition 2, $\ell_{1}(f)=\sum_{s=1}^{l}\ell_{1}(f_{s})=\ell_{1}(f_{s^{*}})$ and $\ell_{1}(\tilde{f})=\sum_{s=1}^{l}\ell_{1}(\tilde{f_{s}})=\ell_{1}(\tilde{f}_{s^{*}})$ . Since $\ell_{1}(f_{s^{*}})<\ell_{1}(\tilde{f}_{s^{*}})$ , we have $\ell_{1}(f)<\ell_{1}(\tilde{f})$ , showing that $(G,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ is an IBP instance. ∎

For an edge $e\in E(G)$ , we use $G/e$ to denote the network obtained from $G$ by contracting $e$ into a new vertex $v_{e}$ . If exactly one of the two vertices incident to $e$ is a terminal vertex of $G$ , then the corresponding terminal of $G/e$ is the new vertex $v_{e}$ . We use $G\setminus e$ to denote the network obtained from $G$ by removing $e$ .

Definition 7 (Nice embedding).

A network $H$ is nicely embedded in the network $G$ if $H$ can be obtained from $G$ by recursive edge removals and contractions under the condition that no terminal set of the networks in the process is merged by the contractions.

Lemma 2.

If network $H$ can be nicely embedded in the network $G$ and $H$ is not immune to IBP, then $G$ is not immune to IBP.

Proof.

We only need to consider the situation that $H$ is $G\setminus e$ or $G/e$ for some edge $e\in E(G)$ . We use $\ell$ to denote the latency function set in $H$ for convenience. If $(H,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ is an IBP instance, then we set $\mathcal{E}^{\prime}=\mathcal{E}$ and $\tilde{\mathcal{E}}^{\prime}=\tilde{\mathcal{E}}$ when $H=G\setminus e$ , and set $\mathcal{E}^{\prime}=\{E\cup\{e\}~{}|~{}E\in\mathcal{E}\}$ and $\tilde{\mathcal{E}}^{\prime}=\{E\cup\{e\}~{}|~{}E\in\tilde{\mathcal{E}}\}$ when $H=G/e$ . Setting $e$ ’s latency function by $\ell_{e}\equiv 0$ , it is easy to see that $(G,\ell,r,\mathcal{E}^{\prime},\tilde{\mathcal{E}}^{\prime})$ is an IBP instance. ∎

3 Necessity Proof

In this section, we establish the necessity of the conditions stated in Theorem 3. It is evident from Theorem 1 that the SLI condition is a prerequisite for IBP-freeness. It remains to prove the necessity of the common block condition. To accomplish this, we only need to consider an IBP-free network $G$ with two OD pairs such that $G_{1}$ and $G_{2}$ are SLI. Furthermore, by Proposition 1 and Lemma 1, we may assume that $G=G_{1}=G_{2}$ is the non-coincident common block of $G_{1}$ and $G_{2}$ . Our objective is to show that $G$ is a cycle, thereby confirming the necessity of the condition.

3.1 An IBP Instance

In this subsection, we show that an IBP can occur in the following network $F_{1}$ with three vertices, two OD pairs $(o_{i},d_{i})_{i=1}^{2}$ , and latency functions $\ell$ , as depicted in Figure 4(a). Specifically, $V(F_{1})=\{u,v,w\}=\{o_{1},d_{1},o_{2},d_{2}\}$ , $E(F_{1})=\{e_{1},e_{2},e_{3},e_{4}\}$ , and latency functions are written beside the corresponding edges, e.g., $\ell_{e_{1}}(x)=0$ , $\ell_{e_{2}}(x)=4x$ , $\ell_{e_{3}}(x)=x+22$ and $\ell_{e_{4}}(x)=10+2x$ .

Suppose that $k=2$ and that for $j=1,2$ , type- $j$ travelers have OD pair $(o_{j},d_{j})$ and traffic rate $r_{j}=5$ . By the symmetry between OD pair indices and that between the vertices in the same OD pair, we may assume $(o_{1},d_{1})=(u,v)$ , $d_{2}=w$ and $o_{2}\in\{o_{1},d_{1}\}$ . The information set of type-1 travelers changes from $E_{1}=\{e_{2},e_{3}\}$ to larger $\tilde{E}_{1}=\{e_{2},e_{3},e_{4}\}$ , while the information set of type-2 travelers is always $E_{2}=\{e_{1},e_{2},e_{4}\}$ . Let $f$ and $\tilde{f}$ denote the ICWE flows before and after type-1 travelers enlarge their information set, respectively.

•

Clearly, $f^{1}_{e_{2}e_{3}}=5$ , $f^{2}_{e_{1}e_{4}}=5$ when $o_{2}=o_{1}$ and $f^{2}_{e_{4}}=5$ when $o_{2}=d_{1}$ , from which we deduce that under $f$ type-1 travelers experience latency $\ell^{1}(f)=47$ .
•

After type-1 travelers known about $e_{4}$ , some of them will use this “new” edge instead of $e_{3}$ . Easy computation shows that these travelers amount to $\tilde{f}^{1}_{e_{4}}=3$ , and the remaining $\tilde{f}^{1}_{e_{3}}=2$ amount of type-1 travelers stick to $e_{3}$ ; accordingly, type-2 travelers will split their routes: when $o_{2}=o_{1}$ (resp. $o_{2}=d_{1}$ ), amount 4 sticking to their left path $e_{1}e_{4}$ (resp. lower path $e_{4}$ ) and amount $1$ changing to their right path $e_{2}$ (resp. upper path $e_{1}e_{2}$ ). See Figure 4(b) and (c) for an illustration. It is easy to check that $\tilde{f}$ is indeed an ICWE flow under which type-1 travelers experience a higher latency $\ell^{1}(\tilde{f})=48$ .

In conclusion, $(F_{1},\ell,r,\{E_{1},E_{2}\},\{\tilde{E}_{1},E_{2}\})$ constitutes an IBP instance, saying that $F_{1}$ is not immune to IBP. Recalling Lemma 2 and the IBP-freeness of $G$ , we have the following corollary.

Corollary 1.

$F_{1}$ cannot be nicely embedded in $G$ .

3.2 Graphical Structures

Since $G=G_{1}=G_{2}$ is a non-coincident block of $G_{1}$ and $G_{2}$ , we have $\{o_{1},d_{1}\}\neq\{o_{2},d_{2}\}$ . A connected graph is $2$ -connected if it contains more than $2$ vertices and has no cut vertices. Since $G$ is a non-coincident block, it contains at least $3$ vertices, and therefore is 2-connected. The reader is referred to [23] for properties of 2-connected graphs. Setting $S=\{o_{1},d_{1},o_{2},d_{2}\}$ , we have $|S|\in\{3,4\}$ because $G$ is non-coincident. Note that if $F_{1}$ can be nicely embedded in $G$ , then there is a mapping $b:F_{1}\rightarrow G$ such that $b^{-1}(S)=\{u,v,w\}$ and $|b^{-1}(\{o_{i},d_{i}\})|=2$ for $i=1,2$ .

Recall that $G_{1}$ and $G_{2}$ are assumed to be SLI networks. So the theta graph $F_{2}$ in Figure 5 can neither be embedded in $G_{1}$ nor in $G_{2}$ [4].

Lemma 3.

If graph $G$ is not a cycle and contains a cycle $C$ with $|S-V(C)|\leq 1$ , then $F_{1}$ can be nicely embedded in $G$ .

Proof.

Suppose without loss of generality that $o_{1},d_{1},o_{2}\in V(C)$ . Since $G$ is not a cycle, we may take $e\in E(G)-E(C)$ such that $d_{2}$ is an end of $e$ whenever $d_{2}\not\in V(C)$ . By the 2-connectivity of $G$ , there is a path $P$ in $G$ between distinct vertices $x,y$ on $C$ that goes through $e$ and is internally disjoint from $C$ . Recall that the theta graph $F_{2}$ (see Figure 5) is not embeddable in $G_{1}$ . So one of the two $o_{1}$ - $d_{1}$ paths in $C$ contains both $x$ and $y$ . Now $C\cup P$ contains both OD pairs, i.e., $S$ . Let $H$ be obtained from $C\cup P$ by iteratively contracting edges as many as possible under the condition that no two distinct vertices from $S$ are merged and that $x$ and $y$ are not merged. If an edge with one end $z\in S\cup\{x,y\}$ is contracted, the vertex resulting from the contraction is named as $z$ . In particular, when both ends of the contracted edge are in $S\cup\{x,y\}$ , it must be the case that one end, say $z_{1}$ , is in $S-\{x,y\}$ and the other, say $z_{2}$ , is in $\{x,y\}-S$ , for which we consider the two ends merge to a new vertex $z_{1}=z_{2}\in S$ . The contraction process contracts $C$ to a cycle $D$ with $V(D)=(S\cap V(C))\cup\{x,y\}$ and contracts $P$ to an $x$ - $y$ path with $V(Q)=(S-V(C))\cup\{x,y\}$ . Thus $H$ with $V(H)=S\cup\{x,y\}$ is edge disjoint union of $D$ and $Q$ . To prove the lemma, it suffices to check that $F_{1}$ can be nicely embedded in $H$ . In the remainder of the proof, we focus on vertices of $H$ instead of those in the original graph $C\cup P$ .

By the construction of $H$ , each edge in $H$ has both ends in $S\cup\{x,y\}$ . If one of $x$ and $y$ , say $x$ , is outside $S$ , then there is an edge $e\in E(H)$ that joins $x$ and a vertex $z\in S-\{y\}$ , and $e$ should have been contracted in the above process of constructing $H$ . So we have $\{x,y\}\subseteq S$ and hence $V(H)=S$ . Note that $x$ and $y$ have degree 3, and other vertices have degree 2 in $H$ .

When $|S|=3$ , we deduce that $H$ with $|V(H)|=3$ is $F_{1}$ itself. It remains to consider the case where $|S|=4$ . If there is $e\in E(H)$ between $\{o_{1},d_{1}\}$ and $\{o_{2},d_{2}\}$ and $e$ does not join $x$ and $y$ , then $H/e=F_{1}$ shows that $F_{1}$ can be nicely embedded in $H$ . Next, we prove that such an edge $e$ does exist. When $x$ and $y$ have a common neighbor, at least one of the two edges incident with the common neighbor qualifies to be $e$ . When $x$ and $y$ have no common neighbor, $x$ and $y$ are neighbors in both $D$ and $Q$ , and there is a 3-edge $x$ - $y$ path in $D$ that contains $S$ ; it is easy to see that one of the three edges in the path qualifies to be the $e$ as desired. ∎

Lemma 4.

Either $G$ is a cycle or $F_{1}$ can be nicely embedded in $G$ .

Proof.

Suppose that $G$ is a 2-connected graph that is not a cycle. Let $C$ be a cycle in $G$ going through $o_{1}$ and $d_{1}$ . By Lemma 3, we only need to consider the case of $o_{2}\notin V(C)$ . Similar to the above proof, the 2-connectivity of $G$ gives a path $P$ between distinct vertices $x,y$ on $C$ that goes through $o_{2}$ and is internally disjoint from $C$ . In turn, excluding theta graph $F_{2}$ implies that both $x$ and $y$ are contained in one of the two $o_{1}$ - $d_{1}$ paths in $C$ ; we denote the path by $Q$ . Now $(C\setminus V(Q(x,y)))\cup P$ is a cycle in $G$ that contains $o_{1},d_{1},o_{2}$ . It follows from Lemma 3 that $F_{1}$ can be nicely embedded in $G$ . ∎

The combination of Lemma 4 and Corollary 1 enforces that $G$ is a cycle as desired. The “only if” part of Theorem 3 has been verified.

4 Sufficiency Proof

In this section, we justify the “if” part of Theorem 3. By contradiction, suppose that network $G$ with $n$ OD pairs satisfies the SLI condition and common block condition, but $G$ is not immune to IBP. It follows from the SLI condition and Proposition 1 that every block of $G$ is a block of some $G_{i}$ , $i\in[n]$ , which is therefore LI. Since $G$ is not immune to IBP, by Lemma 1, some block of $G$ , denoted by $C$ , is not immune to IBP. In turn, Theorem 1 implies that $C$ is a network with $n\,(\geq 2)$ OD pairs. Then, we deduce from Theorem 2 that $C$ is not a coincident block of its subnetworks, which, along with the common block condition, enforces that $C$ is a cycle. To reach a contraction and prove the sufficiency, it suffices to establish the following IBP-freeness.

Theorem 4.

A cycle $C$ with $n~{}(\geq 2)$ OD pairs is IBP-free.

Due to space limitations, the proof of Theorem 4 is deferred to Appendix B. The proof strategies can be summarized as follows:

•

Reduction to fewer traveler types: By Lemmas 5 and 6, we reduce the problem to be the one with fewer types of travelers: If IBP happens, then it happens on a cycle network such that each OD pair is associated with only one type of travelers. According to Lemma 7, we can assume that the travelers of the same type choose the same one OD path before the information expansion and a different OD path after the information expansion.
•

Increasing latencies and non-dominant traffic rates: If IBP occurs, for every type of travelers, the latency of the path chosen before the information expansion will strictly increase after the information expansion (see Lemma 8). In addition, when IBP occurs, the traffic rate of any type of travelers is strictly less than the total traffic rate of all the others (see Lemma 9). Then, we directly derive that a cycle with two OD pairs is IBP-free in Lemma 10, significantly streamlining the proof process in [1].
•

Reduction to fewer OD pairs via path coverage: In Lemma 11, if there are two types of travelers such that the union of their chosen paths covers the entire cycle in an IBP instance, then we can construct a new IBP instance with fewer OD pairs. By using this lemma and case analysis, it follows that a cycle with three OD pairs is IBP-free (see Lemma 12).
•

Reduction to fewer OD pairs via specific path choices: According to Lemmas 13 – 17, if two types of travelers with specific path choices exist in an IBP instance, then we can construct a new IBP instance with fewer OD pairs. Lemma 18 states the relationship between the path choices and the amount of flow in edges.
•

Symmetric structures: Next, we consider two structures on a cycle with $n$ OD pairs: a completely symmetric distribution of terminal vertices and an almost symmetric distribution of terminal vertices. These two structures are proven to be immune to IBP in Lemmas 19 and 20.
•

Traffic rate and structure transformations: In Lemma 21, we convert an IBP instance in a cycle with $n$ OD pairs to one with all integer traffic rates, and in Lemma 22, we transform an IBP instance in a cycle with a finite number of OD pairs such that all traffic rates are equal to $1$ . Moreover, Lemma 23 uses swap operations to convert a general IBP instance (with $n$ OD pairs) into an instance on a completely symmetric structured cycle or an almost symmetric structured cycle.
•

IBP-freeness: Finally, by combining Lemmas 19 – 23, we arrive at the main result of this section (Theorem 4): a cycle with $n$ OD pairs is IBP-free.

5 Concluding Remark

In this paper, we have characterized all undirected IBP-free networks with multiple OD pairs. Investigating the directed counterpart presents an intriguing and potentially challenging avenue for future research.

Our analysis could potentially be extended to other paradoxical settings. For example, classical BP represents the situation where adding an extra link to a network can sometimes strictly increase the travel times for travelers between one OD pair without decreasing travel times for all others. We propose exploring a “strong increase” version of BP, where adding an extra link to a network can sometimes strictly increase the travel times for all travelers whose OD paths contain the link. The analytical methods and characterization properties presented in this paper are also adaptable for studying networks that are immune to this stronger form of BP.

References

[1] Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Informational braess’ paradox: The effect of information on traffic congestion. Operations Research, 66(4):893–917, 2018.
[2] Dietrich Braess. Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung, 12(1):258–268, 1968.
[3] Xujin Chen, Zhuo Diao, and Xiaodong Hu. Network characterizations for excluding braess’s paradox. Theory of Computing Systems, 59(4):747–780, 2016.
[4] Igal Milchtaich. Network topology and the efficiency of equilibrium. Games and Economic Behavior, 57(2):321–346, 2006.
[5] Artur Czumaj. Selfish routing on the internet. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 42. Citeseer, 2004.
[6] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65–69, 2009.
[7] Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236–259, 2002.
[8] Ron Holzman and Nissan Law-yone (Lev-tov). Network structure and strong equilibrium in route selection games. Mathematical Social Sciences, 46(2):193–205, 2003.
[9] Charlotte Roman and Paolo Turrini. Multi-population congestion games with incomplete information. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 565–571. International Joint Conferences on Artificial Intelligence, 2019.
[10] Charlotte Daisy Roman. Routing choices in intelligent transport systems. PhD thesis, University of Warwick, 2021.
[11] Ariel Orda, Raphael Rom, and Nahum Shimkin. Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking, 1(5):510–521, 1993.
[12] Yannis A Korilis, Aurel A Lazar, and Ariel Orda. Achieving network optima using stackelberg routing strategies. IEEE/ACM Transactions on Networking, 5(1):161–173, 1997.
[13] Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49(3):237–252, 1998.
[14] Steven H Low and David E Lapsley. Optimization flow control. i. basic algorithm and convergence. IEEE/ACM Transactions on Networking, 7(6):861–874, 1999.
[15] Joel E Cohen and Paul Horowitz. Paradoxical behaviour of mechanical and electrical networks. Nature, 352(6337):699–701, 1991.
[16] Joel E Cohen and Clark Jeffries. Congestion resulting from increased capacity in single-server queueing networks. IEEE/ACM Transactions on Networking, 5(2):305–310, 1997.
[17] Tim Roughgarden. On the severity of braess’s paradox: Designing networks for selfish users is hard. Journal of Computer and System Sciences, 72(5):922–953, 2006.
[18] Igal Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111–124, 1996.
[19] Richard Cole, Thanasis Lianeas, and Evdokia Nikolova. When does diversity of agent preferences improve outcomes in selfish routing? In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), 2018.
[20] Reshef Meir and David Parkes. Congestion games with distance-based strict uncertainty. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[21] Shreyas Sekar, Liyuan Zheng, Lillian J Ratliff, and Baosen Zhang. Uncertainty in multicommodity routing networks: When does it help? IEEE Transactions on Automatic Control, 65(11):4600–4615, 2019.
[22] Manxi Wu, Saurabh Amin, and Asuman E Ozdaglar. Value of information in bayesian routing games. Operations Research, 69(1):148–163, 2021.
[23] Reinhard Diestel. Graph theory. Springer Berlin, Heidelberg, 2018.

Appendix A Two Critical Flaws in the Proof of Theorem 3 in [9]

This section raises valid concerns about the robustness of the proof of Theorem 3 in [9] by identifying the following two primary issues.

1.

Inequality Derivation (Page 569, left column, fifth paragraph): The inequality $\sum_{e\in s_{a}}c_{e}(f_{e}(\tilde{x}))$ $\leq\sum_{e\in s_{a}}c_{e}(f_{e}(x))$ is derived using the monotonicity of the functions $c_{e}$ . This derivation requires that $\ f_{e}(\tilde{x})\leq f_{e}(x)$ holds for all $e\in s_{a}$ . However, unfortunately, the single inequality $\sum_{e\in s_{a}}f_{e}(\tilde{x})\leq\sum_{e\in s_{a}}f_{e}(x)$ provided by the authors is insufficient to guarantee the required monotonicity condition for each individual term.
2.

Generality Oversight (Page 570, left column, first paragraph): The assertion “without loss of generality” fails to account for a crucial scenario: when the demand for $s_{\alpha i}$ decreases and belongs to $S_{\alpha}$ , while the demand for $s_{\beta i}$ increases and belongs to $S_{\beta}$ . This oversight is significant because this particular scenario cannot be used to support the result of Claim 3 in [9]. In fact, considering this case would lead to the opposite inequality, contradicting the intended conclusion.

Appendix B The Proof of Theorem 4

This section is devoted to the proof of Theorem 4. Without loss of generality, assume that any two terminal vertices $x$ and $y$ are distinct. (If $x$ and $y$ coincide at a single vertex, this vertex can be split into two different vertices, each incident with different (one of the) edges originally incident with the coincident vertex. Name these two vertices $x$ and $y$ , respectively, and add a zero-latency edge between them.) Additionally, it can also be assumed that all vertices on the cycle are terminal vertices in OD pairs. Otherwise, if there is a path of length at least $2$ between $x$ and $y$ that does not pass through any other terminal vertices, then the $x$ - $y$ path can be replaced with a single edge between $x$ and $y$ . The latency function of this edge would be the summation of the latency functions of the edges along the $x$ - $y$ path. In summary, we can assume that there are $2n$ vertices on the cycle $C$ , corresponding to $n$ origin vertices and $n$ destination vertices.

There are exactly two paths between each $(o_{i},d_{i})$ pair on the cycle $C$ , denoted as $\alpha_{i}$ and $\beta_{i}$ , for which we have $C=\alpha_{i}\cup\beta_{i}$ . Here, $C$ represents the set of edges on the cycle, and $\alpha_{i}$ and $\beta_{i}$ represent the sets of edges on the two paths, respectively.

For each OD pair $(o_{i},d_{i})$ , there may be more than one type of travelers taking it as their OD pair. For ease of presentation, we use “type- $(i,j)$ travelers” to mean the $j$ -th type of travelers whose OD pair is $(o_{i},d_{i})$ .

Let us assume that the type- $(1,0)$ travelers with OD pair $(o_{1},d_{1})$ have the expanded information sets. Let the path set before the information expansion be $\mathcal{P}_{(1,0)}=\{\alpha_{1}\}$ , and after the information expansion, the path set becomes $\tilde{\mathcal{P}}_{(1,0)}=\{\alpha_{1},\beta_{1}\}$ . The remaining types of travelers with the unchanged information sets can be defined as follows: For each $i\in[n]$ ,

•

The path set of type- $(i,1)$ travelers is $\mathcal{P}_{(i,1)}=\{\alpha_{i},\beta_{i}\}$ .
•

The path set of type- $(i,2)$ travelers is $\mathcal{P}_{(i,2)}=\{\alpha_{i}\}$ .
•

The path set of type- $(i,3)$ travelers is $\mathcal{P}_{(i,3)}=\{\beta_{i}\}$ .

In the game, there are $3n+1$ types of travelers. The following lemma shows that, aside from the type- $(1,0)$ travelers, it can be assumed that there are only type- $(i,1)$ travelers with the complete information for each $i\in[n]$ .

Lemma 5.

Suppose that $C$ is a cycle with $n$ OD pairs. If there is an IBP instance $(C,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ with $3n+1$ types of travelers $\bigcup_{i=1}^{n}\{(i,1),(i,2),(i,3)\}\cup\{(1,0)\}$ , then there is an IBP instance $(C,\ell^{\prime},r^{\prime},\mathcal{E}^{\prime},\tilde{\mathcal{E}^{\prime}})$ with $n+1$ types of travelers $\bigcup_{i=1}^{n}\{(i,1)\}\cup\{(1,0)\}$ .

Proof.

For any $i\in[n]$ , by the symmetry of $\alpha_{i}$ and $\beta_{i}$ , we only show a new IBP instance without type- $(i,2)$ travelers. Let $r_{(i,2)}$ be the traffic rate of type- $(i,2)$ travelers. Since type- $(i,2)$ travelers always choose to take $\alpha_{i}$ before and after the information expansion of type- $(1,0)$ travelers, the flow of this part can be fixed on the latency function of the edges in path $\alpha_{i}$ . That is, $\ell^{\prime}_{e}(x)=\ell_{e}(x+r_{(i,2)})$ for each $e\in\alpha_{i}$ and $\ell^{\prime}_{e}(x)=\ell(x)$ for each $e\in C\setminus\alpha_{i}$ . Therefore, we can construct a new IBP instance without type- $(i,2)$ and type- $(i,3)$ travelers for each $i\in[n]$ . ∎

Furthermore, we can construct an IBP instance that does not include type- $(1,1)$ travelers.

Lemma 6.

Suppose that $C$ is a cycle with $n$ OD pairs. If there is an IBP instance $(C,\ell,r,\mathcal{E},\tilde{\mathcal{E}})$ with $n+1$ types of travelers $\bigcup_{i=1}^{n}\{(i,1)\}\cup\{(1,0)\}$ , then there is an IBP instance $(C,\ell^{\prime},r^{\prime},\mathcal{E}^{\prime},\tilde{\mathcal{E}^{\prime}})$ with $n$ types of travelers $\bigcup_{i=2}^{n}\{(i,1)\}\cup\{(1,0)\}$ .

Proof.

Denote the path sets for type- $(1,0)$ travelers before and after the information expansion as $\mathcal{P}_{(1,0)}=\{\alpha_{1}\}$ and $\tilde{\mathcal{P}}_{(1,0)}=\{\alpha_{1},\beta_{1}\}$ , respectively. Suppose that $f$ and $\tilde{f}$ are ICWE flows of the network before and after the information expansion. First, we must have $\ell_{\alpha_{1}}(f)>\ell_{\beta_{1}}(f)$ . Otherwise, $f$ would be an ICWE flow of the network after the information expansion, and IBP would not occur. So $f_{\alpha_{1}}^{(1,1)}=0$ . Because the path selection of type- $(1,0)$ travelers changes before and after the information expansion, we have $r_{(1,0)}=f_{\alpha_{1}}^{(1,0)}>\tilde{f}_{\alpha_{1}}^{(1,0)}$ . We know that $f_{\alpha_{1}}=f_{\alpha_{1}}^{(1,0)}+f_{\alpha_{1}}^{(1,1)}=r_{(1,0)}+0=r_{(1,0)}$ and $f_{\beta_{1}}=f_{\beta_{1}}^{(1,1)}=r_{(1,1)}$ .

Next, we will prove that $r_{(1,0)}=f_{\alpha_{1}}>\tilde{f}_{\alpha_{1}}$ . Assume by contradiction that $\tilde{f}_{\alpha_{1}}\geq r_{(1,0)}$ . We construct a new feasible flow $\bar{f}$ for the network before the information expansion. For $i\geq 2$ and for any $P\in\mathcal{P}_{(i,1)}$ , set $\bar{f}_{P}^{(i,1)}=\tilde{f}_{P}^{(i,1)}$ . Let $\bar{f}_{\alpha_{1}}^{(1,0)}=r_{(1,0)}$ , $\bar{f}_{\beta_{1}}^{(1,0)}=0$ , $\bar{f}_{\alpha_{1}}^{(1,1)}=\tilde{f}_{\alpha_{1}}-r_{(1,0)}$ , and $\bar{f}_{\beta_{1}}^{(1,1)}=\tilde{f}_{\beta_{1}}$ . Then, we have $\bar{f}_{\alpha_{1}}=\bar{f}_{\alpha_{1}}^{(1,0)}+\bar{f}_{\alpha_{1}}^{(1,1)}=\tilde{f}_{\alpha_{1}}$ and $\bar{f}_{\beta_{1}}=\bar{f}_{\beta_{1}}^{(1,0)}+\bar{f}_{\beta_{1}}^{(1,1)}=\tilde{f}_{\beta_{1}}$ . Thus, for every OD path $P$ , $\bar{f}_{P}=\tilde{f}_{P}$ . So $\bar{f}$ is an ICWE flow in the network after the information expansion. Since $\bar{f}_{\alpha_{1}}^{(1,0)}=r_{(1,0)}$ , $\bar{f}$ is a feasible flow for the network before the information expansion. Thus, $\bar{f}$ is an ICWE flow for the network before the information expansion. By the uniqueness of ICWE, it follows that $\ell_{(1,0)}(f)=\ell_{(1,0)}(\bar{f})$ . Since $\bar{f}_{\alpha_{1}}=\tilde{f}_{\alpha_{1}}\geq r_{(1,0)}>0$ , we derive $\ell_{(1,0)}(f)=\ell_{(1,0)}(\bar{f})=\ell_{\alpha_{1}}(\bar{f})=\ell_{\alpha_{1}}(\tilde{f})=\ell_{(1,0)}(\tilde{f})$ , which contradicts with the definition of IBP ( $\ell_{(1,0)}(f)<\ell_{(1,0)}(\tilde{f})$ ). Therefore, $f_{\alpha_{1}}>\tilde{f}_{\alpha_{1}}$ .

Then, we construct a new flow $\hat{f}$ for the network after the information expansion with $\hat{f}_{\alpha_{1}}^{(1,1)}=0$ . For $i\geq 2$ and for any $P\in\mathcal{P}_{(i,1)}$ , $\hat{f}_{P}^{(i,1)}=\tilde{f}_{P}^{(i,1)}$ . $\hat{f}_{\alpha_{1}}^{(1,0)}=\tilde{f}_{\alpha_{1}}$ , $\hat{f}_{\beta_{1}}^{(1,0)}=r_{(1,0)}-\tilde{f}_{\alpha_{1}}$ , $\hat{f}_{\alpha_{1}}^{(1,1)}=0$ and $\hat{f}_{\beta_{1}}^{(1,1)}=r_{(1,1)}$ . Then, we have $\hat{f}_{\alpha_{1}}=\hat{f}_{\alpha_{1}}^{(1,0)}+\hat{f}_{\alpha_{1}}^{(1,1)}=\tilde{f}_{\alpha_{1}}$ and $\hat{f}_{\beta_{1}}=\hat{f}_{\beta_{1}}^{(1,0)}+\hat{f}_{\beta_{1}}^{(1,1)}=\tilde{f}_{\beta_{1}}$ . Thus, for every OD path $P$ , $\hat{f}_{P}=\tilde{f}_{P}$ . Thus, $\hat{f}$ is an ICWE of the network after the information expansion with $\hat{f}_{\alpha_{1}}^{(1,1)}=0$ . So type- $(1,1)$ travelers choose the same path of the network before and after the information expansion. By the proof of Lemma 5, we can derive the instance of IBP that results from excluding the type- $(1,1)$ travelers. ∎

By Lemma 6, We can assume that there are $n$ types of travelers in cycle $C$ . Travelers of $n$ types are re-denoted using a simplified notation: type- $i$ for each $i\in[n]$ with $(o_{i},d_{i})$ . Type- $1$ travelers have the expanded information sets $\mathcal{P}_{1}=\{\alpha_{1}\}$ and $\tilde{\mathcal{P}}_{1}=\{\alpha_{1},\beta_{1}\}$ . Type- $i$ travelers have the complete information sets $\{\alpha_{i},\beta_{i}\}$ for $i\in[n]\setminus\{1\}$ . In the remainder of this section, we represent an IBP instance using a simplified triple notation $(C,\ell,r)$ . Suppose that $f$ and $\tilde{f}$ are ICWE flows of the network before and after the information expansion. Since $f_{\alpha_{i}}+f_{\beta_{i}}=\tilde{f}_{\alpha_{i}}+\tilde{f}_{\beta_{i}}$ , we assume $\alpha_{i}$ satisfies $f_{\alpha_{i}}\geq\tilde{f}_{\alpha_{i}}$ and $\beta_{i}$ satisfies $f_{\beta_{i}}\leq\tilde{f}_{\beta_{i}}$ for each $i\in[n]$ . The subsequent lemma indicates that it is sufficient to consider the case where $f_{\beta_{i}}=0$ and $\tilde{f}_{\alpha_{i}}=0$ for each $i\in[n]$ .

Lemma 7.

Suppose that $C$ is a cycle with $n$ OD pairs. If there is an IBP instance $(C,\ell,r)$ with $n$ types of travelers in which all travelers except type- $1$ travelers have the whole cycle $C$ as their information set, then there is an IBP instance $(C,\ell^{\prime},r^{\prime})$ with $f_{\beta_{i}}=0$ and $\tilde{f}_{\alpha_{i}}=0$ for each $i\in[n]$ .

Proof.

Let $r^{\prime}_{i}=f_{\alpha_{i}}-\tilde{f}_{\alpha_{i}}=\tilde{f}_{\beta_{i}}-f_{\beta_{i}}$ and $\ell^{\prime}_{e}(x)=\ell_{e}(x+\sum_{e\in\alpha_{i}}\tilde{f}_{\alpha_{i}}+\sum_{e\in\beta_{i}}f_{\beta_{i}})$ for each $i\in[n]$ and $e\in E(C)$ . Let $f^{\prime}_{\alpha_{i}}=\tilde{f}^{\prime}_{\beta_{i}}=r^{\prime}_{i}$ and $f^{\prime}_{\beta_{i}}=\tilde{f}^{\prime}_{\alpha_{i}}=0$ . We have $\ell_{e}(f_{e})=\ell^{\prime}_{e}(f^{\prime}_{e})$ and $\ell_{e}(\tilde{f}_{e})=\ell^{\prime}_{e}(\tilde{f}^{\prime}_{e})$ for each $e\in E(C)$ . Then we have $f^{\prime}$ and $\tilde{f}^{\prime}$ are ICWE flows of $(G,\ell^{\prime},r^{\prime})$ before and after the information expansion. Since $(G,\ell,r)$ is an IBP instance, $(G,\ell^{\prime},r^{\prime})$ is an IBP instance with $f_{\beta_{i}}=0$ and $\tilde{f}_{\alpha_{i}}=0$ for each $i\in[n]$ . ∎

By Lemmas 6 and 7, we have that if there is an IBP instance $(C,\ell,r)$ with $n$ OD pairs, then there must be an IBP instance with $n$ types of travelers and each type of travelers chooses different paths before and after the information expansion. So we only need to consider this situation: $C$ is a cycle network with $n$ OD pairs and there are $n$ types of travelers. For each $i\in[n]$ , type- $i$ travelers’ OD pair is $(o_{i},d_{i})$ and all of them choose $o_{i}$ - $d_{i}$ path $\alpha_{i}$ before the information expansion and $\beta_{i}$ after the information expansion.

Recall that $f$ and $\tilde{f}$ are ICWE flows before and after the information expansion. Simplified notations:

•

For each edge $e$ , $\ell_{e}=\ell_{e}(f_{e})$ and $\tilde{\ell}_{e}=\ell_{e}(\tilde{f}_{e})$ .
•

For each $\alpha_{i}$ , $\ell_{\alpha_{i}}=\ell_{\alpha_{i}}(f)$ and $\tilde{\ell}_{\alpha_{i}}=\ell_{\alpha_{i}}(\tilde{f})$ .
•

For each $\beta_{i}$ , $\ell_{\beta_{i}}=\ell_{\beta_{i}}(f)$ and $\tilde{\ell}_{\beta_{i}}=\ell_{\beta_{i}}(\tilde{f})$ .

Under the circumstances where IBP occurs, we establish the following inequalities, with the explanation for each detailed after the colon.

1.

$\ell_{\beta_{1}}<\ell_{\alpha_{1}}$ : Otherwise, after the information expansion, the path choices of type- $1$ travelers will not change, which contradicts with the occurrence of IBP.
2.

$\ell_{\alpha_{1}}<\tilde{\ell}_{\beta_{1}}$ : From the definition of IBP, the latency of ICWE after the information expansion is strictly greater than the latency of ICWE before the information expansion.
3.

$\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}$ for each $2\leq i\leq n$ : It can be derived from $f$ being the ICWE before the information expansion and the type- $i$ travelers have complete information for each $2\leq i\leq n$ .
4.

$\tilde{\ell}_{\beta_{i}}\leq\tilde{\ell}_{\alpha_{i}}$ for each $1\leq i\leq n$ : It follows from $\tilde{f}$ being the ICWE after the information expansion and the type- $i$ travelers have complete information for each $1\leq i\leq n$ .

From the above properties, we can deduce the subsequent key lemma:

Lemma 8.

If IBP occurs, then $\ell_{\alpha_{i}}<\tilde{\ell}_{\alpha_{i}}$ for each $i\in[n]$ .

Proof.

According to the above inequalities (2) and (4), we have $\ell_{\alpha_{1}}<\tilde{\ell}_{\beta_{1}}\leq\tilde{\ell}_{\alpha_{1}}$ . By the inequalities (1), (2) and (4), we derive

\ell_{\alpha_{1}}+\ell_{\beta_{1}}<2\ell_{\alpha_{1}}<2\tilde{\ell}_{\beta_{1}}\leq\tilde{\ell}_{\alpha_{1}}+\tilde{\ell}_{\beta_{1}}.

Notice that $\ell_{\alpha_{i}}+\ell_{\beta_{i}}=\ell_{\alpha_{1}}+\ell_{\beta_{1}}$ and $\tilde{\ell}_{\alpha_{i}}+\tilde{\ell}_{\beta_{i}}=\tilde{\ell}_{\alpha_{1}}+\tilde{\ell}_{\beta_{1}}$ for each $2\leq i\leq n$ . According to the inequalities (3) and (4), for each $2\leq i\leq n$ , we have

\ell_{\alpha_{i}}\leq\frac{1}{2}(\ell_{\alpha_{i}}+\ell_{\beta_{i}})=\frac{1}{2}(\ell_{\alpha_{1}}+\ell_{\beta_{1}})<\frac{1}{2}(\tilde{\ell}_{\alpha_{1}}+\tilde{\ell}_{\beta_{1}})=\frac{1}{2}(\tilde{\ell}_{\alpha_{i}}+\tilde{\ell}_{\beta_{i}})\leq\tilde{\ell}_{\alpha_{i}},

which completes the proof. ∎

For the traffic rate $r_{i}$ of type- $i$ travelers, the following lemma is established.

Lemma 9.

If IBP occurs, then $r_{i}<\sum_{j\neq i}r_{j}$ for each $i\in[n]$ .

Proof.

Suppose there exists $i\in[n]$ such that $r_{i}\geq\sum_{j\neq i}r_{j}$ . Consider the path $\alpha_{i}$ . For arbitrary edge $e\in\alpha_{i}$ , $f_{e}\geq r_{i}$ and $\tilde{f}_{e}\leq\sum_{j\neq i}r_{j}$ hold, which means $f_{e}\geq\tilde{f}_{e}$ for each $e\in\alpha_{i}$ . Due to the monotonicity of the latency function, $\ell_{e}\geq\tilde{\ell}_{e}$ for each $e\in\alpha_{i}$ . Then $\ell_{\alpha_{i}}=\sum_{e\in\alpha_{i}}\ell_{e}\geq\sum_{e\in\alpha_{i}}\tilde{\ell}_{e}=\tilde{\ell}_{\alpha_{i}}$ , which contradicts with the result of Lemma 8. ∎

Lemma 10.

A cycle $C$ with two OD pairs is immune to IBP.

Proof.

If IBP occurs, by Lemma 9, the inequalities $r_{1}<r_{2}$ and $r_{2}<r_{1}$ hold simultaneously, which is a contradiction. ∎

Lemma 11.

If there is an IBP instance $(C,\ell,r)$ with $n~{}(\geq 3)$ types of travelers, which satisfies one of the following conditions:

1.

$\exists~{}i,j$ , $\beta_{i}\cup\beta_{j}=C$ ;
2.

$\exists~{}i\neq 1,j\neq 1$ , $\alpha_{i}\cup\alpha_{j}=C$ ,

then we can construct a new IBP instance with $n-1$ types of travelers.

Proof.

Suppose there exists $i$ and $j$ with $\beta_{i}\cup\beta_{j}=C$ . Since $\alpha_{i}\cup\beta_{i}=C$ and $\alpha_{j}\cup\beta_{j}=C$ , then $\alpha_{i}\subset\beta_{j}$ and $\alpha_{j}\subset\beta_{i}$ . Notice that $\alpha_{i}=\beta_{j}\setminus\beta_{i}$ and $\alpha_{j}=\beta_{i}\setminus\beta_{j}$ . Then we have $\tilde{\ell}_{\beta_{i}}\leq\tilde{\ell}_{\alpha_{i}}=\tilde{\ell}_{\beta_{j}\setminus\beta_{i}}\leq\tilde{\ell}_{\beta_{j}}$ and $\tilde{\ell}_{\beta_{j}}\leq\tilde{\ell}_{\alpha_{j}}=\tilde{\ell}_{\beta_{i}\setminus\beta_{j}}\leq\tilde{\ell}_{\beta_{i}}$ . Thus, $\tilde{\ell}_{\alpha_{i}}=\tilde{\ell}_{\beta_{i}}=\tilde{\ell}_{\alpha_{j}}=\tilde{\ell}_{\beta_{j}}$ and $\tilde{\ell}_{\beta_{i}\cap\beta_{j}}=0$ .

Assume, without loss of generality, that $r_{i}\leq r_{j}$ . Construct a new flow $\bar{f}$ : For $k\in[n]\setminus\{i,j\}$ , $\bar{f}_{\alpha_{k}}=0$ and $\bar{f}_{\beta_{k}}=r_{k}$ ; $\bar{f}_{\alpha_{i}}=r_{i}$ , $\bar{f}_{\beta_{i}}=0$ , $\bar{f}_{\alpha_{j}}=r_{i}$ and $\bar{f}_{\beta_{j}}=r_{j}-r_{i}$ . Thus $\bar{f}_{e}=\tilde{f}_{e}$ for any $e\in\alpha_{i}\cup\alpha_{j}$ and $\bar{f}_{e}\leq\tilde{f}_{e}$ for any $e\in\beta_{i}\cap\beta_{j}$ . Then, we derive that $\ell_{e}(\bar{f}_{e})=\tilde{\ell}_{e}$ for any $e\in C$ . Therefore, $\bar{f}$ is an ICWE flow after the information expansion. Then, we know that type- $i$ travelers choose the same path of the network before and after the information expansion. If $i=1$ , then $\bar{f}$ is an ICWE flow in the network before the information expansion. Then we derive that $\ell_{\alpha_{1}}=\ell_{\alpha_{1}}(\bar{f})=\tilde{\ell}_{\alpha_{1}}$ , which contradicts with Lemma 8. Thus, $i\neq 1$ . By the proof of Lemma 5, we can derive the instance of IBP with $n-1$ types travelers.

The proof of the situation $\exists~{}i\neq 1,j\neq 1$ , $\alpha_{i}\cup\alpha_{j}=C$ is similar.

Suppose there exists $i\neq 1$ and $j\neq 1$ with $\alpha_{i}\cup\alpha_{j}=C$ . Since $\alpha_{i}\cup\beta_{i}=C$ and $\alpha_{j}\cup\beta_{j}=C$ , then $\beta_{i}\subset\alpha_{j}$ and $\beta_{j}\subset\alpha_{i}$ . Notice that $\beta_{i}=\alpha_{j}\setminus\alpha_{i}$ and $\beta_{j}=\alpha_{i}\setminus\alpha_{j}$ . Then we have $\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}=\ell_{\alpha_{j}\setminus\alpha_{i}}\leq\ell_{\alpha_{j}}$ and $\ell_{\alpha_{j}}\leq\ell_{\beta_{j}}=\ell_{\alpha_{i}\setminus\alpha_{j}}\leq\ell_{\alpha_{i}}$ . Thus, $\ell_{\beta_{i}}=\ell_{\alpha_{i}}=\ell_{\beta_{j}}=\ell_{\alpha_{j}}$ and $\ell_{\alpha_{i}\cap\alpha_{j}}=0$ .

Assume, without loss of generality, that $r_{i}\leq r_{j}$ . Construct a new flow $\hat{f}$ : For $k\in[n]\setminus\{i,j\}$ , $\hat{f}_{\alpha_{k}}=r_{k}$ and $\hat{f}_{\beta_{k}}=0$ ; $\hat{f}_{\alpha_{i}}=0$ , $\hat{f}_{\beta_{i}}=r_{i}$ , $\hat{f}_{\alpha_{j}}=r_{j}-r_{i}$ and $\hat{f}_{\beta_{j}}=r_{i}$ . Thus $\hat{f}_{e}=f_{e}$ for any $e\in\beta_{i}\cup\beta_{j}$ and $\hat{f}_{e}\leq f_{e}$ for any $e\in\alpha_{i}\cap\alpha_{j}$ . Then, we derive that $\ell_{e}(\hat{f}_{e})=\ell_{e}$ for any $e\in C$ . Therefore, $\hat{f}$ is an ICWE flow before the information expansion. Then, we know that type- $i$ travelers choose the same path of the network before and after the information expansion. By the proof of Lemma 5, we can derive the instance of IBP with $n-1$ types travelers. ∎

Lemma 12.

A cycle $C$ with three OD pairs is immune to IBP.

Proof.

Assume that IBP occurs by contradiction. We will discuss the following scenarios.

1.

There exist $i$ and $j$ such that $\alpha_{i}\subset\alpha_{j}$ .

For any $e\in\alpha_{i}$ , according to Lemma 9, we derive that $f_{e}\geq r_{i}+r_{j}>r_{k}\geq\tilde{f}_{e}$ where $k=\{1,2,3\}\setminus\{i,j\}$ . Then, it follows that $\ell_{\alpha_{i}}\geq\tilde{\ell}_{\alpha_{i}}$ , which contradicts with Lemma 8.
2.

There exist $i$ and $j$ such that $\alpha_{i}\cap\alpha_{j}=\emptyset$ .

Then we have $\beta_{i}\cup\beta_{j}=C$ . By Lemma 11, we can construct a new IBP instance with $2$ types of travelers, which contradicts with Lemma 10.
3.

There exist $i$ and $j$ such that $\alpha_{i}\cup\alpha_{j}=C$ .

If $\{i,j\}=\{2,3\}$ , according to Lemma 11, we can construct a new IBP instance with $2$ types of travelers, which contradicts with Lemma 10.

Otherwise, suppose that $j>i=1$ and let $k=\{2,3\}\setminus\{j\}$ . For any $e\in\alpha_{k}$ , according to Lemma 9, we deduce that $f_{e}\geq r_{k}+\min\{r_{1},r_{j}\}>\max\{r_{1},r_{j}\}\geq\tilde{f}_{e}$ . Then, we show that $\ell_{\alpha_{k}}\geq\tilde{\ell}_{\alpha_{k}}$ , which contradicts with Lemma 8.
4.

For any $i$ and $j$ such that $\alpha_{i}\setminus\alpha_{j}\neq\emptyset$ , $\alpha_{i}\cap\alpha_{j}\neq\emptyset$ and $\alpha_{i}\cup\alpha_{j}\neq C$ .

Figure 6: The symmetric structured network with three OD pairs

In this scenario, the network can only consist of the following structure with three OD pairs as shown in Figure 6. In such a network structure, due to symmetry, we can assume that $\alpha_{1}$ represents the clockwise direction from $o_{1}$ to $d_{1}$ . There are four possible classifications for the paths of $\alpha_{2}$ and $\alpha_{3}$ . In the following three cases as shown in Figure 7, for any $e\in\alpha_{i}$ , according to Lemma 9, we derive that $f_{e}\geq r_{i}+\min\{r_{j},r_{k}\}>\max\{r_{j},r_{k}\}\geq\tilde{f}_{e}$ where $\{i,j,k\}=\{1,2,3\}$ . Then, it follows that $\ell_{\alpha_{i}}\geq\tilde{\ell}_{\alpha_{i}}$ , which contradicts with Lemma 8. The last case is shown in Figure 8. Since $\ell_{\alpha_{2}}\leq\ell_{\beta_{2}}$ and $\ell_{\alpha_{3}}\leq\ell_{\beta_{3}}$ , $\ell_{e_{1}}+\ell_{e_{5}}+\ell_{e_{6}}\leq\ell_{e_{2}}+\ell_{e_{3}}+\ell_{e_{4}}$ and $\ell_{e_{3}}+\ell_{e_{4}}+\ell_{e_{5}}\leq\ell_{e_{1}}+\ell_{e_{2}}+\ell_{e_{6}}$ . So $\ell_{e_{5}}\leq\ell_{e_{2}}$ . Similarly, since $\tilde{\ell}_{\beta_{2}}\leq\tilde{\ell}_{\alpha_{2}}$ and $\tilde{\ell}_{\beta_{3}}\leq\tilde{\ell}_{\alpha_{3}}$ , we show that $\tilde{\ell}_{e_{2}}\leq\tilde{\ell}_{e_{5}}$ . According to Lemma 9, $f_{e_{5}}=r_{2}+r_{3}>r_{1}=\tilde{f}_{e_{5}}$ , which means that $\ell_{e_{5}}\geq\tilde{\ell}_{e_{5}}$ . Similarly, we reveal that $\ell_{e_{1}}\geq\tilde{\ell}_{e_{1}}$ and $\ell_{e_{3}}\geq\tilde{\ell}_{e_{3}}$ . By Lemma 8, $\ell_{e_{1}}+\ell_{e_{2}}+\ell_{e_{3}}=\ell_{\alpha_{1}}<\tilde{\ell}_{\alpha_{1}}=\tilde{\ell}_{e_{1}}+\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ . Then we deduce that $\tilde{\ell}_{e_{2}}>\ell_{e_{2}}$ . Combining the above inequalities, $\tilde{\ell}_{e_{5}}\geq\tilde{\ell}_{e_{2}}>\ell_{e_{2}}\geq\ell_{e_{5}}\geq\tilde{\ell}_{e_{5}}$ , which is a contradiction.

Therefore, a cycle with three OD pairs is IBP-free. ∎

Similar to the fourth case in the proof of Lemma 12, we consider a structure on a cycle with $n$ OD pairs: a completely symmetric distribution of terminal vertices, as shown in Figure 9, which satisfies the following conditions: For any $i$ and $j$ such that $\alpha_{i}\setminus\alpha_{j}\neq\emptyset$ , $\alpha_{i}\cap\alpha_{j}\neq\emptyset$ and $\alpha_{i}\cup\alpha_{j}\neq C$ .

We can represent the paths of type- $i$ travelers by defining an index as follows: For any $i\in[n]$ , define

\sigma(i)=\begin{cases}1&\text{$\alpha_{i}$ is the clockwise path from $o_{i}$ to $d_{i}$.}\\ -1&\text{$\alpha_{i}$ is the counterclockwise path from $o_{i}$ to $d_{i}$.}\\ \end{cases}

Without loss of generality, we assume that $\sigma(1)=1$ .

Lemma 13.

Consider $n\geq 3$ and any $i\neq 1,j\neq 1$ . Let $e_{1}=o_{i}o_{j}$ , $e_{2}=d_{i}d_{j}$ and $r=\sum_{i=1}^{n}r_{i}$ .

1.

If $\sigma(i)=1$ , $\sigma(j)=-1$ and $f_{e_{1}}\geq\frac{r}{2}\geq f_{e_{2}}$ , then $\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ .
2.

If $\sigma(i)=-1$ , $\sigma(j)=1$ and $f_{e_{1}}\leq\frac{r}{2}\leq f_{e_{2}}$ , then $\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ .

Proof.

1. If $\sigma(i)=1$ and $\sigma(j)=-1$ , then $\alpha_{i}\cap\alpha_{j}=\{e_{1}\}$ and $C\setminus(\alpha_{i}\cup\alpha_{j})=\{e_{2}\}$ . We deduce that $\ell_{\alpha_{i}}+\ell_{\alpha_{j}}=\sum_{e\in C}\ell_{e}+\ell_{e_{1}}-\ell_{e_{2}}$ and $\ell_{\beta_{i}}+\ell_{\beta_{j}}=\sum_{e\in C}\ell_{e}-\ell_{e_{1}}+\ell_{e_{2}}$ . Since $\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}$ and $\ell_{\alpha_{j}}\leq\ell_{\beta_{j}}$ , $\sum_{e\in C}\ell_{e}+\ell_{e_{1}}-\ell_{e_{2}}\leq\sum_{e\in C}\ell_{e}-\ell_{e_{1}}+\ell_{e_{2}}$ . Thus, we have $\ell_{e_{1}}\leq\ell_{e_{2}}$ . Similarly, we derive $\tilde{\ell}_{e_{1}}\geq\tilde{\ell}_{e_{2}}$ . As $f_{e_{1}}\geq\frac{r}{2}\geq\tilde{f}_{e_{1}}$ , it follows $\ell_{e_{1}}\geq\tilde{\ell}_{e_{1}}$ . As $f_{e_{2}}\leq\frac{r}{2}\leq\tilde{f}_{e_{2}}$ , it follows $\ell_{e_{2}}\leq\tilde{\ell}_{e_{2}}$ . Combining the above inequalities, we obtain that $\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ .

2. If $\sigma(i)=-1$ and $\sigma(j)=1$ , then $\alpha_{i}\cap\alpha_{j}=\{e_{2}\}$ and $C\setminus(\alpha_{i}\cup\alpha_{j})=\{e_{1}\}$ . We deduce that $\ell_{\alpha_{i}}+\ell_{\alpha_{j}}=\sum_{e\in C}\ell_{e}+\ell_{e_{2}}-\ell_{e_{1}}$ and $\ell_{\beta_{i}}+\ell_{\beta_{j}}=\sum_{e\in C}\ell_{e}-\ell_{e_{2}}+\ell_{e_{1}}$ . Since $\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}$ and $\ell_{\alpha_{j}}\leq\ell_{\beta_{j}}$ , $\sum_{e\in C}\ell_{e}+\ell_{e_{2}}-\ell_{e_{1}}\leq\sum_{e\in C}\ell_{e}-\ell_{e_{2}}+\ell_{e_{1}}$ . Thus, we have $\ell_{e_{2}}\leq\ell_{e_{1}}$ . Similarly, we derive $\tilde{\ell}_{e_{2}}\geq\tilde{\ell}_{e_{1}}$ . As $f_{e_{1}}\leq\frac{r}{2}\leq\tilde{f}_{e_{1}}$ , it follows $\ell_{e_{1}}\leq\tilde{\ell}_{e_{1}}$ . As $f_{e_{2}}\geq\frac{r}{2}\geq\tilde{f}_{e_{2}}$ , it follows $\ell_{e_{2}}\geq\tilde{\ell}_{e_{2}}$ . Combining the above inequalities, we obtain that $\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ . ∎

Lemma 14.

Consider $n\geq 3$ and any $i\neq 1,j\neq 1$ . Let $e_{1}=o_{i}o_{j}$ , $e_{2}=d_{i}d_{1}$ , $e_{3}=d_{1}d_{j}$ and $r=\sum_{i=1}^{n}r_{i}$ .

1.

If $\sigma(i)=1$ , $\sigma(j)=-1$ , $f_{e_{1}}\geq\frac{r}{2}$ and $f_{e_{2}},~{}f_{e_{3}}\leq\frac{r}{2}$ , then $\ell_{e_{1}}=\tilde{\ell}_{e_{1}}=\ell_{e_{2}}+\ell_{e_{3}}=\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ .
2.

If $\sigma(i)=-1$ , $\sigma(j)=1$ , $f_{e_{1}}\leq\frac{r}{2}$ and $f_{e_{2}},~{}f_{e_{3}}\geq\frac{r}{2}$ , then $\ell_{e_{1}}=\tilde{\ell}_{e_{1}}=\ell_{e_{2}}+\ell_{e_{3}}=\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ .

Proof.

1. If $\sigma(i)=1$ and $\sigma(j)=-1$ , then $\alpha_{i}\cap\alpha_{j}=\{e_{1}\}$ and $C\setminus(\alpha_{i}\cup\alpha_{j})=\{e_{2},e_{3}\}$ . We deduce that $\ell_{\alpha_{i}}+\ell_{\alpha_{j}}=\sum_{e\in C}\ell_{e}+\ell_{e_{1}}-\ell_{e_{2}}-\ell_{e_{3}}$ and $\ell_{\beta_{i}}+\ell_{\beta_{j}}=\sum_{e\in C}\ell_{e}-\ell_{e_{1}}+\ell_{e_{2}}+\ell_{e_{3}}$ . Since $\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}$ and $\ell_{\alpha_{j}}\leq\ell_{\beta_{j}}$ , $\sum_{e\in C}\ell_{e}+\ell_{e_{1}}-\ell_{e_{2}}-\ell_{e_{3}}\leq\sum_{e\in C}\ell_{e}-\ell_{e_{1}}+\ell_{e_{2}}+\ell_{e_{3}}$ . Thus, we have $\ell_{e_{1}}\leq\ell_{e_{2}}+\ell_{e_{3}}$ . Similarly, we derive $\tilde{\ell}_{e_{1}}\geq\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ . As $f_{e_{1}}\geq\frac{r}{2}\geq\tilde{f}_{e_{1}}$ , it follows $\ell_{e_{1}}\geq\tilde{\ell}_{e_{1}}$ . As $f_{e_{2}}\leq\frac{r}{2}\leq\tilde{f}_{e_{2}}$ and $f_{e_{3}}\leq\frac{r}{2}\leq\tilde{f}_{e_{3}}$ , it follows $\ell_{e_{2}}+\ell_{e_{3}}\leq\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ . Combining the above inequalities, we obtain that $\ell_{e_{1}}=\tilde{\ell}_{e_{1}}=\ell_{e_{2}}+\ell_{e_{3}}=\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ .

2. If $\sigma(i)=-1$ and $\sigma(j)=1$ , then $\alpha_{i}\cap\alpha_{j}=\{e_{2},e_{3}\}$ and $C\setminus(\alpha_{i}\cup\alpha_{j})=\{e_{1}\}$ . We deduce that $\ell_{\alpha_{i}}+\ell_{\alpha_{j}}=\sum_{e\in C}\ell_{e}+\ell_{e_{2}}+\ell_{e_{3}}-\ell_{e_{1}}$ and $\ell_{\beta_{i}}+\ell_{\beta_{j}}=\sum_{e\in C}\ell_{e}-\ell_{e_{2}}-\ell_{e_{3}}+\ell_{e_{1}}$ . Since $\ell_{\alpha_{i}}\leq\ell_{\beta_{i}}$ and $\ell_{\alpha_{j}}\leq\ell_{\beta_{j}}$ , $\sum_{e\in C}\ell_{e}+\ell_{e_{2}}+\ell_{e_{3}}-\ell_{e_{1}}\leq\sum_{e\in C}\ell_{e}-\ell_{e_{2}}-\ell_{e_{3}}+\ell_{e_{1}}$ . Thus, we have $\ell_{e_{2}}+\ell_{e_{3}}\leq\ell_{e_{1}}$ . Similarly, we derive $\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}\geq\tilde{\ell}_{e_{1}}$ . As $f_{e_{1}}\leq\frac{r}{2}\leq\tilde{f}_{e_{1}}$ , it follows $\ell_{e_{1}}\leq\tilde{\ell}_{e_{1}}$ . As $f_{e_{2}}\geq\frac{r}{2}\geq\tilde{f}_{e_{2}}$ and $f_{e_{3}}\geq\frac{r}{2}\geq\tilde{f}_{e_{3}}$ , it follows $\ell_{e_{2}}+\ell_{e_{3}}\geq\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ . Combining the above inequalities, we obtain that $\ell_{e_{1}}=\tilde{\ell}_{e_{1}}=\ell_{e_{2}}+\ell_{e_{3}}=\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ . ∎

Next, we introduce three edge contraction lemmas.

Lemma 15.

Given an IBP instance $(C,\ell,r)$ with $n~{}(\geq 3)$ types of travelers, if there exist two edges $e_{1}=o_{i}o_{j}$ and $e_{2}=d_{i}d_{j}$ with $i\neq 1$ and $j\neq 1$ satisfying the following conditions:

1.

$|\alpha_{k}\cap\{e_{1},e_{2}\}|=1$ for any $k\in[n]$ ;
2.

$\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ ,

then we can construct a new IBP instance with $n-1$ types of travelers.

Proof.

Suppose that $f$ and $\tilde{f}$ are ICWE flows of the network before and after the information expansion. By shrinking $e_{1}$ and $e_{2}$ on $C$ , we obtain a resulting cycle $C^{\prime}$ . The new labels for the contracted vertices are denoted as $o_{i^{\prime}}$ and $d_{i^{\prime}}$ after shrinking $e_{1}$ and $e_{2}$ , respectively. Let $\alpha_{k}^{\prime}$ be the restricted path of $\alpha_{k}$ on $C^{\prime}$ and $\beta_{k}^{\prime}$ be the restricted path of $\beta_{k}$ on $C^{\prime}$ for $k\in[n]$ . We have that $\ell_{\alpha_{k}^{\prime}}=\ell_{\alpha_{k}}-\ell_{e_{1}}$ , $\ell_{\beta_{k}^{\prime}}=\ell_{\beta_{k}}-\ell_{e_{1}}$ , $\tilde{\ell}_{\alpha_{k}^{\prime}}=\tilde{\ell}_{\alpha_{k}}-\ell_{e_{1}}$ and $\tilde{\ell}_{\beta_{k}^{\prime}}=\tilde{\ell}_{\beta_{k}}-\ell_{e_{1}}$ for $k\in[n]$ .

•

For type- $1$ , $\tilde{\ell}_{\beta_{1}^{\prime}}\leq\tilde{\ell}_{\alpha_{1}^{\prime}}$ and $\ell_{\alpha_{1}^{\prime}}<\tilde{\ell}_{\beta_{1}^{\prime}}$ .
•

For type- $k$ where $k\in[n]\setminus\{1,i,j\}$ , $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ .
•

The type- $i$ and type- $j$ travelers are removed, and type- $i^{\prime}$ travelers with $r_{i^{\prime}}=r_{i}+r_{j}$ are added. The type- $i^{\prime}$ travelers choose $\alpha_{i}^{\prime}$ with $r_{i}$ and $\alpha_{j}^{\prime}$ with $r_{j}$ before the information expansion, while they choose $\beta_{i}^{\prime}$ with $r_{i}$ and $\beta_{j}^{\prime}$ with $r_{j}$ after the information expansion. We have that $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ for $k\in\{i,j\}$ .

We can conclude that $f$ and $\tilde{f}$ restricted on $C^{\prime}$ are ICWE flows of $C^{\prime}$ before and after the information expansion. Thus, we derive a new IBP instance with $n-1$ types of travelers. ∎

Lemma 16.

1.

$|\alpha_{k}\cap\{e_{1},e_{2}\}|=1$ for any $k\in[n]\setminus\{1\}$ ;
2.

$\ell_{e_{1}}=\ell_{e_{2}}=\tilde{\ell}_{e_{1}}=\tilde{\ell}_{e_{2}}$ ;
3.

$\beta_{1}\subset\beta_{t}\cup\{e_{1},e_{2}\}$ for some $t\neq 1$ and $|\alpha_{1}\cap\{e_{1},e_{2}\}|\geq 1$ ,

then we can construct a new IBP instance with $n-1$ types of travelers.

Proof.

•

For type- $1$ , it follows that $\ell_{\alpha_{1}^{\prime}}<\tilde{\ell}_{\beta_{1}^{\prime}}$ . Since $\beta_{1}\subset\beta_{t}\cup\{e_{1},e_{2}\}$ , $\beta_{1}^{\prime}\subset\beta_{t}^{\prime}$ and $\alpha_{t}^{\prime}\subset\alpha_{1}^{\prime}$ . Thus, $\tilde{\ell}_{\beta_{1}^{\prime}}\leq\tilde{\ell}_{\beta_{t}^{\prime}}\leq\tilde{\ell}_{\alpha_{t}^{\prime}}\leq\tilde{\ell}_{\alpha_{1}^{\prime}}$ .
•

For type- $k$ where $k\in[n]\setminus\{1,i,j\}$ , $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ .
•

The type- $i$ and type- $j$ travelers are removed, and type- $i^{\prime}$ travelers with $r_{i^{\prime}}=r_{i}+r_{j}$ are added. The type- $i^{\prime}$ travelers choose $\alpha_{i}^{\prime}$ with $r_{i}$ and $\alpha_{j}^{\prime}$ with $r_{j}$ before the information expansion, while they choose $\beta_{i}^{\prime}$ with $r_{i}$ and $\beta_{j}^{\prime}$ with $r_{j}$ after the information expansion. We have that $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ for $k\in\{i,j\}$ .

Lemma 17.

Given an IBP instance $(C,\ell,r)$ with $n~{}(\geq 3)$ types of travelers, if there exist three edges $e_{1}=o_{i}o_{j}$ , $e_{2}=d_{i}d_{1}$ and $e_{3}=d_{1}d_{j}$ with $i\neq 1$ and $j\neq 1$ satisfying the following conditions:

1.

For any $k\in[n]\setminus\{1\}$ ,it follows that $e_{1}\in\alpha_{k}$ , $e_{2},e_{3}\in\beta_{k}$ or that $e_{2},e_{3}\in\alpha_{k}$ , $e_{1}\in\beta_{k}$ ;
2.

$\ell_{e_{1}}=\tilde{\ell}_{e_{1}}=\ell_{e_{2}}+\ell_{e_{3}}=\tilde{\ell}_{e_{2}}+\tilde{\ell}_{e_{3}}$ ;
3.

$\beta_{1}\subset\beta_{t}\cup\{e_{2},e_{3}\}$ for some $t\neq 1$ and $e_{1}\in\alpha_{1}$ ,

then we can construct a new IBP instance with $n-1$ types of travelers.

Proof.

Suppose that $f$ and $\tilde{f}$ are ICWE flows of the network before and after the information expansion. By shrinking $e_{1}$ and $e_{2}$ on $C$ , we obtain a resulting cycle $C^{\prime}$ . The new labels for the contracted vertices are denoted as $o_{i^{\prime}}$ and $d_{i^{\prime}}$ after shrinking $e_{1}$ and $e_{2}$ , respectively. We change the latency on edge $e_{3}$ to $0$ and relabel $d_{j+1}$ as $d_{1}$ . Let $\alpha_{k}^{\prime}$ be the restricted path of $\alpha_{k}$ on $C^{\prime}$ and $\beta_{k}^{\prime}$ be the restricted path of $\beta_{k}$ on $C^{\prime}$ for $k\in[n]$ . We have that $\ell_{\alpha_{k}^{\prime}}=\ell_{\alpha_{k}}-\ell_{e_{1}}$ , $\ell_{\beta_{k}^{\prime}}=\ell_{\beta_{k}}-\ell_{e_{1}}$ , $\tilde{\ell}_{\alpha_{k}^{\prime}}=\tilde{\ell}_{\alpha_{k}}-\ell_{e_{1}}$ and $\tilde{\ell}_{\beta_{k}^{\prime}}=\tilde{\ell}_{\beta_{k}}-\ell_{e_{1}}$ for $k\in[n]\setminus\{1\}$ . In addition, $\ell_{\alpha_{1}^{\prime}}\leq\ell_{\alpha_{1}}-\ell_{e_{1}}$ and $\tilde{\ell}_{\beta_{1}^{\prime}}\geq\tilde{\ell}_{\beta_{1}}-\ell_{e_{1}}$ .

•

For type- $1$ , it follows that $\ell_{\alpha_{1}^{\prime}}<\tilde{\ell}_{\beta_{1}^{\prime}}$ . Since $\beta_{1}\subset\beta_{t}\cup\{e_{1},e_{2}\}$ , $\beta_{1}^{\prime}\subset\beta_{t}^{\prime}$ and $\alpha_{t}^{\prime}\subset\alpha_{1}^{\prime}$ . Thus, $\tilde{\ell}_{\beta_{1}^{\prime}}\leq\tilde{\ell}_{\beta_{t}^{\prime}}\leq\tilde{\ell}_{\alpha_{t}^{\prime}}\leq\tilde{\ell}_{\alpha_{1}^{\prime}}$ .
•

For type- $k$ where $k\in[n]\setminus\{1,i,j\}$ , $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ .
•

The type- $i$ and type- $j$ travelers are removed, and type- $i^{\prime}$ travelers with $r_{i^{\prime}}=r_{i}+r_{j}$ are added. The type- $i^{\prime}$ travelers choose $\alpha_{i}^{\prime}$ with $r_{i}$ and $\alpha_{j}^{\prime}$ with $r_{j}$ before the information expansion, while they choose $\beta_{i}^{\prime}$ with $r_{i}$ and $\beta_{j}^{\prime}$ with $r_{j}$ after the information expansion. We have that $\tilde{\ell}_{\beta_{k}^{\prime}}\leq\tilde{\ell}_{\alpha_{k}^{\prime}}$ and $\ell_{\alpha_{k}^{\prime}}\leq\ell_{\beta_{k}^{\prime}}$ for $k\in\{i,j\}$ .

Lemma 18.

For any $i\in\{1,\ldots,n\}$ , if $\sigma(i)=1$ , then $f_{o_{i-1}o_{i}}<f_{o_{i}o_{i+1}}$ where $o_{0}=d_{n}$ and $o_{n+1}=d_{1}$ . Otherwise, $f_{o_{i-1}o_{i}}>f_{o_{i}o_{i+1}}$ .

Proof.

Notice that $f^{j}_{o_{i-1}o_{i}}=f^{j}_{o_{i}o_{i+1}}$ for any $j\neq i$ . If $\sigma(i)=1$ , then $f^{i}_{o_{i-1}o_{i}}<f^{i}_{o_{i}o_{i+1}}$ . Thus, $f_{o_{i-1}o_{i}}=\sum_{j=1}^{n}f^{j}_{o_{i-1}o_{i}}<\sum_{j=1}^{n}f^{j}_{o_{i}o_{i+1}}=f_{o_{i}o_{i+1}}$ . If $\sigma(i)=-1$ , then $f^{i}_{o_{i-1}o_{i}}>f^{i}_{o_{i}o_{i+1}}$ . Thus, $f_{o_{i-1}o_{i}}=\sum_{j=1}^{n}f^{j}_{o_{i-1}o_{i}}>\sum_{j=1}^{n}f^{j}_{o_{i}o_{i+1}}=f_{o_{i}o_{i+1}}$ . ∎

Lemma 19.

A cycle $C$ shown in Figure 9 with $n~{}(\geq 3)$ OD pairs is immune to IBP.

Proof.

Case 1. $\sigma(2)=\cdots=\sigma(n)=1$ .
We derive that $f_{o_{n}d_{1}}=\sum_{i=1}^{n}r_{i}=r$ . According to Lemma 9, $f_{o_{n-1}o_{n}}=\sum_{i=1}^{n-1}r_{i}>\frac{r}{2}$ and $f_{d_{1}d_{2}}=\sum_{i=2}^{n}r_{i}>\frac{r}{2}$ . By Lemma 18, $f_{o_{i-1}o_{i}}<f_{o_{i}o_{i+1}}$ and $f_{d_{i-1}d_{i}}>f_{d_{i}d_{i+1}}$ for any $i\in[n]$ when $o_{0}=d_{n}$ , $o_{n+1}=d_{1}$ , $d_{0}=o_{n}$ and $d_{n+1}=o_{1}$ . Let $j=\min\{i\geq 1~{}|~{}f_{o_{i}o_{i+1}}\geq\frac{r}{2}\}$ . Then $1\leq j\leq n-1$ . We know that $f_{o_{i}o_{i+1}}>\frac{r}{2}$ for $i\in\{j,\ldots,n\}$ . If $j=1$ , then for any $e\in\alpha_{1}$ , $f_{e}\geq\frac{r}{2}$ . Thus, $\ell_{\alpha_{1}}\geq\tilde{\ell}_{\alpha_{1}}$ , which contradicts with Lemma 8. If $j\geq 2$ , then $f_{o_{i}o_{i+1}}<\frac{r}{2}$ for $i\in\{1,\ldots,j-1\}$ . Thus, we derive $f_{d_{i}d_{i+1}}>\frac{r}{2}$ for $i\in\{1,\ldots,j-1\}$ . For $e\in\alpha_{j}$ , $f_{e}\geq\frac{r}{2}$ . Thus, $\ell_{\alpha_{j}}\geq\tilde{\ell}_{\alpha_{j}}$ , which contradicts with Lemma 8.

Case 2. $\sigma(2)=\cdots=\sigma(n)=-1$ .
We relabel the vertices in $C$ as follows: $o_{1}^{\prime}=d_{1}$ , $d_{1}^{\prime}=o_{1}$ , $o_{i}^{\prime}=o_{n+2-i}$ , and $d_{i}^{\prime}=d_{n+2-i}$ for $i\in\{2,\ldots,n\}$ . In this case, the problem is transformed into the scenario where $\sigma(1)=\sigma(2)=\cdots=\sigma(n)=-1$ , which is exactly the same as the scenario where $\sigma(1)=\sigma(2)=\cdots=\sigma(n)=1$ . Therefore, this case is proven.

Case 3. $\sigma(2)$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and $\sigma(2)=1$ .
Let $j=\min\{i~{}|~{}\sigma(i)=-1\}$ . Then $3\leq j\leq n$ . If $\sigma(i)=-1$ for any $i\in\{j,\ldots,n\}$ , then $f_{o_{j-1}o_{j}}=r\geq\frac{r}{2}$ . As $\sigma(j-1)=1$ and $\sigma(j)=-1$ , by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. Otherwise, we only need to consider the case $f_{o_{j-1}o_{j}}<\frac{r}{2}$ . Let $k=\min\{i\geq j+1~{}|~{}\sigma(i)=1\}$ . Then $\sigma(j)=\cdots=\sigma(k-1)=-1$ . By Lemma 18, we deduce that $f_{o_{j-1}o_{j}}>f_{o_{j}o_{j+1}}>\cdots>f_{o_{k-1}o_{k}}$ , which means that $f_{o_{k-1}o_{k}}<\frac{r}{2}$ . As $\sigma(k-1)=-1$ and $\sigma(k)=1$ , by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Case 4. $\sigma(2)$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and $\sigma(2)=-1$ .
Let $j=\min\{i\geq 2~{}|~{}\sigma(i)=1\}$ . Then $3\leq j\leq n$ . If $\sigma(i)=1$ for any $i\in\{j,\ldots,n\}$ , then $f_{o_{j-1}o_{j}}=r_{1}<\frac{r}{2}$ by Lemma 9. As $\sigma(j-1)=-1$ and $\sigma(j)=1$ , by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. Otherwise, we only need to consider the case $f_{o_{j-1}o_{j}}>\frac{r}{2}$ . Let $k=\min\{i\geq j+1~{}|~{}\sigma(i)=-1\}$ . Then $\sigma(j)=\cdots=\sigma(k-1)=1$ . By Lemma 18, we deduce that $f_{o_{j-1}o_{j}}<f_{o_{j}o_{j+1}}<\cdots<f_{o_{k-1}o_{k}}$ , which means that $f_{o_{k-1}o_{k}}>\frac{r}{2}$ . As $\sigma(k-1)=1$ and $\sigma(k)=-1$ , by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. ∎

Next, Let us consider a cycle with $n$ OD pairs possessing an almost symmetric distribution of terminal vertices: except for $o_{1}$ and $d_{1}$ of type- $1$ travelers, all other $o_{i}$ and $d_{i}$ are symmetric where $i\neq 1$ . Suppose $d_{1}$ is located between $d_{j}$ and $d_{j+1}$ , where $j\in\{2,\ldots,n\}$ and $d_{n+1}=o_{1}$ , as shown in Figure 10:

Lemma 20.

A cycle $C$ shown in Figure 10 with $n~{}(\geq 3)$ OD pairs is immune to IBP.

Proof.

(by induction on $n$ ) When $C$ contains three OD pairs, the conclusion holds by Lemma 12. Assuming that the conclusion holds for cases containing fewer than $n$ OD pairs, consider an IBP instance where $C$ contains $n$ OD pairs with a completely symmetric distribution of terminal vertices. Suppose that $f$ and $\tilde{f}$ are ICWE flows of the network before and after the information expansion. Let $r=\sum_{i=1}^{n}r_{i}$ . If $\sigma(1)=-1$ , since $\ell_{\alpha_{1}}>\ell_{\beta_{1}}$ and $\ell_{\alpha_{2}}\leq\ell_{\beta_{2}}$ , then $\sigma(2)=1$ . Thus, $\alpha_{1}\cap\alpha_{2}=\emptyset$ , which means that $\beta_{1}\cup\beta_{2}=C$ . By Lemma 11, we derive a IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. Thus, $\sigma(1)=1$ . Let us discuss the values of $\sigma(2),\ldots,\sigma(n)$ below:

Case 1. $\sigma(2)=\cdots=\sigma(n)=1$ .
We derive that $f_{o_{n}d_{2}}=\sum_{i=1}^{n}r_{i}=r$ . By Lemma 18, we have $f_{o_{n}d_{2}}>f_{o_{n-1}o_{n}}>\cdots>f_{o_{1}o_{2}}>f_{d_{n}o_{1}}$ and $f_{o_{n}d_{2}}>f_{d_{2}d_{3}}>\cdots>f_{d_{j}d_{1}}>f_{d_{1}d_{j+1}}>\cdots>f_{d_{n-1}d_{n}}>f_{d_{n}o_{1}}$ . Let $k=\min\{i~{}|~{}f_{o_{i}o_{i+1}}\geq\frac{r}{2}\}$ . Notice that $f_{o_{1}o_{2}}=r_{1}<\frac{r}{2}$ and $f_{o_{n-1}o_{n}}=\sum_{i=1}^{n-1}r_{i}>\frac{r}{2}$ by Lemma 9. Then $2\leq k\leq n-1$ . By the definition of $k$ , we know that $f_{o_{k-1}o_{k}}<\frac{r}{2}$ . Then if $k\neq j+1$ , then $f_{d_{k-1}d_{k}}>\frac{r}{2}$ ; if $k=j+1$ , then $f_{d_{k-1}d_{1}}>\frac{r}{2}$ and $f_{d_{1}d_{k}}>\frac{r}{2}$ . For $e\in\alpha_{k}$ , $f_{e}\geq\frac{r}{2}$ . Thus, $\ell_{\alpha_{k}}\geq\tilde{\ell}_{\alpha_{k}}$ , which contradicts with Lemma 8.

Case 2. $\sigma(2)=\cdots=\sigma(n)=-1$ .
We derive that $f_{o_{1}o_{2}}=\sum_{i=1}^{n}r_{i}=r$ . By Lemma 18, $f_{o_{1}o_{2}}>f_{o_{2}o_{3}}>\cdots>f_{o_{n-1}o_{n}}>f_{o_{n}d_{2}}$ and $f_{o_{1}o_{2}}>f_{d_{n}o_{1}}>\cdots>f_{d_{1}d_{j+1}}>f_{d_{j}d_{1}}>\cdots>f_{d_{2}d_{3}}>f_{o_{n}d_{2}}$ . Let $k=\max\{i\geq 2~{}|~{}f_{o_{i-1}o_{i}}\geq\frac{r}{2}\}$ . Notice that $f_{o_{2}o_{3}}=r-r_{2}>\frac{r}{2}$ and $f_{o_{n}d_{2}}=r_{1}<\frac{r}{2}$ by Lemma 9. Then $3\leq k\leq n$ . By the definition of $k$ , we know that $f_{o_{k}o_{k+1}}<\frac{r}{2}$ where $o_{n+1}=d_{2}$ . Then if $k\neq j$ , then $f_{d_{k}d_{k+1}}>\frac{r}{2}$ ; if $k=j$ , then $f_{d_{k}d_{1}}>\frac{r}{2}$ and $f_{d_{1}d_{k+1}}>\frac{r}{2}$ . For $e\in\alpha_{k}$ , $f_{e}\geq\frac{r}{2}$ . Thus, $\ell_{\alpha_{k}}\geq\tilde{\ell}_{\alpha_{k}}$ , which contradicts with Lemma 8.

Case 3. $\sigma(2)$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and $\sigma(2)=\cdots=\sigma(j)=\sigma(j+1)=-1$ .
Let $k=\min\{i\geq j+1~{}|~{}\sigma(i)=1\}$ . Then $\sigma(k-1)=-1$ and $\sigma(k)=1$ . If $f_{o_{k-1}o_{k}}\leq\frac{r}{2}$ , by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. If $f_{o_{k-1}o_{k}}>\frac{r}{2}$ , then there exists $i\geq k+1$ with $\sigma(i)=-1$ . Otherwise, $f_{o_{k-1}o_{k}}=r_{1}<\frac{r}{2}$ by Lemma 9. Let $l=\min\{i\geq k+1~{}|~{}\sigma(i)=-1\}$ . Then $\sigma(l-1)=1$ and $\sigma(l)=-1$ . According to Lemma 18, $f_{o_{l-1}o_{l}}>f_{o_{k-1}o_{k}}>\frac{r}{2}$ . By Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Case 4. $\sigma(2)$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and $\sigma(2)=\cdots=\sigma(j)=-1$ , $\sigma(j+1)=1$ .
If $f_{o_{j}o_{j+1}}>\frac{r}{2}$ , then there exists $i\geq j+2$ with $\sigma(i)=-1$ . Otherwise, $f_{o_{j}o_{j+1}}=r_{1}<\frac{r}{2}$ by Lemma 9. Let $l=\min\{i\geq j+2~{}|~{}\sigma(i)=-1\}$ . Then $\sigma(l-1)=1$ and $\sigma(l)=-1$ . According to Lemma 18, $f_{o_{l-1}o_{l}}>f_{o_{j}o_{j+1}}>\frac{r}{2}$ . By Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. If $f_{o_{j}o_{j+1}}\leq\frac{r}{2}$ , then $f_{d_{j}d_{1}}\geq\frac{r}{2}$ and $f_{d_{1}d_{j+1}}\geq\frac{r}{2}$ . According to the proof of Lemma 13, we have that $\delta=\ell_{o_{j}o_{j+1}}=\tilde{\ell}_{o_{j}o_{j+1}}=\ell_{d_{j}d_{1}}+\ell_{d_{1}d_{j+1}}=\tilde{\ell}_{d_{j}d_{1}}+\tilde{\ell}_{d_{1}d_{j+1}}$ . By Lemma 17, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Case 5. $\sigma(2)=-1$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and there exists $3\leq i\leq j$ with $\sigma(i)=1$ .
Let $k=\min\{3\leq i\leq j~{}|~{}\sigma(i)=1\}$ . Then $\sigma(k-1)=-1$ and $\sigma(k)=1$ . Thus, $\beta_{1}\subset\beta_{k}$ . If $f_{o_{k-1}o_{k}}<\frac{r}{2}$ , by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. Then $f_{o_{k-1}o_{k}}\geq\frac{r}{2}$ . Let us consider the edge $e\in\alpha_{k}$ in the following five cases:

1.

For $e=o_{l}o_{l+1}$ where $l\in\{k,\ldots,j-1\}$ , if $\sigma(l)=-1$ and $\sigma(l+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
2.

For $e=o_{j}o_{j+1}$ , if $\sigma(j)=-1$ and $\sigma(j+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 14 and 17, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
3.

For $e=o_{l}o_{l+1}$ where $l\in\{j+1,\ldots,n-1\}$ , if $\sigma(l)=-1$ and $\sigma(l+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
4.

For $e=o_{n}d_{2}$ , if $\sigma(n)=-1$ and $\sigma(2)=-1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 14 and 17, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
5.

For $e=d_{l}d_{l+1}$ where $l\in\{2,\ldots,k-1\}$ , if $\sigma(l)=1$ and $\sigma(l+1)=-1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Let us take the edge with the minimum flow in $\alpha_{k}$ , denoted as $e^{\ast}$ . We aim to prove that $f_{e^{\ast}}>\frac{r}{2}$ . If $e^{\ast}=o_{k}o_{k+1}$ , since $\sigma(k)=1$ , then $f_{o_{k}o_{k+1}}>f_{o_{k-1}o_{k}}\geq\frac{r}{2}$ . Since $\sigma(k-1)=-1$ , $f_{d_{k-1}d_{k}}>f_{d_{k-2}d_{k-1}}$ . Thus, $e^{\ast}\neq d_{k-1}d_{k}$ . When $e^{\ast}\neq o_{k}o_{k+1}$ and $e^{\ast}\neq d_{k-1}d_{k}$ , $e^{\ast}$ has edges on both sides in $\alpha_{k}$ and $f_{e^{\ast}}$ does not exceed the flow of the edges on its two sides, then $e^{\ast}$ must belong to one of the five cases mentioned above, which means that $f_{e^{\ast}}>\frac{r}{2}$ . Therefore, $\ell_{\alpha_{k}}\geq\tilde{\ell}_{\alpha_{k}}$ , which contradicts with Lemma 8.

Case 6. $\sigma(2)$ , $\sigma(3)$ , $\ldots$ , $\sigma(n)$ are not all equal and $\sigma(2)=\sigma(n)=1$ .
Then, $\beta_{1}\subset\beta_{2}$ . If $f_{o_{1}o_{2}}<\frac{r}{2}$ , since $\sigma(1)=1$ , then $f_{d_{n}o_{1}}<f_{o_{1}o_{2}}<\frac{r}{2}$ . Since $\sigma(2)=1$ and $\sigma(n)=1$ , by Lemmas 14 and 17, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption. Then $f_{o_{1}o_{2}}\geq\frac{r}{2}$ . Let us consider the edge $e\in\alpha_{2}$ in the following three cases:

1.

For $e=o_{l}o_{l+1}$ where $l\in\{2,\ldots,j-1\}$ , if $\sigma(l)=-1$ and $\sigma(l+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
2.

For $e=o_{j}o_{j+1}$ , if $\sigma(j)=-1$ and $\sigma(j+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 14 and 17, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
3.

For $e=o_{l}o_{l+1}$ where $l\in\{j+1,\ldots,n-1\}$ , if $\sigma(l)=-1$ and $\sigma(l+1)=1$ , then $f_{e}>\frac{r}{2}$ . Otherwise, by Lemmas 13 and 15, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Let us take the edge with the minimum flow in $\alpha_{2}$ , denoted as $e^{\ast}$ . We aim to prove that $f_{e^{\ast}}>\frac{r}{2}$ . If $e^{\ast}=o_{2}o_{3}$ , since $\sigma(2)=1$ , then $f_{o_{2}o_{3}}>f_{o_{1}o_{2}}\geq\frac{r}{2}$ . Since $\sigma(n)=1$ , $f_{o_{n}d_{2}}>f_{o_{n-1}o_{n}}$ . Thus, $e^{\ast}\neq o_{n}d_{2}$ . When $e^{\ast}\neq o_{2}o_{3}$ and $e^{\ast}\neq o_{n}d_{2}$ , $e^{\ast}$ has edges on both sides in $\alpha_{2}$ and $f_{e^{\ast}}$ does not exceed the flow of the edges on its two sides, then $e^{\ast}$ must belong to one of the three cases mentioned above, which means that $f_{e^{\ast}}>\frac{r}{2}$ . Therefore, $\ell_{\alpha_{2}}\geq\tilde{\ell}_{\alpha_{2}}$ , which contradicts with Lemma 8.

Case 7. $\sigma(2)=1$ and $\sigma(j)=\sigma(n)=-1$ .
Let us renumber the vertices on $C$ as follows:

•

Swap the labels of $o_{1}$ and $d_{1}$ .
•

Swap the labels of $o_{k}$ and $d_{j+2-k}$ for $k\in\{2,\ldots,j\}$ .
•

Swap the labels of $o_{k}$ and $o_{n+j+1-k}$ for $k\in\{j+1,\ldots,j+\lfloor\frac{n-j}{2}\rfloor\}$ .
•

Swap the labels of $d_{k}$ and $d_{n+j+1-k}$ for $k\in\{j+1,\ldots,j+\lfloor\frac{n-j}{2}\rfloor\}$ .

Then $\sigma(1)=-1$ and $\sigma(2)=1$ , which is equivalent to the scenario where $\sigma(1)=1$ and $\sigma(2)=-1$ . The result in this scenario has been proved in Cases 2, 3, 4 and 5.

Case 8. $\sigma(2)=\sigma(j)=1$ and $\sigma(j+1)=\sigma(n)=-1$ .
Let us renumber the vertices on $C$ as follows:

•

Swap the labels of $o_{1}$ and $d_{1}$ .
•

Swap the labels of $o_{k}$ and $d_{j+2-k}$ for $k\in\{2,\ldots,j\}$ .
•

Swap the labels of $o_{k}$ and $o_{n+j+1-k}$ for $k\in\{j+1,\ldots,j+\lfloor\frac{n-j}{2}\rfloor\}$ .
•

Swap the labels of $d_{k}$ and $d_{n+j+1-k}$ for $k\in\{j+1,\ldots,j+\lfloor\frac{n-j}{2}\rfloor\}$ .

Then $\sigma(1)=\sigma(2)=\sigma(n)=-1$ , which is equivalent to the scenario where $\sigma(1)=\sigma(2)=\sigma(n)=1$ . The result in this scenario has been proved in Cases 1 and 6.

Case 9. $\sigma(2)=\sigma(j)=\sigma(j+1)=1$ and $\sigma(n)=-1$ .
Then, $\beta_{1}\subset\beta_{2}$ . We have the following inequalities:

•

$f_{d_{n-1}d_{n}}<f_{d_{n}o_{1}}<f_{o_{1}o_{2}}$ .
•

$f_{o_{j-1}o_{j}}<f_{o_{j}o_{j+1}}$ .
•

$f_{d_{2}d_{3}}<f_{o_{n}d_{2}}$ .
•

$f_{d_{j+1}d_{j+2}}<f_{d_{1}d_{j}+1}<f_{d_{j}d_{1}}$ .

Let us consider the edge with the minimum flow on $C$ and denote it as $e^{\ast}$ . Based on the previous inequalities, we can conclude that $e^{\ast}$ does not belong to the set $\{d_{n}o_{1},o_{1}o_{2},o_{j}o_{j+1},o_{n}d_{2},$ $d_{j}d_{1},d_{1}d_{j+1}\}$ . Therefore, there are only two possible cases:

•

For $e^{\ast}=o_{k}o_{k+1}$ where $k\in\{2,\ldots,n-1\}\setminus\{j\}$ , then $\sigma(k)=-1$ and $\sigma(k+1)=1$ . If $f_{e^{\ast}}\leq\frac{r}{2}$ , by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.
•

For $e^{\ast}=d_{k}d_{k+1}$ where $k\in\{2,\ldots,n-1\}\setminus\{j\}$ , then $\sigma(k)=1$ and $\sigma(k+1)=-1$ . If $f_{e^{\ast}}\leq\frac{r}{2}$ , by Lemmas 13 and 16, we derive a new IBP instance with $n-1$ types of travelers, which contradicts with the induction assumption.

Thus, $f_{e}>\frac{r}{2}$ for any $e\in\alpha_{2}$ . Therefore, $\ell_{\alpha_{2}}\geq\tilde{\ell}_{\alpha_{2}}$ , which contradicts with Lemma 8.

In conclusion, a cycle $C$ shown in Figure 10 with $n~{}(\geq 3)$ OD pairs is IBP-free. ∎

Next, we will transform a cycle containing $n$ OD pairs with the general distribution of the terminal vertices into a completely symmetric structured network as shown in Figure 9 or an almost symmetric structured network as shown in Figure 10 through a finite number of steps. The following lemma allows us to convert the traffic rates of all types of travelers into integers.

Lemma 21.

If there exists an IBP instance in a cycle with $n~{}(\geq 3)$ OD pairs, then we can construct an IBP instance in a cycle with $n~{}(\geq 3)$ OD pairs and all the traffic rates are integers.

Proof.

If all the traffic rates are rational numbers, then we assume that $r_{i}=\frac{p_{i}}{q_{i}}$ where $p_{i},q_{i}$ are positive integers for any $i\in[n]$ . Let $Q$ be the least common multiple of $q_{1},q_{2},\ldots,q_{n}$ . Then the new IBP instance have the traffic rates: $r_{i}^{\prime}=r_{i}\cdot Q$ for any $i\in[n]$ . Otherwise, suppose that $r_{i}=a$ is an irrational number for some $i\in[n]$ . Let $A=\{e\in C~{}|~{}\ell_{e}=\tilde{\ell}_{e}\}$ and $b=\min_{e\in C\setminus A}|f_{e}-\tilde{f}_{e}|$ . Since the rational points are dense on the number axis, we can choose a rational number $c$ such that $a<c<a+\frac{b}{2}$ . Let $r_{i}^{\prime}=c$ and $r_{j}^{\prime}=r_{j}$ for $j\in[n]\setminus\{i\}$ . Let $f^{\prime}$ be the flow of the network before the information expansion where type- $i$ travelers unanimously choose the path $\alpha_{i}$ for any $i\in[n]$ and $\tilde{f}^{\prime}$ be the flow of the network before the information expansion where type- $i$ travelers unanimously choose the path $\beta_{i}$ for any $i\in[n]$ . Since $a<c<a+\frac{b}{2}$ , we have that $|f_{e}-f_{e}^{\prime}|<\frac{b}{2}$ and $|\tilde{f}_{e}-\tilde{f}^{\prime}_{e}|<\frac{b}{2}$ for any $e\in C$ . Then, we derive

•

If $f_{e}-\tilde{f}_{e}>0$ , then $f_{e}-\tilde{f}_{e}\geq b$ . We have that $f^{\prime}_{e}-\tilde{f}^{\prime}_{e}=(f_{e}-\tilde{f}_{e})-(f_{e}-f^{\prime}_{e})-(\tilde{f}^{\prime}_{e}-\tilde{f}_{e})$ $>b-\frac{b}{2}-\frac{b}{2}=0$ .
•

If $f_{e}-\tilde{f}_{e}<0$ , then $f_{e}-\tilde{f}_{e}\leq-b$ . We have that $f^{\prime}_{e}-\tilde{f}^{\prime}_{e}=(f_{e}-\tilde{f}_{e})-(f_{e}-f^{\prime}_{e})-(\tilde{f}^{\prime}_{e}-\tilde{f}_{e})$ $<-b+\frac{b}{2}+\frac{b}{2}=0$ .

Next, we construct the latency functions for any edge $e\in C$ : For $e\in A$ , $\hat{\ell}_{e}(x)\equiv\ell_{e}$ where $x\in[0,\infty)$ . For $e\in C\setminus A$ ,

\hat{\ell}_{e}(x)=\begin{cases}\min\{\ell_{e},\tilde{\ell}_{e}\}&x\in[0,\min\{f^{\prime}_{e},\tilde{f}^{\prime}_{e}\}],\\ \frac{\ell_{e}-\tilde{\ell}_{e}}{f_{e}^{\prime}-\tilde{f}_{e}^{\prime}}x+\frac{\tilde{\ell}_{e}\cdot f_{e}^{\prime}-\ell_{e}\cdot\tilde{f}_{e}^{\prime}}{f_{e}^{\prime}-\tilde{f}_{e}^{\prime}}&x\in(\min\{f^{\prime}_{e},\tilde{f}^{\prime}_{e}\},\max\{f^{\prime}_{e},\tilde{f}^{\prime}_{e}\}),\\ \max\{\ell_{e},\tilde{\ell}_{e}\}&x\in[\max\{f^{\prime}_{e},\tilde{f}^{\prime}_{e}\},+\infty).\end{cases}

Then, it follows that $\ell^{\prime}_{e}(f_{e}^{\prime})=\ell_{e}$ and $\ell^{\prime}_{e}(\tilde{f}^{\prime}_{e})=\tilde{\ell}_{e}$ for any $e\in C$ . Then $f^{\prime}$ and $\tilde{f}^{\prime}$ are ICWE flows of the network before and after the information expansion. Thus, this is a new IBP instance. We can repeatedly perform the above operation, converting all $r_{i}$ into rational numbers, and then further transform all $r_{i}$ into integers. ∎

The next lemma allows us to transform all integers $r_{i}$ into $1$ .

Lemma 22.

If there exits an IBP instance in a cycle with $n~{}(\geq 3)$ OD pairs and all integer traffic rates, then we can construct an IBP instance in a cycle with $(\sum_{i=1}^{n}r_{i})$ OD pairs and all the traffic rates are equal to $1$ .

Proof.

We divide the type- $i$ travelers into $r_{i}$ types of travelers: $(i,1),(i,2),$ $\ldots,(i,r_{i})$ . These types of travelers have a traffic rate of $1$ and their OD pairs and the path choices remain consistent with the type- $i$ travelers. On the cycle $C$ , we replace the vertex $o_{i}$ with a path of length $r_{i}-1$ , denoted as $o_{i}^{1}o_{i}^{2}\cdots o_{i}^{r_{i}}$ , and replace the vertex $d_{i}$ with a path of length $r_{i}-1$ , denoted as $d_{i}^{1}d_{i}^{2}\cdots d_{i}^{r_{i}}$ . The latency of all newly added edges is defined as $0$ . ∎

For any IBP instance with a traffic rate of $1$ , we can transform it into an IBP instance of the completely symmetric structured cycle or the almost symmetric structured cycle.

Lemma 23.

If there exits an IBP instance in a cycle with $n~{}(\geq 3)$ OD pairs and all traffic rates are $1$ , then we can construct an IBP instance in the completely symmetric structured cycle or the almost symmetric structured cycle.

Proof.

Let $K=[n]\setminus\{1\}$ and $M=\{\{i,j\}~{}|~{}\alpha_{j}\subset\alpha_{i},~{}i,j\in K\}$ . Suppose that $M\neq\emptyset$ . Take $\{i,j\}\in M$ and assume that $\alpha_{j}\subset\alpha_{i}$ as shown in Figure 11. $o_{i}$ , $o_{j}$ , $d_{j}$ , and $d_{i}$ divide the cycle $C$ into four paths:

•

$P_{1}$ is the path from $o_{i}$ clockwise to $o_{j}$ .
•

$P_{2}$ is the path from $o_{j}$ clockwise to $d_{j}$ , which is actually $\alpha_{j}$ .
•

$P_{3}$ is the path from $d_{j}$ clockwise to $d_{i}$ .
•

$P_{4}$ is the path from $d_{i}$ clockwise to $o_{i}$ , which is actually $\beta_{i}$ .

Swap $d_{i}$ and $d_{j}$ . Define new paths $\bar{\alpha}_{i}=P_{1}\cup P_{2}$ , $\bar{\beta}_{i}=P_{3}\cup P_{4}$ , $\bar{\alpha}_{j}=P_{2}\cup P_{3}$ , and $\bar{\beta}_{j}=P_{1}\cup P_{4}$ . For $k\in\{i,j\}$ , type- $k$ travelers choose $\bar{\alpha}_{k}$ before and $\bar{\beta}_{k}$ after the information expansion. We can observe that the traffic flow on each edge of the cycle remains unchanged after the swap, indicating that we still have an IBP instance. Next, we will prove that with each iteration of the above operation, the value of $|M|$ strictly decreases.

Let $M^{\prime}$ be the set obtained after performing one swap operation on $M$ . We firstly have that $\{i,j\}\in M$ and $\{i,j\}\not\in M^{\prime}$ . Consider any $\{k,l\}\in M^{\prime}$ and $\{k,l\}\not\in M$ :

•

If $\{k,l\}\cap\{i,j\}=\emptyset$ , since $\{k,l\}\in M^{\prime}$ , then $\{k,l\}\in M$ , which is a contradiction.
•

If $k\neq i,j$ and $l=i$ , since $\{k,i\}\in M^{\prime}$ and $\{k,i\}\not\in M$ , we have either $o_{k}\in P_{3}$ and $d_{k}\in P_{4}$ , or $o_{k}\in P_{4}$ and $d_{k}\in P_{3}$ . Thus, $\{k,j\}\in M$ and $\{k,j\}\not\in M^{\prime}$ .
•

If $k\neq i,j$ and $l=j$ , since $\{k,j\}\in M^{\prime}$ and $\{k,j\}\not\in M$ , we have either $o_{k}\in P_{2}$ and $d_{k}\in P_{3}$ , or $o_{k}\in P_{3}$ and $d_{k}\in P_{2}$ . Thus, $\{k,i\}\in M$ and $\{k,i\}\not\in M^{\prime}$ .

Thus, it follows that $|M^{\prime}|<|M|$ .

Therefore, after a finite number of steps, an IBP instance obtained corresponds to $M=\emptyset$ , i.e., for any $i,j\in K$ , $\alpha_{i}\setminus\alpha_{j}\neq\emptyset$ . If there exist $i,j\in K$ such that $\alpha_{i}\cap\alpha_{j}=\emptyset$ or $\alpha_{i}\cup\alpha_{j}=C$ , according to Lemma 11, we can construct a new IBP instance by removing one type of travelers. Therefore, the final IBP instance satisfies: for any $i,j\in K$ , $\alpha_{i}\setminus\alpha_{j}\neq\emptyset$ , $\alpha_{i}\cap\alpha_{j}\neq\emptyset$ and $\alpha_{i}\cup\alpha_{j}\neq C$ , which is actually an IBP instance of the completely symmetric structured cycle or the almost symmetric structured cycle. ∎

Finally, we are ready to prove the main theorem of this section, which establishes our characterization for IBP-free networks with multiple OD pairs (Theorem 3).

Proof of Theorem 4.

By Lemma 10, a cycle with two OD pairs is IBP-free. Suppose that there exists an IBP instance in $C$ with $n~{}(\geq 3)$ OD pairs. By Lemmas 21, 22 and 23, we obtain an IBP instance of the completely symmetric structured cycle or the almost symmetric structured cycle, which contradicts with Lemma 19 or Lemma 20. ∎