A Combinatorial Characterization of Immunity to the Strong Braess Paradox

In a nonatomic congestion game, a strong Braess paradox occurs when reducing resource costs, population demands, or both increases at least one population's equilibrium cost. We characterize immunity when each population's available strategies form a fixed finite family of nonempty subsets of a common resource set. Immunity means that no such paradox can arise for any nonnegative continuous nondecreasing resource cost functions common to all populations and any positive demand vector. Our characterization resolves the open question posed by Fujishige et al.(2017) without varying the resource embedding. A menu is positively exposed if it consists of all available strategies of minimum total weight for some strictly positive resource weights. For a single population, we prove that immunity holds if and only if the column matroid of the augmented incidence matrix is series-parallel for every positively exposed menu. For multiple populations, we consider one menu for each population, all exposed by the same positive weights. The associated dual matroid includes one labeled element for each population to track its demand. Immunity holds if and only if, for every such collection of menus, each marked resource block is series-parallel and all demand labels retained in that block are parallel. We establish these characterizations through an affine response criterion and a blockwise ray lemma. Our results recover the immunity of matroid base systems under arbitrary resource sharing and the series-parallel routing criterion for complete acyclic path systems. Whenever a strategy system is not immune, we construct a strong Braess paradox with all demands equal to one and affine resource costs having strictly positive slopes and intercepts, by lowering just one intercept while keeping it positive. When strategies are listed explicitly, nonimmunity has polynomial-size certificates.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20640
Primary Topic
Game Theory and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Combinatorial Characterization of Immunity to the Strong Braess Paradox

Daorong Yu, Changjun Wang, Xujin Chen
arXiv (Cornell University)
Game Theory and Applications
preprint

A Combinatorial Characterization of Immunity to the Strong Braess Paradox

Daorong Yu, Changjun Wang, Xujin Chen
preprint en

Abstract

In a nonatomic congestion game, a strong Braess paradox occurs when reducing resource costs, population demands, or both increases at least one population's equilibrium cost. We characterize immunity when each population's available strategies form a fixed finite family of nonempty subsets of a common resource set. Immunity means that no such paradox can arise for any nonnegative continuous nondecreasing resource cost functions common to all populations and any positive demand vector. Our characterization resolves the open question posed by Fujishige et al.(2017) without varying the resource embedding. A menu is positively exposed if it consists of all available strategies of minimum total weight for some strictly positive resource weights. For a single population, we prove that immunity holds if and only if the column matroid of the augmented incidence matrix is series-parallel for every positively exposed menu. For multiple populations, we consider one menu for each population, all exposed by the same positive weights. The associated dual matroid includes one labeled element for each population to track its demand. Immunity holds if and only if, for every such collection of menus, each marked resource block is series-parallel and all demand labels retained in that block are parallel. We establish these characterizations through an affine response criterion and a blockwise ray lemma. Our results recover the immunity of matroid base systems under arbitrary resource sharing and the series-parallel routing criterion for complete acyclic path systems. Whenever a strategy system is not immune, we construct a strong Braess paradox with all demands equal to one and affine resource costs having strictly positive slopes and intercepts, by lowering just one intercept while keeping it positive. When strategies are listed explicitly, nonimmunity has polynomial-size certificates.

arXiv (Cornell University)
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon