pith. sign in

arxiv: 2604.11733 · v1 · submitted 2026-04-13 · 💻 cs.GT · cs.AI· cs.IT· math.IT

Endogenous Information in Routing Games: Memory-Constrained Equilibria, Recall Braess Paradoxes, and Memory Design

Saad Alqithami This is my paper

Pith reviewed 2026-05-10 15:20 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.ITmath.IT
keywords routing gamesmemory constraintsRecall Braess ParadoxForgetful Wardrop Equilibriumsalience modelendogenous informationWardrop equilibriasurfacing policy
0
0 comments X

The pith

Travelers with limited memory create endogenous route sets, and designs that improve recall can raise equilibrium delays without any capacity change.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Travelers in routing games optimize only over routes they remember or that interfaces surface, rather than over a fixed exogenous set. The paper builds a micro model in which each traveler holds a finite memory state, chooses among surfaced options by logit, and updates memory under policies such as LRU, producing a stationary Forgetful Wardrop Equilibrium. A macro salience layer then summarizes these memory and interface effects as route-specific weights; the resulting salience-weighted stochastic user equilibrium is the unique minimizer of a strictly convex potential. This layer is exactly equivalent to the micro model when memory holds only the last choice and approximately equivalent otherwise via an explicit LRU-to-TTL-to-salience pipeline with contraction error bounds. The paper proves that Recall Braess Paradoxes arise on every two-terminal network with at least two distinct paths, so that policies improving recall can increase total equilibrium delay.

Core claim

Finite traveler memory makes the considered route set endogenous; the resulting stationary equilibria are captured exactly by a salience-weighted stochastic user equilibrium when memory size is one and approximately so for larger memories through an explicit approximation pipeline with contraction bounds, while any interior salience vector is realizable by a suitable surfacing policy and Recall Braess Paradoxes occur on every two-terminal network possessing at least two distinct s-t paths.

What carries the argument

The salience-weighted stochastic user equilibrium, which summarizes persistent memory and surfacing effects as route-specific weights and is the unique minimizer of a strictly convex potential.

Load-bearing premise

The LRU-to-TTL-to-salience approximation pipeline together with contraction bounds keeps error from larger memories small enough that it does not distort fixed-point or welfare calculations.

What would settle it

A direct simulation on any two-path network or the classic Braess network in which raising memory size B under the LRU update rule produces a measurable increase in equilibrium total delay.

Figures

Figures reproduced from arXiv: 2604.11733 by Saad Alqithami.

Figure 1
Figure 1. Figure 1: Exp-1 (Pigou): stationary choice shares under the micro model (left), oracle-availability AWL approximation [PITH_FULL_IMAGE:figures/full_fig_p034_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Exp-2: micro vs. TTL recall statistics on a controlled parallel instance. Top: recall/hit probabilities [PITH_FULL_IMAGE:figures/full_fig_p035_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Exp-3 (Braess): stationary micro social cost vs. memory budget [PITH_FULL_IMAGE:figures/full_fig_p036_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Exp-4: governed design frontier on a parallel network. [PITH_FULL_IMAGE:figures/full_fig_p036_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Exp-5: distribution of required influence budgets [PITH_FULL_IMAGE:figures/full_fig_p037_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Exp-6: runtime scaling on the diamond-chain SP family (split-flow vs. path enumeration). [PITH_FULL_IMAGE:figures/full_fig_p038_6.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies routing games with endogenous route recall via finite-memory travelers who update memory under policies like LRU and choose via logit. It defines Forgetful Wardrop Equilibrium (FWE) for the micro model, proves existence under mild regularity and uniqueness in contraction regimes, and introduces a salience-weighted stochastic user equilibrium as a tractable macro model that admits a strictly convex potential. Exact equivalence between layers holds for memory size B=1; for B>1 an LRU-to-TTL-to-salience approximation pipeline with contraction bounds is used. The paper characterizes implementability under ratio budgets and derives a Recall Braess Paradox (improving recall raises equilibrium delay) that arises on every two-terminal network with at least two distinct s-t paths, supported by targeted experiments.

Significance. If the results hold, the work supplies a design-oriented theory for memory and information surfacing in routing games, extending classical Wardrop and SUE models with endogenous action sets. Strengths include the strictly convex potential enabling clean optimization, exact micro-macro equivalence at B=1, and constructive algorithms on parallel/series-parallel networks. The Recall Braess Paradox provides a falsifiable, network-wide existence result that could inform information-system design to avoid or exploit recall-induced inefficiencies.

major comments (2)
  1. [Recall Braess Paradox and approximation pipeline] Section on the Recall Braess Paradox and the micro-macro bridge: the paradox (delay(B') > delay(B) for B' > B) is shown inside the salience-weighted SUE. While contraction bounds translate surrogate-map deviation into fixed-point and welfare error for B>1, these bounds are one-sided on distance and do not guarantee sign preservation of the delay inequality. Consequently the claim that the paradox arises on every two-terminal network with ≥2 s-t paths does not automatically transfer to the finite-memory FWE once B exceeds 1.
  2. [LRU-to-TTL-to-salience pipeline] Section on the LRU-to-TTL-to-salience pipeline: the error-propagation analysis controls the magnitude of deviation from the salience fixed point but supplies no explicit bound or numerical verification that the welfare ordering (higher delay under improved recall) is preserved under the approximation for general networks. This is load-bearing for extending the “every network” existence result beyond B=1.
minor comments (2)
  1. Notation for the salience weights and TTL parameters could be unified across the micro and macro sections to avoid redefinition.
  2. Figure captions for the example networks would benefit from explicit indication of which paths are used in the B=1 versus B>1 cases.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to rigorously bridge the Recall Braess Paradox from the salience-weighted SUE to the finite-memory FWE. We address both comments below and will revise the manuscript to close the identified gap.

read point-by-point responses

  1. Referee: Section on the Recall Braess Paradox and the micro-macro bridge: the paradox (delay(B') > delay(B) for B' > B) is shown inside the salience-weighted SUE. While contraction bounds translate surrogate-map deviation into fixed-point and welfare error for B>1, these bounds are one-sided on distance and do not guarantee sign preservation of the delay inequality. Consequently the claim that the paradox arises on every two-terminal network with ≥2 s-t paths does not automatically transfer to the finite-memory FWE once B exceeds 1.

    Authors: We agree that one-sided distance bounds alone do not automatically preserve the sign of the welfare difference. In revision we will add a new proposition establishing a sufficient condition: if the macro-level delay gap exceeds twice the welfare-error bound (itself controlled by the contraction constant of the reduced map), then the inequality direction is preserved for the FWE. Because the contraction regime permits the approximation error to be made arbitrarily small for any fixed network (by lowering the logit temperature or tuning memory-update rates), the paradox can be realized in the micro model on every two-terminal network with at least two s-t paths. The revised statement will explicitly reference this sufficient condition and include the short proof. revision: yes

  2. Referee: Section on the LRU-to-TTL-to-salience pipeline: the error-propagation analysis controls the magnitude of deviation from the salience fixed point but supplies no explicit bound or numerical verification that the welfare ordering (higher delay under improved recall) is preserved under the approximation for general networks. This is load-bearing for extending the “every network” existence result beyond B=1.

    Authors: We will augment the pipeline section with an explicit welfare-error bound expressed in terms of the surrogate-map deviation, the Lipschitz constant of the delay operator, and the contraction factor. We will also add a numerical verification on a small non-parallel network (a 3-link grid) confirming that the ordering is preserved once the contraction is sufficiently strong. These additions will appear in the main text or a dedicated appendix subsection. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained with explicit equivalence and bounded approximations

full rationale

The paper's core chain defines a finite-memory micro model yielding stationary FWE, then introduces a salience-weighted SUE layer whose equilibrium is the unique minimizer of a strictly convex potential (a direct consequence of the weighted logit structure, not a redefinition of inputs). Equivalence between layers is stated exactly for B=1 via the paper's own reduction; for B>1 an explicit LRU-to-TTL-to-salience pipeline plus contraction-mapping bounds are supplied to control fixed-point and welfare deviation, without using those bounds to force the sign or existence of the Recall Braess Paradox. The paradox itself is defined as an increase in equilibrium delay from improved recall and shown to arise on every qualifying two-terminal network inside the salience model, with micro-model transfer supported by the exact B=1 case plus targeted experiments rather than by construction. No load-bearing self-citation, no fitted parameter renamed as prediction, and no ansatz smuggled via prior work appear in the derivation; the models remain independently verifiable against the stated assumptions and external network instances.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 2 invented entities

The framework rests on standard choice models and memory policies plus new equilibrium and salience constructs; no independent evidence is given for the invented equilibrium concept beyond the paper's definitions.

free parameters (1)
  • memory size B
    Finite per-traveler memory capacity that governs the micro model and approximation regime.
axioms (2)
  • domain assumption Travelers select among surfaced routes via a logit rule
    Invoked to define choice probabilities in the micro model.
  • domain assumption Memory updates follow an LRU policy
    Used to close the micro-model dynamics.
invented entities (2)
  • Forgetful Wardrop Equilibrium (FWE) no independent evidence
    purpose: Stationary equilibrium concept for memory-constrained routing
    Defined as the fixed point of the memory-update process.
  • salience-weighted stochastic user equilibrium no independent evidence
    purpose: Reduced macro model that summarizes memory and interface effects
    Introduced as the unique minimizer of a strictly convex potential.

pith-pipeline@v0.9.0 · 5616 in / 1241 out tokens · 57317 ms · 2026-05-10T15:20:54.102456+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    Shaddin Dughmi

    doi: 10.1016/0022-247X(65)90125-3. Shaddin Dughmi. Algorithmic information structure design: a survey.SIGecom Exch., 15(2):2–24, February 2017. doi: 10.1145/3055589.3055591. URLhttps://doi.org/10.1145/3055589.3055591. Ronald Fagin. Asymptotic miss ratios over independent references.Journal of Computer and System Sciences, 14(2):222–250, 1977. ISSN 0022-00...

    work page doi:10.1016/0022-247x(65)90125-3 2017

  2. [2]

    Dov Monderer and Lloyd S

    doi: 10.1016/j.geb.2005.09.005. Dov Monderer and Lloyd S. Shapley. Potential games.Games and Economic Behavior, 14(1):124–143, 1996. doi: 10.1006/game.1996.0044. J. D. Murchland. Braess’s paradox of traffic flow.Transportation Research, 4:391–394, 1970. URL https://api. semanticscholar.org/CorpusID:154755145. Eric I. Pas and Shari L. Principio. Braess’ pa...

    work page doi:10.1016/j.geb.2005.09.005 2005

  3. [3]

    Transportation Networks for Research Core Team

    doi: 10.1287/trsc.17.3.301. Transportation Networks for Research Core Team. Transportationnetworks: A repository of transportation network datasets. GitHub repository. URL https://github.com/bstabler/TransportationNetworks. Accessed: 2026-01-25. Leizhen Wang, Peibo Duan, Zhengbing He, Cheng Lyu, Xin Chen, Nan Zheng, Li Yao, and Zhenliang Ma. Agentic large...

    work page doi:10.1287/trsc.17.3.301 2026

  4. [4]

    doi: https://doi.org/10.1016/j.trc.2025.105307

    ISSN 0968-090X. doi: https://doi.org/10.1016/j.trc.2025.105307. URL https://www.sciencedirect. com/science/article/pii/S0968090X25003110. 51 John Glen Wardrop. Some theoretical aspects of road traffic research.Proceedings of the Institution of Civil Engineers, 1(3):325–378, 1952. doi: 10.1680/ipeds.1952.11362. Jin Y . Yen. Finding the k shortest loopless ...

    work page doi:10.1016/j.trc.2025.105307 2025