跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20640 · v1

A Combinatorial Characterization of Immunity to the Strong Braess Paradox

首次提交 2026-11-16 15:01
版本更新 2026-11-16 15:01
雷达观测 2026-11-17 13:07
arXiv ↗PDF ↗

摘要

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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 15:01 · 最新观测版本

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.

查看此版本解读 →查看此版本原文 ↗