arXiv:2604.11733v1 [cs.GT] 13 Apr 2026
E NDOGENOUS I NFORMATION IN ROUTING G AMES : M EMORY-C ONSTRAINED E QUILIBRIA , R ECALL B RAESS PARADOXES , AND M EMORY D ESIGN
Saad Alqithami [email protected]
A BSTRACT We study routing games in which travelers (or an AI guidance layer mediating their choices) optimize over an action set that is itself produced by bounded memory, surfacing, and forgetting policies. We present two coupled layers. First, we give a fully specified micro model in which each agent carries a finite memory state that evolves as a Markov chain (e.g., LRU eviction) and selects among recalled and surfaced routes via a logit response; a stationary Forgetful Wardrop Equilibrium (FWE) exists as a fixed point between congestion and the memory chain’s stationary law. Second—and as the main design layer—we introduce stationary salience policies (additive utility biases over routes) that summarize the effect of memory and interface ranking on choice. Salience-weighted stochastic user equilibrium is the unique minimizer of a strictly convex potential, yielding uniqueness and global convergence without contraction assumptions, and enabling inverse-equilibrium analysis: we characterize implementable flows under ratio budgets and affine tying (fairness) constraints and derive tractable solvers on parallel and series-parallel networks. We tighten the bridge between the layers. For last-choice memory (B = 1) the micro model is exactly equivalent to the salience model with salience proportional to the surfacing distribution; hence any interior salience vector is operationally realizable by an appropriate surfacing policy. For larger memories (B > 1) with LRU eviction, we develop and validate an approximation pipeline LRU→TTL→independent availability→salience, quantify its error under a Poissonized repeated-choice regime, and propose scalable surrogate solvers. We define a social-cost Recall Braess Paradox—improving recall can increase equilibrium delay without changing physical capacity—and prove a network-class theorem: every two-terminal network with at least two distinct s–t paths admits latencies and a canonical recall-richness expansion (menuinclusion order) that induces the paradox. Keywords routing games · stochastic user equilibrium · imperfect recall · endogenous information · Braess paradox · implementability · memory governance · series-parallel networks.
1
Introduction
Traffic routing is a canonical noncooperative game: each traveler selects a route to minimize personal travel time, while congestion couples decisions through shared edge latencies. The resulting Wardrop equilibrium (the non-atomic analogue of Nash equilibrium) is stable to unilateral deviations but can be socially inefficient, and classic Braess’ paradox shows that adding a physical “shortcut” can increase equilibrium delay. This paper focuses on a different mechanism that is increasingly operational in AI-mediated mobility: endogenous information created by memory. In practice, travelers (and navigation assistants that mediate their choices) do not optimize over a fixed, fully known set of routes. They act on a small, evolving subset shaped by experience, attention, and explicit memory-management policies. In modern AI systems, memory is a first-class design variable governed by retention budgets and eviction policies (FIFO/LRU/priority-decay/summary-based retention) that trade off utility, compute, and privacy.
1.1
Running example: calibrated forgetting as a Pigouvian correction
The following two-link instance illustrates both the opportunity and the conceptual novelty. Consider a single OD pair with total demand d = 1 and two parallel routes: route a has constant latency ℓa (x) ≡ 1 and route b has latency ℓb (x) = x. With full recall, the Wardrop equilibrium routes all demand through b (since b is initially shorter), yielding equilibrium social cost SC = 1. The system-optimal split routes half the demand through a and half through b, yielding SC = 3/4. Example 1 (Pigouvian forgetting). Suppose an AI system (or a cognitive limitation) induces calibrated forgetting: an α fraction of the population does not recall route b and therefore uses a. Then xb = 1 − α and the social cost is SC(α) = α · 1 + (1 − α) · (1 − α) = 1 − α + α2 . This is minimized at α⋆ = 1/2 with SC(α⋆ ) = 3/4, exactly matching the system optimum without changing network capacity and without tolls. Example 1 motivates the central mechanism studied in this paper: recall is an endogenous action-set constraint that can act as a non-monetary congestion-control instrument. This mechanism is distinct from (i) physical interventions (Braess), and (ii) exogenous changes in what travelers are told (informational Braess). Here, information is generated and erased dynamically by a memory process coupled to congestion through experience and guidance. 1.2
Problem identification: the endogenous-information externality
Limiting recall restricts a player’s feasible action set, which in congestion games can change equilibrium selection and welfare. The scientific question is therefore not “does more capacity help?” but rather: how does improving recall change equilibrium, and what recall policy should an AI system implement under governance constraints? 1.3
Three core questions
We organize the paper around three targets that, taken together, define a strong AI–game-theory contribution: 1. Well-posedness and stability. Does the coupled flow–memory system admit a unique stationary equilibrium, and do natural day-to-day dynamics converge to it? 2. Recall Braess phenomena. When can improving recall (larger memory budgets or weaker forgetting) worsen equilibrium welfare without changing network capacity? 3. Equilibrium-aware memory design. How can an AI route guidance system choose retention and surfacing policies to reduce congestion externalities subject to governance constraints (privacy, fairness, compute)? 1.4
Contributions and roadmap 1. A fully specified forgetful routing game (Sections 3–7.3). We introduce a stationary mean-field routing model with endogenous recall in which each agent has a finite memory state, receives surfaced alternatives, chooses via a bounded-rational response, and updates memory under an explicit eviction/forgetting policy. 2. Equilibrium concept and existence (Section 8). We define Forgetful Wardrop Equilibrium (FWE) as the fixed point coupling within-period congestion consistency with stationarity of the memory Markov chain, and we prove existence under mild regularity. 3. A convex-potential “design layer” beyond contraction (Section 4.1, especially Section 4.1.3). We introduce a policy-relevant reduced-form equilibrium model in which memory/guidance act through route salience. We show that salience-weighted SUE is the unique minimizer of a strictly convex potential, yielding uniqueness and global algorithmic stability without contraction assumptions. We further give (i) an exact micro-foundation for B = 1 last-choice memory, p and (ii) an explicit LRU→TTL→salience approximation for B > 1 LRU-type memory with a provable log B/B rate under Poissonized requests (Section 9.1). We also quantify the accuracy of the Poissonization device for discrete-time day-to-day departures under diffused route popularity (Lemma 6 and Corollary 6). 4. Implementability and governance constraints (Section 5). We formalize implementability as an inverseequilibrium problem for memory/guidance policies. In the salience model, every interior feasible flow is implementable by an explicit inverse construction, and we give a sharp constrained-implementability theorem under influence budgets. We interpret this as implementability by stationary interface/ranking salience; it is micro-realizable without loss in the B = 1 regime via Corollary 2. We then show that governed salience design reduces to a single-level implementable-flow optimization problem over this constrained set (Theorem 6). On the series-parallel class, we further show that a low-dimensional decomposition-tied salience policy 2
Statement
Layer
Status
Reference
Existence of a stationary Forgetful Wardrop Equilibrium (FWE) Exact equivalence of B = 1 last-choice memory and salience-weighted logit (Operational) realizability of any interior salience vector via surfacing when B = 1 LRU→TTL approximation of recall probabilities (Poissonized requests) Random-menu logit ≈ availability-weighted logit (large menus) Convex potential, uniqueness, and global stability of SW-SUE Full implementability and governed implementability geometry
Micro (Markov) Micro→salience Micro design Micro→TTL TTL→salience Salience Salience design
Exact Exact Exact Approx. (rate) Approx. (rate) Exact Exact
Thm. 12 Thm. 1 Cor. 2 Thm. 15 Prop. 8, Cor. 7 Prop. 1 Thm. 2, Thm. 5
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 an approximation/validation pathway for B > 1.
can implement any interior s–t flow by a linear-time inverse construction (Theorem 7), and local influence budgets become linear-time implementability tests (Corollary 5). We then characterize implementability under fairness/tying constraints (Section 5.3). 5. Recall Braess paradox and a network-class theorem (Sections 10–11). We define a social-cost Recall Braess Paradox and prove: (i) a sharp analytic Pigou instance where calibrated forgetting strictly improves welfare over full recall, and (ii) a network-class theorem showing social-cost RBP can occur on every two-terminal network with at least two distinct s–t paths (the only immunity class is a unique-path network). 6. Equilibrium-aware design with closed-form and network-class results (Section 6). We pose equilibriumaware memory/guidance design as a bilevel optimization problem under governance constraints and provide an implicit-differentiation sensitivity formula enabling gradient-based policy optimization. On parallel networks, we derive a constructive reduction of bounded-influence optimal salience design to a one-dimensional search plus convex subproblems (Section 6.4). On two-terminal series-parallel networks, we show how to evaluate the logit partition function and edge marginals in linear time (Theorem 10), derive an equivalent split-flow convex program with first-order convergence guarantees (Theorem 11 and Proposition 4), and (in the implementability layer) give a constructive inverse design for decomposition-tied salience with linear-time feasibility under local budgets (Theorem 7). Paper organization and reading guide. Part I (Sections 4.1–6) develops the stationary salience design layer, implementability under governance, and equilibrium-aware design algorithms. Part II (Sections 7.3–11) introduces the explicit micro memory model, proves existence/stability results for Forgetful Wardrop Equilibrium, develops the LRU→TTL→salience approximation pipeline, and establishes Recall Braess phenomena. Part III (Sections 12–13) provides experimental evaluation and a discussion of limitations. 1.5
Exact vs. approximate: a layer map
A central objective of this paper is to keep the strongest claims tightly aligned with what is actually proved in each modeling layer. The main mechanism-design contributions (implementability, governed design under constraints, and tractable network-class algorithms) are proved in the stationary salience design layer (Sections 4.1, 5, and 6). The finite-state memory Markov chain model (Sections 7.3–8) serves as a micro-foundation: it is exactly equivalent to the salience model for B = 1 (Theorem 1), and it motivates and validates the salience abstraction for B > 1 via an explicit approximation pipeline (Section 9.1). Table 1 summarizes what is exact, what is approximate, and what is specific to the reduced-form design layer. 1.6
Scope note
This version prioritizes the salience design layer (convex equilibrium structure, implementability, governanceconstrained mechanism design, and tractable network-class theorems) as the main contribution, and treats the finite-state memory Markov model as a micro-foundation and validation tool. The micro model is mathematically complete and yields an exact bridge to salience for B = 1, but its exact computation is combinatorial for large route sets (Section 8); for B > 1 we therefore emphasize approximations and scalable surrogates (Section 9.1). Large-scale empirical evaluation and system implementation details for specific AI memory architectures are important, but are secondary in this working-paper version. 3
2
Related Work
Traffic equilibria, stochastic user equilibrium, and day-to-day dynamics. Non-atomic routing games originate with Wardrop’s user-equilibrium principle [Wardrop, 1952]. Under standard monotonicity/continuity assumptions, Wardrop equilibria admit equivalent variational inequality and convex potential formulations [Beckmann et al., 1956, Dafermos and Sparrow, 1969, Smith, 1979], which underpin much of traffic assignment theory [Sheffi, 1985, Patriksson, 2015]. Stochastic user equilibrium (SUE) and logit-based route choice models are classical tools for capturing dispersed preferences, perception errors, and within-period randomness [Dial, 1971, Ben-Akiva and Lerman, 1985, Sheffi, 1985]. Day-to-day adjustment and learning dynamics have been studied extensively in transportation science; a representative route-swapping family is developed in [Cascetta and Cantarella, 1991]. Congestion games, potential structure, and efficiency loss. Congestion games are canonical potential games [Rosenthal, 1973, Monderer and Shapley, 1996]. In nonatomic routing, the efficiency loss from selfish behavior is formalized by the price of anarchy (PoA), with tight bounds for broad latency classes [Roughgarden and Tardos, 2002, Roughgarden, 2005] and refinements via smoothness/variational techniques [Correa et al., 2004, 2008, Koutsoupias and Papadimitriou, 1999]. We also leverage structural parallels with finite congestion games when discussing policy and governance constraints [Christodoulou and Koutsoupias, 2005]. Braess-type paradoxes and network classes. Braess’s paradox—the possibility that adding capacity worsens equilibrium travel times—was first identified in [Braess, 1968] and popularized in the transportation literature in [Murchland, 1970]. Subsequent work characterized when paradoxes can and cannot occur under different modeling assumptions and network structures [Steinberg and Zangwill, 1983, Pas and Principio, 1997, Dafermos and Nagurney, 1984, Milchtaich, 2006]. Series-parallel structure plays a recurring role in both algorithm design and topology-based characterizations [Duffin, 1965]. Information design, endogenous information, and consideration sets. The informational Braess paradox (IBP) shows that providing additional route information to a subpopulation can worsen overall performance [Acemoglu et al., 2018]. This connects to the broader literature on information design / Bayesian persuasion [Kamenica and Gentzkow, 2011, Bergemann and Morris, 2019, Dughmi, 2017] and to recent algorithmic information-design work specialized to congestion games [Zhou et al., 2022]. Our paper is complementary: we focus on endogenous consideration sets generated by memory and surfacing, rather than belief noise or exogenous information structures. This links to random-attention and consideration-set models [Masatlioglu et al., 2012, Manzini and Mariotti, 2014, Cattaneo et al., 2020], and to rational-inattention foundations for multinomial logit [Matejka and McKay, 2015, Caplin and Dean, 2015]. Caching-based approximations for limited memory. To bridge explicit bounded-memory dynamics to a stationary “salience” design layer, we draw on classical and modern cache approximations for LRU/TTL policies, including asymptotic miss-ratio analysis and characteristic-time approximations [Fagin, 1977, Che et al., 2002, Fricker et al., 2012, Gast and Van Houdt, 2017, Jiang et al., 2018]. Algorithmic governance and constrained influence. Our governance constraints (ratio budgets and tying/affine structure) are motivated by how modern AI systems surface options under auditability and fairness constraints. They are also closely related, mathematically, to exposure-based fairness constraints in ranking and recommender systems [Singh and Joachims, 2018, Biega et al., 2018, Zehlike et al., 2017, Celis et al., 2018]. Finally, we build on recent work that uses AI agents and large language models to study day-to-day route choice and bounded rationality at scale [Wang et al., 2025, Li et al., 2024], and on our own recent work on imperfect recall and cognitive memory architectures [Alqithami, 2025b,a].
3
Preliminaries: Non-Atomic Routing Games
We review the standard non-atomic model; we focus on a single origin–destination pair for clarity and note extensions later. 3.1
Network and flows
Let G = (V, E) be a directed graph with origin s and destination t. Each edge e ∈ E has a latency (travel time) function ℓe : R≥0 → R≥0 that is continuous and nondecreasing. A (simple) s–t path is denoted p ∈ P. A (non-atomic) flow is a 4
P P vector f = (fp )p∈P with fp ≥ 0 and p∈P fp = d, where d > 0 is total demand. Edge loads are xe (f ) = p∋e fp . P Path latency is Lp (f ) = e∈p ℓe (xe (f )). 3.2
Wardrop equilibrium and social optimum
Definition 1 (Wardrop equilibrium). A feasible flow f ⋆ is a Wardrop equilibrium if for every path p with fp⋆ > 0, we have Lp (f ⋆ ) ≤ Lp′ (f ⋆ ) for all p′ ∈ P. The social cost (total latency) is C(f ) =
X
xe (f ) ℓe (xe (f )) =
e∈E
X
fp Lp (f ).
p∈P
A socially optimal flow minimizes C(f ) over feasible flows.
4
Design layer: stationary salience policies
This section introduces the reduced-form stationary salience model that serves as the main design layer of the paper. The model abstracts recall and guidance as multiplicative weights on routes and yields a strictly convex equilibrium characterization. Subsequent sections use this layer to derive implementability tests and equilibrium-aware design algorithms. Later sections connect this design layer back to the explicit micro memory model. 4.1
Stationary salience policies: a convex potential and uniqueness
The explicit memory model of Section 7.3 induces a high-dimensional stochastic process, and establishing global uniqueness/stability of its stationary flow can require strong contraction assumptions (Theorem 13). To obtain sharp equilibrium structure and enable tractable optimization, we introduce a reduced-form stationary salience policy model that represents recall and guidance via deterministic multiplicative weights on routes. This abstraction yields a strictly convex potential, a unique equilibrium, and an explicit inverse mapping from target flows to implementing salience (Section 5). We return to the micro-to-salience connection in Section 9.1. Interpretation. In many AI-mediated choice systems, the user does not literally face a strict feasibility constraint; instead, the system retrieves/surfaces options with different prominence and the user responds stochastically. This motivates modeling memory as route-dependent salience weights that tilt logit choice. 4.1.1
Stationary salience policies
Fix a finite path set Pk for each commodity k. Definition 2 (Stationary salience policy). A stationary salience policy is a collection of strictly positive weights P |P | s = sk,p k∈K, p∈P ∈ R>0k k , k
where sk,p represents the (policy-induced) salience of path p for commodity k. Equivalently, define additive biases ak,p ≜ β1 log sk,p . Given congestion x, the salience-weighted logit choice probability is sk,p exp − βLp (x) Pr(p | k, x; s) = P r∈Pk sk,r exp − βLr (x)
(p ∈ Pk ).
(1)
This coincides with logit choice on utilities −Lp (x) + ak,p . Definition 3 (Salience-weighted stochastic user equilibrium (SW-SUE)). Fix (ℓe )e∈E and a salience policy s. A ⋆ feasible path-flow vector f ⋆ = (fk,p ) is a SW-SUE if for every commodity k and path p ∈ Pk , ⋆ fk,p = dk Pr(p | k, x(f ⋆ ); s),
where x(f ⋆ ) is defined by (44). 5
(2)
SW-SUE is a stochastic user equilibrium with alternative-specific constants. While the strict convexity/potential formulation is well known in logit SUE (it is essentially Beckmann’s potential plus an entropy regularizer), we record it here because it is the technical backbone of our governance and implementability results: once salience is treated as a policy lever, the equilibrium map becomes an explicitly solvable convex program. Crucially, it admits a strictly convex potential characterization, which yields uniqueness and algorithmic stability without requiring a contraction bound on a reduced fixed-point map. 4.1.2
Potential formulation and uniqueness
Define the feasible set F ≜
n o X f ≥0: fk,p = dk ∀k ∈ K . p∈Pk
For a salience policy s, define the objective X Z xe (f ) 1 X X Φs (f ) ≜ ℓe (u) du + fk,p log fk,p − log sk,p , β 0 e∈E
(3)
k∈K p∈Pk
with the convention 0 log 0 = 0. Proposition 1 (Convex program for SW-SUE). Assume β > 0 and each ℓe is continuous and nondecreasing. Then Φs is strictly convex on F and admits a unique minimizer f ⋆ ∈ F. Moreover, f ⋆ is the unique SW-SUE in Definition 3. Proof idea. Write the SW-SUE fixed point as the first-order optimality conditions of the Beckmann potential augmented with an entropic regularizer shifted by log s. The entropy term makes the objective strictly convex over F, yielding existence and uniqueness; the KKT conditions recover the salience-weighted logit form. Full proof is deferred to Appendix A.6. 4.1.3
Micro-foundation: last-choice memory yields stationary salience
The salience abstraction in (1) can be given an exact micro-foundation as a special case of the dynamic recall model in Section 7.3. This strengthens the interpretation of sk,p as an endogenous information mechanism rather than an ad hoc reduced form. B=1 last-choice memory with surfacing. Fix a commodity k and suppose the memory budget is Bk = 1. The memory state is simply the last chosen route m ∈ Pk . Each period, a candidate route q ∼ ρk is surfaced, and the traveler chooses from {m, q} using the logit rule (42) (with costs evaluated at a fixed congestion vector x). After choosing a route p, memory updates deterministically to m+ = p. For fixed congestion x, this induces a Markov chain on Pk with transition probabilities X exp − βLp′ (x) 1{p′ ∈ {p, q}} (k) ′ . Px (p | p) = ρk (q) exp − βLp (x) + exp − βLq (x) q∈P
(4)
k
(When q = p, the denominator is 2 exp(−βLp (x)) and the chain stays at p.) Theorem 1 (Exact reduction: stationary last-choice memory induces salience-weighted logit). Fix k and a congestion vector x. Assume ρk has full support and β > 0. Then the Markov chain (4) is irreducible and aperiodic, and it is reversible with unique stationary distribution ρk (p) exp − βLp (x) . πk,x (p) = P (5) r∈Pk ρk (r) exp − βLr (x) Moreover, in stationarity the marginal probability of choosing route p in a period equals πk,x (p). Equivalently, the stationary choice rule is exactly the salience-weighted logit (1) with salience weights sk,p ∝ ρk (p). Proof. Irreducibility follows from full support of ρk and the fact that from any current route p the candidate q = p′ occurs with positive probability and is chosen with positive probability under logit. Aperiodicity holds because (k) Px (p | p) > 0 for all p (take q = p). 6
To show reversibility, define π̃(p) ∝ ρk (p)e−βLp (x) . For distinct p ̸= p′ , the only way to move from p to p′ in one step is that the surfaced candidate equals p′ and the logit chooses p′ . Thus Px(k) (p′ | p) = ρk (p′ )
e−βLp′ (x) . e−βLp (x) + e−βLp′ (x)
Hence, for p ̸= p′ , e−βLp′ (x) = π̃(p′ ) Px(k) (p | p′ ), π̃(p) Px(k) (p′ | p) = ρk (p)e−βLp (x) · ρk (p′ ) −βL (x) p e + e−βLp′ (x) so detailed balance holds. Therefore πk,x in (5) is stationary; uniqueness follows from irreducibility. Finally, when the process is stationary, the next-period memory state equals the chosen route, so the stationary distribution of memory coincides with the stationary distribution of choices, yielding the claim. Corollary 1 (Coupled routing equilibrium equals SW-SUE for Bk = 1). Consider the non-atomic routing game with last-choice memory (Bk = 1 for all k) and surfacing distributions {ρk }. If the induced equilibrium exists, then its flow component is exactly a SW-SUE with salience weights sk,p ∝ ρk (p). In particular, uniqueness and algorithmic stability follow from Proposition 1. Proof idea. By Theorem 1, in the Bk = 1 micro model the stationary per-period choice probabilities equal a salienceweighted logit with weights sk,p ∝ ρk (p). Substituting these probabilities into the non-atomic flow definition yields exactly the SW-SUE fixed point, and uniqueness follows from strict convexity of the SW-SUE potential. Full proof is deferred to Appendix A.12. Corollary 2 (Operational realizability of salience via surfacing when Bk = 1). Fix any collection of strictly positive salience weights {sk,p }k∈K, p∈Pk . Define, for each commodity k, a surfacing distribution ρk (p) ≜ P
sk,p
r∈Pk sk,r
.
Consider the Bk = 1 last-choice memory micro model with these surfacing distributions. Then the induced stationary within-period choice probabilities coincide exactly with the salience-weighted logit model with salience s, and the induced network equilibrium flow is the unique SW-SUE for s. Consequently, in the Bk = 1 regime, any interior flow implementable by stationary salience (Theorem 2) is also implementable by an explicit micro policy (choice of ρ). Proof idea. Theorem 1 shows that for Bk = 1 the stationary choice law is salience-weighted logit with salience proportional to the surfacing distribution: sk,p ∝ ρk (p). Since salience is defined only up to a per-commodity multiplicative constant, choosing ρk proportional to a target sk realizes that target exactly. The equilibrium statement then follows from Corollary 1. Full proof is deferred to Appendix A.13. Remark 1. Theorem 1 provides an explicit bridge between the micro memory kernel and the salience mechanism. Richer memory states (Bk > 1, LRU lists, summary-based retention) expand the policy space beyond pure surfacing weights; however, the Bk = 1 case already shows that a simple AI “suggestion layer” can induce an equilibrium that is exactly the optimizer of a strictly convex potential. This is the key technical reason salience policies provide a strong design handle beyond contraction.
5
Implementability: inverse equilibrium and memory-as-control
The stationary salience layer (Section 4.1) yields a unique equilibrium for every choice of salience policy s. This raises an inverse question that is central for design: given a target equilibrium behavior, when is it implementable by some salience policy, and how much “influence” is required? This section provides (i) an explicit inverse mapping from interior target flows to salience parameters, (ii) sharp feasibility tests under influence budgets and tying/fairness constraints, and (iii) a “governed” implementability characterization that will underwrite the single-level design reductions in Section 6. 7
5.1
Full implementability under salience policies
We now show that the stationary salience model in Section 4.1 yields an explicit and very strong implementability guarantee. Comment on novelty. The unconstrained “full implementability” statement below is, in hindsight, an explicit inversion of the salience-weighted logit equilibrium conditions. Its value in this paper is as a building block: it (i) cleanly separates what is a property of the reduced-form salience layer from what is micro-founded, and (ii) becomes nontrivial once we impose governance constraints (ratio budgets, tying/fairness, feature constraints) and seek tractable network-class design algorithms. Theorem 2 (Full implementability of interior flows under salience). Consider a fixed network with continuous nondecreasing latencies and a fixed β > 0. Let f¯ ∈ F be an interior feasible flow, i.e., f¯k,p > 0 for all k and all p ∈ Pk . Define salience weights by sk,p ≜ f¯k,p exp β Lp x(f¯) . (6) Then f¯ is the unique SW-SUE (Definition 3) induced by s. In particular, every interior feasible flow is implementable by stationary salience policies. Proof. Let s be defined by (6). Then sk,p exp − βLp (x(f¯)) = f¯k,p . P P ¯ Summing over p ∈ Pk yields p sk,p e−βLp (x(f )) = p f¯k,p = dk . Substituting into (1) gives dk Pr(p | k, x(f¯); s) = dk
f¯k,p = f¯k,p , dk
so f¯ satisfies the SW-SUE fixed point (2). Uniqueness follows from Proposition 1. Corollary 3 (Implementing the system optimum without tolls). If the system-optimal flow f SO is interior, then it is implementable by a stationary salience policy via (6). If f SO is not interior, it is ε-implementable for any ε > 0 by perturbing f SO to an interior flow and applying Theorem 2. Proof idea. If f SO is interior, apply Theorem 2 directly. If not, perturb f SO to an interior flow within ε; implementability of the perturbed flow and continuity of costs yield ε-implementability of f SO . Full proof is deferred to Appendix A.27.
5.2
Constrained implementability under influence budgets and governance
Theorem 2 is intentionally strong: unconstrained salience can implement any interior flow. Top-tier AI/game-theory settings, however, often impose governance constraints on how strongly an AI system may bias or rank alternatives. We formalize this via influence budgets and derive sharp implementability characterizations. Scale invariance and influence budgets. Only relative salience matters: for a fixed commodity k, replacing sk,p by ck sk,p for any constant ck > 0 leaves (1) unchanged. Accordingly, a natural constraint is a bound on within-commodity salience ratios. Definition 4 (Influence budget (bounded salience ratios)). Fix Rk ≥ 1 for each commodity k. A salience vector s satisfies the influence budget if sk,p max ≤ Rk for all k ∈ K. (7) p,r∈Pk sk,r Equivalently, maxp log sk,p − minp log sk,p ≤ log Rk . Theorem 3 (Exact constrained implementability under ratio budgets). Fix β > 0 and continuous nondecreasing latencies. Let f¯ ∈ F be an interior feasible flow. Define the required log-salience up to scale by ak,p (f¯) ≜ log f¯k,p + β Lp x(f¯) , k ∈ K, p ∈ Pk . (8) Then f¯ is implementable by stationary salience policies satisfying the influence budgets (7) if and only if max ak,p (f¯) − min ak,p (f¯) ≤ log Rk for all k ∈ K. p∈Pk
p∈Pk
Moreover, the minimal required budget for commodity k is Rkmin (f¯) = exp maxp ak,p (f¯) − minp ak,p (f¯) . 8
(9)
Proof. (If.) Suppose (9) holds. Set sk,p ≜ exp(ak,p (f¯)). Then sk,p ∝ f¯k,p exp(βLp (x(f¯))), so by the same calculation as in Theorem 2, f¯ is the unique SW-SUE induced by s. Finally, log sk,p = ak,p (f¯), so the ratio bound follows directly from (9). (Only if.) If f¯ is implementable by some s satisfying (7), then at equilibrium f¯k,p ∝ sk,p exp(−βLp (x(f¯))), i.e., log sk,p = log f¯k,p + βLp (x(f¯)) + ck for some constant ck (normalization) depending on k only. Thus the range of log sk,p over p equals the range of ak,p (f¯), so (7) implies (9). Remark 2 (Menu-size and fairness constraints). Beyond ratio budgets, governance may constrain the menu size (how many routes can be surfaced) or impose fairness (e.g., salience cannot depend on protected attributes). In the stationary ⋆ salience model, imposing sk,p = 0 forces fk,p = 0. Thus menu-size constraints translate into sparsity constraints on s (bounded support), and fairness constraints translate into tying parameters across groups/commodities. Theorem 3 isolates a first-order, scale-invariant “influence” constraint that already yields nontrivial implementability geometry. 5.3
Implementability under tying and fairness constraints
Influence budgets (Definition 4) constrain how much an AI system can tilt attention. A different and equally important class of governance constraints restricts which distinctions the system is allowed to encode. In particular, many fairness and compliance regimes require the guidance policy to be group-blind (or to satisfy bounded disparity) with respect to protected attributes, which naturally induces parameter tying across subpopulations. We formalize such constraints as affine restrictions on log-salience. Let uk,p ≜ log sk,p and stack these into a vector P u ∈ R k |Pk | . A broad class of constrained salience policies can be written as u ∈ U ≜ {Aθ + b : θ ∈ Rd },
(10)
where A encodes tying or feature-based parameterization and b is a fixed offset. Examples include: (i) group-blind policies that force uk,p to be identical across protected groups k that share the same route p; (ii) feature-based policies uk,p = θ⊤ ϕk,p (shared θ) that only depend on approved route features ϕk,p . Because salience is scale-invariant within each commodity, we also allow commodity-specific intercepts. Let C ≜ {c ∈ R
P
k |Pk |
: ck,p = ck for each k and all p ∈ Pk }.
(11)
Theorem 4 (Exact implementability under affine tying constraints). Fix β > 0 and continuous nondecreasing latencies, and let f¯ ∈ F be interior. Define the required log-salience vector (up to scale) by a(f¯)k,p ≜ log f¯k,p + β Lp x(f¯) . Then f¯ is implementable by stationary salience policies with log-salience u ∈ U if and only if a(f¯) ∈ U + C. Equivalently, there exist θ ∈ Rd and intercepts {ck } such that for all k and p ∈ Pk , (Aθ + b)k,p + ck = log f¯k,p + β Lp x(f¯) .
(12)
(13)
Proof. At any SW-SUE induced by u = log s, the fixed point implies f¯k,p ∝ exp(uk,p ) exp(−βLp (x(f¯))) , i.e., uk,p = log f¯k,p + βLp (x(f¯)) + ck for some commodity-specific constants ck . Thus f¯ is implementable with u ∈ U if and only if a(f¯) = u − c for some u ∈ U and c ∈ C, i.e. a(f¯) ∈ U + C. Corollary 4 (Group-blind salience forces identical route shares). Suppose commodities k correspond to protected groups that share the same feasible route set P and face the same latencies. If the fairness constraint enforces group-blind salience, i.e. uk,p = uk′ ,p for all groups k, k ′ and all p ∈ P, then at any SW-SUE all groups induce the same route-share vector: fk,p fk′ ,p = for all k, k ′ , p ∈ P. dk dk′ Consequently, any target flow that assigns different route shares across groups is not implementable under group-blind salience. 9
Proof idea. With identical costs and group-blind salience, each group faces the same salience-weighted logit rule at the same congestion, so their route-choice distributions coincide. Since each group’s flow is its demand times this common distribution, all groups induce identical route shares. Full proof is deferred to Appendix A.24. Remark 3 (Approximate implementability and projection). When (12) fails, a natural “best-effort” policy solves the convex regression problem min ∥Aθ + b + c − a(f¯)∥2 , θ,c∈C
or, more structurally, minimizes the equilibrium social cost over the constrained policy class U using the sensitivity tools in Section 6. This yields a quantitative distance to implementability under governance constraints, and highlights when fairness restrictions make certain welfare targets infeasible. Remark 4 (What is “salience” in a memory system?). In an AI memory architecture, sk,p can be interpreted as a stationary retrieval intensity for route p (how often it is surfaced or made salient in the user’s context) or, more broadly, as an alternative-specific bias induced by ranking, summarization, and retrieval. Theorem 2 shows that, at least at the level of a stationary abstraction, memory can act as a full-fledged mechanism-design primitive. 5.4
Putting it together: governed implementability (tying and influence budgets)
In many deployments, governance combines both intensity limits (influence budgets) and structure limits (fairness/tying). Theorem 3 and Theorem 4 compose cleanly into a single geometric characterization. For convenience, define the per-commodity range operator rangek (v) ≜ max vk,p − min vk,p , p∈Pk
p∈Pk
and the governed set of admissible log-salience vectors (up to commodity-wise scale) n o G(U , R) ≜ u ∈ U + C : rangek (u) ≤ log Rk ∀k ∈ K .
(14)
Theorem 5 (Governed implementability under affine tying and ratio budgets). Fix β > 0 and continuous nondecreasing latencies. Let U = {Aθ + b : θ ∈ Rd } encode the policy’s allowed log-salience structure, and let R = {Rk }k∈K encode per-commodity influence budgets. For any interior feasible flow f¯ ∈ F, define a(f¯)k,p ≜ log f¯k,p + β Lp (x(f¯)). Then f¯ is implementable by a stationary salience policy that satisfies both (i) the tying constraint u ∈ U and (ii) the ratio budgets (7) if and only if a(f¯) ∈ G(U, R). (15) Proof. By Theorem 4, f¯ is implementable under tying if and only if a(f¯) ∈ U + C. By Theorem 3, f¯ is implementable under ratio budgets if and only if rangek (a(f¯)) ≤ log Rk for all k. Because adding commodity-wise intercepts does not change ranges, the two constraints are compatible and their conjunction is exactly (15). Theorem 6 (Governed salience mechanism design reduces to implementable-flow optimization). Consider the governed salience design problem min SC f ⋆ (u) , (16) u∈G(U ,R)
where u = log s is the log-salience vector, G(U , R) is the governed feasible set (14), and f ⋆ (u) is the (unique) SW-SUE induced by u (Proposition 1). Assume equilibria are interior (f ⋆ (u) ∈ F ◦ ) for all feasible u. Then (16) is equivalent to the single-level program min SC(f )
f ∈F ◦
s.t.
a(f ) ∈ G(U, R),
(17)
and any optimizer f ⋆ of (17) can be implemented by some u⋆ ∈ G(U, R) via the inverse formula (6) (up to commoditywise intercepts). Proof. If u ∈ G(U, R) is feasible in (16), then f ⋆ (u) is implementable under the same governance constraints. By Theorem 5, this implies a(f ⋆ (u)) ∈ G(U , R), so f ⋆ (u) is feasible for (17). Conversely, if f ∈ F ◦ satisfies a(f ) ∈ G(U , R), then again by Theorem 5 it is implementable by some governed log-salience u ∈ G(U, R). Because the SW-SUE induced by a fixed u is unique (Proposition 1), the induced equilibrium must equal f . Therefore the feasible objective values of (16) and (17) coincide, and the constructions above map optimizers to optimizers. Remark 5 (Geometry vs. tractability). Theorem 6 separates (i) network physics, via Lp (x(f )), from (ii) governance geometry, via G(U , R). On general networks, (17) remains nonconvex because of the log f term and the nonlinear dependence of L on f ; however, on certain network classes it becomes tractable (Section 6.4). 10
5.5
A network-class theorem: series-parallel implementability under decomposition-tied salience
The full implementability result (Theorem 2) treats the log-salience vector u = log s as fully flexible at the path level. In many networks, however, the number of s–t paths is enormous, and governance may prefer a structured control surface. On the two-terminal series-parallel (SP) class, the network itself provides a natural low-dimensional parameterization: local biases at parallel composition nodes. Decomposition-tied salience. Fix a single commodity (one OD pair) on a two-terminal SP network with an SP decomposition tree T . Each internal node of T is either a series composition (⊗) or a parallel composition (⊕) of two subgraphs. For each parallel node v ∈ T with children (vL , vR ), introduce a relative log-salience parameter δv ∈ R that biases the left child vs. the right child. Operationally, δv is a “branch-level” salience signal: how strongly the platform steers users into the left subnetwork relative to the right at that decision point. Formally, under decomposition-tied salience, the unnormalized logit weight of any s–t path p is X exp − βLp (x) · exp δv , v∈V⊕ (p)
where V⊕ (p) is the set of parallel nodes at which p takes the left branch. Equivalently, each parallel node contributes a multiplicative factor eδv to all paths that go left at that node, and a factor 1 to all paths that go right. (Only the relative bias matters; adding a constant to both branches at a node cancels in normalization.) Inclusive values on an SP tree. For any edge-flow vector x and any set of {δv }, define the (log) inclusive value of a subgraph H in the SP tree by X X VH (x, δ) ≜ log exp − βLp (x) · exp δv , p∈P(H)
v∈V⊕ (p)
where P(H) denotes the s–t paths within subgraph H. The inclusive values satisfy the standard SP recursion: for a leaf edge e, Ve = −βℓe (xe ); for a series node H = H1 ⊗ H2 , VH = VH1 + VH2 ; and for a parallel node H = HL ⊕ HR with relative bias δH on the left branch, VH = log eδH +VHL + eVHR . (18) Theorem 7 (Constructive implementability on series-parallel networks under decomposition-tied salience). Fix β > 0 and a single-commodity two-terminal SP network with decomposition tree T . Let x̄ be any strictly interior feasible s–t edge flow, meaning that at every parallel node H = HL ⊕ HR in T , the induced branch flows d¯HL , d¯HR satisfy d¯HL > 0 and d¯HR > 0. Then there exists a vector of branch-bias parameters δ = {δH } such that x̄ is the unique SW-SUE edge flow induced by decomposition-tied salience δ. Moreover, δ can be computed in O(|E|) time by a single bottom-up pass on T via the local inverse formula d¯H δH = log ¯ L − VHL (x̄, δ) − VHR (x̄, δ) , for each parallel node H. (19) dHR Proof. Fix an interior feasible target flow x̄. Because the network is two-terminal SP with decomposition tree T , x̄ induces a well-defined subgraph demand d¯H for every subgraph node H ∈ T : at the root, d¯root = d; at a series node H = H1 ⊗ H2 , we have d¯H1 = d¯H2 = d¯H ; and at a parallel node H = HL ⊕ HR , feasibility implies a flow split d¯H = d¯HL + d¯HR with d¯HL , d¯HR > 0 by the interior assumption. We compute (δ, V ) bottom-up on T as follows. For a leaf edge e, set Ve = −βℓe (x̄e ). For a series node H = H1 ⊗ H2 , set VH = VH1 + VH2 . For a parallel node H = HL ⊕ HR , first assume VHL , VHR have been computed; then set d¯H δH = log ¯ L − VHL − VHR , dHR
VH = log eδH +VHL + eVHR .
This is exactly (19) and (18). The computation visits each tree node once and is therefore O(|E|). P Now define the induced salience weights on s–t paths by sp ≜ exp v∈V⊕ (p) δv . Consider the logit path-flow induced by (x̄, s): sp exp(−βLp (x̄)) f¯p ≜ d · P . (20) q∈P sq exp(−βLq (x̄)) 11
We claim that the resulting edge flow satisfies x(f¯) = x̄. To show this, it is convenient to work recursively on T . For any subgraph node H ∈ T , let P(H) denote its internal s–t paths and define the conditional logit distribution within H by P exp(−βLp (x̄)) exp( v∈V⊕ (p) δv ) q̄H (p) ≜ , p ∈ P(H), exp(VH ) where VH is the inclusive value computed above. By construction, q̄H is a probability distribution on P(H). We prove by induction on H that q̄H routes exactly the target subflow d¯H through subgraph H: for every leaf edge e in the subtree of H, the induced edge flow equals x̄e . The base case is a leaf edge: P(e) contains a single path and thus all flow d¯e traverses e, matching x̄e . For a series node H = H1 ⊗ H2 , every path in H is a concatenation p = p1 ⊗ p2 with pi ∈ P(Hi ). Because costs add and biases in the two subtrees are disjoint, we have P
q̄H (p1 ⊗ p2 ) =
e−β(Lp1 +Lp2 ) e( δ in H1 )+( eVH1 +VH2
P
δ in H2 )
= q̄H1 (p1 ) q̄H2 (p2 ),
i.e., the conditional distribution factorizes. Since the total flow through each child equals d¯H in a series composition, the induction hypothesis implies the induced edge flows within each child match x̄ restricted to that child. For a parallel node H = HL ⊕ HR , every path is either in the left child or the right child. Summing the unnormalized weights over P(HL ) and P(HR ) gives eδH +VHL eVHR , Pr{choose HR } = δH +VH . V V H q̄H q̄H L + e HR e +e R e By the inverse choice of δH , we have eδH +VHL −VHR = d¯HL /d¯HR , hence Prq̄H {HL } = d¯HL /(d¯HL + d¯HR ). Multiplying by the parent flow d¯H = d¯HL + d¯HR yields exactly the target branch flows d¯HL and d¯HR . Conditioned on choosing HL (resp. HR ), the distribution within that child is exactly q̄HL (resp. q̄HR ), so the induction hypothesis ensures the internal edge flows match x̄ on each side. This completes the induction. Applying the induction to the root node shows that the full path flow (20) induces x(f¯) = x̄. But (20) is exactly the SW-SUE fixed-point condition (2) at x = x̄ with salience weights s. Therefore x̄ is an SW-SUE edge flow under decomposition-tied salience. Uniqueness follows from strict convexity of the SW-SUE potential (Proposition 1). Pr{choose HL } =
δH +VHL
Corollary 5 (Governance as local budget constraints on SP trees). Suppose governance restricts branch-level influence at each parallel node H to a ratio budget RH ≥ 1, i.e. |δH | ≤ log RH . Then an interior target flow x̄ is implementable under these budgets if and only if its induced branch splits satisfy the local inequalities d¯H log ¯ L − VHL (x̄, δ) − VHR (x̄, δ) ≤ log RH d HR
for all parallel nodes H,
where δ is the recursively defined inverse-bias vector from (19). Consequently, implementability testing under per-node budgets is linear-time in |E| on SP networks. Proof idea. The SP implementability theorem expresses the required bias δH at each parallel node as the log ratio between target split masses corrected by downstream soft-values. Imposing |δH | ≤ log RH is therefore equivalent to a pair of local inequalities. Conversely, if the inequalities hold, choosing admissible δH and reconstructing edge-additive salience implements the target flow. Full proof is deferred to Appendix A.25. Remark 6 (Why this is useful). Theorem 7 identifies a network class on which implementability is both constructive and low-dimensional: the control variables live at parallel splits rather than at the path level. This matches UI-level intervention points (“take the highway vs. the arterial”), and it yields a direct bridge to algorithmic design: one can optimize over SP-tree split patterns subject to local budget constraints without enumerating an exponential path set. Section 6 returns to richer policy classes (explicit memory kernels and surfacing distributions) and to equilibrium-aware optimization under governance constraints.
6
Equilibrium-Aware Memory and Guidance Design
Sections 4.1 and 5 provide (i) a strictly convex equilibrium characterization for SW-SUE under stationary salience policies and (ii) sharp implementability and governance constraints. We now formulate and solve equilibrium-aware 12
design problems: choose a policy within a governance class (influence budgets, tying/fairness, or both) to optimize welfare at the induced equilibrium. The main technical theme is that strict convexity enables efficient single-level reductions and first-order methods (including implicit differentiation of the equilibrium map). Later we return to the explicit memory model and quantify when micro-level interventions can be accurately proxied by salience designs. 6.1
Policy parameterization
Let θ ∈ Θ parameterize a class of policies. A policy may control, for each commodity k: • a surfacing distribution ρk,θ over candidate routes (which routes are suggested or explored), and • a memory update rule (eviction/forgetting) Uk,θ or, more generally, a memory kernel Qk,θ (m′ | m, p) that may include resets, summarization, or privacy-driven deletion. This mirrors real AI memory architectures in which the system selects what to store, what to summarize, and what to discard under explicit budgets and governance constraints. Given θ, the induced FWE (when unique) is (x⋆ (θ), µ⋆ (θ)). 6.2
Bilevel optimization objective
We consider an equilibrium-aware objective of the form min θ∈Θ
SC(x⋆ (θ)) | {z }
equilibrium congestion
+λ
Cost(θ) | {z }
Fair(θ) ≤ 0 | {z }
s.t.
compute / privacy / UX
.
(21)
fairness / individual harm constraints
Here Cost(θ) can encode, e.g., expected memory usage, summarization overhead, or a privacy-risk proxy; and Fair(θ) can enforce constraints such as “no user type is made worse off by the policy” or “bounded disparity across groups.” 6.3
A closed-form optimal design on a canonical network class
To emphasize that the “memory as mechanism” perspective yields analytically tractable design problems (not only numerical bilevel programs), we give a closed-form optimal salience result on the canonical Pigou network. This provides a baseline for more complex network classes. Pigou instance. Consider a single OD pair (d = 1) with two parallel routes a and b. Route a has constant latency ℓa (x) = 1 and route b has latency ℓb (x) = x. Let β > 0 and consider stationary salience policies with weights (sa , sb ); only the ratio r ≜ sb /sa matters. Under SW-SUE, the equilibrium flow on route b is a scalar fb ∈ (0, 1) satisfying fb =
r exp(−βfb ) exp(−β) + r exp(−βfb )
⇐⇒
r=
fb exp β(fb − 1) . 1 − fb
(22)
The equilibrium social cost is
SC(fb ) = (1 − fb ) · 1 + fb2 = 1 − fb + fb2 , (23) SO which is uniquely minimized at the system-optimal split fb = 1/2. Theorem 8 (Optimal bounded-influence salience on the Pigou network). Fix β > 0 and an influence budget R ≥ 1 so that r ∈ [1/R, R]. Then: fb 1. The mapping fb 7→ r(fb ) = 1−f exp(β(fb − 1)) is strictly increasing on (0, 1). Hence for each r > 0 there b is a unique equilibrium fb (r) ∈ (0, 1).
2. Let fmin ≜ fb (1/R) and fmax ≜ fb (R). The social-cost-minimizing feasible equilibrium split is n o fb⋆ = clip 12 ; fmin , fmax ≜ min max 21 , fmin , fmax ,
(24)
and the optimal salience ratio is r⋆ = r(fb⋆ ). 3. The system optimum fbSO = 12 is exactly implementable under budget R if and only if R ≥ exp(β/2) (equivalently, 1/R ≤ exp(−β/2)), in which case an optimal ratio is r⋆ = exp(−β/2). 13
Proof. (1) Differentiate log r(fb ) = log fb − log(1 − fb ) + β(fb − 1), giving 1 1 d log r(fb ) = + + β > 0, dfb fb 1 − fb so r(fb ) is strictly increasing. (2) Because fb (r) is increasing in r by (1), the feasible equilibria correspond to fb ∈ [fmin , fmax ]. Since SC(fb ) in (23) is convex with unique minimizer 1/2, the constrained minimizer over the interval is the projection (clipping) of 1/2 onto that interval, yielding (24). (3) Plugging fb = 1/2 into (22) yields the unique ratio rSO = exp(−β/2). Feasibility under r ∈ [1/R, R] requires 1/R ≤ rSO ≤ R, and since rSO ≤ 1, this reduces to R ≥ exp(β/2). Remark 7. Theorem 8 makes explicit how a governance knob (influence budget R) controls how closely a saliencebased memory/guidance layer can approximate the system optimum. In richer networks, the same logic applies but without closed-form inversion; the strict convexity of Φs (Proposition 1) still yields a well-posed inner problem, and Theorem 3 provides a tractable feasibility test for exact implementation of a candidate target flow. 6.4
Parallel networks: bounded-influence design beyond Pigou
The Pigou network (two parallel routes) admits a closed-form inversion (Theorem 8). We now extend this to a broader network class: a single OD pair with m ≥ 2 parallel routes, each with its own latency function. This is a natural next step because parallel networks isolate the essence of “shortcut” competition without path-overlap complications, and because many real mobility decisions (e.g., highway vs. arterial) are well-approximated by a small set of parallel alternatives. Model. Consider m parallel routesP indexed by i ∈ {1, . . . , m} with demand normalized to 1. Let fi ∈ (0, 1) denote the equilibrium flow on route i, so i fi = 1, and latency is ℓi (fi ) (continuous, nondecreasing). Fix β > 0 and a salience ratio budget R ≥ 1 so that ui = log si satisfies maxi ui − mini ui ≤ log R. Define the strictly increasing transform gi (z) ≜ log z + β ℓi (z), z ∈ (0, 1). (25) ′ ′ (Strict monotonicity follows because gi (z) = 1/z + β ℓi (z) > 0 whenever ℓi is differentiable, and holds more generally in the sense of monotone derivatives for continuous nondecreasing ℓi .) m Proposition 2 (Implementable equilibria on parallel networks under ratio budgets). An interior flow vector f ∈ (0, 1) P with i fi = 1 is implementable as the SW-SUE induced by some salience weights s satisfying the ratio budget R if and only if max gi (fi ) − min gi (fi ) ≤ log R. (26) i
i
Moreover, whenever (26) holds, one feasible implementing policy is si ∝ fi exp β ℓi (fi ) ,
(27)
with the proportionality constant chosen so that maxi log si − mini log si ≤ log R (which is possible exactly when (26) holds). Proof. This is Theorem 3 specialized to a single commodity with parallel routes. The required log-salience up to scale is ai (f ) = log fi + βℓi (fi ) = gi (fi ). The ratio budget requires the range of ai (f ) to be at most log R, which is (26). The inverse construction (27) follows from (6). A constructive reduction of optimal design to one-dimensional search. m X SC(f ) = fi ℓi (fi ).
The social cost on a parallel network is
i=1
Under very mild conditions (e.g., each ℓi nondecreasing), SC is continuous; if each ℓi is convex, then SC is convex in f . By Proposition 2, bounded-influence salience design on a parallel network reduces to m X min m SC(f ) s.t. fi = 1, max gi (fi ) − min gi (fi ) ≤ log R. f ∈(0,1)
i
i=1
i
While (28) is not obviously convex in full generality, it admits a useful structural decomposition. 14
(28)
Theorem 9 (One-dimensional reduction for bounded-influence optimal design on parallel networks). Assume each gi in (25) is strictly increasing (equivalently, each ℓi is continuous and nondecreasing, with mild regularity). Then the constraint (26) holds if and only if there exists a scalar t ∈ R such that for all i, t ≤ gi (fi ) ≤ t + log R.
(29)
For any fixed t, define bounds f i (t) ≜ gi−1 (t + log R),
f i (t) ≜ gi−1 (t),
(30)
and consider the inner problem V (t) ≜ minm SC(f ) f ∈R
s.t.
X
fi = 1,
f i (t) ≤ fi ≤ f i (t) ∀i.
(31)
i
Then the optimal value of (28) equals mint V (t), and any minimizer f ⋆ of (28) is obtained by solving (31) at some t⋆ ∈ arg mint V (t). If, in addition, each ℓi is convex, then for every fixed t the inner problem (31) is a convex program with a unique minimizer. Proof. The band representation (29) is equivalent to the range condition (26) by taking t = mini gi (fi ). Because each gi is strictly increasing, (29) is equivalent to the interval constraints f i (t) ≤ fi ≤ f i (t), yielding (31). Taking the minimum over t recovers (28). When ℓi is convex, the function fi 7→ fi ℓi (fi ) is convex, hence SC(f ) is convex, and the feasible set in (31) is a polytope (simplex with box constraints), so (31) is convex. Strict convexity (e.g., if at least one ℓi is strictly convex on the relevant interval) yields uniqueness. Proposition 3 (Optimality characterization on the parallel network class: clipped marginal-cost equalization). Assume each latency ℓi is continuously differentiable and convex. Fix any band parameter t for which the inner problem (31) is feasible, and let f ⋆ (t) be its (unique) minimizer. Then there exists a scalar λ(t) ∈ R such that, for every route i, ⋆ = λ(t), if f i (t) < fi (t) < f i (t), ⋆ (32) mi fi (t) ≥ λ(t), if fi⋆ (t) = f i (t), ⋆ ≤ λ(t), if fi (t) = f i (t), where mi (z) ≜ ℓi (z) + z ℓ′i (z) denotes the marginal social cost on route i. Consequently, any globally optimal solution of the bounded-influence design problem (28) equalizes marginal social costs across all non-saturated routes, and “clips” this equalization only when forced by the salience band constraint (29). Proof. For fixed t, the inner problem (31) is a convex program on a simplex P with box constraints. The KKT conditions yield the existence of a Lagrange multiplier λ(t) for the equality constraint i fi = 1 and nonnegative multipliers for the box constraints; these imply (32) by complementary slackness. Remark 8 (Algorithmic implication). Theorem 9 reduces bounded-influence optimal salience design on a parallel network to a one-dimensional outer search in t plus an efficiently solvable inner convex program (31). Once an optimal f ⋆ is computed, an implementing salience policy follows from (27). This provides a concrete “network-class design theorem” beyond Pigou: the optimal guidance/memory policy can be computed with provable guarantees for all parallel networks, not just for the two-link instance. Remark 9 (Extending the network-class theorem to affine tying). Theorem 9 gives an exact and computationally efficient characterization for unconstrained salience vectors under a pure ratio budget. If the policy class further imposes affine tying u = Aθ + b (Section 5.4), then implementability on a parallel network becomes the feasibility of gi (fi ) = ui + c
for some
u ∈ U, c ∈ R,
together with
max ui − min ui ≤ log R. i
i
This adds linear structure to the band (29). When the feature dimension d is small, optimal governed design can still be solved by low-dimensional outer search in (t, θ) with a convex inner problem in f (a box-constrained simplex program as in (31) plus linear equalities induced by A). We leave the full algorithmic development (and extensions beyond parallel networks) to future work. 15
6.5
Series-parallel networks: fast equilibrium evaluation and gradients without path enumeration
The parallel-network class admits a particularly sharp characterization because each route’s latency depends only on its own flow. We can go beyond parallel networks by exploiting structural decomposability of the path set. A prominent example is the two-terminal series-parallel (SP) class, which admits an SP-tree decomposition and supports dynamic-programming evaluation of logit path distributions. Edge-additive salience (feature tying). To avoid explicit path-level salience vectors on exponentially many paths, we consider a policy class in which log-salience is edge-additive: there exists a vector u = (ue )e∈E such that X log sp = ue . (33) e∈p
This is a natural tying constraint: the platform attaches persistent salience biases to links (or to low-dimensional route features that sum along a route), which is typical of ranking and guidance systems. Under (33), the salience-weighted logit distribution over paths can be written in terms of generalized edge costs ue , β
ce (x, u) ≜ ℓe (xe ) − since
X sp exp(−βLp (x)) = exp − β ce (x, u) . e∈p
A Gibbs distribution over s–t paths and its partition function. For fixed (x, u), define the partition function X X Z(x, u) ≜ exp − β ce (x, u) . (34) e∈p
p∈P
The induced path distribution is P (p) = Z(x, u)−1 exp(−β used equals
P
e∈p ce (x, u)). The marginal probability that edge e is
πe (x, u) ≜ Pr{e ∈ p} = −
1 ∂ log Z(x, u), β ∂ce
(35)
and thus the expected edge load under demand d is x′e = d πe (x, u). Definition 5 (Two-terminal series-parallel network). A directed two-terminal network (G, s, t) is series-parallel if it can be obtained from a single edge by recursively applying series composition and parallel composition of two-terminal subnetworks. Theorem 10 (Linear-time evaluation of partition functions and edge marginals on SP networks). Let (G, s, t) be a two-terminal series-parallel network with an SP decomposition tree of size O(|E|). For any generalized edge costs {ce }, the partition function Z in (34) and all edge marginals {πe } in (35) can be computed in O(|E|) time. Proof idea. For series-parallel graphs, the path partition function factorizes: series composition multiplies partition functions and parallel composition adds them. A bottom-up pass computes Z; edge marginals are obtained by differentiating log Z through the same recursion (equivalently, a reverse-mode pass on the SP tree). Full proof is deferred to Appendix A.10. Remark 10 (Computing SW-SUE without enumerating paths). Theorem 10 provides an efficient oracle for the map (x, u) 7→ x′ defined by x′e = d πe (x, u). Combined with the strict convexity of the salience potential (Proposition 1), it yields polynomial-time equilibrium computation on SP networks under edge-additive salience, and it makes gradients with respect to u tractable via automatic differentiation through the SP recursion. This extends the tractable network class beyond pure parallel networks while remaining compatible with feature-based governance constraints. 6.5.1
A convex split-flow formulation and first-order convergence on SP networks
Theorem 10 provides an efficient oracle for evaluating logit probabilities for fixed generalized edge costs. To go beyond mere evaluation and obtain a deterministic algorithm with convergence guarantees, we can exploit the SP-tree structure to express the SW-SUE convex potential (Proposition 1) in a low-dimensional set of split variables. 16
Split variables. Fix a single commodity with demand d on a two-terminal SP network with decomposition tree T . Let V⊕ be the set of parallel nodes of T . For each H ∈ V⊕ with children (HL , HR ), introduce a split-flow variable yH ∈ (0, dH ) representing the flow sent through HL , where dH is the total flow entering subgraph H (determined recursively by the splits above H). Given y = (yH )H∈V⊕ , the induced edge-flow vector x(y) is obtained by a single top-down pass on T and can be computed in O(|E|) time. Entropy decomposes on SP trees. On a series-parallel decomposition, path choice can be viewed as a hierarchical sequence of binary decisions at parallel nodes. Accordingly, the path-flow entropy term in the SW-SUE potential decomposes into a sum of local entropies at parallel nodes (up to an additive constant depending only on total demand). This yields the following low-dimensional convex program. Theorem 11 (Split-flow convex program for SW-SUE on SP networks). Consider a single commodity of demand d on a two-terminal SP network with continuous nondecreasing edge latencies. Assume edge-additive salience (feature tying) with parameters u = (ue )e∈E as in (33). Define the split-flow objective X Z xe (y) 1X 1 X yH log yH +(dH −yH ) log(dH −yH )−dH log dH , Ψu (y) ≜ ℓe (z) dz − ue xe (y) + β β 0 e∈E
e∈E
H∈V⊕
(36) where dH is the flow entering subgraph H under splits y. Then Ψu is strictly convex on its feasible region, and its unique minimizer y ⋆ induces the unique SW-SUE edge flow x⋆ = x(y ⋆ ) under u. Proof. We start from the SW-SUE convex potential in path flows under edge-additive salience. For a single commodity of demand d, Proposition 1 implies that the SW-SUE path flow is the unique minimizer of X Z xe (f ) 1X 1 X Φu (f ) = ℓe (z) dz − ue xe (f ) + fp log fp , (37) β β 0 e∈E
e∈E
p∈P
over feasible path flows f (up to an additive constant depending only on d). The key observation is that on a two-terminal SP network, the objective (37) admits an exact dynamic-programming elimination on the SP tree, reducing it to split variables. A value-function recursion on the SP tree. For each SP subgraph node H ∈ T and scalar dH ≥ 0, define the reduced value function ( ) X X Z xe (f H ) 1 X 1 fpH log fpH −dH log dH FH (dH ) ≜ min ℓe (z) dz− ue xe (f H )+ , β β f H ∈F (H;dH ) 0 e∈E(H)
e∈E(H)
p∈P(H)
(38) P where F(H; dH ) is the set of feasible s–t path flows within subgraph H with total flow p∈P(H) fpH = dH . (The subtraction of dH log dH removes the normalization constant at each subproblem and will expose local entropy terms at parallel splits.) At the root node, droot = d is fixed, and minimizing (37) is equivalent (up to the constant d log d/β) to minimizing Froot (d). We now show by structural induction on the SP tree that FH obeys the following recursion: 1. Leaf edge. If H is a single edge e, then there is only one path in P(H) and the entropy term cancels, yielding Z d 1 Fe (d) = ℓe (z) dz − ue d. β 0 2. Series composition. If H = H1 ⊗ H2 is a series composition, then FH (d) = FH1 (d) + FH2 (d). 3. Parallel composition. If H = HL ⊕ HR is a parallel composition, then n o 1 y log y + (d − y) log(d − y) − d log d . FH (d) = min FHL (y) + FHR (d − y) + 0≤y≤d β 17
The leaf and parallel cases follow directly from the definition (38) because (i) a leaf has a single path, and (ii) in a parallel composition the path sets are disjoint so both the congestion term and the entropy term split additively across children. The series case requires an “independence is optimal” argument for the entropy term. Let H = H1 ⊗ H2 and consider any feasible joint path flow f on P(H) = P(H1 ) × P(H2 ) with total mass d. Let f (1) and f (2) be the (1) (2) induced marginals on P(H1 ) and P(H2 ) (each has total mass d). Define the product coupling gp1 ,p2 ≜ fp1 fp2 /d. Nonnegativity of KL divergence gives X
0 ≤ D(f ∥g) =
fp1 ,p2 log
p1 ,p2 (1)
fp1 ,p2 gp1 ,p2
X
=⇒
fp1 ,p2 log fp1 ,p2 ≥
p1 ,p2
X
fp1 ,p2 log gp1 ,p2 .
p1 ,p2
(2)
Expanding log gp1 ,p2 = log fp1 + log fp2 − log d shows X X X fp1 ,p2 log gp1 ,p2 = fp(1) log fp(1) + fp(2) log fp(2) − d log d. 1 1 2 2 p1 ,p2
p1
p2
P
Thus the entropy part f log f −d log d is minimized (equivalently, entropy is maximized) by the independent coupling f = g, and the reduced objective (38) decomposes as FH1 (d) + FH2 (d). This establishes the recursion. From the recursion to the split-flow objective. Unrolling the recursion on the full SP tree introduces exactly one scalar split decision yH for each parallel node H ∈ V⊕ , and the resulting reduced objective equals (36) with x(y) computed by the induced split flows. Hence minimizing the original path-flow potential (37) is equivalent to minimizing Ψu (y). Convexity and uniqueness. Each FH is convex in its scalar argument (leaf terms are convex by monotonicity of ℓe , and parallel nodes add a strictly convex entropy term). Therefore Ψu is strictly convex in y and has a unique minimizer y ⋆ . The induced edge flow x⋆ = x(y ⋆ ) is the unique SW-SUE edge flow because it arises from the unique minimizer of (37). Proposition 4 (First-order convergence guarantee (projected gradient)). Assume each ℓe is Lipschitz on [0, d] and consider a compact interior domain in which all split variables satisfy ϵ ≤ yH ≤ dH − ϵ for some ϵ > 0. On this domain, Ψu in (36) has an L-Lipschitz gradient and is µ-strongly convex for some L, µ > 0. Projected gradient descent with step size 1/L therefore converges linearly to y ⋆ : Ψu (y (t) ) − Ψu (y ⋆ ) ≤ (1 − µ/L)t Ψu (y (0) ) − Ψu (y ⋆ ) . Each gradient evaluation can be computed in O(|E|) time by a forward (flow) pass and a reverse (adjoint) pass on T . Proof idea. On a compact interior domain, the split-flow objective has bounded Hessian eigenvalues because each parallel node contributes a strictly convex entropy term and each series segment contributes a smooth convex term. This yields L-smoothness and µ-strong convexity. Standard projected gradient descent guarantees then give linear convergence to the unique minimizer. Full proof is deferred to Appendix A.26. Remark 11 (Beyond contraction). Theorems 11 and Proposition 4 provide a convergence guarantee for equilibrium computation on a nontrivial network class (two-terminal SP) without relying on contraction of the equilibrium map. The key is strict convexity of the potential plus a low-dimensional split-flow representation. 6.6
Differentiating through equilibrium
When the induced equilibrium is isolated (in particular, when it is unique—e.g., under Theorem 13 for the full memory model or under Theorem 16 for stationary salience policies), the mapping θ 7→ x⋆ (θ) can be differentiated via implicit differentiation (Theorem 14). For any differentiable scalar objective J(θ) = SC(x⋆ (θ)) + λ Cost(θ), the chain rule yields dx⋆ ∇θ J(θ) = ∇x SC(x⋆ (θ)) + λ ∇θ Cost(θ), (39) dθ ⋆
with dx dθ given by (53). This is a standard “differentiate through fixed points” primitive, but it becomes nontrivial here because Tθ depends on θ both directly (surfacing) and indirectly (through the stationary distribution of a policy-induced memory Markov chain). 18
Algorithm 1 Equilibrium-aware memory/guidance optimization (template) 1: Input: initial θ (0) , step size schedule {γt }, tolerance ε 2: for t = 0, 1, 2, . . . do 3: Equilibrium solve: compute x⋆ (θ(t) ) (and µ⋆ (θ(t) )) via Algorithm 2 4: Sensitivity: compute/estimate ∇x Tθ(t) (x⋆ ) and ∇θ Tθ(t) (x⋆ ) 5: Solve (I − ∇x Tθ(t) (x⋆ )) v = ∇x SC(x⋆ ) for v (linear system) ⊤ ⋆ (t) d Form gradient estimate ∇ θ J ← v ∇θ Tθ (t) (x ) + λ∇θ Cost(θ ) d 7: Update: θ(t+1) ← ΠΘ θ(t) − γt ∇ θ J (projected step) (t+1) (t) 8: if ∥θ − θ ∥ ≤ ε then 9: break 10: end if 11: end for 12: Output: optimized θ and resulting equilibrium (x⋆ , µ⋆ )
6:
6.7
Algorithmic template: equilibrium-aware policy gradient
Algorithm 1 sketches a practical approach when Tθ is a contraction and the stationary distributions can be computed (or estimated) efficiently. Remark 12 (Implementation notes). (i) In large route sets, ∇θ Tθ can be estimated by sampling surfaced routes and using automatic differentiation through the softmax/logit components. (ii) The linear solve in Algorithm 1 can be done iteratively (e.g., conjugate gradients) because the contraction regime implies (I − ∇x T ) is well-conditioned. (iii) If fairness constraints are required, one can use projected-gradient or primal–dual updates with type-level cost estimates extracted from the equilibrium. 6.8
From toy instances to general networks
The Pigou results in Section 11 demonstrate a central point: the optimal amount of recall is generally interior, not “as much as possible.” In general networks, the design variables θ (surfacing and forgetting) allow the system to trade off: • efficiency: reduce congestion externalities by dampening herding onto low-latency routes, • stability: avoid oscillations driven by overreactive guidance, • governance: satisfy privacy and cost constraints inherent to memory-bounded AI systems. The main technical agenda for a top AI/game-theory venue is to characterize when such policies can guarantee improvement over full recall and how close they can get to the social optimum under natural constraints (nondiscrimination, limited control authority, and bounded memory).
7
From Information to Recall: Modeling Imperfect Recall
This section is the main modeling fork relative to classic routing games. We define a recall model that is compatible with the informational Braess framework while enabling endogenous recall under memory policies. 7.1
Recall sets as a baseline abstraction
We first recall the informational-Braess style baseline in which each traveler type has access only to a fixed subset of routes. This subsection is used only as a point of contact with ICWE/IBP; our main model in Section 7.3 replaces fixed recall sets with an endogenous memory process. We assume a finite set of traveler types i ∈ {1, . . . , I} with demands di summing to d. Each type i has a recall set of edges Ei ⊆ E (or, equivalently, a recall set of feasible paths Pi ⊆ P consisting only of edges in Ei ). Type i can only route on paths in Pi . A recall policy parameter θ may index a family {Pi (θ)} (e.g., varying memory budget, recall suppression, or information exposure). In the static recall view, we treat Pi as fixed and study the induced equilibrium. In the dynamic recall view, recall sets are generated endogenously by a stochastic memory process together with an AI surfacing policy (Section 7.3); here θ corresponds to controllable memory/guidance parameters rather than an exogenous menu. 19
7.2
Information-constrained Wardrop equilibrium as a baseline
Definition 6 (Recall/Information-constrained Wardrop equilibrium (ICWE/RCWE)). Given recall sets Pi , a flow profile (i) (i) f = (fp ) is a recall-constrained Wardrop equilibrium if for each type i and every path p ∈ Pi with fp > 0, for all p′ ∈ Pi .
Lp (f ) ≤ Lp′ (f )
When Pi = P for all i, this reduces to Wardrop equilibrium. This equilibrium notion is equivalent to the ICWE of [Acemoglu et al., 2018] under fixed information sets. Proposition 5 (Existence via potential minimization (standard)). Assume each ℓe is continuous and nondecreasing. For fixed recall sets {Pi }Ii=1 , an ICWE/RCWE exists. Moreover, if there is a single origin–destination pair and each ℓe is strictly increasing on [0, d], then the induced equilibrium edge loads are unique (though path flows need not be). Proof idea. Define the Beckmann potential over feasible path flows restricted to the fixed recall sets and minimize it over a compact simplex. Convexity and continuity yield existence; KKT conditions recover the (information-constrained) Wardrop inequalities. For a single OD with strictly increasing latencies, strict convexity of the potential in edge loads yields uniqueness of equilibrium edge loads. Full proof is deferred to Appendix A.11. Remark 13. We state the proposition for completeness; it follows from standard convexity arguments (Beckmann-type potentials) and is established explicitly in the informational Braess framework [Acemoglu et al., 2018]. 7.3
Dynamic recall: a fully specified stochastic model
This subsection replaces the earlier sketch with a concrete, mathematically complete model. The goal is to capture endogenous recall under explicit memory budgets and eviction policies while retaining a clean non-atomic routing foundation. 7.3.1
Primitives
We consider a finite set of origin–destination (OD) commodities K. Each commodity k ∈ K has origin sk , destination tk , and a fixed demand (population mass) dk > 0. Let Pk denote a finite set of feasible sk –tk paths.1 The physical network is G = (V, E) with continuous, nondecreasing edge latency functions ℓe : R≥0 → R≥0 . Given |E| an edge-load vector x ∈ R≥0 , the latency of path p is X Lp (x) = ℓe (xe ). (40) e∈p
7.3.2
Memory state space and recall
Fix a memory budget Bk ∈ {1, 2, . . . , |Pk |} for each commodity k. Definition 7 (Memory state space). For commodity k, a memory state is an ordered list m = (p(1) , p(2) , . . . , p(Bk ) ) ∈ Mk , where p(j) ∈ Pk are distinct paths. The order encodes recency/priority, with p(1) interpreted as the most “salient” or most recently activated route. The recalled set induced by m is S(m) = {p(1) , . . . , p(Bk ) } ⊆ Pk . Exogenous discovery (route surfacing). To allow routes that are not currently recalled to become available, we assume a simple discovery/surfacing process. For each commodity k, fix a distribution ρk over Pk with full support, i.e., ρk (p) > 0 for all p ∈ Pk . At each period (day) and for each traveler of commodity k, an independent “surfaced” route q is drawn as q ∼ ρk . The traveler can choose from the available set A(m, q) = S(m) ∪ {q}.
(41)
This is a minimal, analytically convenient abstraction of (i) occasional exploration, or (ii) an interface (e.g., navigation app) that surfaces a candidate alternative outside the traveler’s currently recalled set. 1
The finiteness assumption is standard when working with explicit path sets; in computational experiments one can take Pk as a candidate route set generated by k-shortest paths, column generation, or sampling.
20
7.3.3
Route choice given congestion
Fix an inverse-temperature (rationality) parameter β ≥ 0. Given a memory state m, surfaced route q, and congestion x, the traveler’s mixed strategy over available routes is the logit response exp − β Lp (x) σ(p | m, q, x) = P for p ∈ A(m, q), (42) r∈A(m,q) exp − β Lr (x) and σ(p | m, q, x) = 0 otherwise. The limit β → ∞ recovers (tie-broken) best response on the available set. Information structure. We treat x (and hence the travel-time estimates Lp (x)) as a contemporaneous signal observed by the agent or provided by the guidance platform for the routes in the available set A(m, q). Thus, memory affects consideration (which routes can be chosen) rather than beliefs about costs. This aligns the model with “random attention”/consideration-set foundations and isolates the externality created by policy-controlled recall. Extensions in which memory also stores (possibly biased) cost estimates can be layered on top, but are not needed for the implementability and governance results proved in the stationary salience design layer. 7.3.4
Eviction/forgetting policy: LRU as a canonical baseline
A memory policy specifies how the state updates after a route is chosen. We give a canonical policy that is (i) widely used in computer systems, (ii) cognitively interpretable, and (iii) yields a finite-state Markov chain: least-recently used (LRU) eviction. Definition 8 (LRU update map). For commodity k, define the deterministic update map Uk : Mk × Pk → Mk as follows. Let m = (p(1) , . . . , p(Bk ) ) and let p ∈ Pk be the route chosen in the current period. 1. If p ∈ S(m) and p = p(j) for some j, then Uk (m, p) is obtained by moving p to the front and shifting the earlier items back one position: Uk (m, p) = (p, p(1) , . . . , p(j−1) , p(j+1) , . . . , p(Bk ) ). 2. If p ∈ / S(m), then p is inserted at the front and the last element is dropped: Uk (m, p) = (p, p(1) , . . . , p(Bk −1) ). Remark 14 (Other policies). The same framework accommodates FIFO, random replacement, score-based priority eviction, and summary/hybrid policies. We use LRU to obtain a clean, fully discrete baseline; later sections can compare policies empirically and (where possible) analytically. 7.3.5
Population state, induced flows, and the within-period fixed point
Travelers are non-atomic and persistent. For each commodity k, let µk be a probability distribution over memory states Mk (equivalently, a population share over memory states). A population memory profile is µ = (µk )k∈K . Given a memory profile µ and congestion x, the induced expected path flow on p ∈ Pk is X X fk,p (µ, x) = dk µk (m) ρk (q) σ(p | m, q, x). m∈Mk
(43)
q∈Pk |E|
Let f (µ, x) denote the concatenation over all commodities. The induced edge-load vector x(f ) ∈ R≥0 is defined componentwise by X X xe (f ) = fk,p 1{e ∈ p} for each e ∈ E. (44) k∈K p∈Pk
Definition 9 (Congestion consistency for a memory profile). A congestion vector x is consistent with memory profile µ if x = x f (µ, x) . (45) We write x ∈ Ξ(µ) for the (possibly set-valued) correspondence of solutions. Remark 15. Under logit choice (finite β) and standard regularity of latencies, (45) is the equilibrium condition of a smooth stochastic user equilibrium on restricted choice sets; in many settings it admits a unique solution. For the purposes of model definition, we take Ξ(µ) as the equilibrium correspondence that maps population memory to congestion. 21
7.3.6
Memory-state Markov kernel induced by congestion
Fix a congestion vector x. For each commodity k, the LRU update together with logit choice and route surfacing induces a Markov chain on Mk . Its transition kernel is X X Px(k) (m′ | m) = ρk (q) σ(p | m, q, x) 1{m′ = Uk (m, p)}. (46) q∈Pk
p∈A(m,q)
Given a current population distribution µk , the next-period distribution is the pushforward X ′ µ+ µk (m) Px(k) (m′ | m). k (m ) =
(47)
m∈Mk
We write µ+ = Φx (µ) for the full profile update across commodities. 7.3.7
Forgetful Wardrop equilibrium (FWE)
We can now define a stationary equilibrium that couples (i) congestion consistency and (ii) stationary memory dynamics. Definition 10 (Forgetful Wardrop equilibrium (FWE)). A pair (x⋆ , µ⋆ ) is a forgetful Wardrop equilibrium if: 1. Congestion consistency: x⋆ ∈ Ξ(µ⋆ ), i.e., x⋆ satisfies (45) for µ⋆ . 2. Memory stationarity: for every commodity k ∈ K, µ⋆k is stationary under the kernel induced by x⋆ : X (k) µ⋆k = µ⋆k (m) Px⋆ (· | m). m∈Mk
Equivalently, µ⋆ = Φx⋆ (µ⋆ ). Remark 16 (Relation to classical models). If Bk = |Pk | and ρk is irrelevant (or if A(m, q) = Pk always), FWE reduces to a stochastic user equilibrium (and in the limit β → ∞ to a Wardrop equilibrium). If recall sets are fixed exogenously (no memory dynamics), FWE collapses to an information-constrained Wardrop equilibrium (ICWE/RCWE).
8
Existence, Characterization, and Computation of Forgetful Wardrop Equilibrium
This section records baseline theoretical properties of the model in Section 7.3. The main purpose is twofold: (i) to establish that the coupled flow–memory equilibrium is well-posed, and (ii) to provide a concrete computational template that will later support empirical results and algorithmic policy design. 8.1
Feasible set and standing assumptions P Let D ≜ k∈K dk denote total demand. Because each traveler selects exactly one path per period and paths are simple, every edge load satisfies 0 ≤ xe ≤ D. We therefore work on the compact convex set X ≜ [0, D]|E| .
(48)
Assumption 1 (Regularity and exploration). For each edge e ∈ E, the latency function ℓe (·) is continuous and nondecreasing on [0, D]. For each commodity k, the surfacing distribution ρk has full support on Pk . Finally, the logit parameter satisfies β < ∞. Assumption 1 implies that (i) every available route has strictly positive choice probability under (42), and (ii) every route can be surfaced with positive probability. 8.2
Ergodicity of the memory Markov chain
Lemma 1 (Ergodicity and uniqueness of the stationary memory distribution). Fix a commodity k and a congestion (k) vector x ∈ X . Under Assumption 1, the Markov chain on Mk with transition kernel Px defined in (46) is irreducible and aperiodic. Consequently, it admits a unique stationary distribution, denoted πk (x) ∈ ∆(Mk ), with full support on Mk . 22
Proof idea. Irreducibility is shown by constructing a positive-probability sequence of surfaced routes that (under logit) can be chosen to “write” any target LRU list into memory via repeated insertions. Aperiodicity follows from the positive self-loop obtained when the traveler selects the most recent recalled route, leaving the ordered list unchanged. Full proof is deferred to Appendix A.2. Lemma 2 (Continuity of the stationary memory map). Under Assumption 1, for each commodity k the mapping x 7→ πk (x) is continuous on X . Proof idea. The transition matrix entries depend continuously on x through continuous latencies and the smooth logit map. The stationary distribution is the unique solution of a linear system whose coefficient matrix remains nonsingular under ergodicity; continuity then follows from continuity of matrix inversion on the set of nonsingular matrices. Full proof is deferred to Appendix A.3. Lemma 1 yields an important simplification: in a forgetful Wardrop equilibrium, the memory profile is pinned down by congestion via µ⋆k = πk (x⋆ ). Thus the equilibrium can be characterized by a fixed point in edge-load space alone. 8.3
Within-period congestion consistency
Proposition 6 (Existence of a congestion-consistent flow for fixed memory). Fix a memory profile µ. Under Assumption 1, the set Ξ(µ) of congestion vectors consistent with µ (Definition 9) is nonempty. Proof idea. For fixed µ, the induced flow map x 7→ f (µ, x) is continuous, hence so is the induced edge-load map Tµ (x) = x(f (µ, x)). Since Tµ maps the compact convex set X to itself, Brouwer’s fixed point theorem yields x = Tµ (x). Full proof is deferred to Appendix A.4. 8.4
Existence of Forgetful Wardrop equilibrium
Define π(x) ≜ (πk (x))k∈K and the reduced fixed-point map T : X → X by T (x) ≜ x(f (π(x), x)) .
(49)
Theorem 12 (Existence of FWE). Under Assumption 1, there exists at least one forgetful Wardrop equilibrium (x⋆ , µ⋆ ). Moreover, any x⋆ ∈ X satisfying x⋆ = T (x⋆ ) together with µ⋆k = πk (x⋆ ) for each k constitutes a FWE. Proof idea. Combine Lemma 1 and Lemma 2 to obtain a continuous stationary-memory map x 7→ π(x). Substituting µ = π(x) into the congestion consistency map yields a continuous self-map T on X , so Brouwer yields a fixed point x⋆ = T (x⋆ ) and hence an FWE. Full proof is deferred to Appendix A.5. 8.5
A practical fixed-point computation template
Theorem 12 suggests a direct numerical approach: iterate the reduced map T (·) while recomputing the stationary (k) memory distributions. In finite state spaces, πk (x) can be computed via power iteration on Px (or more stable linear-algebra routines for the eigenvector corresponding to eigenvalue 1). Algorithm 2 is a baseline; later drafts can add acceleration, monotone VI solvers for the within-period subproblem, and policy-gradient-style updates when optimizing memory/guidance parameters. Remark 17 (State-space explosion and scalable surrogates). Algorithm 2 is primarily a conceptual fixed-point template. The memory state space for commodity k has cardinality |Mk | = |Pk | · (|Pk | − 1) · · · (|Pk | − Bk + 1), which is factorial in Bk and quickly becomes intractable even for moderate candidate route sets. In large networks, one should therefore avoid explicit enumeration of Mk . Two scalable alternatives are: (i) Monte Carlo estimation of stationary choice frequencies by simulating the memory chain directly (without storing the full transition matrix), and (ii) mean-field closures that track only per-route recall probabilities (e.g., the LRU→TTL→salience surrogate developed in Section 9.1), which reduce equilibrium computation to solving a strictly convex SW-SUE potential. 8.6
Uniqueness and global stability under a contraction condition
Existence via Brouwer is not the end of the story: for algorithmic design and comparative statics we need uniqueness and stability. This subsection provides a sufficient condition under which the reduced equilibrium map T is a contraction on X , implying a unique FWE and global convergence of natural day-to-day dynamics. 23
Algorithm 2 Fixed-point iteration for FWE (basic template) 1: Input: initial x(0) ∈ X , damping η ∈ (0, 1], tolerance ε > 0 2: for t = 0, 1, 2, . . . until convergence do 3: for each commodity k ∈ K do (k)
Build transition matrix Px(t) from (46) 5: Compute stationary distribution πk (x(t) ) (e.g., power iteration) 6: end for 7: Form π(x(t) ) = (πk (x(t) ))k∈K 8: Compute induced path flows f (π(x(t) ), x(t) ) via (43) 9: Compute updated edge loads x̃(t+1) ← x(f (π(x(t) ), x(t) )) via (44) 10: Damped update: x(t+1) ← (1 − η)x(t) + η x̃(t+1) 11: if ∥x(t+1) − x(t) ∥∞ ≤ ε then 12: break 13: end if 14: end for 15: Output: x(t+1) and µ⋆ = π(x(t+1) ) 4:
Assumption 2 (Lipschitz latencies). Each ℓe (·) is continuously differentiable on [0, D] with derivative bounded by Le , and we define L ≜ maxe∈E Le . Assumption 3 (Uniform mixing of memory dynamics (Doeblin condition)). For each commodity k there exist εk ∈ (0, 1] and a distribution νk ∈ ∆(Mk ) such that for all x ∈ X and all m ∈ Mk , Px(k) (· | m) ≥ εk νk (·)
(50)
(componentwise).
Remark 18 (How to enforce Assumption 3 by design). A simple sufficient mechanism is an exogenous reset: with probability εk per period, the memory state is redrawn from νk independently of the chosen route. This is natural in AI memory systems (e.g., periodic consolidation/summary refresh or privacy-driven deletion) and yields (50) directly. Define the maximum path length H ≜ max max |p| k∈K p∈Pk
(where |p| is the number of edges on path p), and recall that total demand is D =
P
k dk .
Lemma 3 (Logit sensitivity). Fix any finite action set A. The logit map c 7→ σ(· | c) defined by σ(a | c) ∝ exp(−βca ) is β-Lipschitz from (R|A| , ∥ · ∥∞ ) to (∆(A), ∥ · ∥1 ): σ(· | c) − σ(· | c′ ) 1 ≤ β ∥c − c′ ∥∞ . Proof idea. Differentiate the logit map: its Jacobian has entries bounded in magnitude by β times a probability product. Bounding the induced operator norm from ℓ∞ to ℓ1 yields a global Lipschitz constant β. The claim then follows from the mean value theorem. Full proof is deferred to Appendix A.20. Lemma 4 (Lipschitz continuity of x 7→ πk (x) with explicit dependence on mixing). Under Assumptions 1–3 and 2, for each commodity k the stationary distribution πk (x) is unique and satisfies, for all x, y ∈ X , ∥πk (x) − πk (y)∥1 ≤
1 sup P (k) (· | m) − Py(k) (· | m) 1 . εk m∈Mk x
Moreover, using Lemma 3 and the Lipschitz bound on path costs, one may take Ck =
βHL , εk
so that ∥πk (x) − πk (y)∥1 ≤ Ck ∥x − y∥∞ . Proof idea. Uniform mixing (Doeblin) implies a contraction of total-variation distances under the kernel and yields standard perturbation bounds for stationary distributions. Bounding ∥Px − Py ∥ via logit sensitivity and Lipschitz path costs gives ∥π(x) − π(y)∥1 = O(∥x − y∥∞ ). Full proof is deferred to Appendix A.7. 24
Proposition 7 (Lipschitz bound for the reduced equilibrium map). Under Assumptions 1, 2, and 3, the reduced map T in (49) is Lipschitz on X . In particular, there exists κ > 0 such that for all x, y ∈ X , ∥T (x) − T (y)∥∞ ≤ κ ∥x − y∥∞ , and one admissible (conservative) choice is κ = D β H L + max Ck . k∈K
(51)
Proof idea. Bound changes in path costs by Lipschitz latencies and the fact that edge loads are linear in path flows. Use Lemma 4 to control how the stationary memory distribution changes with x, and Lemma 3 to control how logit probabilities change with costs. Aggregating over commodities and paths yields the stated Lipschitz factor κ. Full proof is deferred to Appendix A.21. Theorem 13 (Uniqueness and global convergence). Suppose Assumptions 1, 2, and 3 hold and the Lipschitz factor κ in Proposition 7 satisfies κ < 1. Then: 1. The reduced map T has a unique fixed point x⋆ , hence the FWE (x⋆ , µ⋆ ) is unique with µ⋆ = π(x⋆ ). 2. The fixed-point iteration x(t+1) ← T (x(t) ) converges to x⋆ from any initialization, at a linear rate bounded by κ. 3. The coupled day-to-day dynamics xt+1 = x(f (µt , xt )) ,
µt+1 = Φxt (µt )
are globally convergent to (x⋆ , µ⋆ ) under mild damping, i.e., for sufficiently small step size in the x-update. Proof idea. Under κ < 1, Proposition 7 implies T is a contraction on the complete metric space (X , ∥ · ∥∞ ). Banach’s fixed point theorem yields a unique fixed point x⋆ and global convergence of the fixed-point iteration; mapping back via µ⋆ = π(x⋆ ) yields uniqueness of the FWE. Full proof is deferred to Appendix A.22. Remark 19 (Interpretation of the contraction regime). The contraction condition κ < 1 is satisfied when congestion costs are not overly sensitive (small L), agents are not overly deterministic (moderate β), or the memory dynamics mix rapidly (large εk ). This regime is operationally meaningful for AI guidance: injected randomness and periodic reset/consolidation are standard tools, and they simultaneously ensure both privacy and equilibrium stability. 8.7
Comparative statics and differentiability for policy optimization
For equilibrium-aware design we require that the equilibrium depends smoothly on policy parameters. Let θ ∈ Θ parameterize a family of surfacing distributions and memory policies (e.g., reset rate, eviction rule, or summary (k) frequency), inducing kernels Px,θ , stationary distributions πk,θ (x), and a reduced map Tθ (x) ≜ x(f (πθ (x), x; θ)) ,
πθ (x) = (πk,θ (x))k∈K .
Theorem 14 (Implicit differentiation of an isolated FWE). Assume Θ is an open set and that Tθ is continuously differentiable in (x, θ). Fix θ ∈ Θ and suppose x⋆ is a fixed point of Tθ such that det I − ∇x Tθ (x⋆ ) ̸= 0. (52) Then there exists a neighborhood U of θ and a unique continuously differentiable map θ′ 7→ x⋆ (θ′ ) on U such that x⋆ (θ) = x⋆ and x⋆ (θ′ ) = Tθ′ (x⋆ (θ′ )) for all θ′ ∈ U . Moreover, −1 dx⋆ = I − ∇x Tθ (x⋆ ) ∇θ Tθ (x⋆ ). (53) dθ Proof idea. Apply the implicit function theorem to F (x, θ) = Tθ (x)−x. The Jacobian with respect to x is ∇x Tθ (x)−I, which is invertible at x⋆ by (52). This yields a locally unique differentiable selection x⋆ (θ) and the derivative formula. Full proof is deferred to Appendix A.23. Equation (53) is the key technical enabler for gradient-based policy optimization in Section 6. 25
9
Micro-to-salience surrogates for richer memories
The stationary salience layer is exact for B = 1 last-choice memory (Theorem 1), but realistic recall involves larger memory budgets and more complex update rules. This section develops a mean-field approximation pipeline that maps explicit LRU memory to an endogenized TTL model and then to stationary salience parameters, yielding a practical surrogate for stationary behavior without simulating the full memory Markov chain. 9.1
Beyond B=1: a mean-field micro-to-salience approximation for larger memories
The exact reduction in Theorem 1 relies on the special structure of Bk = 1 (“last choice”). For larger memory budgets Bk > 1 and realistic eviction rules such as LRU, the stationary choice probabilities no longer admit a closed form. Nevertheless, the salience abstraction remains useful: it can arise as a controlled approximation that compresses rich memory dynamics into route availability frequencies. Approximation assumptions for the micro→salience surrogate (for Bk > 1). Our Bk > 1 bridge relies on four explicit approximation ingredients: (i) Poissonization of discrete repeated choice into independent Poisson request streams (Assumption 4 and Lemma 5), (ii) an LRU→TTL (characteristic-time) approximation in the large-cache/large-catalog regime (Theorem 15), (iii) an independent-availability menu surrogate with a nonempty baseline (Assumption 5), and (iv) randomdenominator concentration for “large” available sets (Proposition 8 and Corollary 7). These assumptions are not implied by the fully specified discrete-time micro Markov model; rather, they are standard mean-field/caching approximations that become accurate in diffused-popularity and large-menu regimes, and we validate them empirically in Section 12.
Setup: LRU recall sets. Fix commodity k and congestion vector x. Let the memory state be an ordered list of the Bk most recently chosen routes (LRU stack), so the recalled set is S(m) ⊆ Pk with |S(m)| = Bk . Each period, a candidate route q ∼ ρk is surfaced, and the traveler chooses from the available set A = S(m) ∪ {q} via the logit rule (42), after which the chosen route moves to the top of the LRU stack. Let πk,x (·) denote the stationary marginal distribution of the chosen route for the resulting Markov chain (when it exists and is unique). Step 0: from nonatomic repeated choice to a Poisson request stream. The cache-theoretic results we invoke (LRU→TTL approximations) are stated for request processes in continuous time. To connect them to repeated routechoice, we use a standard Poissonization device that is exact in a nonatomic mean-field limit and convenient for analysis. Assumption 4 (Poissonized stationary request model). Fix a commodity k and congestion vector x and consider a stationary repeated-choice regime. Each infinitesimal traveler generates decision epochs according to an independent Poisson process of rate 1. At each epoch, the traveler selects a route label p ∈ Pk with probability πk,x (p), independently across epochs and travelers. Lemma 5 (Thinning and superposition yield independent Poisson requests). Under Assumption 4, the aggregate request process for each route p ∈ Pk is a Poisson process with intensity λk,p (x) = dk πk,x (p), and these route-specific request processes are mutually independent across p. Proof. By superposition, the union of independent Poisson clocks (one per infinitesimal traveler) is a Poisson process of rate dk . Thinning this process by independently labeling each event with route p with probability πk,x (p) yields independent Poisson processes with rates dk πk,x (p) for each label p. Step 0a: Discrete-time departures and the accuracy of Poissonization. Many day-to-day route-choice models are discrete: each agent departs once per period and draws a route label i.i.d. with probabilities πp . In that setting, each route’s request stream is Bernoulli on a grid and inter-request times are geometric. The Poissonization device above replaces geometric inter-request times by exponential ones; the next lemma quantifies the induced error at the level of the TTL/working-set “hit” probability that drives our micro→salience surrogate. Lemma 6 (Working-set vs. Poisson TTL hit probabilities). Fix a route with per-period request probability π ∈ (0, 1) in a discrete-time i.i.d. request stream, and let W ∈ N be a window length. The discrete-time working-set hit probability is H WS (W ) = 1 − (1 − π)W . The continuous-time Poisson TTL approximation with rate λ = π and horizon T = W is H TTL (W ) = 1 − e−πW . Then 0 ≤ H WS (W ) − H TTL (W ) = e−πW − (1 − π)W ≤ 26
π 2 W −πW π2 W e ≤ . 1−π 1−π
Proof. The bound (1−π)W ≤ e−πW follows from log(1−π) ≤ −π. For the other direction, log(1−π) ≥ −π/(1−π) implies (1 − π)W ≥ e−πW/(1−π) . Therefore 2 π 2 W −πW e−πW − (1 − π)W ≤ e−πW − e−πW/(1−π) = e−πW 1 − e−π W/(1−π) ≤ e , 1−π where the last step uses 1 − e−y ≤ y. Corollary 6 (Diffused popularity justifies Poissonization). Let πmax ≜ maxp πp and assume a regime in which πmax → 0 (e.g., a large choice set with no dominant route). If the relevant window scales so that supp πp W = O(1), then sup HpWS (W ) − HpTTL (W ) = O(πmax ). p
Proof idea. Apply Lemma 6 to each route p and use πp2 W ≤ (πp W )πp . Under the regime supp πp W = O(1) and πmax → 0, the uniform difference between working-set and Poisson TTL hit probabilities is O(πmax ). Full proof is deferred to Appendix A.14. TTL Remark 20 (Normalization). Under the Poissonized model, the TTL in-cache probability is Hk,p (t) = 1 − e−λk,p (x)t . TTL −πk,x (p)t Equivalently, by rescaling time by dk one can write Hk,p (t/dk ) = 1 − e , which matches the form in (54).
Step 1: approximating recall frequencies by TTL/Che approximation. Under i.i.d. “request” models, LRU caches admit accurate and in some regimes asymptotically exact approximations in terms of a characteristic time (often called the TTL or Che approximation). In our setting, the “request” process is the stationary sequence of chosen routes, whose marginal is πk,x . Motivated by the TTL approximation for LRU caches [Fricker et al., 2012, Jiang et al., 2018, Gast and Van Houdt, 2017], we define the approximate recall probability for each route p by hk,p (x) ≈ 1 − exp − πk,x (p) Tk (x) , (54) where the characteristic time Tk (x) ≥ 0 is chosen to satisfy the cache-size constraint X hk,p (x) = Bk .
(55)
p∈Pk
Intuitively, (54) says a route is recalled if it was requested at least once in the “recent” time window of length Tk (x). Step 1b: LRU→TTL accuracy and an explicit rate under Poissonized requests. Step 1 replaces the LRU recall list by a TTL cache with a single characteristic time Tk (x). This approximation is not merely heuristic: for large caches and large catalogs, an LRU cache becomes asymptotically equivalent to a TTL cache with an appropriately chosen characteristic time. We record a specialization of the convergence and rate results of [Jiang et al., 2018]. Theorem 15 (LRU→TTL accuracy for individual hit probabilities). Fix a commodity k and let n ≜ |Pk |. Assume that route requests for distinct p ∈ Pk are described by mutually independent stationary and ergodic point processes with intensities {λk,p }p∈Pk , and let the LRU cache size satisfy Bk = Bk (n) → ∞ as n → ∞. Let Tk,n denote the LRU characteristic time (the unique TTL timer value) defined by the occupancy equation X TTL Bk = Hk,p (Tk,n ), (56) p∈Pk TTL TTL where Hk,p (t) is the TTL “in-cache” probability of route p at timer t (for Poisson requests, Hk,p (t) = 1 − e−λk,p t ). LRU Let Hk,p (n) be the stationary LRU hit probability of route p.
Under the regularity conditions of [Jiang et al., 2018, Prop. 4.4], LRU TTL max Hk,p (n) − Hk,p (Tk,n ) −→ 0
p∈Pk
as n → ∞.
Moreover, under the Poisson request model, Jiang et al. [2018, Prop. 5.2 and Ex. 5.3] give the explicit bound ! r log Bk LRU TTL max Hk,p (n) − Hk,p (Tk,n ) = O . p∈Pk Bk
(57)
(58)
Proof idea. This is a direct translation of the LRU→TTL approximation results of Jiang et al. [2018]: the occupancy equation defines the characteristic time, and their propositions bound the uniform gap between LRU hit probabilities and the corresponding TTL in-cache probabilities. We verify that our request-process hypotheses match theirs and map notation. Full proof is deferred to Appendix A.15. 27
Implication for the micro→salience surrogate. Under the TTL approximation, availability indicators are independent across routes whenever the underlying request point processes are independent, because membership in the TTL cache is “route-local” (it depends only on the route’s own request history). Thus, Assumption 5 is exact for TTL and becomes asymptotically accurate for LRU by Theorem 15. In the Poissonized repeated-choice regime (i.i.d. route labels with intensities proportional to stationary choice probabilities), p the additional approximation error incurred by replacing LRU recall probabilities with TTL probabilities is of order log Bk /Bk . Step 2: from recall frequencies to an effective salience. Define the stationary availability probability of route p as ηk,p (x) ≜ Pr{p ∈ A} = hk,p (x) + 1 − hk,p (x) ρk (p), (59) since p is available either because it is recalled, or because it is surfaced when not recalled. The unconditional stationary choice probability under random availability is 1{p ∈ A} exp(−βLp (x)) P πk,x (p) = E . r∈A exp(−βLr (x))
(60)
This is a “random attention” logit: logit applied to a random menu A. Proposition 8 (Availability-weighted logit approximation). Fix k andPx and assume all routes have strictly positive availability ηk,p (x) > 0. Let wp ≜ exp(−βLp (x)) and let Z ≜ r∈A wr denote the random denominator in (60). AssumeP A is almost surely nonempty (equivalently, Z > 0 almost surely). pIf Z concentrates around its mean µ ≜ E[Z] = r ηk,r (x)wr in the sense that the coefficient of variation cv(Z) ≜ Var(Z)/µ is small and maxp wp /µ is small, then ηk,p (x) exp(−βLp (x)) wr πk,x (p) = P + O cv(Z)2 + max . (61) r µ r∈Pk ηk,r (x) exp(−βLr (x)) In particular, when the available set contains many routes with non-negligible weight (e.g., large Bk ), the error term in (61) is small. P Proof idea. Write π(p) = E[1{p ∈ A}wp /Z] with Z = r∈A wr and expand 1/Z around 1/µ on the high-probability event |Z − µ| ≤ µ/2. Control the remainder using the coefficient of variation of Z and bound the effect of including a single term wp via wp /µ. This yields the stated error bound. Full proof is deferred to Appendix A.16. Assumption 5 (Independent-availability menu model (with nonempty menu)). Fix a commodity k and an aggregate load state x. To avoid degenerate empty-menu events (which make the logit denominator undefined), assume there exists a designated baseline route p0 ∈ Pk that is always available, i.e., p0 ∈ A almost surely (equivalently ηk,p0 (x) = 1). For each other route p ∈ Pk \{p0 }, the availability indicators {1{p ∈ A}} are independent Bernoulli random variables with Pr(p ∈ A) = ηk,p (x). Equivalently, the menu is generated as A = {p0 } ∪ S where S includes each p ̸= p0 independently with probability ηk,p (x). This surrogate is exact for TTL-type caches with independent request processes conditional on an always-available baseline (e.g., the last chosen route),pand by Theorem 15 it becomes asymptotically accurate for LRU recall in the large-cache regime (with an explicit log B/B rate under Poissonized requests). When one does not want to single out a baseline route, an equivalent workaround is to sample all routes independently and condition on A ̸= ∅; in the large-menu regime of interest, Pr(A = ∅) is negligible and the conditioning has vanishing effect on our concentration bounds. Lemma 7 (A simple concentration proxy under independent availability). Under Assumption 5, let wp ≜ P P exp(−βLp (x)), wmax ≜ maxp wp , and Z ≜ r∈A wr . Then with µ ≜ E[Z] = p ηk,p (x)wp , Var(Z) ≤ wmax µ,
and hence
cv(Z)2 ≤
wmax . µ
(62)
Moreover, maxp wp /µ = wmax /µ. P P P Proof. Write Z = p wp 1{p ∈ A}. Independence gives Var(Z) = p wp2 ηk,p (x) 1 − ηk,p (x) ≤ p wp2 ηk,p (x). P Since wp2 ≤ wmax wp , we obtain Var(Z) ≤ wmax p ηk,p (x)wp = wmax µ. The remaining statements are immediate from definitions. 28
Corollary 7 (An explicit 1/B-type rate under bounded costs and large menus). Fix k and assume the feasible load region X is compact so that path costs are uniformly bounded: Lp (x) ∈ [Lmin , Lmax ] for all x ∈ X and all p ∈ Pk . Then wp ∈ [wmin , wmax ] with wmin = e−βLmax and wmax = e−βLmin . If the policy ensures that the available set has size at least B almost surely (e.g., an LRU recall list of size B with an additional surfaced candidate), then µ = E[Z] ≥ B wmin and hence wmax wmax eβ(Lmax −Lmin ) ≤ = . (63) µ B wmin B Combining Proposition 8 with Lemma 7 yields an explicit large-B regime in which the availability-weighted logit surrogate (61) is accurate: the approximation error decays at least on the order of eβ(Lmax −Lmin ) /B whenever Lmax − Lmin is bounded. Proof idea. Bounded costs imply wp ∈ [wmin , wmax ]. If |A| ≥ B a.s., then µ = E[Z] ≥ Bwmin , hence wmax /µ ≤ eβ(Lmax −Lmin ) /B. Lemma 7 gives cv(Z)2 ≤ wmax /µ, and substituting into Proposition 8 yields an O(1/B) error. Full proof is deferred to Appendix A.17. Corollary 8 (A combined large-B rate under LRU recall). Fix k and assume the bounded-cost conditions of Corollary 7. Assume further that the LRU recall list of size Bk is generated by a Poissonized request stream satisfying the hypotheses of Theorem 15. Then, in the large-cache regime, the stationary micro choice probabilities are well-approximated by the TTL–salience fixed-point surrogate obtained by coupling (54)–(55) with the availability-weighted logit map (61), with a total approximation error of the form ! r β(Lmax −Lmin ) log B e k micro TTL-salience πk,x − πk,x ≤ O + O . (64) 1 Bk Bk The first term is the random-attention (random-denominator) error controlled by menu size (Proposition 8 and Lemma 7); the second term is the LRU→TTL cache approximation error (Theorem 15). Proof idea. Decompose the micro-to-surrogate error into (i) a random-menu (availability-weighted logit) approximation term and (ii) an LRU→TTL cache approximation term. Apply Corollary 7 to bound (i) and Theorem 15 to bound (ii), then combine via the triangle inequality. Full proof is deferred to Appendix A.18. Remark 21 (Interpretation). Equation (61) shows that, beyond the exact Bk = 1 case, salience-weighted logit remains a principled approximation: the effective salience weight is the stationary availability probability ηk,p (x) induced by the memory policy. Combining (54)–(55) with (61) yields an explicit fixed-point surrogate for LRU-type memory with Bk > 1 that can be used for equilibrium computation and for policy design. Algorithm 3 avoids enumerating the factorial-sized memory state space (Remark 17) by tracking only per-route frequencies. It is the computational primitive used in our synthetic validations (Section 12) and is the natural workhorse if one wants to optimize governed salience policies while retaining a micro-founded interpretation for Bk > 1. Theorem 16 (Uniqueness and global stability beyond contraction). Under the conditions of Proposition 1, SW-SUE exists and is unique. Moreover, any algorithm that globally minimizes Φs over F (e.g., projected gradient descent, mirror descent, or Frank–Wolfe on the Beckmann term with entropic regularization) converges to the unique equilibrium. Proof idea. Proposition 1 shows SW-SUE coincides with the unique minimizer of a strictly convex potential Φs . Existence and uniqueness are therefore immediate. Any method that globally minimizes Φs converges to this unique minimizer by definition of global convergence for convex optimization. Full proof is deferred to Appendix A.19. Remark 22 (Connection to the explicit memory model). The explicit memory model in Section 7.3 induces random consideration sets. In regimes with fast mixing (Assumption 3) and high-frequency AI surfacing, these random consideration effects can often be summarized as persistent route-specific salience biases (e.g., via stationary retrieval frequencies). Theorems 1–16 therefore provide a tractable “design layer” for memory/guidance optimization even when the underlying microdynamics are more complex. 9.2
Limitations of the salience abstraction and the B > 1 micro→salience bridge
The stationary salience model is deliberately a reduced form. It is the right “design layer” if the platform can directly manipulate exposure/utility biases (ranking, recommendations, interface architecture), and it is exactly micro-founded for B = 1 (Theorem 1 and Corollary 2). For richer memories (B > 1), the LRU→TTL→availability→salience bridge (Section 9.1) should be interpreted as a mean-field approximation and may be inaccurate outside the regimes that make its assumptions plausible. 29
Algorithm 3 Scalable TTL–salience surrogate for Bk > 1 (mean-field equilibrium solver) 1: Input: initial x(0) ∈ X , damping η ∈ (0, 1], tolerances εx , επ (0)
2: Initialize πk on Pk for each commodity k (e.g., uniform) 3: for t = 0, 1, 2, . . . until convergence do 4: for each commodity k ∈ K do 5: 6: 7: 8: 9: 10: 11:
(t)
Find Tk ≥ 0 such that
P
p∈Pk
(t)
(t)
1 − e−πk (p) Tk
= Bk (bisection)
(t) (t) (t) hk,p ← 1 − e−πk (p) Tk for all p ∈ Pk (t) (t) (t) ηk,p ← hk,p + (1 − hk,p ) ρk (p) (t+1) (t) πk (p) ∝ ηk,p exp − βLp (x(t) ) for all p ∈ Pk
(TTL recall) (availability) (AWL update)
end for Form path flows f (t+1) from π (t+1) and compute x̃(t+1) ← x(f (t+1) ) Damped update: x(t+1) ← (1 − η)x(t) + η x̃(t+1) (t+1) (t) 12: if ∥x(t+1) − x(t) ∥∞ ≤ εx and maxk ∥πk − πk ∥1 ≤ επ then 13: break 14: end if 15: end for 16: Output: (x(t+1) , π (t+1) , h(t+1) , η (t+1) )
When the bridge can fail. The technically vulnerable points are: (i) non-i.i.d. requests / slow mixing: the Poissonization device and caching approximations assume the chosen-route sequence is close to an i.i.d. label stream over the time scale relevant for recall; this can fail under strong day-to-day nonstationarity or path-dependent learning; (ii) correlated availability: LRU recall indicators are generally correlated across routes, and the independent-menu model (Assumption 5) is only justified asymptotically (Theorem 15); (iii) small menus or steep utilities: the random-denominator bounds in Proposition 8 can have large constants when β(Lmax − Lmin ) is large, so “O(1/B)” rates can be numerically loose unless costs are well behaved; and (iv) beliefs vs. consideration: we model memory as shaping consideration sets but not beliefs about Lp (x) (Section 7.3); settings in which memory stores cost estimates or induces systematic belief biases require an additional information layer. Interpretation for design claims. Accordingly, the strongest implementability and governance theorems in Sections 5 and 6 are stated for the stationary salience layer. They can be operationalized directly as interface/ranking interventions, and (in the micro model) they are guaranteed to be realizable without loss only in the B = 1 regime. Characterizing the micro-realizable subset of salience vectors for richer eviction/retention policies, and proving micro-level implementability beyond B = 1, are important directions for future work.
10
Value of Recall for Routing
We now propose a routing analogue of the Value of Recall (VoR) metric used in imperfect-recall games and memoryaware network dynamics [Alqithami, 2025b]. Let J(δ) denote a welfare objective under equilibrium at recall factor δ; for example: J(δ) = C f ⋆ (δ) , the total latency at the (appropriate) equilibrium f ⋆ (δ). Definition 11 (Value of Recall for routing (VoR-R)). Define VoRrouting (δ) =
J(δ) . J(1)
Values VoRrouting (δ) < 1 indicate that imperfect recall (at δ) improves welfare relative to perfect recall. Remark 23. If one prefers a “higher is better” utility convention, take U (δ) = −J(δ) and compute U (1)/U (δ), matching the ratio form in [Alqithami, 2025b]. 30
11
Recall Braess Paradox: Definition and Sharp Instances
This section isolates the core paradoxical effect we care about: equilibrium delay can increase when recall improves, even though the physical network is unchanged. Unlike classic Braess’ paradox, the mechanism here is informational and policy-driven. 11.1
Welfare and the Recall Braess Paradox (RBP)
For any edge-load vector x ∈ X , define the standard total travel time (social cost) X SC(x) ≜ xe ℓe (xe ).
(65)
e∈E
Let θ denote a recall-policy parameter (e.g., memory budget, reset rate, summary frequency, or a parameter of the surfacing distribution). Assume for each θ the FWE is unique, yielding x⋆ (θ). For each θ, let Ak,θ denote the (random) available set presented to a representative infinitesimal traveler of commodity k at stationarity (the realized menu A(m, q) in the micro model, or the deterministic set Pk (θ) in the static recall baseline). Define the menu-inclusion probabilities hk,θ (p) ≜ Pr{p ∈ Ak,θ },
p ∈ Pk .
We use the following canonical recall-richness order. Definition 12 (Recall-richness order (menu inclusion)). We say θ2 is (weakly) more recall-rich than θ1 , written θ2 ⪰ θ1 , if for every commodity k and every path p ∈ Pk , hk,θ2 (p) ≥ hk,θ1 (p). We write θ2 ≻ θ1 if θ2 ⪰ θ1 and strict inequality holds for at least one pair (k, p). A stronger sufficient condition is almost sure menu inclusion: Ak,θ1 ⊆ Ak,θ2 almost surely for all k, which implies θ2 ⪰ θ1 . Definition 13 (Recall Braess Paradox (social form)). A Recall Braess Paradox occurs if there exist θ1 , θ2 such that θ2 ≻ θ1 in the recall-richness order of Definition 12, yet SC(x⋆ (θ2 )) > SC(x⋆ (θ1 )) . The next results show that RBP is not a pathological artifact of exotic topologies: it can arise on the simplest possible series-parallel network. 11.2
A sharp analytic instance: Pigouvian forgetting on the Pigou network
Consider the two-link Pigou network: a single OD pair with total demand 1 and two parallel edges. Edge a has constant latency ℓa (x) = 1 and edge b has latency ℓb (x) = x. Under full recall (standard Wardrop), all flow routes to edge b and the equilibrium social cost is SC = 1. The system optimum splits flow evenly (xa = xb = 12 ) and achieves SC = 34 . We now introduce a uniform recall-suppression policy parameterized by α ∈ [0, 1]: in each period, an α fraction of agents do not recall (or are not shown) edge b and therefore must choose edge a; the remaining 1 − α fraction have full recall and choose selfishly. This is implementable in our framework by a memory reset/surfacing policy that, with probability α, makes A(m, q) = {a} and otherwise A(m, q) = {a, b}. Theorem 17 (Pigouvian forgetting implements the system optimum). In the Pigou network with ℓa (x) = 1 and ℓb (x) = x, the induced (information/recall constrained) equilibrium under recall-suppression level α routes xa = α and xb = 1 − α, and the resulting social cost is SC(α) = α + (1 − α)2 = 1 − α + α2 . The minimizer is α⋆ = 21 , yielding SC(α⋆ ) = 43 (the system optimum). Moreover, α = 0 ≻ α = 12 in the sense of Definition 12, yet improving recall from α = 12 to α = 0 increases equilibrium social cost from 34 to 1; hence a Recall Braess Paradox occurs even on a series-parallel network. Proof. Given α, an α mass must use edge a. All remaining mass has access to both edges. Since ℓb (1 − α) = 1 − α ≤ 1 = ℓa (α), all unconstrained agents strictly prefer b (or are indifferent at α = 0). Thus (xa , xb ) = (α, 1 − α). Substituting into (65) yields SC(α) = α · 1 + (1 − α) · (1 − α). The minimizer follows by differentiation. 31
Remark 24 (Why this is a “Braess” phenomenon). Classic Braess’ paradox requires a non-series-parallel structure for two-terminal networks, whereas the Pigou network is series-parallel. The inefficiency here is not caused by adding physical capacity; it is caused by improving recall, which shifts behavior toward the selfish equilibrium and away from the system optimum. 11.3
Generalization: one constant link and one increasing link
The Pigou example is not an isolated curiosity. It illustrates a general mechanism: when private and social marginal costs differ, calibrated information friction can mimic a corrective Pigouvian toll. Proposition 9 (Optimal recall suppression on a generalized Pigou network). Consider a two-link parallel network with demand 1, where ℓa (x) = c is constant and ℓb (x) = g(x) is continuously differentiable, strictly increasing, and satisfies g(0) = 0. Suppose further that g(1) ≤ c so that the full-recall Wardrop equilibrium routes all flow on b. Let y opt ∈ (0, 1) denote the system-optimal flow on edge b, i.e., a minimizer of min c(1 − y) + y g(y). y∈[0,1]
Then the recall-suppression policy with level α⋆ = 1 − y opt implements the system optimum as an equilibrium and strictly improves over full recall whenever y opt < 1. Proof idea. Under suppression level α, equilibrium sends α mass on the constant link and 1 − α on the increasing link. The resulting social cost is an explicit convex quadratic in α, minimized at α⋆ = 1/2 (the system-optimal split), which proves both optimality and the non-monotonicity in recall. Full proof is deferred to Appendix A.8. Proposition 9 shows that calibrated recall friction can act as a Pigouvian correction in the simplest canonical networks. We next (i) identify a network class theorem showing that social-cost RBP is essentially ubiquitous whenever users have any nontrivial route choice, and (ii) formalize implementability as an inverse-equilibrium problem for memory/guidance policies. 11.4
Network classes: ubiquity and immunity for social RBP
We now show that, under the social-cost notion in Definition 13, paradoxical non-monotonicity in recall is not confined to exotic graph topologies. Definition 14 (Choiceful vs. series two-terminal networks). A two-terminal directed network (G, s, t) is series if there is a unique simple s–t path. Otherwise, it is choiceful (there exist at least two distinct simple s–t paths). Theorem 18 (Ubiquity of social Recall Braess Paradox). Let (G, s, t) be a choiceful two-terminal network. Then there exist continuous nondecreasing edge latencies (ℓe )e∈E , total demand d = 1, and two recall policies θ1 , θ2 such that θ2 ≻ θ1 in the menu-inclusion order of Definition 12 and yet SC(x⋆ (θ2 )) > SC(x⋆ (θ1 )). Equivalently, social-cost RBP can occur on every choiceful two-terminal network. Conversely, if (G, s, t) is series (unique s–t path), then for any latencies and any recall policy, the induced flow is unique and invariant; social-cost RBP cannot occur. Proof idea. Any choiceful two-terminal network contains two distinct s–t paths; by penalizing all other edges, one can embed a Pigou subinstance where recall-suppression changes the equilibrium split. This yields an instance with higher cost under increased recall; conversely, series networks admit no choices so recall policies cannot affect flows. Full proof is deferred to Appendix A.9. Remark 25 (Interpretation). Theorem 18 separates our social-cost notion from topology-based immunity results for classic Braess’ paradox (which does not occur on series-parallel networks) and from group-harm informational paradox notions. Under social cost, any nontrivial route choice admits a Pigou-type externality that can be mitigated by calibrated information friction.
12
Experiments and Evaluation
12.1
Goals and overview
Top-tier venues typically expect (i) clear implementation details, (ii) stress tests of the modeling assumptions, (iii) comparisons against strong baselines, and (iv) evidence of computational scale. Our experiments are organized around six questions that map directly to the paper’s technical claims: 32
1. Micro-to-salience validity under endogenous congestion. When edge costs depend on flow, how accurately do the salience surrogates from Section 9.1 predict the stationary outcomes of the explicit memory model in Section 7.3? 2. Assumption validation for the LRU→TTL→salience bridge. Empirically quantify (a) discrete-time vs. Poissonization error (Lemma 6) and (b) LRU vs. TTL (Che) hit-probability error (Theorem 15) across popularity regimes. 3. Recall Braess phenomena beyond toy instances. Measure the incidence and magnitude of social-cost Recall Braess Paradox (RBP) under nested recall expansions on Pigou and Braess-like families (Section 11). 4. Governed design tradeoffs. Quantify the welfare–governance frontier: how equilibrium social cost changes with influence budgets (Definition 4) and with tying/fairness constraints (Theorem 4). 5. Implementability prediction accuracy. Validate that the implementability tests (Theorems 2–5) correctly predict which target behaviors can be induced, and quantify the slack required when exact feasibility fails. 6. Scalability. Demonstrate that the proposed solvers (e.g., the SP split-flow program of Theorem 11) scale to exponentially large path sets, and quantify when micro-level simulation becomes infeasible without surrogates. Reporting. Unless otherwise noted, we report mean ± standard deviation over random seeds/instances, and we report runtimes for both equilibrium computation and (when applicable) micro simulation. 12.2
Experimental setup and implementation details
Instance families. We evaluate on three tiers of instances: (i) canonical small networks (Pigou and Braess-type constructions) used for controlled diagnostics; (ii) synthetic families with controlled structure (parallel networks; two-terminal series-parallel (SP) networks); and (iii) “stress” instances generated by scaling path catalogs and influence budgets. In this draft we focus on synthetic families to provide clean stress tests that map directly to the paper’s theoretical claims; realistic multi-OD case studies are an important next step. Latency models. For synthetic instances we use affine latencies ℓe (xe ) = ae xe + be with (ae , be ) drawn from instance-specific ranges (described in each experiment). For the SP scaling experiment we use affine latencies on each edge. Micro model implementation. We simulate the explicit memory process from Section 7.3 under LRU (Definition 8) by agent-based simulation. Each “day” t: (i) given edge loads xt , each agent draws a surfaced route q ∼ ρk and chooses from A(m, q) via the logit rule (42); (ii) we aggregate chosen paths into path flows f t and update edge loads xt+1 = x(f t ); and (iii) each agent updates memory via LRU. Stationary quantities are estimated by time averaging after a burn-in. Surrogates and SW-SUE solver. We evaluate two surrogates from Section 9.1: (i) an oracle-availability surrogate that plugs micro-estimated availability probabilities η into the availability-weighted logit (AWL) approximation (61); and (ii) the fully endogenized TTL–salience fixed point (Algorithm 3). We compute SW-SUE (Definition 3) by minimizing the strictly convex potential Φs (Proposition 1) via projected gradient/mirror descent until the relative KKT residual falls below 10−6 . Governed design. For influence budgets and tying constraints we use the single-level reductions from Theorems 3 and 4 when applicable, and otherwise we optimize over policy parameters using gradient-based methods enabled by strict convexity (Proposition 1) and implicit differentiation (Theorem 14). 12.3
Exp-1: Micro vs. salience surrogates under endogenous congestion
Purpose. A central question is whether the reduced-form TTL–salience surrogate from Section 9.1 predicts stationary outcomes of the explicit memory process (Section 7.3) when costs are endogenously coupled to flows. Instances and protocol. We report two tiers. Canonical diagnostic (Pigou). We simulate the micro model on a Pigou network (two parallel routes) with demand 1, latencies ℓa (x) = x and ℓb (x) = 1 (config: β = 5, B = 2, 8000 agents, T = 3000 periods, burn-in 1000). Benchmark multi-OD instance (Sioux Falls). We use a standard transportation benchmark (Sioux Falls) [LeBlanc et al., 1975, Transportation Networks for Research Core Team] with multi-OD demand and BPR-type edge latencies [Bureau of Public Roads, 1964], restricting to the top-50 OD pairs by demand 33
Table 2: Exp-1: micro simulation vs. salience surrogates under endogenous congestion. “Rel. gap” reports (SCsur − SCmicro )/SCmicro . Instance Pigou (canonical) SiouxFalls (top-50 OD)
β 5.0 5.0
B 2 2
SCmicro 0.8199 9.52 × 105
SCTTL 0.8200 8.89 × 105
Rel. gap +0.001% -6.63%
ℓ1 (oracle) 7.34e − 05 0.295
ℓ1 (TTL-eq) 3.86e − 05 0.272
Time (s) 266 905
Figure 1: Exp-1 (Pigou): stationary choice shares under the micro model (left), oracle-availability AWL approximation (middle), and TTL–salience equilibrium prediction (right).
and generating Kpaths = 8 candidate routes per OD via k-shortest paths on free-flow time [Yen, 1971] (config: β = 5, B = 2, 800 agents per OD, T = 2000, burn-in 500). Comparators and metrics. We compare stationary micro outcomes to: (i) the oracle-availability AWL approximation that plugs micro-estimated availability probabilities P into (61), and (ii) the fully endogenized TTL–salience fixed point (Section 9.1). We report social cost SC(x) = e xe ℓe (xe ), ℓ1 errors in stationary path-share vectors, and wall-clock time for micro simulation. Results. Table 2 summarizes outcomes. On Pigou, the TTL–salience surrogate matches micro outcomes essentially exactly (as expected once B ≥ |P |). On Sioux Falls (top-50 OD, Kpaths = 8), the surrogate underestimates micro social cost by about 6.6% at (β, B) = (5, 2) and has nontrivial path-share error, consistent with the paper’s caution that the B > 1 bridge relies on approximations whose constants can degrade with overlap, heterogeneity, and near-deterministic choice. 12.4
Exp-2: Validating Poissonization and LRU→TTL accuracy regimes
Purpose. Section 9.1 uses two approximation layers: (i) a Poissonized request model to connect routing decisions to cache-theoretic approximations, and (ii) the TTL (Che) approximation for LRU recall probabilities (Theorem 15). Here we quantify the induced discrepancies between micro-observed recall statistics and the corresponding TTL predictions in a controlled setting. Instance and protocol. We consider a single-commodity parallel network with m = 6 routes and constant latencies b ∈ {0.5, 0.7, 0.9, 1.1, 1.3, 1.5} (config: β = 4.0, B = 3, N = 12000 agents, T = 4000, burn-in 1000). We simulate the micro model with LRU memory and estimate: (i) stationary path shares π micro and (ii) stationary recall probabilities hmicro . We then compute the TTL characteristic time T and the corresponding TTL predictions (hTTL , π TTL ). Results. In this regime, TTL predicts stationary choice shares accurately (∥π TTL − π micro ∥1 ≈ 0.026), while the corresponding hit-probability vector has larger ℓ1 discrepancy (∥hTTL − hmicro ∥1 ≈ 0.253). Figure 2 plots micro vs. TTL recall and choice statistics. 12.5
Exp-3: Recall Braess Paradox on the canonical Braess network
Purpose. Theorems 17–18 establish that increasing recall can increase equilibrium social cost (Recall Braess Paradox, RBP). Here we provide a direct micro-simulation illustration on the canonical Braess network by varying the memory budget B. 34
Figure 2: Exp-2: micro vs. TTL recall statistics on a controlled parallel instance. Top: recall/hit probabilities h (micro vs. TTL). Bottom: stationary choice shares π (micro vs. TTL). Table 3: Exp-3 (Braess): stationary micro social cost vs. memory budget B. “Rel. vs. B = 1” reports (SC(B) − SC(1))/SC(1). B
SC
Rel. vs. B = 1
Time (s)
1 2 3
1.6712 1.6912 1.6610
+0.000% +1.20% -0.61%
266 262 245
Instance and protocol. We simulate the micro model on the standard Braess network with demand 1 (config: β = 5, N = 8000 agents, T = 3000, burn-in 1000) for memory budgets B ∈ {1, 2, 3} (note that the candidate set has |P | = 3 simple s → t paths, hence B ≤ 3). Results. Table 3 and Figure 3 report the stationary micro social cost as a function of B. Social cost increases when recall expands from B = 1 to B = 2 (about +1.2% relative to B = 1), illustrating RBP in a minimal overlapping-path instance; increasing to B = 3 then reduces social cost in this configuration. 12.6
Exp-4: Governed design—welfare vs. influence budgets
Purpose. Section 5 characterizes implementability under influence budgets (Definition 4) and Section 6 develops equilibrium-aware design methods. Here we trace the welfare–governance frontier on a controlled parallel instance. 35
Figure 3: Exp-3 (Braess): stationary micro social cost vs. memory budget B (one seed).
Figure 4: Exp-4: governed design frontier on a parallel network. Instance and protocol. We consider a single-commodity parallel network with m = 5 routes and affine latencies ℓp (xp ) = ap xp + bp with (ap , bp ) given in the config file (demand 1, β = 5). For each influence budget R we solve the governed design problem and record the optimal equilibrium social cost. Results. Figure 4 plots the frontier SC∗ (R) and Table 4 reports the values. Social cost decreases monotonically in R and plateaus once R exceeds the minimal budget required by the target (here ≈ 3.87), consistent with Theorem 3. 12.7
Exp-5: Implementability prediction and required influence budgets
Purpose. Theorem 3 yields an explicit minimal influence budget R{ min}(f¯) required to implement a target behavior f¯ (under the salience model). Here we sample random interior target flows on the Braess instance and evaluate the resulting required budgets under an edge-additive tying class. Protocol. We sample n = 30 interior target path-flow vectors on the Braess network, compute the implied log-salience differences a(f¯), and evaluate the minimal ratio budget R{ min}(f¯). We then classify each target as feasible/infeasible under a fixed available budget R = 5. Results. At budget R = 5, only 4/30 targets are predicted feasible. The required budgets are heavy-tailed: median 38.54, 90th percentile 2.7 × 103 , and maximum 1.2 × 105 . Figure 5 plots the empirical CDF of R{ min}(f¯). 36
Table 4: Exp-4: social cost at the optimized governed equilibrium as a function of influence budget R. “Req. R” reports the minimal budget required by the optimal solution as predicted by Theorem 3. R
SC∗ (R)
Req. R
1.00 1.10 1.25 1.50 2.00 3.00 5.00 10.00
0.2943 0.2924 0.2902 0.2877 0.2851 0.2832 0.2829 0.2829
1.000 1.100 1.250 1.500 2.000 3.000 3.874 3.874
Figure 5: Exp-5: distribution of required influence budgets R{ min}(f¯) over random targets (log-scale x-axis). 12.8
Exp-6: Scalability on series-parallel networks
Purpose. We provide runtime evidence for the series-parallel (SP) split-flow approach (Theorem 11) compared to naive path enumeration, using the “diamond chain” SP family where the number of paths grows exponentially with network size. Instance family and protocol. We consider a chain of k diamond gadgets in series, yielding |E| = 2k edges and |P| = 2k s → t paths. For each k ∈ {4, 6, 8, 10, 12, 14, 16, 18} we compute the SW-SUE equilibrium using: (i) the SP split-flow solver, and (ii) a path-enumeration solver on the full path set. Results. Figure 6 and Table 6 show that the split-flow solver runs in sub-millisecond time across the sweep, while path enumeration becomes rapidly infeasible as |P| grows (hours by k = 18), even though both methods agree on the computed social cost.
13
Discussion and limitations
The paper deliberately separates exact design-layer results from approximate bridges back to micro-level memory dynamics (Section 1.5). Two limitations are worth highlighting. Behavioral scope of the salience abstraction. Stationary salience policies capture persistent, average effects of recall and guidance on menus, but do not directly model transient learning, endogenous formation of attention, or rich correlation structures in route availability. The approximation pipeline in Section 9.1 partially addresses this by endogenizing availability through TTL equations; nevertheless, regimes with highly concentrated popularity, neardeterministic choice (large β), or strong overlap across alternatives can require micro simulation or richer surrogates. From synthetic to real networks. Our experiments focus on synthetic instance families to provide controlled stress tests that align tightly with the theory (micro-to-salience accuracy, implementability frontiers, and SP scaling). A 37
Table 5: Exp-5: summary statistics for required influence budgets on random target behaviors. Quantity Samples n Feasible at R = 5 Median R{ min} 90th percentile R{ min} Maximum R{ min}
Value
Notes
30 4 / 30 38.54 2.7 × 103 1.2 × 105
random interior targets predicted by Theorem 3
Figure 6: Exp-6: runtime scaling on the diamond-chain SP family (split-flow vs. path enumeration). natural next step is to evaluate governed design and surrogate accuracy on benchmark transportation networks with multiple OD pairs and standard BPR-type latencies.
14
Conclusion
This working paper develops a policy-controlled notion of endogenous information in routing games, bridging microlevel memory dynamics (LRU recall and surfacing) with macro-level equilibrium analysis and design. The key technical idea is to expose an inverse map from target flows to required salience (log-salience equals log f + βL up to scale), which yields implementability tests and transforms governed policy design into optimization over implementable flows. On a nontrivial network class (parallel networks), bounded-influence optimal design reduces to a one-dimensional search plus convex subproblems. Near-term next steps are: (i) extending the tractable design results beyond parallel and series-parallel networks (e.g., graphs with low treewidth, decomposable route-set representations, or column-generation over path features); (ii) incorporating richer, feature-based tying constraints into efficient solvers; and (iii) validating the model on real route-choice datasets with controlled information interventions.
A
Deferred and extended proofs
This appendix collects complete proofs for results whose proofs are deferred from the main text. We retain the notation introduced in the main body. To minimize repetition across proofs, we make explicit a set of standing assumptions and conventions used throughout Appendix A; individual proofs only call out additional assumptions when needed. A.1
Standing assumptions and conventions for Appendix A
Unless explicitly stated otherwise, the arguments in this appendix use the following standing assumptions. A1 Finite path sets. For each commodity k ∈ K, the path set Pk is finite; hence the induced memory state space Mk is finite. P A2 Latency regularity. Each edge latency ℓe (·) is continuous and nondecreasing on [0, D], where D = k∈K dk is the total demand. When strict monotonicity or Lipschitz regularity is needed, it is stated explicitly. 38
Table 6: Exp-6: runtime scaling (milliseconds for split-flow; seconds for path enumeration). k
|P| = 2k
Split-flow (ms)
Path-enum (s)
4 6 8 10 12 14 16 18
16 64 256 1024 4096 16384 65536 262144
0.090 0.104 0.236 0.135 0.148 0.247 0.267 0.284
2.0 5.9 21.8 85.4 338.7 1362.0 5401.4 25625.9
A3 Finite logit temperature. In the dynamic-recall model, β < ∞ so every available route has strictly positive choice probability. In salience-weighted SUE results we assume β > 0. A4 Nonempty availability. Random menus/available sets are almost surely nonempty, so denominators such as P Z = r∈A wr are well-defined. (This is automatic in the endogenous-recall model because the surfaced route is always available.) A5 Full-support surfacing. In the endogenous-recall Markov chain, each surfacing distribution ρk has full support on Pk . A.2
Proof of Lemma 1
Proof. Fix a commodity k and a congestion vector x ∈ X . The state space Mk is finite. It therefore suffices to show (k) that the Markov chain with kernel Px is (i) irreducible and (ii) aperiodic. Irreducibility. Let m, m′ ∈ Mk be arbitrary. Write m′ = (p′(1) , . . . , p′(Bk ) ). Consider the event that for j = 1, 2, . . . , Bk the surfaced route equals q (j) = p′(Bk −j+1) . QBk Because ρk has full support on Pk , this surfacing sequence occurs with strictly positive probability j=1 ρk (q (j) ) > 0. (j) (j) (j) Conditional on this surfacing sequence, at each step j the route q belongs to the available set A(m , q ) by (41). Since β < ∞, the logit rule (42) assigns every available route strictly positive probability, hence σ q (j) | m(j) , q (j) , x > 0. Therefore the joint event that the traveler chooses the surfaced route at every step also has strictly positive probability (the product of these positive terms). Under the LRU update map Uk in Definition 8, whenever the chosen route is not already in the current recalled list it is inserted at the front (and the last element is dropped). Starting from an arbitrary initial state m, after choosing q (1) = p′(Bk ) the first element becomes p′(Bk ) ; after choosing q (2) = p′(Bk −1) the first two elements become (p′(Bk −1) , p′(Bk ) ); continuing for Bk steps yields exactly m(Bk +1) = (p′(1) , p′(2) , . . . , p′(Bk ) ) = m′ . Hence m′ is reachable from m with positive probability in Bk steps, implying irreducibility. Aperiodicity. Fix any state m = (p(1) , . . . , p(Bk ) ). For any surfaced route q, the route p(1) is always available because p(1) ∈ S(m) ⊆ A(m, q). Under logit with finite β, σ(p(1) | m, q, x) > 0. Moreover, under LRU, choosing the most-recent route leaves the ordered list unchanged: Uk (m, p(1) ) = m. Therefore X Px(k) (m | m) ≥ ρk (q) σ(p(1) | m, q, x) > 0, q∈Pk
so the chain admits a self-loop at every state and is aperiodic. Since Mk is finite and the chain is irreducible and aperiodic, it is ergodic and admits a unique stationary distribution πk (x) with full support. 39
A.3
Proof of Lemma 2
Proof. Fix a commodity k and let n ≜ |Mk |. For each x ∈ X , let Px denote the n × n transition matrix of the chain (with rows indexed by m ∈ Mk ). Under Assumption 1, each entry of Px is a continuous function of x because it is a finite sum of terms of the form ρk (q)σ(p | m, q, x) and x 7→ σ(· | m, q, x) is continuous (indeed smooth) whenever β < ∞ and x 7→ Lp (x) is continuous. By Lemma 1, for every x ∈ X the chain is ergodic and therefore has a unique stationary distribution. Let π(x) ∈ Rn denote the stationary distribution written as a column vector. It is the unique solution to the linear system Px⊤ π(x) = π(x), n×n
1⊤ π(x) = 1.
(66)
by taking I − Px⊤ and replacing its last row by 1⊤ , and define b ∈ Rn by bn = 1 and
Define the matrix Bx ∈ R bi = 0 for i < n. Then (66) is equivalent to
Bx π(x) = b. (67) Because the stationary distribution is unique, (67) has a unique solution, hence Bx is invertible. The mapping x 7→ Bx is continuous, and matrix inversion is continuous on the set of invertible matrices. Therefore x 7→ π(x) = Bx−1 b is continuous on X . A.4
Proof of Proposition 6
Proof. Fix a memory profile µ. Define the map Tµ : X → X by Tµ (x) ≜ x(f (µ, x)) , where f (µ, x) is defined in (43) and x(f ) is defined in (44). P Step 1: Tµ maps X into itself. For each commodity k, the induced path flows satisfy p∈Pk fk,p (µ, x) = dk because σ(· | m, q, x) is a probability distribution over A(m, q) and the outer sums in (43) preserve total mass. Therefore, for any edge e, X X X X X 0 ≤ xe (f (µ, x)) = fk,p (µ, x) 1{e ∈ p} ≤ fk,p (µ, x) = dk = D. k∈K p∈Pk
k∈K p∈Pk
k∈K
Hence Tµ (x) ∈ [0, D]|E| = X . Step 2: continuity. Under Assumption 1, the latency functions are continuous and the logit rule is continuous in the cost vector. Thus (µ, x) 7→ f (µ, x) is continuous because it is a finite sum of continuous functions. The edge-load map f 7→ x(f ) is linear, hence continuous. Therefore Tµ is continuous. Step 3: apply Brouwer. The set X is compact and convex. By Brouwer’s fixed point theorem, the continuous map Tµ : X → X admits a fixed point x ∈ X satisfying x = Tµ (x), which is exactly the congestion consistency condition (45). Therefore Ξ(µ) is nonempty. A.5
Proof of Theorem 12
Proof. Define π(x) ≜ (πk (x))k∈K and recall the reduced map T (x) ≜ x(f (π(x), x)) . Step 1: continuity of T . By Lemma 2, each x 7→ πk (x) is continuous; thus x 7→ π(x) is continuous. As in the proof of Proposition 6, the map (µ, x) 7→ f (µ, x) is continuous and f 7→ x(f ) is linear. Therefore T is continuous on X . Step 2: T maps X into itself. The same argument as in Proposition 6 shows that for any x ∈ X , all edge loads in T (x) lie in [0, D], hence T (x) ∈ X . Step 3: apply Brouwer and verify the FWE conditions. By Brouwer’s fixed point theorem, there exists x⋆ ∈ X such that x⋆ = T (x⋆ ). Define µ⋆ ≜ π(x⋆ ). By definition of πk (x⋆ ), for each commodity k the distribution µ⋆k is stationary for the memory kernel induced by x⋆ , i.e., it satisfies the stationarity requirement in Definition 10. Moreover, x⋆ = T (x⋆ ) is precisely the within-period congestion consistency condition with µ⋆ . Hence (x⋆ , µ⋆ ) is a forgetful Wardrop equilibrium. 40
A.6
Proof of Proposition 1
Proof. Fix a salience policy s and recall the feasible set n o X F = f ≥0: fk,p = dk ∀k ∈ K . p∈Pk
Step 1: strict convexity and existence of a unique minimizer. The Beckmann term f 7→ convex because each ℓe is nondecreasing and xe (f ) is linear in f . The entropic term 1X f 7→ fk,p log fk,p − log sk,p β
P
R xe (f )
e∈E
0
ℓe (u) du is
k,p
is strictly convex on F when β > 0 because z 7→ z log z is strictly convex on R>0 and sk,p > 0. Therefore Φs is strictly convex on the convex set F and can have at most one minimizer. Moreover, F is a product of simplices and is compact, and Φs is continuous on F (taking 0 log 0 = 0), so a minimizer exists. Hence Φs admits a unique minimizer f ⋆ ∈ F. ⋆ Step 2: first-order conditions yield SW-SUE. We show that the minimizer is interior, i.e., fk,p > 0 for all k, p. ⋆ ⋆ Fix any commodity k and any path p. If fk,p = 0, then for any ϵ > 0 and any r ∈ Pk with fk,r > 0 (which must P ⋆ exist because p fk,p = dk > 0), consider shifting ϵ mass from r to p while preserving feasibility. The directional derivative of the entropic term in the p-direction diverges to −∞ as fk,p ↓ 0, implying that such a perturbation strictly decreases Φs for sufficiently small ϵ, contradicting optimality. Therefore f ⋆ is interior.
For interior points, the KKT conditions are necessary and sufficient. Let x⋆ = x(f ⋆ ). The derivative of the Beckmann term with respect to fk,p equals the path latency: Z X ∂ X xe (f ) ℓe (u) du = ℓe (x⋆e ) = Lp (x⋆ ). ∂fk,p 0 e∈p e∈E
⋆ The derivative of the entropic term is β1 (log fk,p + 1 − log sk,p ). Introducing Lagrange multipliers λk for the equality P constraints p∈Pk fk,p = dk , the first-order conditions read 1 ⋆ Lp (x⋆ ) + log fk,p + 1 − log sk,p + λk = 0 ∀k ∈ K, ∀p ∈ Pk . β Rearranging yields ⋆ fk,p = sk,p exp − β(Lp (x⋆ ) + λk ) e−1 . P ⋆ Using p∈Pk fk,p = dk to eliminate λk shows that for each commodity k,
sk,p exp(−βLp (x⋆ )) , ⋆ r∈Pk sk,r exp(−βLr (x ))
⋆ fk,p = dk P
which is precisely the SW-SUE condition in Definition 3. Step 3: equivalence. Conversely, any flow satisfying the SW-SUE fixed point satisfies the KKT system above and therefore minimizes Φs . By uniqueness of the minimizer, the SW-SUE is unique and equals f ⋆ . A.7
Proof of Lemma 4 (k)
Proof. Fix a commodity k and write Px for Px and π(x) for πk (x) to lighten notation. Assumption 3 implies the minorization Px (· | m) = εk νk (·) + (1 − εk ) Pex (· | m) ∀m ∈ Mk , e for some stochastic kernel Px (obtained by renormalizing the residual probabilities). Let α, β be any two distributions on Mk . Then αPx − βPx = (1 − εk ) αPex − β Pex ,
Step 1: a contraction inequality under Doeblin.
because the common term εk νk cancels. Since multiplication by a stochastic matrix is nonexpansive in ℓ1 , ∥αPex − β Pex ∥1 ≤ ∥α − β∥1 , hence ∥αPx − βPx ∥1 ≤ (1 − εk ) ∥α − β∥1 . (68) 41
Step 2: perturbation bound for stationary distributions. π(y) = π(y)Py , we write
Let x, y ∈ X . Using stationarity, π(x) = π(x)Px and
π(x) − π(y) = π(x)Px − π(y)Py = (π(x) − π(y))Px + π(y)(Px − Py ). Taking ℓ1 norms and applying (68) gives ∥π(x) − π(y)∥1 ≤ ∥(π(x) − π(y))Px ∥1 + ∥π(y)(Px − Py )∥1 ≤ (1 − εk )∥π(x) − π(y)∥1 + ∥π(y)(Px − Py )∥1 . Rearranging yields ∥π(x) − π(y)∥1 ≤
1 ∥π(y)(Px − Py )∥1 . εk
Finally, π(y) is a convex combination of rows, hence X ∥π(y)(Px − Py )∥1 = π(y)(m) Px (· | m) − Py (· | m) m∈Mk
≤ 1
sup m∈Mk
Px (· | m) − Py (· | m) 1 ,
which proves the first inequality in Lemma 4. Step 3: an explicit Lipschitz constant in ∥x − y∥∞ . Fix m ∈ Mk . Using the definition (46) and the fact that the update map Uk is deterministic, the distribution Px (· | m) is a pushforward of the logit choice distribution on the available set. Therefore, for each surfaced route q, Px (· | m, q) − Py (· | m, q) 1 ≤
σ(· | m, q, x) − σ(· | m, q, y) 1 ,
and after averaging over q ∼ ρk we obtain Px (· | m) − Py (· | m) 1 ≤ sup σ(· | m, q, x) − σ(· | m, q, y) 1 . q∈Pk
By Lemma P3, the logit map is β-Lipschitz from ∥ · ∥∞ costs to ∥ · ∥1 probabilities. For any route p, the path cost is Lp (x) = e∈p ℓe (xe ). Under Assumption 2, X X L |xe − ye | ≤ |p| L ∥x − y∥∞ ≤ HL ∥x − y∥∞ . |Lp (x) − Lp (y)| ≤ |ℓe (xe ) − ℓe (ye )| ≤ e∈p
e∈p
Combining these bounds yields sup m∈Mk
Px (· | m) − Py (· | m) 1 ≤ β HL ∥x − y∥∞ .
Substituting into the first inequality proves the second inequality with Ck = βHL/εk . A.8
Proof of Proposition 9
Proof. Let y ∈ [0, 1] denote the flow routed on edge b (so 1 − y is routed on edge a). The total travel time (social cost) is SC(y) = c(1 − y) + y g(y). Since g is continuously differentiable and strictly increasing, any interior minimizer y opt ∈ (0, 1) satisfies the first-order condition d SC(y) = −c + g(y) + yg ′ (y) = 0. (69) dy Because g ′ (y opt ) > 0 and y opt > 0, (69) implies g(y opt ) = c − y opt g ′ (y opt ) < c. Now consider the recall-suppression policy with α⋆ = 1 − y opt . By definition, an α⋆ fraction of agents cannot access edge b and must choose a, so xa = α⋆ . The remaining mass 1 − α⋆ = y opt has access to both edges. At the flow profile (xa , xb ) = (α⋆ , y opt ), the latency on b equals g(y opt ) < c = ℓa , so every agent with access to both edges strictly prefers b. Hence the unique equilibrium under this policy routes exactly y opt flow on b, matching the system optimum. Finally, if y opt < 1, then α⋆ > 0 and the equilibrium under full recall (α = 0) routes all flow on b by assumption g(1) ≤ c. Since y opt minimizes SC(y), it follows that SC(y opt ) < SC(1) whenever y opt ̸= 1, proving strict improvement over full recall. 42
A.9
Proof of Theorem 18
Proof. We prove the two claims separately. Part I: choiceful networks admit social-cost RBP. Assume (G, s, t) is choiceful, so there exist at least two distinct simple s–t paths. Let P and Q be two such paths. Let u be the last common vertex on the shared prefix of P and Q (starting from s), and let v be the first vertex after u at which the paths meet again (possibly v = t). By construction, the subpaths P [u → v] and Q[u → v] are internally vertex-disjoint directed u–v paths. Moreover, P and Q share the same prefix from s to u and the same suffix from v to t. We now assign latencies so that the effective routing problem reduces to the Pigou network on the two u–v subpaths. Let M > 2 be a large constant. Set the latency of every edge not belonging to P ∪ Q equal to the constant M (independent of flow). Set the latency of every edge on the common prefix s → u and common suffix v → t equal to 0. On the subpath P [u → v], set all edges to have zero latency except for one designated edge ea on that subpath, for which we set a constant latency ℓea (x) = 1. On the subpath Q[u → v], set all edges to have zero latency except for one designated edge eb on that subpath, for which we set ℓeb (x) = x. Because P [u → v] and Q[u → v] are internally vertex-disjoint, every unit of flow that chooses the Q route must traverse eb , so the flow on eb equals the total flow routed along Q. Similarly, the flow on ea equals the total flow routed along P . Therefore, within the subgraph induced by P ∪ Q, the two s–t path costs equal LP (x) = 1,
LQ (x) = xQ ,
where xQ is the flow on route Q. Any alternative s–t path that uses an edge outside P ∪ Q incurs cost at least M > 2, which is strictly dominated by both P and Q for all feasible flows (LP ≤ 1 and LQ ≤ 1). Thus in any Wardrop equilibrium (with or without recall suppression as defined below), no flow uses edges outside P ∪ Q, and the effective game reduces to the Pigou network with latencies ℓa (x) = 1 and ℓb (x) = x. Finally, define a nested recall family indexed by α ∈ [0, 1] as follows: an α fraction of agents can access only route P (equivalently, their feasible set is {P }), while the remaining 1 − α fraction can access both routes {P, Q}. This is a special case of the information/recall constrained model used in Theorem 17. By the Pigou calculation (Theorem 17), the induced equilibrium routes xP = α and xQ = 1 − α and the social cost is SC(α) = α + (1 − α)2 , minimized at α = 1/2. In particular, SC(0) = 1 > SC(1/2) = 3/4, so social-cost RBP occurs on (G, s, t). Part II: series networks are immune. If (G, s, t) is series, there is a unique simple s–t path. Hence every feasible flow (and every equilibrium under any recall policy) routes all demand along that path, yielding a unique and policyinvariant congestion vector and social cost. Therefore recall policies cannot change the equilibrium outcome, and social-cost RBP is impossible. A.10
Proof of Theorem 10
Proof. Let (G, s, t) be a two-terminal series-parallel (SP) network and fix generalized edge costs {ce }. For any two-terminal subnetwork H with terminals (sH , tH ), define its partition function X X ZH ≜ exp − β ce , e∈p
p∈P(H)
where P(H) is the set of all sH –tH paths in H. At the root H = G, this coincides with (34). Bottom-up recursion for ZH .
We proceed by structural induction along the SP decomposition tree.
Leaf edge. If H is a single edge e, then P(H) = {e} and ZH = exp(−βce ). Series composition. Suppose H = H1 ⊗ H2 , meaning that tH1 is identified with sH2 and every sH –tH path is the concatenation of a path in H1 and a path in H2 . Then X X X X ZH = exp − β ce exp − β ce = ZH1 ZH2 . p1 ∈P(H1 ) p2 ∈P(H2 )
e∈p1
e∈p2
Parallel composition. Suppose H = H1 ⊕ H2 , meaning that sH1 = sH2 = sH and tH1 = tH2 = tH and P(H) = P(H1 ) ∪ P(H2 ) (disjoint union). Then X X X X ZH = exp − β ce + exp − β ce = ZH1 + ZH2 . p∈P(H1 )
e∈p
p∈P(H2 )
43
e∈p
Thus, one can compute ZH for every node H in one bottom-up traversal, in total time linear in the number of nodes, i.e., O(|E|). Edge marginals via a top-down P probability pass. Let PG denote the Gibbs distribution on s–t paths in G with weight proportional to exp(−β e∈p ce ). For each node H in the SP tree, define wH as the probability that a random path p ∼ PG traverses the subnetwork H (equivalently, that p lies in the set of sH –tH paths of H once restricted to H). At the root, wG = 1. We propagate wH down the tree as follows. Series node H = H1 ⊗ H2 . Every sH –tH path is a concatenation of an H1 path and an H2 path. Therefore, conditional on traversing H, the random path necessarily traverses both children. Hence wH1 = wH2 = wH . Parallel node H = H1 ⊕ H2 . Conditional on traversing H, the random path chooses either H1 or H2 . The probability of choosing H1 equals the total Gibbs weight of paths in H1 divided by that in H, i.e., ZH1 /ZH ; similarly for H2 . Hence Z H2 Z H1 , wH2 = wH . wH1 = wH ZH ZH By induction on the tree, these recursions compute wH for every node in time O(|E|). Finally, for a leaf edge e (viewed as a leaf subnetwork), the event that the random path uses edge e is exactly the event that it traverses the leaf node corresponding to e. Therefore the edge marginal in (35) satisfies πe = we . This yields all edge marginals in linear time. A.11
Proof of Proposition 5
Proof. Fix recall sets {Pi }Ii=1 and demands {di }Ii=1 . Let FR denote the feasible set of (type-indexed) path flows n o X FR ≜ (fp(i) )i,p : fp(i) ≥ 0, fp(i) = di for each i . p∈Pi
This set is nonempty, compact, and convex. For f ∈ FR , define edge loads x(f ) by (44) and the Beckmann potential X Z xe (f ) Ψ(f ) ≜ ℓe (u) du. e∈E
0
Rx Because each ℓe is continuous, Ψ is continuous. Because each ℓe is nondecreasing, xe 7→ 0 e ℓe (u) du is convex, and since f 7→ x(f ) is linear, Ψ is convex on FR . Hence Ψ attains its minimum over FR at some f ⋆ . We now show that f ⋆ is an ICWE/RCWE in the sense of Definition 1. The partial derivative of Ψ with respect to a path (i) flow coordinate fp is X ∂Ψ (f ) = ℓe xe (f ) = Lp x(f ) , (i) ∂fp e∈p (i)
because increasing fp by an infinitesimal amount increases xe by the same amount on every edge e ∈ p. Applying the KKT conditions to the convex program minf ∈FR Ψ(f ) yields multipliers {λi }Ii=1 such that for each type i and each p ∈ Pi , Lp x(f ⋆ ) ≥ λi , with equality whenever fp⋆(i) > 0. Equivalently, every used path in Pi has minimum cost within Pi , which is exactly the ICWE/RCWE condition. Finally, R xassume there is a single origin–destination pair and each ℓe is strictly increasing on [0, d]. Then each map xe 7→ 0 e ℓe (u) du is strictly convex, so the aggregate potential is strictly convex in the edge-load vector x. If f ⋆ and f˜⋆ are two minimizers, then their edge loads must coincide: otherwise strict convexity would imply Ψ 21 f ⋆ + 12 f˜⋆ < 12 Ψ(f ⋆ ) + 12 Ψ(f˜⋆ ), contradicting optimality. Thus equilibrium edge loads are unique (though path flows may not be). 44
A.12
Proof of Corollary 1
Proof. Fix a congestion vector x. For Bk = 1, Theorem 1 shows that the stationary per-period route-choice probability for commodity k is ρk (p) exp(−βLp (x)) πk,x (p) = P . r∈Pk ρk (r) exp(−βLr (x)) In the coupled routing model, the induced stationary flow therefore satisfies ρk (p) exp(−βLp (x)) . r∈Pk ρk (r) exp(−βLr (x))
fk,p = dk πk,x (p) = dk P
Since the scaling of salience weights cancels in the logit rule, taking sk,p ∝ ρk (p) yields exactly the SW-SUE fixed-point condition (2). Thus the flow component of any coupled equilibrium is an SW-SUE with salience weights sk,p ∝ ρk (p). Uniqueness (and algorithmic stability) follows from Proposition 1, which shows the SW-SUE is the unique minimizer of a strictly convex potential. A.13
Proof of Corollary 2
P Proof. Fix strictly positive salience weights {sk,p } and define ρk (p) = sk,p / r∈Pk sk,r . For each commodity k with Bk = 1, Theorem 1 shows that the stationary within-period choice law induced by the micro model is a salience-weighted logit model with salience proportional to ρk . Because salience is defined only up to a per-commodity multiplicative constant, the choice law coincides exactly with the salience model with weights sk . Applying Corollary 1 then yields that the induced network equilibrium is the unique SW-SUE for salience s. For the final statement, let x̄ be any interior flow that is implementable by stationary salience in the sense of Theorem 2, and let s be a salience vector that implements x̄. Choosing ρ proportional to s as above makes the Bk = 1 micro model induce the same SW-SUE, hence implement x̄ without monetary tolls. A.14
Proof of Corollary 6
Proof. For each route p, Lemma 6 gives 0 ≤ HpWS (W ) − HpTTL (W ) ≤
πp2 W . 1 − πp
Therefore, sup HpWS (W ) − HpTTL (W ) ≤ p
1 sup π 2 W. 1 − πmax p p
Using πp2 W = (πp W )πp ≤ supr πr W πmax and the assumption supp πp W = O(1) yields sup HpWS (W ) − HpTTL (W ) ≤ O(1) · p
πmax = O(πmax ), 1 − πmax
as claimed. A.15
Proof of Theorem 15
Proof. The statement is a direct specialization of the asymptotic LRU → TTL equivalence results in Jiang et al. [2018]. In their notation, objects are indexed by i ∈ {1, . . . , n} with request intensities Pn λi , cache size Cn , and characteristic time Tn defined as the unique solution of the occupancy equation Cn = i=1 HiTTL (Tn ). Identifying objects with routes p ∈ Pk , setting Cn = Bk , and matching intensities λi = λk,p yields exactly (56). Under the regularity hypotheses of Jiang et al. [2018, Prop. 4.4], they show that the LRU hit probability of each object converges uniformly to the TTL in-cache probability at the characteristic time, i.e., maxi |HiLRU − HiTTL (Tn )| → 0 as n → ∞. This gives (57). LRU Under − HiTTL (Tn )| = p Poisson requests, Jiang et al. [2018, Prop. 5.2 and Ex. 5.3] provide the explicit rate maxi |Hi O( log Cn /Cn ). Substituting Cn = Bk yields (58).
45
A.16
Proof of Proposition 8
P Proof. Fix k and x, and write wp = exp(−βLp (x)). Let Ip ≜ 1{p ∈ A}, let Z ≜ r∈A wr denote the random P denominator in (60), and let µ ≜ E[Z] = r ηk,r (x)wr . By Assumption A4 (nonempty availability), Z > 0 almost surely. For a fixed route p ∈ Pk , ηk,p (x)wp 1 1 µ−Z πk,x (p) − = E Ip wp − = E Ip wp . µ Z µ µZ Let E ≜ {Z ≥ µ/2}. On E.
Since Z ≥ µ/2, we have 1/Z ≤ 2/µ and therefore Ip wp
2wp µ−Z ≤ 2 |Z − µ|. µZ µ
p Taking expectations and using E|Z − µ| ≤ Var(Z) yields µ−Z wmax 2wp E Ip wp 1E ≤ cv(Z) ≤ 2 cv(Z), µZ µ µ where wmax ≜ maxr∈Pk wr . On E c .
On {Z < µ/2} we use the simple bound Ip wp
Ip wp µ−Z µ ≤ Ip wp = ≤ 1, µZ µZ Z
because whenever Ip = 1 the denominator satisfies Z ≥ wp . Hence µ−Z E Ip wp 1E c ≤ Pr(Z < µ/2) ≤ Pr(|Z − µ| ≥ µ/2) ≤ 4 cv(Z)2 , µZ by Chebyshev’s inequality. Combining the two bounds yields πk,x (p) −
ηk,p (x)wp wmax ≤2 cv(Z) + 4 cv(Z)2 . µ µ
(70)
Finally, if wmax /µ ≥ 1, then the claimed error bound O(cv(Z)2 + wmax /µ) holds trivially because the left-hand side is at most 1. If instead wmax /µ ≤ 1, then 2(wmax /µ)cv(Z) ≤ (wmax /µ)2 + cv(Z)2 ≤ (wmax /µ) + cv(Z)2 , so (70) implies ηk,p (x)wp wmax 2 πk,x (p) = + O cv(Z) + . µ µ P Substituting µ = r ηk,r (x)wr yields (61). A.17
Proof of Corollary 7
Proof. Bounded costs imply wp ∈ [wmin , wmax ] for all p. If |A| ≥ B almost surely, then Z = almost surely, and hence also µ = E[Z] ≥ Bwmin . Therefore max p
P
r∈A wr ≥ Bwmin
wp wmax eβ(Lmax −Lmin ) ≤ = . µ Bwmin B
Under Assumption 5, Lemma 7 gives cv(Z)2 ≤ wmax /µ, hence cv(Z)2 = O(eβ(Lmax −Lmin ) /B) as well. Substituting these bounds into Proposition 8 yields an approximation error of order eβ(Lmax −Lmin ) /B. 46
A.18
Proof of Corollary 8
micro TTL-salience Proof. Let πk,x denote the stationary micro choice probabilities under LRU recall of size Bk , and let πk,x denote the surrogate obtained by (i) replacing LRU by the TTL characteristic-time approximation and (ii) replacing the TTL-menu random-attention logit by the availability-weighted logit map (61). Insert an intermediate surrogate πk,x that uses the TTL approximation for availability but still uses the exact random-attention logit (60). Then, by the triangle inequality, micro TTL-salience micro TTL-menu TTL-menu TTL-salience πk,x − πk,x ≤ πk,x − πk,x + πk,x − πk,x . 1 1 1 p The first term is precisely the cache approximation error, which is O( log Bk /Bk ) by Theorem 15. The second term is the random-menu (random-denominator) approximation error, which is O(eβ(Lmax −Lmin ) /Bk ) under the bounded-cost and large-menu conditions of Corollary 7. Combining yields (64).
A.19
Proof of Theorem 16
Proof. Proposition 1 shows that an SW-SUE is exactly a minimizer of the strictly convex potential Φs over the compact convex feasible set F. Since Φs is continuous, a minimizer exists; since Φs is strictly convex, the minimizer is unique. Therefore the SW-SUE exists and is unique. For the algorithmic statement, let {f (t) } be the iterates of any method that globally minimizes Φs over F (in the sense that Φs (f (t) ) ↓ minf ∈F Φs (f ) and every limit point is a minimizer). Because the minimizer is unique, every limit point equals the unique minimizer f ⋆ , and hence f (t) → f ⋆ . A.20
Proof of Lemma 3
Proof. Let A be a finite action set and define σ(· | c) ∈ ∆(A) by σ(a | c) = exp(−βca )/ c, c′ ∈ R|A| and set h = c′ − c. By the mean value theorem, Z 1 σ(· | c′ ) − σ(· | c) = J(c + th) h dt,
P
b∈A exp(−βcb ). Fix
0
where J(·) is the Jacobian of σ. A direct calculation gives ∂σ(a | c) Jab (c) = = −β σ(a | c) 1{a = b} − σ(b | c) . ∂cb P Fix any vector v with ∥v∥∞ ≤ 1 and let m ≜ b σ(b | c) vb . Then (J(c)v)a = −β σ(a | c) va − m , so X ∥J(c)v∥1 = β σ(a | c) |va − m| = β E |V − m| , a
where V is a random variable supported on p p{va } with law σ(· | c). Since V ∈ [−1, 1] and m = E[V ], Cauchy–Schwarz yields E[|V − m|] ≤ E[(V − m)2 ] = Var(V ) ≤ 1. Therefore ∥J(c)v∥1 ≤ β for all ∥v∥∞ ≤ 1, i.e., the operator norm ∥J(c)∥∞→1 ≤ β uniformly in c. Finally, ∥σ(· | c′ ) − σ(· | c)∥1 ≤
Z 1
∥J(c + th)∥∞→1 dt ∥h∥∞ ≤ β ∥c′ − c∥∞ ,
0
as claimed. A.21
Proof of Proposition 7
Proof. Fix x, y ∈ X . Recall T (x) = x(f (π(x), x)), where edge loads are linear in path flows (44). Let fx ≜ f (π(x), x) and fy ≜ f (π(y), y). Then for each edge e, X X |Te (x) − Te (y)| = |xe (fx ) − xe (fy )| ≤ |(fx )k,p − (fy )k,p | = ∥fx − fy ∥1 , k p∈Pk
so ∥T (x) − T (y)∥∞ ≤ ∥fx − fy ∥1 . We decompose ∥fx − fy ∥1 ≤ ∥f (π(x), x) − f (π(x), y)∥1 + ∥f (π(x), y) − f (π(y), y)∥1 . 47
Step 1: sensitivity to congestion for fixed memory. Fix µ and consider the map x 7→ f (µ, x). For each commodity k, each memory state m, and each surfaced candidate q, the logit choice probabilities σ(· | m, q, x) depend on x only through the menu path costs. Under Assumption 2, each edge latency is L-Lipschitz on X and each path contains at most H edges, hence max |Lp (x) − Lp (y)| ≤ HL ∥x − y∥∞ . p∈Pk
Applying Lemma 3 on the menu action set yields that, for each (m, q), σ(· | m, q, x) − σ(· | m, q, y) 1 ≤ β H L ∥x − y∥∞ . Averaging over m ∼ µk and q ∼ ρk and multiplying by demand dk in (43) gives ∥fk (µ, x) − fk (µ, y)∥1 ≤ dk β H L ∥x − y∥∞ . Summing over k yields ∥f (µ, x) − f (µ, y)∥1 ≤ D β H L ∥x − y∥∞ .
(71)
Step 2: sensitivity to memory for fixed congestion. Fix y and two memory profiles µ, µ′ . For each commodity k, the induced flow fk (µ, y) is a convex combination of probability vectors indexed by memory states m ∈ Mk . Therefore ∥fk (µ, y) − fk (µ′ , y)∥1 ≤ dk ∥µk − µ′k ∥1 . Taking µ = π(x) and µ′ = π(y) and using Lemma 4 yields X ∥f (π(x), y) − f (π(y), y)∥1 ≤ dk ∥πk (x) − πk (y)∥1 ≤ D max Ck ∥x − y∥∞ . k
k
(72)
Combining (71) and (72) yields ∥T (x) − T (y)∥∞ ≤ D β H L + max Ck ∥x − y∥∞ , k
which proves the claim with κ as in (51). A.22
Proof of Theorem 13
Proof. By Proposition 7, T is κ-Lipschitz on X with κ < 1. Because X is compact (hence complete) under ∥ · ∥∞ , T is a contraction mapping on a complete metric space. Banach’s fixed point theorem therefore implies that T has a unique fixed point x⋆ ∈ X . Moreover, for any initialization x(0) ∈ X , the iterates x(t+1) = T (x(t) ) converge to x⋆ at a geometric rate: ∥x(t) − x⋆ ∥∞ ≤ κt ∥x(0) − x⋆ ∥∞ . Setting µ⋆k = πk (x⋆ ) then yields a unique FWE (x⋆ , µ⋆ ). Finally, the flow iteration induced by x(t) converges as well because f (π(x), x) is continuous in x under Assumptions 1, 2, and Lemma 2. A.23
Proof of Theorem 14
Proof. Define F : X × Θ → R|E| by F (x, θ) ≜ Tθ (x) − x. By assumption, F is continuously differentiable. Moreover, ∇x F (x, θ) = ∇x Tθ (x) − I. ⋆
At (x , θ), the nondegeneracy condition (52) is exactly det(∇x F (x⋆ , θ)) ̸= 0, so ∇x F (x⋆ , θ) is invertible. Therefore, by the implicit function theorem, there exists a neighborhood U of θ and a unique continuously differentiable map θ′ 7→ x⋆ (θ′ ) on U such that F (x⋆ (θ′ ), θ′ ) = 0 for all θ′ ∈ U and x⋆ (θ) = x⋆ . Equivalently, x⋆ (θ′ ) is the unique fixed point of Tθ′ in a neighborhood of x⋆ . Differentiating the identity F (x⋆ (θ), θ) = 0 with respect to θ and rearranging yields ∇x F (x⋆ , θ) so
dx⋆ + ∇θ F (x⋆ , θ) = 0, dθ
−1 −1 dx⋆ = − ∇x F (x⋆ , θ) ∇θ F (x⋆ , θ) = I − ∇x Tθ (x⋆ ) ∇θ Tθ (x⋆ ), dθ
which is (53). 48
A.24
Proof of Corollary 4
Proof. At an SW-SUE with salience utilities u, the route-share vector for group k is fk,p exp(uk,p ) exp(−βLp (x)) =P . dk r∈P exp(uk,r ) exp(−βLr (x)) If salience is group-blind, then uk,p = uk′ ,p for all k, k ′ and all p, and the right-hand side is independent of k. Therefore fk,p /dk = fk′ ,p /dk′ for all groups and routes, proving the first claim. The non-implementability of targets with heterogeneous route shares across groups follows immediately. A.25
Proof of Corollary 5
Proof. Theorem 7 characterizes implementability on an SP network via the node-wise inverse-bias recursion (19). At any parallel node H, the required bias is d¯H δH = log ¯ L − VHL (x̄, δ) − VHR (x̄, δ) . dH R
Imposing the per-node ratio budget |δH | ≤ log RH is therefore equivalent to the local inequality in the statement. Conversely, if the local inequalities hold for every parallel node, then the recursively defined δ is feasible under the budgets. Applying Theorem 7 with this feasible δ yields a decomposition-tied salience vector that implements x̄. The linear-time claim follows because both the forward computation of (VH ) and the backward computation of (δH ) traverse the SP decomposition tree once, i.e., in O(|E|) time. A.26
Proof of Proposition 4
Proof. Consider the split-variable formulation on a fixed SP decomposition tree T and the objective Ψu in (36). On an interior domain where every split variable satisfies ϵ ≤ yH ≤ dH − ϵ, the Hessian of each parallel-node entropy term is uniformly bounded above and below: the second derivative of y 7→ y log y + (dH − y) log(dH − y) is 1/y + 1/(dH − y), which lies in [2/dH , 2/ϵ] on this domain. Series nodes contribute smooth convex terms inherited from the Beckmann integrals; Lipschitzness of ℓe on [0, d] implies that these terms have Lipschitz gradients with constants bounded by a function of the edge Lipschitz constant and the tree structure. Summing contributions over nodes yields global constants L, µ > 0 such that Ψu is L-smooth and µ-strongly convex on the domain. Projected gradient descent on a closed convex set with step size 1/L for an L-smooth, µ-strongly convex objective satisfies the standard linear convergence bound Ψu (y (t) ) − Ψu (y ⋆ ) ≤ (1 − µ/L)t Ψu (y (0) ) − Ψu (y ⋆ ) , where y ⋆ is the unique minimizer. Finally, a gradient evaluation requires computing the induced edge flows from the split variables (a forward pass on T ) and then backpropagating marginal costs to obtain partial derivatives with respect to splits (a reverse/adjoint pass). Both passes visit each node/edge a constant number of times, so the cost is O(|E|). A.27
Proof of Corollary 3
Proof. If f SO is interior, Theorem 2 applies directly and yields a stationary salience policy (via (6)) whose SW-SUE coincides with f SO . If f SO is not interior, fix any ε > 0 and choose an interior flow f˜ with ∥f˜ − f SO ∥1 ≤ ε (e.g., a convex combination of f SO with the uniform interior flow on each commodity). Applying Theorem 2 to f˜ yields a salience policy that implements f˜ exactly. Since latencies are continuous and social cost is continuous in the flow, f˜ is an ε-approximation of f SO in induced performance, establishing ε-implementability.
References Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Informational Braess’ paradox: The effect of information on traffic congestion. Operations Research, 66(4):893–917, 2018. doi: 10.1287/opre.2017.1712. Saad Alqithami. Forgetful but faithful: A cognitive memory architecture and benchmark for privacy-aware generative agents. arXiv preprint arXiv:2512.12856, 2025a. URL https://arxiv.org/abs/2512.12856. 49
Saad Alqithami. Dynamic homophily with imperfect recall: Modeling resilience in adversarial networks. Social Network Analysis and Mining, 16(5):1–27, 2025b. doi: 10.1007/s13278-025-01483-2. Martin Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956. Moshe Ben-Akiva and Steven R. Lerman. Discrete Choice Analysis: Theory and Application to Travel Demand. MIT Press, 1985. Dirk Bergemann and Stephen Morris. Information design: A unified perspective. Journal of Economic Literature, 57 (1):44–95, 2019. doi: 10.1257/jel.20181489. Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. Equity of attention: Amortizing individual fairness in rankings. In Proceedings of the 41st International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). ACM, 2018. Dietrich Braess. Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung, 12:258–268, 1968. doi: 10.1007/BF01918335. Bureau of Public Roads. Traffic assignment manual. Technical report, U.S. Department of Commerce, Urban Planning Division, 1964. Andrew Caplin and Mark Dean. Revealed preference, rational inattention, and costly information acquisition. American Economic Review, 105(7):2183–2203, 2015. doi: 10.1257/aer.20140117. Ennio Cascetta and Giuseppe E. Cantarella. A day-to-day and within-day dynamic stochastic assignment model. Transportation Research Part A: General, 1991. doi: 10.1016/0191-2607(91)90144-F. Matias D. Cattaneo, Xinwei Ma, Yusufcan Masatlioglu, and Emre Suleymanov. Random attention models. Journal of Political Economy, 128(7):2796–2836, 2020. L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with Fairness Constraints. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-076-7. doi: 10.4230/LIPIcs.ICALP.2018.28. URL https://drops.dagstuhl.de/entities/ document/10.4230/LIPIcs.ICALP.2018.28. Hao Che, Ye Tung, and Zhijun Wang. Hierarchical web caching systems: Modeling, design and experimental results. IEEE Journal on Selected Areas in Communications, 20(7):1305–1314, 2002. doi: 10.1109/JSAC.2002.801752. George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pages 67–73. ACM, 2005. doi: 10.1145/1060590.1060600. José R. Correa, Andreas S. Schulz, and Nicolás E. Stier-Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):961–976, 2004. doi: 10.1287/moor.1040.0098. José R. Correa, Andreas S. Schulz, and Nicolás E. Stier-Moses. A geometric approach to the price of anarchy in nonatomic congestion games. Games and Economic Behavior, 64(2):457–469, 2008. Stella Dafermos and Anna Nagurney. On some traffic equilibrium theory paradoxes. Transportation Research Part B: Methodological, 18(2):101–110, 1984. doi: 10.1016/0191-2615(84)90023-7. Stella C. Dafermos and Frederick T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, Section B: Mathematical Sciences, 73B(2):91–118, 1969. doi: 10.6028/jres.073b.010. Robert B. Dial. A probabilistic multipath traffic assignment model which obviates path enumeration. Transportation Research, 5(2):83–111, 1971. doi: 10.1016/0041-1647(71)90012-8. R. J. Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10:303–318, 1965. 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. URL https://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-0000. doi: https://doi.org/10.1016/S0022-0000(77)80014-7. URL https: //www.sciencedirect.com/science/article/pii/S0022000077800147. Christine Fricker, Philippe Robert, and James Roberts. A versatile and accurate approximation for lru cache performance. In 2012 24th International Teletraffic Congress (ITC 24), pages 1–8, 2012. 50
Nicolas Gast and Benny Van Houdt. TTL approximations of the cache replacement algorithms LRU(m) and h-LRU. Performance Evaluation, 117:1–17, 2017. doi: 10.1016/j.peva.2017.09.002. Bo Jiang, Philippe Nain, and Don Towsley. On the convergence of the ttl approximation for an lru cache under independent stationary request processes. ACM Trans. Model. Perform. Eval. Comput. Syst., 3(4), September 2018. ISSN 2376-3639. doi: 10.1145/3239164. URL https://doi.org/10.1145/3239164. Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590–2615, 2011. doi: 10.1257/aer.101.6.2590. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Christoph Meinel and Sophie Tison, editors, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 404–413, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. ISBN 978-3-540-49116-3. Larry J. LeBlanc, Edward K. Morlok, and William P. Pierskalla. An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research, 9(5):309–318, 1975. doi: 10.1016/0041-1647(75) 90030-1. Jiayang Li, Zhaoran Wang, and Yu (Marco) Nie. Wardrop equilibrium can be boundedly rational: A new behavioral theory of route choice. Transportation Science, 58(5):973–994, 2024. doi: 10.1287/trsc.2023.0132. Paola Manzini and Marco Mariotti. Stochastic choice and consideration sets. Econometrica, 82(3):1153–1176, 2014. doi: 10.3982/ECTA10156. Yusufcan Masatlioglu, Daisuke Nakajima, and Erkut Ozbay. Revealed attention. American Economic Review, 102(5): 2183–2205, 2012. doi: 10.1257/aer.102.5.2183. Filip Matejka and Alisdair McKay. Rational inattention to discrete choice: A new foundation for the multinomial logit model. American Economic Review, 105(1):272–298, 2015. doi: 10.1257/aer.20130047. Igal Milchtaich. Network topology and the efficiency of equilibrium. Games and Economic Behavior, 57(2):321–346, 2006. 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’ paradox: Some new insights. Transportation Research Part B-methodological, 31:265–276, 1997. URL https://api.semanticscholar.org/CorpusID:14659553. M. Patriksson. The Traffic Assignment Problem: Models and Methods. Dover Publications, 2015. ISBN 9780486802275. URL https://books.google.com.sa/books?id=PDhkBgAAQBAJ. Robert W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65–67, 1973. doi: 10.1007/BF01737559. Tim Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236–259, 2002. doi: 10.1145/506147.506153. Yochi Sheffi. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, 1985. Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD). ACM, 2018. Michael J. Smith. The existence, uniqueness and stability of traffic equilibria. Transportation Research Part B: Methodological, 13(4):295–304, 1979. doi: 10.1016/0191-2615(79)90022-5. Richard Steinberg and Willard I. Zangwill. The prevalence of braess’ paradox. Transportation Science, 17(3):301–318, 1983. 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 language models for day-to-day route choices. Transportation Research Part C: Emerging Technologies, 180:105307, 2025. 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 paths in a network. Management Science, 17(11):712–716, 1971. doi: 10.1287/mnsc.17.11.712. Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. Fa*ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, page 1569–1578, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349185. doi: 10.1145/3132847.3132938. URL https://doi.org/10.1145/3132847.3132938. Chenghan Zhou, Thanh H. Nguyen, and Haifeng Xu. Algorithmic information design in multi-player games: Possibilities and limits in singleton congestion. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 869, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450391504. doi: 10.1145/3490486.3538238. URL https://doi.org/10.1145/3490486.3538238.
52