Informational Braess' Paradox: The Effect of Information on Traffic Congestion

1 Introduction

• The model assigns users different information sets, limits their routes to edges they know, and defines ICWE by requiring minimum-cost choices among those feasible routes.Users face edge-specific congestion costs, and route costs sum the costs of their edges.Source: §1 · p. 2
• For single-origin–destination networks, the paper establishes ICWE existence and essential uniqueness and characterizes its main properties.The single-pair assumption is later relaxed.Source: §1 · p. 2
• IBP is impossible exactly on SLI networks, a strict subset of series-parallel networks; outside SLI, some edge-cost configuration produces IBP.Thus expanded information always benefits users in SLI networks, but can worsen their equilibrium costs in non-SLI networks.Source: §1 · pp. 2, 4
• SLI networks are series compositions of linearly independent subnetworks, and whether a network is SLI can be decided in linear time.In a linearly independent network, every route contains an edge used by no other route.Source: §1 · pp. 2–3
• When only one user type initially lacks complete route information and all users gain it, IBP occurs if and only if the network is not series-parallel.This specialized information change makes IBP less likely than under general changes in information sets.Source: §1 · p. 3
• For multiple origin–destination pairs, the paper gives a sufficient network-topology condition for ruling out IBP; its results also apply to congested resource-allocation problems beyond traffic.Because SLI is restrictive and few real-world networks may belong to it, the authors argue that IBP is difficult to rule out in practice.Source: §1 · pp. 3–4

Introduction

• Arnott et al. [1991] show that imperfect information about road capacity or delay can be worse than no information.Their model considers atomic drivers choosing departure times and routes.Source: §1 · p. 4
• Different user information sets do not change the worst-case inefficiency of traffic equilibrium characterized by Roughgarden and Tardos [2002].The paper frames this as a price-of-anarchy result for Information Constrained Wardrop Equilibrium.Source: §1 · pp. 4–5
• The paper proves existence and essential uniqueness of Information Constrained Wardrop Equilibrium.It also introduces the series-of-linearly-independent network class and establishes basic properties used in the later analysis.Source: §1 · p. 5
• Informational Braess’ Paradox occurs if and only if the network is not in the series-of-linearly-independent class.The introduction identifies this as the paper’s main result.Source: §1 · p. 5

2.1 Environment

• The network is an undirected graph with distinct origin and destination terminals; each user type has a demand and an information set defining its feasible routes.The model assumes each type has at least one feasible route.Source: §2.1 · pp. 5–6
• Each edge has a latency function of its flow that is continuous, nonnegative, and nondecreasing.Source: §2.1 · p. 6

2.2 Information Constrained Wardrop Equilibrium

• An Information Constrained Wardrop Equilibrium routes each type only on its known routes, with every positively used route having minimum cost among that type’s known routes.The positively used routes for a type therefore have equal cost.Source: §2.2 · p. 6
• Wardrop equilibrium is the single-information-type special case of ICWE.Source: §2.2 · p. 6
• In the example, equilibrium costs can differ across types, while types using a common route at equilibrium have the same cost.Source: §2.2 · p. 7

3 Existence of Information Constrained Wardrop Equilibrium

• An ICWE is characterized as a solution to an optimization problem, extending the Wardrop equilibrium optimization characterization.The proof uses this characterization to establish existence and essential uniqueness.Source: §3 · pp. 7–8
• An ICWE exists and is essentially unique, meaning each type has the same equilibrium cost across all equilibria.The existence and essential uniqueness result assumes non-decreasing cost functions.Source: §3 · pp. 7–8
• With strictly increasing cost functions, all equilibria have the same total flow on every edge.This strengthens essential uniqueness from equality of each type’s equilibrium cost to equality of edge flows.Source: §3 · p. 8

Some Graph-Theoretic Notions

• SP networks can be built from a single edge by series or parallel composition, while LI networks additionally exclude three embedded network patterns.SP networks are also characterized by the absence of the Wheatstone network; LI networks have a further common-route-segment characterization.Source: §4 · pp. 9–10
• An LI network gives every route an edge belonging to no other route, and LI networks form a subset of SP networks.Equivalently, route vectors in edge space are linearly independent.Source: §4 · p. 9
• An SLI network is a single LI network or a series connection of two SLI networks, equivalently several LI blocks connected in series.An LI block is a biconnected LI network.Source: §4 · p. 10
• A network is SLI exactly when none of the networks in Figure 3 is embedded in it.Figure 3 shows the excluded networks.Source: §4 · p. 10, Figure 3 · p. 11
• An algorithm recognizes whether a network is SLI in O(|E| + |V|) time.The bound is linear in the number of edges and vertices.Source: §4 · p. 11

Definition

• IBP occurs when expanding one user type’s information set, while keeping other types’ information sets fixed, strictly increases that type’s equilibrium cost.The definition takes the expanding type to be type 1 without loss of generality.Source: §5 · pp. 11–12

Relation to Braess’ Paradox

• IBP generalizes classic Braess’ Paradox because adding an edge can be viewed as expanding a user type’s information set, and it can occur in a broader class of networks.The section identifies IBP-free network classes as a goal of its topology analysis.Source: §5 · pp. 12–13

Examples

• IBP occurs in every basic network shown in Figure 3, including the Wheatstone network and the other networks embedded in non-SLI networks.For the Wheatstone network, the example follows from classic Braess’ Paradox; the other listed networks use the construction described in Example 2(c).Source: §5 · p. 12
• In the Figure 3b example, newly informed type 1 users shift flow from e2e3 toward e1e3, raising type 2’s e1e4 cost and pushing its flow to e5.The passage reports that type 1’s equilibrium cost is higher after e1 is added to its information set.Source: §5 · p. 12

Robustness

• The examples are not isolated: infinitely many cost-function assignments produce IBP in Figure 3b and in the other illustrated networks.The Figure 3b result includes an infinite set of affine cost functions; the passage also notes infinitely many cost functions for the other listed examples.Source: §5 · pp. 12–13

6.1 Three Key Lemmas

• In LI networks, greater total traffic raises flow on some route (weakly on each edge), while expanding information for one or multiple types leaves at least one type’s equilibrium cost no higher—not necessarily type 1’s.The latter property alone is insufficient to establish that expanding type 1 users’ information does not increase their cost.Source: §6.1 · pp. 13–14
• When two networks are attached in series, restricting an equilibrium flow to either component yields an equilibrium there, and each type’s total equilibrium cost is the sum of its component costs.Source: §6.1 · p. 14
• In an LI network, when traffic shifts from route set RA to RB, the maximum cost improvement among routes in RA is at least the minimum improvement among routes in RB.The authors identify this as a key lemma for analyzing traffic reallocation when users obtain more information.Source: §6.1 · p. 14
• The 6.1 argument identifies a route and edge with opposing flow shifts, then restricts to a subnetwork with common paths and applies induction.The selected route in RB has at least as much flow after expansion, while the edge carries less type-A flow and at least as much type-B flow; induction is applied to the restricted subnetwork.Source: §6.1 · pp. 15–17

6.2 Characterization of Informational Braess’ Paradox

• IBP does not occur in any SLI network under any assignment of costs, demands, and information sets, whereas every non-SLI network admits a configuration in which IBP occurs.This is the stated if-and-only-if characterization.Source: §6.2 · pp. 17–18
• The LI-network proof partitions types and routes by cost changes: types whose costs rise use higher-cost routes before expansion, while types whose costs do not rise use lower-cost routes afterward.These claims imply a shift in total flow away from higher-cost routes, which leads to the contradiction used to rule out IBP in LI networks.Source: §6.2 · pp. 18–19
• To extend an IBP construction from an embedded motif to a non-SLI network, edge division preserves equilibrium flow, while added edges are excluded from information sets and remain unused.The proof uses the embedded networks characterized in Theorem 2 and assigns costs and information sets that retain IBP in the full network.Source: §6.2 · p. 20
• If IBP occurs in a network, it occurs for infinitely many cost functions.The proof extends an IBP-inducing configuration from an embedded basic network to the full network.Source: §6.2 · p. 20

6.3 IBP with Restricted Information Sets

• With restricted information sets, IBP occurs exactly on non-series-parallel networks: it is absent on series-parallel networks and can occur otherwise.This restriction considers the case where one user type initially lacks all edges and then learns them all.Source: §6.3 · p. 21

6.4 Extension to Multiple Origin-Destination Pairs

• With multiple origin-destination pairs, IBP is excluded if every relevant network is SLI and any overlap between pairs consists of all their coincident LI blocks.The proposition gives a sufficient condition for excluding IBP in this setting.Source: §6.4 · pp. 22–23
• IBP does not occur on Example 3’s network for any set of edge-cost functions, despite the network failing Proposition 4’s conditions.Its common LI block is not coincident because the terminal sets differ.Source: §6.4 · p. 23
• Under Chen et al.’s [2016] definition, BP occurs in Example 3’s network even though IBP does not.Their definition counts an increase in one OD pair’s equilibrium cost after adding an edge, even if that edge is never used by that pair.Source: §6.4 · pp. 23–24

Efficiency of Information Constrained Wardrop Equilibrium

• ICWE has the same worst-case inefficiency bounds as standard Wardrop equilibrium, with the worst case occurring for homogeneous users.The bounds are tight for the stated cost-function classes.Source: §7 · pp. 24, 26
• Aggregate efficiency loss compares total costs at ICWE and the social optimum, which minimizes costs summed across all user types.A social optimum exists when each cost function is continuous; tight bounds are established for different cost-function classes.Source: §7 · pp. 24–25
• With affine cost functions, some user groups can have worse than 3/4 performance relative to the social optimum under type-specific efficiency loss.The paper contrasts type-specific bounds with the standard Wardrop bounds and illustrates the distinction in Example 4.Source: §7 · pp. 24, 27, Figure 7 · p. 28

• The paper extends congestion games to heterogeneous edge-information sets, defines ICWE for routes using only known edges, and establishes its existence and essential uniqueness.Source: §8 · p. 28
• IBP cannot occur in SLI networks, but a suitable edge-cost configuration causes it in every non-SLI network, which embeds a basic obstruction network.Source: §8 · pp. 28–29
• In SLI networks, every origin-destination path has an edge absent from every other such path; SLI membership can be determined in linear time.Source: §8 · p. 29
• ICWE’s worst-case inefficiency is no worse than that of standard Wardrop equilibrium with one user type.Source: §8 · p. 29
• Open questions include when additional information harms other users and how likely IBP-inducing costs are in non-SLI networks, with fairness and ex-ante assessment motivating both.Source: §8 · p. 29
• Another direction is to find information sets for K user types that minimize their total ICWE cost, given their traffic demands.Source: §8 · p. 29
• For networks with multiple origin-destination pairs, the paper establishes a sufficient condition for avoiding IBP and leaves necessary-and-sufficient conditions open.Source: §8 · p. 29
• The paper also raises the empirical question of whether IBP can be detected in real-world settings.Source: §8 · p. 29

9.1.1 Proof of Proposition 1

• Every optimal solution of Eq. (2) is an ICWE, as shown by the optimizer’s KKT conditions.The proof uses the convex objective and affine constraints to establish KKT conditions and identify the resulting flow as an equilibrium.Source: §9.1.1 · p. 30
• Conversely, every ICWE is an optimal solution of Eq. (2), because its flow satisfies sufficient KKT conditions for the convex objective with affine constraints.The proof invokes Bertsekas [1999, Chapter 3] for the sufficiency of KKT conditions.Source: §9.1.1 · p. 30

9.1.2 Proof of Theorem 1

• The feasible-flow set is compact in K|R|-dimensional Euclidean space, and continuous edge costs make the potential function continuous.These properties supply the existence conditions used in the proof of Theorem 1.Source: §9.1.2 · p. 31
• The cited theorem establishes that optimization problem Eq. (2) attains its minimum, which Proposition 1 identifies as an ICWE.Source: §9.1.2 · p. 31
• Any two ICWEs are optimal solutions of Eq. (2), so their potential values both equal the optimum.The proof uses Proposition 1 and convexity of the potential function.Source: §9.1.2 · p. 31
• Because the edge-integral functions are convex, their edge costs are constant between the two equilibrium flows, implying equal equilibrium costs.Thus the equilibrium cost is the same for each user type in both equilibria.Source: §9.1.2 · p. 31

9.2.1 Proof of Equivalence in Definition 5

• The proof shows that SLI networks are exactly those formed by attaching several LI blocks in series, equivalently single LI networks or serial connections of SLI networks.Source: §9.2.1 · pp. 31–32

9.2.2 Proof of Theorem 2

• For series-parallel networks, the proof shows that SLI implies none of the Figure 3 networks is embedded, while any network that is not SLI contains an embedding of a network from Figures 3b–3i.Source: §9.2.2 · pp. 32–33

9.2.3 Proof of Proposition 3

• Valdes et al. [1979] show that series-parallel networks reduce to one edge by S/P operations and admit linear-time binary tree decompositions.Source: §9.2.3 · p. 34
• A non-series-parallel graph is not SLI; for a series-parallel graph, the proof obtains a binary-tree decomposition in linear time.The decomposition represents edges as leaves, with series and parallel attachment nodes.Source: §9.2.3 · p. 34
• In the decomposition, an S-root is SLI exactly when both subtrees are SLI, while a P-root is SLI exactly when both subtrees are LI.The proof applies these tests inductively to verify SLI membership in linear time.Source: §9.2.3 · p. 35
• For LI recognition, a P-root is LI exactly when both subtrees are LI, while an S-root is LI when one subtree has only S labels and the other is LI.The proof checks the S-label condition by traversing the tree and uses induction to verify the LI subtree.Source: §9.2.3 · p. 35

9.3.1 Expansion of Example 2

• In Example 2, expanding type 1 users’ information set from {e1, e2, e3, e4} to include e5 increases their equilibrium cost.The example uses K = 1 and edge costs ce1(x) = x, ce2(x) = 1, ce3(x) = 1, ce4(x) = x, and ce5(x) = 0.Source: §9.3.1 · pp. 35–36

9.3.2 Proof of the Claim of Remark 2

• For Figure 3b, whenever a1, a3, and a5 are positive and a1 + a3 > a5, infinitely many nonnegative affine edge-cost configurations can yield IBP.The costs have the form cei(x) = aix + bi for 1 ≤ i ≤ 5.Source: §9.3.2 · pp. 36, 38
• An explicit information-set configuration yielding IBP uses E2 = {e1, e4, e5}, E1 = {e2, e3, e5}, and expanded Ẽ1 = {e1, e2, e3, e5}.Source: §9.3.2 · p. 36

9.4.1 Proof of Lemma 1

• The proof of Lemma 1 aggregates flows across information types into a single-type flow and applies Milchtaich’s result before comparing equilibria under larger information sets.It uses the fact that a route available to a type before expansion remains available afterward.Source: §9.4.1 · p. 38

9.4.2 Proof of Lemma 2

• The proof of Lemma 2 shows that restricting an equilibrium flow to either component of a series composition yields an equilibrium there, with user costs adding across the components.For a used route, its cost is the sum of the costs of its two component routes.Source: §9.4.2 · p. 39

9.4.3 Proof of Theorem 4

• After expanding type 1 users’ information to all edges, their equilibrium cost does not increase.The proof uses a route-flow comparison and bounds based on the costs of the other user types.Source: §9.4.3 · p. 40
• An IBP instance on the Wheatstone network can be extended through the embedding steps to any non-series-parallel network.The proof updates information sets and cost functions during embedding to preserve IBP in the resulting network.Source: §9.4.3 · p. 41

9.4.4 Omitted Proof of Example 3

• In the cases examined for Example 3, information expansion does not produce IBP.The proof reduces the setup to one fully informed type and one or two types for the other origin-destination pair, then examines the possible cases.Source: §9.4.4 · p. 41
• Across the first examined configuration, edge costs and all types’ equilibrium costs remain unchanged after information expansion, so IBP does not occur.The excerpt also concludes that IBP does not occur in the subsequent examined configurations.Source: §9.4.4 · p. 42
• For the two-type configuration, the proof concludes that IBP does not occur across the considered equilibrium cases.These include cases distinguished by whether the expanded-information type uses e1 and by changes in edge flows.Source: §9.4.4 · p. 43
• For the three-type configurations examined, the proof finds no IBP and, in one case, unchanged edge and equilibrium costs for all types.The conclusions cover the listed route-information configurations and cases of the resulting edge-flow changes.Source: §9.4.4 · p. 43