When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing?

1 Introduction

It is a common belief that diversity helps. In non-cooperative multi-agent systems, where a central theme is the tension between selfish behavior and social optimality-can diversity of agent preferences help to bring us closer to the coveted social optimality? We provide an answer to this question in the context of non-atomic selfish routing, where diversity naturally arises in the way agents trade-off two criteria, for example, time and cost, or, in the presence of uncertain delays, expectation and variance of delay.

As we shall see, there is no unique answer. Rather, it depends on the setting. To address our question we need to specify how to measure the cost of an outcome, and define a benchmark setting with no agent heterogeneity. To measure the cost of an outcome, we treat an agent's cost as the sum of two terms associated with two criteria: If we let ℓP denote the cost of one criterion (e.g., the latency) over a path P, and vP be the cost of the second criterion, then the overall cost is given by ℓP + r · vP , where r is our diversity parameter. The special case of r = 0 corresponds to indifference to the second criterion and results in the classic selfish routing model where agents simply minimize travel time.

A first approach to measuring the effect of diversity might be to compare the cost of an outcome with r = 0 (i.e., just the total latency) to that with other values of r, including possibly mixed values of r across the population being routed. However, this approach does not pinpoint the gains and losses from agent heterogeneity as opposed to agent homogeneity; rather, it (mostly) pinpoints the gains and losses depending on whether players are affected by the second criterion or not. Instead, we focus on the sum of the costs incurred by the agents as measured by their cost functions, and compare costs incurred by a heterogeneous population of agents to those incurred by an equivalent population of homogeneous agents. What are equivalent populations? Suppose the heterogeneous population's diversity profile is given by a population density function f(r). Then, we define the corresponding homogeneous population to have the single diversity parameter ¯ r = ∫ rf(r)dr. In addition, we require the two populations to have the same size, in the sense that the total source-to-sink flows that they induce are equal.

Contribution. We fully characterize the topology of networks for which diversity is never harmful, regardless of the demand size and the distribution of the diversity parameter (discrete or continuous). We do so both for single and multicommodity networks.

For single-commodity networks it turns out that this topology is that of series-parallel networks. In Theorem 1, we show that if the network is series-parallel, then diversity only helps for any choice of demand and edge functions. The key observation is that there is a path for which the homogeneous flow is at least as large as the heterogeneous flow. As the cost of the homogeneous flow is the same on all used paths, while the cost of each unit of heterogeneous flow is lowest on the path it uses, one can then deduce that the cost of the heterogeneous flow is at most that of the homogeneous flow. To show necessity, we first provide an instance on the Braess graph for which diversity is harmful, and then show how to embed it in any non-series-parallel graph.

In multi-commodity networks, by the result above, each commodity must route its flow through a series-parallel subnetwork. But, as Proposition 2 shows, this is not enough, and the way in which these series-parallel networks overlap needs to be constrained. The necessary constraint is exactly captured by the class of block-matching networks, defined in this paper. Sufficiency in this case then follows quite easily from the same result for the single commodity case.

The main technical challenge is to show necessity. To this end, assuming diversity does no harm, we show, via a case analysis, how the subnetworks of the commodities may overlap. First, in Proposition 2, we give an instance on a network of two commodities and three paths for which diversity hurts. Then we mimic this instance on a general network. The difficult part is to choose the corresponding paths for the mimicking, so that, in the created instance, all the flow under both equilibria goes through these paths. The challenge is that the commodities' subnetworks may overlap in subtle ways.

Related work. Our work was inspired by the selfish routing literature where agents have to tradeoff two criteria such as time versus tolls, or expected travel time versus variance. In the former setting, early results (e.g., [Beckmann et al., 1956]) showed that tolls can help implement the social optimum as an equilibrium, when agents all have the same linear objective function combining time and money. Much more recently, these results were extended to the case where agents trade-off travel time and money differently, by Cole et al. (2003) and Fleischer (2005) for the single commodity case, and by Karakostas and Kolliopoulos (2004a) and Fleischer et al. (2004) for the multicommodity case. We remark that the above works, apart from [Cole et al., 2003], consider only the case where the social welfare is defined as the total travel time, whereas in our work we consider the total agent cost, which encapsulates both criteria. This, for example, is also the case for Christodoulou et al. (2014) and Karakostas and Kolliopoulos (2004b). In stochastic selfish routing and related frameworks, most models assume homogeneous agents (e.g., [Piliouras et al., 2013], [Nikolova and Stier-Moses, 2015], [Lianeas et al., 2016], [Kleer and Sch¨afer, 2016]) and study the degradation of a network's performance due to risk aversion. Fotakis et al. (2015) considered games with heterogeneous risk-averse players and showed how uncertainty can be used to improve a network's performance.

Characterizing the topology of networks that satisfy some property is a common theme in computer science. Relevant to our work, Epstein et al. (2009) characterized the topology of single-commodity networks for which all Nash equilibria are social optima (under bottleneck costs), and Milchtaich (2006) characterized the topology of single-commodity networks which do not suffer from the Braess Paradox for any cost functions. Chen et al. (2015) fully characterized the topology of multi-commodity networks that do not suffer from the Braess paradox. These characterizations appear similar to ours, although there does not seem to be any other connection between the two problems, as (i) there are instances where diversity helps while the Braess Paradox occurs and others where diversity hurts but the paradox does not occur, and (ii) the Braess Paradox may occur in series-parallel networks when considering selfish routing with heterogeneity in agent preferences, which is not the case for the classic selfish routing model.

In the following works, the characterizing topology for the corresponding question (for a single commodity) is similar to ours. Fotakis and Spirakis (2008) considered atomic games and proved that series-parallel networks are the largest class of networks for which strongly optimal tolls are known to exist. Nikolova and Stier-Moses (2015) considered homogeneous agents and a social cost function that does not account for the second criterion; They showed that series-parallel networks admit the best bound on the degradation of the network due to risk aversion. Theorem 4 of Acemoglu et al. (2016), proves that series-parallel networks are the characterizing topology for what they call the Informational Braess Paradox with Restricted Information Sets; this theorem compares the cost of one agent type before and after more information is revealed to agents of that type, but does not consider the change in the cost of other agent types. In contrast, our work considers non-atomic games with heterogeneous agents and bounds the overall costs faced by the collection of agents. Most relevant to our work is [Meir and Parkes, 2014] and its Theorem 3.1 as it implies that for series-parallel networks the cost of an agent of average parameter only increases when switching from the heterogeneous instance to the corresponding homogeneous one and thus for our sufficiency theorems, one is left to prove that the heterogeneous equilibrium cost is no greater than the cost of an agent of average parameter (though we give a different proof).

2 Preliminaries

Consider a directed multi-commodity network G = (V,E) with an aggregate demand of dk units of flow between origindestination pairs (sk, tk) for k ∈ K. We let Pk be the set of all paths between sk and tk, and P := ∪k∈KPk be the set of all origin-destination paths. We let [m] denote {1, . . . ,m}. We assume that K = [m], for some m. The agents in the network-i.e., the players of the game-must choose routes that connect their origins to their destinations. We encode the collective decisions of agents in a flow vector f = (fπ)π∈P ∈ R|P| + over all paths. Such a flow is feasible when demands are satisfied, as given by constraints ∑π∈Pk fπ = dk for all k ∈ K. For simplicity, we let fe denote the flow on edge e; note that fe = ∑π:e∈π fπ. When we need multiple flow variables, we use the analogous notation g, gπ, ge.

The network is subject to congestion that affects two criteria the players consider. These two criteria are modeled by two edge-dependent functions that take as input the edge flow fe of e, for each edge e: a latency function ℓe(x) assumed to be continuous and non-decreasing, and a deviation function σe(x) assumed to be continuous (but not necessarily non-decreasing).

Throughout the paper we refer to the agent's objective as the cost along a route. Formally, for a given agent, on letting ℓπ(f) = ∑e∈π ℓe(fe) and σπ(f) = ∑e∈π σe(fe), for a constant r ≥ 0 that quantifies the agent diversity parameter, the agent's cost along route π under flow f is

We assume that for any edge and any agent's diversity parameter r, the functions ℓe and ℓe + rσe are non-decreasing. Note that if there is an upper bound rmax on the possible values of the diversity parameter r, then the latter assumptions do not require σe to be non-decreasing. This is desirable because, for example, in risk-averse selfish routing where σe models the variance, σe may be decreasing in the flow.

Players Heterogeneity. We assume that there may be more than one value of the diversity parameters r for the players routing commodity k. We use the term single-minded to refer to players with r = 0. We handle both the cases of a continuous and a discrete distribution of the diversity parameter among the players, though, for our results, we need only consider the discrete case. 1

For a discrete distribution of, say, n discrete values rk 1 , . . . , rkn , the demand dk is a vector dk = (dk1 , . . . , dkn ) where each dki denotes the total demand of Commodity k with diversity parameter rk i . We let dk denote Commodity k's total demand, dk = ∑ni=1 dki . Variables f r π and f r e denote the flow of diversity parameter r on path π and edge e, respectively. Formally, an instance is described by the tuple (G, {(ℓe, σe)}e∈E, {(sk, tk)}k∈K, {dk}k∈K, {rk}k∈K), where rk = (rk 1 , . . . , rkn ) is the vector of different diversity parameters encountered in the heterogeneous population.

Equilibrium flows. The Wardrop equilibrium of an instance is a flow f such that for every k ∈ K, for every path π ∈ Pk with positive flow, and any diversity parameter r on it, the path cost crπ (f) ≤ crπ′ (f) for all paths π′ ∈ Pk .

From here on, we shall refer to the Wardrop equilibrium as the equilibrium. Our goal is to compare the total agent cost at the equilibrium of an instance with a population that has heterogeneous diversity parameters, to the total agent cost at the equilibrium of the same instance but with the population of each commodity keeping its magnitude but changed to be homogeneous, with diversity parameter equal to the expected value of the diversity parameter distribution in the heterogeneous population of the commodity. To differentiate more easily, for a heterogeneous instance we call the former the heterogeneous equilibrium and the latter the (corresponding) homogeneous equilibrium. We usually denote the heterogeneous equilibrium by g and the homogeneous equilibrium by f. The existence of both equilibria is guaranteed by e.g. [Schmeidler, 1973, Theorem 2]. We note here that in general we do not need uniqueness of equilibria, neither for the edge costs nor for the edge flows. Our results hold for any arbitrary pair of heterogeneous and homogeneous equilibria of the corresponding instances. Also, as for classic routing games, without loss of generality (WLOG) we may assume that equilibrium flows are acyclic.

Total Costs. For a heterogeneous equilibrium flow vector g, the heterogeneous total cost of Commodity k is denoted by C k,ht (g) = ∑j=1...n dkj ck,rk j (g) where ck,rk j (g) denotes the common cost at equilibrium g for players of diversity parameter rk j in Commodity k. The heterogeneous total cost of g is then C ht (g) = ∑k∈K C k,ht (g). For the corresponding homogeneous equilibrium flow f, i.e. the instance with diversity parameter ¯ rk , where ¯ rk denotes the average diversity parameter for Commodity k, players of Commodity k share the same cost c¯ rk (f). Then, the homogeneous total cost of Commodity k under f is C k,hm(f) = dkc¯ rk (f), and the homogeneous total cost of f is C hm(f) = ∑k∈K C k,hm(f).

1 This is basically because the flow gp of a path p with diversity parameter within some range, can be changed to have parameter equal to the average parameter on p, and the equilibrium remains.

Finally, if C ht (g) ≤ C hm(f), we say that diversity helps; if not, we say that diversity hurts. For our characterization to be meaningful, we assume an average-respecting demand, i.e., a demand where ∀i, j : ¯ ri = ¯ rj . Otherwise, diversity may hurt in simple instances, e.g., with two parallel links and two commodities.

Networks. For a network G we let V (G) and E(G) denote its vertex set and edge set, respectively.

A directed s-t network G is series-parallel if it consists of a single edge (s, t), or it is formed by the series or parallel composition of two series-parallel networks with terminals (s1, t1) and (s2, t2), respectively. In a series composition, t1 is identified with s2, s1 becomes s, and t2 becomes t. In a parallel composition, s1 is identified with s2 and becomes s, and t1 is identified with t2 and becomes t. The internal vertices of a series-parallel network G are all its vertices other than its terminals.

An s-t series-parallel network may be represented using a sequence of networks Bj connected in series, where each Bj is either a single edge or two series-parallel networks connected in parallel. Given a series-parallel network H, we can write H = sB1v1B2v2 . . . Bb-1vb-1Bbt, where for any j and triple xBjy, x and y are the terminals of the seriesparallel network Bj, and Bj is either a single edge or a parallel combination of two series-parallel networks. We refer to the Bj's as blocks, the prescribed representation as the block representation of H, and the vi's as separators, as they separate s from t. Two series-parallel networks G1 and G2 are said to be block-matching if for every block B of G1 and every block D of G2, either E(B) = E(D) or E(B) ∩ E(D) = ∅. Note that E(B) = E(D) implies that B and D have the same terminals and direction, as for either B or D, the source vertex will have only outgoing edges toward the internal vertices and the target vertex will have only incoming edges from the internal vertices.

For a k-commodity network G, let Gi be the subnetwork of G that contains all the vertices and edges of G that belong to a simple si-ti path for Commodity i. In other words, Gi is the subnetwork of G for Commodity i that equilibria flows will consider, as they are, WLOG, acyclic. A multicommodity network G is block-matching if for every i, Gi is series-parallel, and for every i, j, Gi and Gj are blockmatching. An example is given in Figure 1.

3 Topology of Single-Commodity Networks for which Diversity Helps

In this section, we fully characterize the topology of singlecommodity networks for which, with any choice of heterogeneous demand and edge functions, diversity helps. WLOG we may restrict our attention to single-commodity networks whose edges all belong to some simple source-destination path as only these edges are going to be used by the (WLOG, acyclic) equilibria and thus all other edges can be discarded. It turns out that this topology is exactly that of series-parallel networks (Theorems 1 and 2).

3.1 Series Parallel Implies Diversity is Helpful

Throughout this section we will be considering a heterogeneous instance G on an s-t series-parallel network G. We let F denote the corresponding homogeneous instance. We let g denote an equilibrium flow for G and f an equilibrium flow for F. Finally, we let C ht (g) denote the cost of flow g and C hm(f) the cost of flow f . Although redundant, we keep the superscripts as a further reminder of the flow type at hand.

The key observation is that there is a path P used by flow f such that for every edge in P, fe ≥ ge, and hence for any r ∈ [0, rmax], crp (f) ≥ crp (g) (Lemmas 1 2 and 2). We then deduce our result: C ht (g) ≤ C hm(f) (Theorem 1).

Lemma 1. Let G be an s-t series-parallel network and let x and y be flows on G that route d1 and d2 units of traffic respectively, with d1 ≥ d2 and d1 > 0. Then, there exists an s-t path P such that for all e ∈ P, xe > 0 and xe ≥ ye.

Lemma 2. There exists a path P used by f such that for any r ∈ [0, rmax], crp (g) ≤ crp (f).

Proof. Flows f and g have the same magnitude on the seriesparallel network G. Applying Lemma 1 with x = f and y = g implies that there exists an s-t path P such that for all e ∈ P, fe > 0, implying that WLOG P is used by f, and fe ≥ ge. By assumption, for any r ∈ [0, rmax], ℓe + rσe is non-decreasing, and thus for all e ∈ P, ℓe(fe) + rσe(fe) ≥ ℓe(ge)+rσe(ge). Consequently, ∑e∈P (ℓe(fe)+rσe(fe)) ≥ ∑e∈P (ℓe(ge) + rσe(ge)) ⇔ crp (g) ≤ crp (f) as needed.

Proof. Since G is a series-parallel network, on setting ¯ r = E[r] and then applying Lemma 2, we obtain that there is a path P used by f such that

WLOG we can assume that the total demand d = 1. We first bound the total cost of g in terms of the cost of path P under g and then we use (2) to further bound it in terms of the cost of path P under f. The latter equals the cost of f, as the demand is equal to 1.

2 Lemma 1 is similar to [Milchtaich, 2006, Lemma 2].

3 The inequality might be strict. Consider the case of 2 parallel links with (ℓ1(x), σ1(x)) = (1, x) and (ℓ2(x), σ2(x)) = (2, 0), and 1 unit of flow, half with r = 0 and half with r = 2.

Consider the heterogeneous equilibrium flow g. By the equilibrium conditions, for any player of diversity parameter r, for any r, the cost she incurs with flow g is cr (g) ≤ ∑e∈p ℓe(ge) + r ∑e∈p σe(ge). In other words, there is no incentive to deviate to path P (if not already on it). Thus, for the demand vector (d1, . . . , dk) of diversity parameters (r1, . . . , rk), C ht (g) ≤ ∑ki=1 di(∑e∈p ℓe(ge) + ri ∑e∈p σe(ge)) = ℓp(g) + ¯ rσp(g), with the equality following as the total demand is 1 and the average diversity parameter is ¯ r = ∑ki=1 diri. As P is used by f, we have C hm(f) = ℓp(f) + ¯ rσp(f), and applying (2) we obtain C ht (g) ≤ ℓp(g)+¯ rσp(g) ≤ ℓp(f )+¯ rσp(f ) = C hm(f ).

3.2 The Series Parallel Condition is Necessary

To prove the necessity of the network being series-parallel, we begin by constructing an instance for which diversity hurts, i.e. the heterogeneous equilibrium has total cost strictly greater than the total cost of the homogeneous equilibrium (Proposition 1). Then, in Theorem 2, we show how to embed this instance into any network that is not series-parallel.

Recall the Braess graph GB, shown in Figure 2.

Proposition 1. For any strictly heterogeneous demand on the Braess graph GB, there exist edge functions (ℓe)e∈E and (σe)e∈E that depend on the demand, for which C ht (g) > C hm(f). 4

Proof. We may assume WLOG that the demand is of unit size. Let ¯ r be the average diversity parameter, r0 be the minimum of the diversity parameters' distribution and let d0 be the total demand with diversity parameter equal to r0. Since the demand is strictly heterogeneous, it must be r0 < ¯ r. In addition, we let h be any continuous, strictly increasing cost function with h( 1 2 ) = 1 and h( 12 + d0 2 ) = 1+ ¯ r-r0 2 .

Consider the Braess graph GB = ({s, u, v, t}, {(s, u), (u, t), (u, v), (s, v), (v, t)}) with cost functions ℓ(s,u)(x) = ℓ(v,t)(x) = h(x), σ(s,u)(x) = σ(v,t)(x) = 0, ℓ(u,t)(x) = ℓ(s,v)(x) = 2 + ¯ r+r0 2 , and σ(u,t)(x) = σ(s,v)(x) = 0, and ℓ(u,v)(x) = 1 and σ(u,v)(x) = 1. The instance is shown in Figure 2.

The heterogeneous equilibrium g routes the d0 units that have r = r0 through the zig-zag path, i.e. path s, u, v, t; the rest of the flow is split between the upper and lower paths s, u, t and s, v, t, and has C ht (g) = 3+ ¯ r. The homogeneous equilibrium f splits the flow between the upper and lower paths and has C hm(f) = 3 + ¯ r+r0 2 < 3+ ¯ r = C ht (g).

4 The proposition remains true even if we are restricted to only using affine functions.

Theorem 2. If G is not series-parallel, then for any strictly heterogeneous demand there are cost functions for which C ht (g) > C hm(f ).

Proof sketch. If G is not series-parallel then the Braess graph can be embedded in it (see e.g. [Valdes et al., 1979]). Thus, starting from the Braess network GB, by subdividing edges, adding edges and extending one of the terminals by one edge, we can obtain G. Fixing such a sequence of operations, for the given heterogeneous demand, we start from the Braess instance given by Proposition 1 and apply the sequence of operations one by one, so that, throughout the procedure, there are exactly 3 paths that correspond to the upper, lower and zig-zag paths of Proposition 1, with corresponding costs, and all other paths have some very large costs. Then, C ht (g) > C hm(f) follows exactly as in Proposition 1.

4 Topology of Multi-Commodity Networks for which Diversity Helps

In this section we fully characterize the topology of multicommodity networks for which, with any choice of heterogeneous average-respecting demand and edge functions, diversity helps. Because of Theorem 2, if we require diversity to help on any instance on G, then for any commodity i, Gi needs to be series-parallel. Yet, as we shall see in Proposition 2, this is not enough. We also need to understand the overlaps of the Gi's. It turns out that the allowable overlaps are exactly captured by the topology of block-matching networks (Theorems 3 and 4).

4.1 Sufficiency

Using Theorem 1, we can obtain an analogous theorem for the multi-commodity case.

Theorem 3. Let G be a k-commodity block-matching network. Then, for any instance on G with average-respecting demand C ht (g) ≤ C hm(f ).

Proof sketch. Consider Commodity i and let Gi = siB1v1 . . . vbi-1Bbi ti be its block representation. Consider an arbitrary Bj with terminals vj-1 and vj. Because G is block-matching, any other Commodity l either contains Bj as a block in its block representation or contains none of its edges. Also, recall that, as explained in the preliminaries section, if Gl contains Bj, it has the same terminals vj-1 and vj. This implies that under any routing of the demand, either all of l's demand goes through Bj or none of it does. This means that under both equilibria g and f, the total traffic routed from vj-1 to vj through Bj is the same which further implies that, if restricted to the block, the cost of the heterogeneous equilibrium is less than or equal to that of the homogeneous equilibrium: C ht (g)∣∣∣Bj ≤ C hm(f)∣∣∣Bj . On the other hand, if we let B be the set of all the blocks of all commodities, then C ht (g) = ∑B∈B C ht (g)∣∣∣B and C hm(f) = ∑B∈B C hm(f)∣∣∣B which using the previous inequality proves the result.

4.2 Necessity

To derive the necessity we first give an example of a nonblock-matching network for which diversity hurts (Proposition 2). Then, after giving some properties for commodities for which the corresponding Gi's are series-parallel (Lemmas 3 and 4), we mimic the above example to obtain contradicting instances for networks that are not block-matching and thereby prove Theorem 4.

Let G be the following 2-commodity network, depicted in Figure 3. G2, the subnetwork for Commodity 2, consists of a simple s2-t2 path P2, while G1, the subnetwork for Commodity 1, is formed from two simple s1-t1 paths named P1 and P3; P1 and P2 are disjoint, while P2 and P3 share a single edge, named e2. Finally e1 is an edge on P1 but not on P3.

Proposition 2. There exist edge functions and demands on G for which diversity hurts.

Proof. Let d1 = d2 = 1 be the total demands for Commodities 1 and 2 respectively. Let G1's demand consist of 3 4 single-minded players (i.e., with diversity parameter equal to 0) and 14 players with diversity parameter equal to 4, and let G2's demand be homogeneous with diversity parameter equal to 1. To all edges other than e1 and e2, assign latency and deviation functions equal to 0. Assign edge e1 the constant latency function ℓ1(x) = 1 and the constant deviation function σ1(x) = 2. Assign edge e2 the constant deviation σ2 = 0, and as latency function any ℓ2 that is continuous and strictly increasing, with ℓ2(1) = 3 and ℓ2( 5 4 ) = 9.

The equilibrium costs depend only on the flow through edges e1 and e2, as all other edges have cost 0. Also note that at least 1 unit of flow will go through e2 as this is the only route for G2's demand.

In the heterogeneous equilibrium g of this instance, 34 units of flow are routed through e1, and 1 + 1 4 units of flow are routed through e2, giving C ht (g) = 1· 3 4 d1+9· 14 d1+9·d2 = 12. In the homogeneous equilibrium f, G1's demand uses only P1. Thus, C hm(f) = 3 · d1 + 3 · d2 = 6 < C ht (g).

Remark 1. Proposition 2 would still hold if the common portion of P1 and P3, and the portion of P2 after e2, both had positive costs instead of zero. This is close to the way we will mimic this instance in the proof of Theorem 4. The idea, in both equilibria, is to route all the flow of Commodity 1 through two paths, P1 and P3, each containing one of e1 or e2, and to route the flow of Commodity 2 through a path, P2, that contains e2. This is done by putting (relatively) big constants as latency functions on all other edges that depart from vertices of the corresponding paths up to the point where e1 or e2 is reached, though some care is needed. Then, the relation of the equilibria costs will follow as in Proposition 2, as the exact same edge functions will be used for edges e1

and e2. This will be specified precisely when we give the construction.

Next, we state some useful properties of series-parallel networks that are based on their block structure. They will be used in the proof of Theorem 4.

Lemma 3. Let i be a commodity of network G and suppose that Gi is series-parallel.

(i) Let B1 and B2 be distinct blocks of Gi, with B1 preceding B2. There is no edge in G from an internal vertex of B1 to an internal vertex of B2.

(ii) Let u and v be vertices in Gi. If (u, v) is an edge of G then there is a simple si-ti path in Gi that contains both u and v (not necessarily in that order).

Lemma 4. Let i be a commodity of network G and suppose that Gi is series-parallel with block representation Gi = siB1v1 . . . vb-1Bbti. Let w be a vertex of Bk for some k ∈ [b].

(i) Suppose that w ̸= vk-1, and let P be an arbitrary path from a vertex u, in a block A that precedes Bk in the block representation, to vertex w. Let w′ be the first vertex on P that is an internal vertex in Bk, if any. Then P must include an edge of Bk exiting vk-1 prior to visiting w′ .

(ii) Suppose that w ̸= vk. Then any path of G from w to a vertex u in a block succeeding Bk has to first enter vk through one of its incoming edges that belong to Bk, before going to a block C that succeeds Bk in the block representation.

(iii) Every simple vk-1-vk path in G is completely contained in Bk.

Theorem 4. Let G be a multi-commodity network. If diversity helps for every instance on G with average-respecting demand (i.e. for any heterogeneous equilibrium g and any homogeneous equilibrium f, C ht (g) ≤ C hm(f)), then G is a block-matching network.

Proof. Let G have k commodities. First, we note that for any i ∈ [k], Gi is a series-parallel network. For otherwise, by Proposition 1, there is some heterogenous players' demand for Commodity i and edge functions for Gi such that diversity hurts. Letting all other commodities have zero demand yields an instance on G for which diversity hurts, a contradiction.

To prove that G is block-matching, it remains to show that for any two commodities i and j of G, for any block B of Gi and any block D of Gj, either E(B) = E(D) or E(B) ∩ E(D) = ∅. To reach a contradiction we assume otherwise, i.e. WLOG we assume that for Commodities 1 and 2 there exist two blocks B of G1 and D of G2 that share some common edge, and at the same time, WLOG, there is an edge in B that is not in D. The latter implies that B is not a single edge, and thus it must be a parallel combination of two series-parallel networks.

Let u and v be the endpoints of B. We first prove that all simple s2-t2 paths of G2 that share an edge with B first traverse an edge starting at u before traversing any other edge of B (Proposition 3). Then we prove that all s2-t2 simple paths of G2, that share an edge with B, reach u before traversing any internal vertex of B (Proposition 4). Since E(B) ∩ E(D) ̸= ∅, there is a simple s2-t2 path of G2 that shares an edge with B. Proposition 4 implies that this path, Q, has a subpath consisting of a simple s2-u path Q1 that shares no internal vertex with B. A completely symmetric argument shows that Q has a subpath consisting of a simple v-t2 path Q3 that shares no internal vertex with B. 5 But then, for any simple u-v path Q2 inside B, the path Q′ = Q1,Q2,Q3 is a simple s2-t2 path, and thus it belongs to G2. But this implies that all the edges of B belong to G2 and because B is a block, these edges will all be in a single block of G2. This block must be block D, since by assumption E(B) ∩ E(D) ̸= ∅, contradicting the existence of an edge in B and not in D. Therefore, once these propositions are proved, the theorem will follow.

The proofs of these propositions rely on the same idea. For each proposition, assuming that it does not hold, we construct instances, i.e. we choose demand and edge functions for G, such that diversity hurts, contradicting the assumption that for any instance on G diversity helps. The construction of the contradicting instances is based on Remark 1.

Proposition 3. Let P be a simple s2-t2 path in G2 which shares an edge with B. The first edge on P in B departs from u, i.e. has the form (u, x) for some x in B.

Proof. Let B be the parallel combination of H1 and H2. WLOG we may assume that P only visits vertices of G1, plus s2 and t2, as we may treat subpaths of P that have vertices that lie outside G1 as simple edges. Let w be the first internal vertex of P that belongs to B, and WLOG suppose that w lies in H1. By Lemma 3(ii), the edge of P exiting w will either go toward t1, i.e. forward, and thus traverse an edge of B for the first time (recall also Lemma 4(ii)), or will go toward s1, i.e. backward, either staying in H1 or going back to one of the preceding blocks of B. If it goes to one of the preceding blocks of B, then by Lemma 4(i), it has to traverse an edge of B departing from u in order to re-enter the internal portion of B (recall that P has some edge in B) and then the proposition would hold. The remaining possibility is that the backward edge leads to another internal vertex of H1. However, we can only repeat this process finitely often so if the proposition does not hold, it must be that P eventually traverses a first edge in B that departs from an internal vertex of H1. In this case we will reach a contradiction by creating an instance where diversity hurts. This instance will be based on the instance of Proposition 2.

We would like to use the following construction at this point. Let P2 be the path P resulting from the discussion in the previous paragraph and let e2 be the first edge on P that lies in B. Then let P3 be an s1-t1 path through e2. Recall that e2 lies in H1. Now let P1 be an s1-t1 path that goes through H2 and let e1 be an arbitrary edge on P1 in B. The intention is to force the s1-t1 flow to use just paths P1 and P3, while the s2-t2 flow uses just path P2, at the same time ensuring that diversity is harmful as in Proposition 2. Consider the following edge functions. e1 and e2 receive the same edge functions as in Proposition 2. The other edges all receive a constant deviation function equal to 0. For their latency functions, edges on P1 and P3 that are in B receive 0 functions. Out-edges from P1 and P3 that lie in B all receive functions of constant value N even if they are on P2. All as yet unassigned edges on P2 receive 0 functions, and the remaining edges are all given functions of constant value M ≫ N. However, the example in Figure 4 shows that there is a zero cost s2-t2 path (s2, w, z, t2), which defeats the construction.

5 For the symmetric argument, simply reverse all the arcs and the directions of the demand.

We fix this problem by defining the path P2 as follows. Let x be the first vertex on path P (in the example, this is w) such that there is an edge (x, y) in B and such that there is a y-t2 path Py-t2 which does not go through any earlier vertex on P (i.e. any vertex from s2 to x inclusive). Then (x, y) is chosen to be e2, and P2 is defined to be the simple path comprising the initial portion of P up to x, followed by e2, followed by Py-t2 (it may be that P2 = P ). Now the above cost functions, modulo a few details, achieve the desired contradiction.

Proposition 4. All simple s2-t2 paths of G2 that share an edge with B reach u before any internal vertex of B.

The proof is largely similar to that of Proposition 3.

Acknowledgements

We thank the anonymous referees for their thoughtful feedback that helped improve this work. Part of this work was completed while the authors were visiting the Simons Institute for the Theory of Computing, Berkeley, CA. Research partially supported by NSF grants CCF-1527568, CCF-1216103, CCF-1350823, CCF-1331863, CCF 1733832.