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

Saad Alqithami

cs.GTApr 13, 2026

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

Authors: Saad Alqithami

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.

Figures & tables

Statement	Layer	Status	Reference
Existence of a stationary Forgetful Wardrop Equilibrium (FWE)	Micro (Markov)	Exact	Thm. 12
Exact equivalence of $B=1$ last-choice memory and salience-weighted logit	Micro $\rightarrow$ salience	Exact	Thm. 1
(Operational) realizability of any interior salience vector via surfacing when $B=1$	Micro design	Exact	Cor. 2
LRU $\rightarrow$ TTL marginal-hit bound (external independent Poisson requests)	External cache	Conditional rate	Thm. 15
Random-menu logit $\approx$ availability-weighted logit under explicit menu assumptions	Menu surrogate	Coordinate bound	Prop. 8 , Cor. 7
Convex potential and uniqueness of SW-SUE	Salience	Exact	Prop. 1

Table 1: Exact vs. approximate statements by modeling layer. Unless explicitly stated otherwise, implementability and design results are proved in the salience layer; the micro memory model provides an exact foundation for

B=1

and a heuristic pathway requiring validation for

B>1

Instance	$\overline{\mathrm{SC}}$	$\mathrm{SC}(\bar{x})$	TTL	Oracle
Pigou	$0.820055\pm 0.000025$	$0.819937\pm 0.000025$	0.819960	0.819960
Sioux Falls ( $10^{6}$ )	$2.130624\pm 0.000080$	$0.952318\pm 0.000008$	0.889140	$0.8891404\pm 0.0000003$

Table 2: Exp-1 costs. Sioux Falls entries are divided by

10^{6}

; Pigou is unscaled. Uncertainty is the 95% interval half-width across ten seeds. TTL is a deterministic stationary prediction. The oracle is a separately solved equilibrium for each seed’s measured availability.

Figure 1: Stationary predictions and simulated congestion costs at

\beta=5

. (a) Pigou with full memory (

B=2

); (b) Sioux Falls with

B=2

of eight routes per OD. The first two bars report mean daily cost,

\overline{\mathrm{SC}}

, and cost at the mean flow,

\mathrm{SC}(\bar{x})

. The remaining bars report the TTL equilibrium and an equilibrium with availability marginals frozen at their simulated values (oracle). Numbers beside bars give the plotted values; error bars are 95% intervals across ten seeds and may be smaller than the bar outlines. The panels use different units. These comparisons combine dynamic variation with model approximation; they do not isolate TTL equilibrium error.

Instance	TTL distance	Oracle distance	Local AWL distance	Window drift
Pigou	$0.000119\pm 0.000073$	$0.000119\pm 0.000073$	$0.000227\pm 0.000139$	$0.000173\pm 0.000077$
Sioux Falls	$0.300175\pm 0.000007$	$0.299874\pm 0.000007$	$0.317466\pm 0.000007$	$0.000105\pm 0.000020$

Table 3: Exp-1 demand-weighted share diagnostics (mean

\pm

95% half-width). Local AWL is evaluated at the observed mean flow; oracle distance uses the separately solved frozen-availability equilibrium. Window drift compares the first and second halves of the retained sample.

Comparison	$\ell_{1}$ discrepancy
Simulation choice vs. exact choice	$0.000307\pm 0.000067$
Simulation recall vs. exact recall	$0.001613\pm 0.000788$
TTL recall at exact choices vs. exact recall	0.162964
AWL using exact availability vs. exact choice	0.003239
TTL equilibrium vs. exact choice	0.025885

Table 4: Exp-2 separates approximation stages. The first two rows summarize ten simulations; the remaining rows are deterministic comparisons with the exact finite-state reference. Each row compares the indicated quantity with its exact counterpart; the errors are not additive.

Figure 2: Two stages of the larger-memory approximation on six constant-cost routes, with

B=3

\beta=4

, and uniform surfacing. Solid bars use the exact 120-state memory chain; hatched bars use TTL. (a) Recall probabilities, with TTL evaluated at the exact choice vector. Recall probabilities need not sum to one: several routes can be remembered together. (b) Route-choice probabilities from the exact model and the endogenous TTL equilibrium, each summing to one. Routes are ordered by increasing cost

(0.5,0.7,0.9,1.1,1.3,1.5)

. The annotated

\ell_{1}

discrepancies are sums of absolute coordinate differences. All values are deterministic calculations.

Catalog	Capacity	$z=0$	$z=0.6$	$z=1.2$	$z=2$
6	1	$0.0007\pm 0.0002$	$0.0166\pm 0.0003$	$0.0452\pm 0.0004$	$0.0796\pm 0.0005$
20	6	$0.0027\pm 0.0004$	$0.0067\pm 0.0009$	$0.0122\pm 0.0008$	$0.0169\pm 0.0012$
100	30	$0.0076\pm 0.0008$	$0.0084\pm 0.0010$	$0.0103\pm 0.0011$	$0.0277\pm 0.0033$
500	150	$0.0201\pm 0.0022$	$0.0207\pm 0.0018$	$0.0354\pm 0.0028$	$0.1500\pm 0.0082$

Table 5: External IID LRU cache: maximum marginal occupancy discrepancy from TTL, mean

\pm

95% half-width over ten streams. Fixed simulation length, rare requests, and correlated occupancy can limit accuracy at large catalog sizes; this table does not estimate an asymptotic convergence rate.

Figure 3: External-cache comparisons under independent requests, with memory capacity

B=\max\{1,\lfloor 0.3n\rfloor\}

and Zipf exponents distinguished by line style and marker. (a) Maximum absolute difference between simulated LRU occupancy and the TTL prediction, averaged over ten streams of one million requests (100,000 discarded); error bars are 95% seed intervals. (b) Exact

\ell_{1}

difference between discrete TTL occupancy

1-(1-p)^{\tau}

and Poisson TTL occupancy

1-e^{-p\tau}

, using the same rounded positive integer timer. Both axes are logarithmic. Connecting segments guide the eye between evaluated catalog sizes; neither panel estimates an endogenous-routing convergence rate.

$B$	Equilibrium cost	Residual	Mean daily cost	Cost at mean flow
1	1.671202613	$8.87\times 10^{-10}$	$1.671252\pm 0.000076$	$1.671218\pm 0.000076$
2	1.691247314	$9.17\times 10^{-10}$	$1.691326\pm 0.000045$	$1.691242\pm 0.000047$
3	1.671202613	$8.87\times 10^{-10}$	$1.680816\pm 0.000229$	$1.660650\pm 0.000219$

Table 6: Exp-3 stationary equilibrium and dynamic costs. Residuals apply to stationary equations. Dynamic columns report mean

\pm

95% half-width over ten finite-population simulations and are not interchangeable with equilibrium costs.

Figure 4: Equilibrium and dynamics on the three-route Braess network (

\beta=5

, uniform surfacing). (a) Stationary costs at discrete memory budgets. The equality at

B=1

and

B=3

follows from their common stationary logit rule. (b) Full-recall equilibrium cost compared with mean daily cost and cost at the mean flow from ten finite-population simulations; error bars are 95% seed intervals, smaller than the markers at this scale. These are different cost measures. (c) Last ten iterations of deterministic full-recall adjustment,

q_{t+1}=\operatorname{softmax}[-5L(q_{t})]

, initialized at

(0.208,0.206,0.586)

. Routes 1 and 2 exchange shares each iteration while route 3 stays at

56.66\%

; shares sum to one at every step. The connecting lines join discrete iterates. This cycle results from synchronous undamped adjustment and is distinct from a stationary equilibrium. The budget comparison alone does not establish a nested-menu Recall Braess Paradox.

$R$	Variable-route share	Optimal cost	Required ratio
1	0.764499	0.819960	1
1.1	0.755406	0.815232	1.1
1.25	0.743023	0.809060	1.25
1.5	0.725013	0.800631	1.5
2	0.695849	0.788357	2
3	0.653439	0.773544	3

Table 7: Exp-4 globally optimal Pigou design. These are deterministic results. The required ratio can be below the available budget once the system optimum becomes feasible.

Figure 5: Globally optimal influence-budget frontier for unit-demand Pigou at

\beta=5

. Markers give the evaluated budgets; connecting segments guide the eye. At each budget

R

, the minimizer is the projection of the system-optimal variable-route share

1/2

onto the feasible interval

|\log[x/(1-x)]+5(x-1)|\leq\log R

. The system-optimal cost

0.75

first becomes attainable at

R=e^{5/2}\approx 12.18

and remains optimal for larger budgets. The horizontal axis is logarithmic. This deterministic frontier concerns the specified two-route instance.

Quantity	Value
Distinct sampled targets	300
Minimum required ratio	1.285151
Median required ratio	57.519078
90th percentile required ratio	1003.868097
Maximum required ratio	94874.270438
Edge-additive feasible at $R=5$	36/300 (12%)

Table 8: Exp-5 descriptive results for 300 targets, each assessed in both tying classes. Quantiles refer to the sampled Dirichlet targets.

Figure 6: Empirical distribution of the unrestricted salience ratio required to implement 300 Braess target flows drawn from

\mathrm{Dirichlet}(1,1,1)

\beta=5

. At horizontal coordinate

R

, the step curve gives the fraction of sampled targets requiring a ratio no larger than

R

. The budget

R=5

admits 36 targets (12%); the median required ratio is

57.52

. The horizontal axis is logarithmic. The edge-additive class has full row rank on this route catalog, so these ratios also determine feasibility in that class; they do not describe the restrictive one-parameter tying class.

$k$	Routes	Split (ms)	Enumeration (ms)	Max. load difference
4	16	0.240	0.694	$3.81\times 10^{-10}$
6	64	0.236	0.758	$4.35\times 10^{-10}$
8	256	0.286	0.904	$3.35\times 10^{-10}$
10	1024	0.320	1.476	$4.26\times 10^{-10}$
12	4096	0.392	5.196	$4.65\times 10^{-10}$
14	16384	0.485	26.160	$4.42\times 10^{-10}$

Table 9: Exp-6 median complete-solve times over five repetitions and maximum observed difference between final edge loads.

Figure 7: Complete equilibrium-solve times on diamond chains with

k

parallel pairs and

2^{k}

routes. Markers show medians of five repetitions; vertical bars show the observed minimum and maximum, not confidence intervals. Enumeration includes construction of the full path catalog, while the split solver exploits the separable chain structure. Shared coefficient generation and warm-up are excluded. Timings use one numerical-library thread on an Intel Xeon Platinum 8573C; the vertical axis is logarithmic. At

k=18

, both methods solve the 262,144-route instance, with medians of

0.729

ms and

513.200

ms. This benchmark concerns the specified equilibrium solvers, not a general constrained design optimizer.

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Feb 26, 2026Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1Frank-Wolfe Algorithms Stackelberg Games
EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences
Did You Check the Right Pocket? Cost-Sensitive Store Routing for Memory-Augmented Agents
Mar 8, 2026Madhava GaikwadMemory-Augmented Agents Agent Memory Management
BRAID: Learning Equilibrium Maps in Interdependent Security Games via Weight-Tied Iterative Graph Neural Networks
Aug 14, 2026Elnaz Nowrouzi, Zhiqun Zuo, Xueru Zhang +1Nash Equilibrium Computation Game Theory
Computer Science and Engineering, The Ohio State University

Feb 26, 2026J/K move · Enter open · S save

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

Saeed Masiha, Sepehr Elahi, Negar Kiyavash, Patrick Thiran

EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences

Frank-Wolfe Algorithms Stackelberg Games Congestion Games Game Theory Zeroth-Order Optimization Constrained Optimization

Open paper AskPDF arXiv

We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (or other combinatorial strategies) and settle at a congestion equilibrium. The leader minimizes a system-level objective (e.g., total travel time) evaluated at equilibrium, but this objective is typically nonsmooth because the set of used strategies can change abruptly. We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update, avoiding differentiation through equilibria. We prove convergence to generalized Goldstein stationary points of the true equilibrium objective, with explicit dependence on the equilibrium approximation error, and analyze subsampled oracles: if an exact minimizer is sampled with probability

κ_m

, then the Frank--Wolfe error decays as

\mathcal{O}(1/(κ_m T))

. We also propose stratified sampling as a practical way to avoid a vanishing

κ_m

when the strategies that matter most for the Wardrop equilibrium concentrate in a few dominant combinatorial classes (e.g., short paths). Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline while converging to follower equilibria.

Abstract

Game Theory

Explore similar work

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

Did You Check the Right Pocket? Cost-Sensitive Store Routing for Memory-Augmented Agents

BRAID: Learning Equilibrium Maps in Interdependent Security Games via Weight-Tied Iterative Graph Neural Networks