PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, Asuman Ozdaglar

arXiv:1601.02039v2cs.GT

TL;DR

The paper asks whether giving some drivers more route information can increase their equilibrium congestion costs. It models users with heterogeneous edge information through Information Constrained Wardrop Equilibrium, then characterizes Informational Braess’ Paradox across network topologies. IBP cannot occur in SLI networks but can occur outside that class, while ICWE has no worse worst-case inefficiency than standard Wardrop equilibrium.

  • Problem

    The paper studies whether additional route information, such as that supplied by GPS guidance systems, can make receiving users worse off through greater equilibrium congestion costs.

  • Method

    The paper extends congestion games with heterogeneous information sets, defines Information Constrained Wardrop Equilibrium and Informational Braess’ Paradox, and analyzes network topology and equilibrium inefficiency.

  • Results

    IBP cannot occur in SLI networks, occurs for some edge-cost configuration in every non-SLI network, and ICWE’s worst-case inefficiency is no worse than standard Wardrop equilibrium.

  • Takeaways & Limitations

    Whether additional route information can harm users is characterized by network structure: SLI networks rule out IBP, whereas non-SLI networks permit it under suitable costs.

  • Takeaways & Limitations

    Because SLI is restrictive and few real-world networks are expected to belong to it, IBP may be difficult to rule out in practice.

Abstract

from arXiv · show

To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of Information Constrained Wardrop Equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of Informational Braes' Paradox (IBP), which extends the classic Braess' Paradox in traffic equilibria, and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent (SLI) class, which is a strict subset of series-parallel networks, IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which IBP will occur. In the process, we establish several properties of the SLI class of networks, which include the characterization of the complement of the SLI class in terms of embedding a specific set of networks, and also an algorithm which determines whether a graph is SLI in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop equilibrium.

1 Introduction

The paper develops a framework for studying how route information affects congestion equilibria and defines Informational Braess’ Paradox (IBP) as the possibility that expanded information worsens users’ equilibrium costs. It characterizes exactly when IBP occurs, identifies the relevant network class, and establishes related equilibrium and inefficiency results.

  • Model: Users have different information sets about available edges and can use only routes composed of edges in their own information sets.Edge costs represent congestion, and users choose minimum-cost routes among those available to them.
  • Model: Information Constrained Wardrop Equilibrium applies the Wardrop condition separately to routes contained in each user type’s information set.The paper establishes existence and essential uniqueness for the equilibrium under its model.
  • Informational Braess’ Paradox: IBP asks whether expanding some users’ information sets can increase their equilibrium congestion costs.The question is motivated by route guidance systems that reveal routes users previously did not know.
  • Main result: IBP occurs if and only if the network is not in the series of linearly independent (SLI) class.In SLI networks, users with expanded information always benefit; outside SLI, some edge-cost configuration produces IBP.
  • Network structure: SLI networks are formed by joining linearly independent networks in series, and SLI is a strict subset of series-parallel networks.The paper characterizes non-SLI networks through embedded network structures and provides a linear-time test for SLI membership.
  • Equilibrium inefficiency: The presence of users with different information sets does not worsen the worst-case inefficiency bound relative to standard Wardrop equilibrium.The paper also reports a specialized result: informing all users completely yields IBP exactly when the network is not series-parallel.

2 Model

The model represents traffic networks with multiple user types whose route choices are constrained by differing edge information sets. It defines ICWE by requiring each type to use minimum-cost routes available within its information set.

  • Network and users: A traffic network consists of an undirected multigraph with origin O, destination D, user-type demands, information sets, and edge cost functions.Each type i knows edges E_i and can use routes R_i formed from those edges; edge costs are continuous, nonnegative, and nondecreasing.
  • Flows and costs: A feasible flow assigns each type’s demand across its available routes, with total edge flow obtained by aggregating traffic across types.Route costs are sums of the costs of their constituent edges under the resulting total flow.
  • Information Constrained Wardrop Equilibrium: ICWE requires every user type to route positive flow only on minimum-cost routes within its information set.Thus, routes in R_i carrying positive type-i flow have equal cost, while different types may have different equilibrium costs when their information sets differ.
  • Relation to Wardrop equilibrium: With one information type, the model reduces to the standard Wardrop equilibrium.The paper also illustrates that users with different information can face unequal equilibrium costs, whereas types sharing a common route have the same route cost.

3 Existence of Information Constrained Wardrop Equilibrium

The paper establishes existence and essential uniqueness of Information Constrained Wardrop Equilibrium for traffic networks with multiple information types. It also characterizes ICWE as the solution of a potential-function optimization problem.

  • Existence and uniqueness: ICWE is essentially unique: all equilibria give each user type the same equilibrium cost.If edge costs are strictly increasing, total flow on every edge is also identical across equilibria.
  • Optimization characterization: An ICWE is exactly a solution to the paper’s potential-function optimization problem.This extends the classical optimization characterization of Wardrop equilibrium to information-constrained users.
  • Existence and uniqueness: An ICWE exists for every traffic network with multiple information types.The theorem applies under continuous, nonnegative, nondecreasing edge cost functions.
  • Relation to prior congestion-game results: The model can be viewed as a player-specific congestion game in which unavailable edges impose infinite cost.Existing results for that class can establish equilibrium existence, while the paper supplies an alternative proof based on classical congestion-equilibrium results.

4 Some Graph-Theoretic Notions

This section introduces series-parallel, linearly independent, and series-of-linearly-independent network classes and develops structural characterizations used to analyze informational Braess’ Paradox. SLI networks are characterized by excluded embeddings and can be recognized in linear time.

  • Series-parallel and linearly independent networks: Series-parallel networks are built recursively from a single edge through series and parallel composition, while linearly independent networks require each route to contain an edge unique to that route.LI networks form a subclass of series-parallel networks.
  • Series of linearly independent networks: A network is SLI when it is a single LI network or is constructed by connecting SLI networks in series.Equivalently, an SLI network consists of several LI blocks connected in series.
  • Embedding characterizations: SLI networks are exactly those containing none of the networks shown in Figure 3 as an embedded network.This characterization is the structural basis for identifying networks in which IBP cannot occur and those in which it can be constructed.
  • Recognition algorithm: An algorithm recognizes whether a network is SLI in O(|E| + |V|) time.The algorithm builds on linear-time recognition of series-parallel networks.

5 Informational Braess’ Paradox

Informational Braess’ Paradox (IBP) occurs when expanding one user type’s information set increases that type’s equilibrium cost. The paper establishes IBP as a generalization of Braess’ Paradox and constructs examples showing it can occur across non-SLI network structures.

  • IBP occurs when providing more information to a subset of traffic-network users increases those users’ equilibrium costs.
  • IBP generalizes Braess’ Paradox because adding an edge can be represented as expanding a user type’s information set to include that edge.
  • IBP also occurs in the other basic networks embedded in non-SLI networks under the same construction with additional zero-cost edges.
  • For Wheatstone networks, a suitable assignment of cost functions and information sets produces IBP, following the occurrence of classical Braess’ Paradox.
  • The examples are nondegenerate and admit infinitely many affine cost-function assignments for which IBP occurs.
  • The paper investigates topology classes that rule out IBP for every edge-cost assignment, finding that IBP can occur in a broader class of networks than classical BP.

6 Characterization of Informational Braess’ Paradox

The characterization rests on lemmas describing equilibrium costs and flows in linearly independent (LI) networks and their series compositions. The main theorem states that IBP is impossible exactly on series of linearly independent (SLI) networks, while non-SLI networks admit an IBP construction; restricted-information IBP is characterized by series-parallel networks.

  • Three Key Lemmas: In an LI network, expanding type 1 users’ information sets guarantees that at least one user type’s equilibrium cost does not increase.
  • Three Key Lemmas: For series-composed networks, restricting an equilibrium flow to either component remains an equilibrium flow.
  • Three Key Lemmas: For series-composed networks, each type’s total equilibrium cost equals the sum of its equilibrium costs on the two components.
  • Three Key Lemmas: In an LI network, rerouting traffic from route subset RA to RB bounds the maximum cost improvement on RA below by the minimum improvement on RB.
  • Characterization of IBP: IBP does not occur if and only if the network is SLI: every SLI network rules out IBP for arbitrary costs, demands, and information sets.
  • Characterization of IBP: If a network is not SLI, some assignment of costs, demands, and information sets produces IBP, and such occurrences extend through the network construction.
  • Restricted Information Sets: With restricted information sets, IBP does not occur if and only if the network is series-parallel.
  • Multiple Origin-Destination Pairs: For multiple origin-destination pairs, the paper gives a proposition ensuring no IBP under the stated relevant-network conditions and examples of networks where it does not occur.

7 Efficiency of Information Constrained Wardrop Equilibrium

The paper evaluates ICWE efficiency against social optimum and standard Wardrop equilibrium, distinguishing aggregate from type-specific losses. Aggregate worst-case inefficiency matches standard Wardrop bounds, while some user types can experience lower relative performance.

  • ICWE’s worst-case inefficiency performance is no worse than that of standard Wardrop equilibrium.
  • The social optimum minimizes total cost across all edges and user types, while aggregate efficiency loss compares equilibrium and optimal total costs.
  • Under continuous edge-cost functions, a social optimum exists.
  • The efficiency bounds established for standard Wardrop equilibrium extend exactly to ICWE with heterogeneous information types.

8 Concluding Remarks

The paper introduces ICWE for users with heterogeneous information about available network edges and studies whether additional information can increase equilibrium costs. It characterizes exactly when IBP occurs and bounds ICWE inefficiency relative to standard Wardrop equilibrium.

  • ICWE extends Wardrop equilibrium to users who can use only routes composed of edges in their individual information sets.
  • IBP asks whether users receiving additional route information can become worse off through higher equilibrium costs or delays.
  • IBP cannot occur in SLI networks, whereas every non-SLI network has some edge-cost configuration producing IBP.
  • SLI networks are formed by joining linearly independent networks in series, with each origin-destination path containing an edge unique to that path.
  • Non-SLI networks embed one of a specific set of basic networks, and SLI membership can be determined in linear time.
  • The paper leaves open whether additional information harms other users, how likely harmful cost configurations are, and whether real-world IBP can be detected.

9.1 Proofs of Section 3

The proofs characterize ICWE through a convex optimization formulation. They use KKT conditions to establish equivalence between optimal solutions and equilibria, existence, and essential uniqueness of equilibrium costs.

  • An optimal solution of the convex potential problem is an ICWE, and every ICWE is an optimal solution.
  • The proof identifies the type-specific equilibrium costs through the KKT multipliers associated with route-flow constraints.
  • The equivalence follows from KKT conditions because the objective is convex and the flow constraints are affine.
  • Continuity of edge-cost functions makes the potential function continuous, so compactness and the extreme value theorem ensure an optimum exists.
  • Any two ICWE solutions have the same equilibrium cost for each information type.

9.2 Proofs of Section 4

This section proves equivalent structural characterizations of SLI networks and characterizes non-SLI series-parallel networks through embeddings of basic obstruction networks.

  • Equivalent SLI characterizations: An SLI network is either one LI network or the series connection of two SLI networks.The proof also identifies SLI networks with networks formed by attaching several LI blocks in series.
  • Equivalent SLI characterizations: Induction on the number of edges proves that the class of networks formed from LI blocks in series equals the recursively defined SLI class.The two inclusions are established by decomposing either class into a single LI block and a series attachment.
  • Excluded embeddings: Every SLI network is series-parallel and contains none of the basic obstruction networks shown in Figure 3.The contradiction argument uses route intersections: the obstruction construction yields routes that cannot share the required common node.
  • Excluded embeddings: Conversely, every series-parallel network that is not SLI contains an embedding of one of the obstruction networks in Figures 3b–3i.The proof proceeds by induction over the final series or parallel construction step and analyzes the divergence and reconvergence of two routes.

9.3 Proofs of Section 5

This section constructs cost functions and information sets that generate IBP on the basic obstruction network, proving that the phenomenon can occur for infinitely many parameter choices.

  • Example construction: With ce1(x)=x, ce2(x)=1, ce3(x)=1, ce4(x)=x, ce5(x)=0 and s1=1, expanding type 1’s information set raises its equilibrium cost from 3.The expanded information set is Ẽ1={e1,e2,e3,e4,e5}, and the resulting route e1e5e4 has cost 2 in the displayed calculation.
  • General construction: For any a1,a3,a5>0 satisfying a1+a3>a5, there exist non-negative parameters producing IBP on the network in Figure 3b.The claim permits infinitely many affine edge-cost functions satisfying the construction’s feasibility conditions.
  • General construction: A concrete information configuration that yields IBP uses E2={e1,e4,e5}, E1={e2,e3,e5}, and Ẽ1={e1,e2,e3,e5}.The edge-cost functions are affine, ce_i(x)=a_i x+b_i, under the stated parameter choices.
  • General construction: The construction imposes route-cost equalities before and after information expansion, then selects parameters so the post-expansion equilibrium is strictly more costly.The conditions are expressed through equations linking edge slopes, intercepts, demands, and equilibrium flows.

9.4 Proofs of Section 6

This section proves monotonicity and decomposition properties of ICWE, then uses them to show that information expansion cannot cause IBP on SLI networks but can be propagated from Wheatstone networks to non-series-parallel networks.

  • Series decomposition: For a series composition, restricting an ICWE to either component yields an ICWE for that component, and route costs decompose additively.If r=r1+r2, then its cost is the sum of the costs on the two component routes.
  • Cost bounds: In a series-parallel network with one restricted-information type and all other types fully informed, every positive-flow route cost lies between the minimum and maximum equilibrium type costs.The bound is proved by induction over series and parallel network composition.
  • Information expansion: Expanding information sets cannot increase the equilibrium cost of the users whose information expands.The proof constructs comparable feasible flows and uses route-load dominance together with the ICWE condition.
  • Non-series-parallel networks: If a network is not series-parallel, IBP can be transferred from an embedded Wheatstone network by updating information sets and edge costs during the embedding steps.Thus, IBP in the initial Wheatstone network persists in the final non-series-parallel network.
  • SLI networks: These structural bounds imply that IBP does not occur in SLI networks.The proof examines the possible information expansions after reducing the network structure and shows each case avoids an increase in equilibrium cost.
Loading 1601.02039v2…