研究记忆有限的路径选择,发现改善记忆可能让交通更堵。
Endogenous Information in Routing Games: Memory-Constrained Equilibria, Recall Braess Paradoxes, and Memory Design

- 用有限记忆和选择规则建模旅行者行为,得到稳定均衡解。
- 提出可实现的权重设计方法,使系统整体效率最优。
- 揭示‘回忆悖论’:更好记反而更堵,适用于所有复杂路网。
本文研究旅行者基于自身记忆选择路径的路由博弈,而非固定选项。微观层面,每位旅行者拥有有限记忆状态,接收推荐路径,按Logit规则选择并依如LRU策略更新记忆,形成平稳的遗忘型沃德罗普均衡(FWE);在弱正则条件下存在性可证,收缩条件下唯一性成立。宏观层面,提出基于路径显著性权重的简化模型,其对应的随机用户均衡是严格凸势函数的唯一极小值点,具备清晰优化与可实现性理论。该层刻画了比率预算与仿射绑定约束下的可控实现性,并在并行与串并联网络上给出构造算法。当记忆容量为1时,微观模型与宏观模型完全等价;对于更大记忆,构建了从LRU到TTL再到显著性权重的近似流程,并提供基于收缩的误差界,将代理映射误差转化为固定点与福利误差。最后定义‘回忆悖论’——提升记忆能力却导致均衡延迟上升,且在至少含两条独立路径的任意两终端网络中均可能发生。实验验证了近似效果、可控设计预测及降维层的计算优势。
原文摘要 · Abstract (English)
We study routing games in which travelers optimize over routes that are remembered or surfaced, rather than over a fixed exogenous action set. The paper develops a tractable design theory for endogenous recall and then connects it back to an explicit finite-memory micro model. At the micro level, each traveler carries a finite memory state, receives surfaced alternatives, chooses via a logit rule, and updates memory under a policy such as LRU. This yields a stationary Forgetful Wardrop Equilibrium (FWE); existence is proved under mild regularity, and uniqueness follows in a contraction regime for the reduced fixed-point map. The paper's main design layer is a stationary salience model that summarizes persistent memory and interface effects as route-specific weights. Salience-weighted stochastic user equilibrium is the unique minimizer of a strictly convex potential, which yields a clean optimization and implementability theory. In this layer we characterize governed implementability under ratio budgets and affine tying constraints, and derive constructive algorithms on parallel and series-parallel networks. The bridge between layers is exact for last-choice memory (B=1): the micro model is then equivalent to the salience model, so any interior salience vector can be realized by an appropriate surfacing policy. For larger memories, we develop an explicit LRU-to-TTL-to-salience approximation pipeline and add contraction-based bounds that translate surrogate-map error into fixed-point and welfare error. Finally, we define a Recall Braess Paradox, in which improving recall increases equilibrium delay without changing physical capacity, and show that it can arise on every two-terminal network with at least two distinct s-t paths. Targeted experiments support the approximation regime, governed-design predictions, and the computational advantages of the reduced layer.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。