Navigation apps that tell every driver the fastest route can make traffic worse. Everyone piles onto the recommended road, and it becomes the slow one. The usual fix is anticipation: the guidance provider predicts how drivers will respond and recommends routes that stay fast after they do. We argue that this fix fails in a specific and measurable way. The provider computes the response at its best guess of demand and compliance. Road delay grows steeply and convexly with flow, so the expected delay on a busy road is larger than the delay at the expected flow. The gap is a curvature effect, not random noise. It always points the same way, makes popular roads look better than they are, and recreates herding even when the provider anticipates the response. This is the bias that filtering researchers call linearization error, here showing up inside a congestion game.
The proposal fixes it by propagating uncertainty through the delay functions with a small set of deterministic samples (sigma points), as the unscented Kalman filter does. Done over individual paths, this is hopeless, because a city has thousands of correlated paths. We therefore do it over a few topological corridors, the classes of routes that pass the same way around non-traversable regions such as rivers, rail lines and parks. The two-sentence version: anticipatory route guidance herds because it evaluates steep delay curves at the mean of an uncertain flow. Computing the anticipated equilibrium in expectation, with uncertainty carried at the level of homotopy corridors, removes that bias cheaply and should close a measurable part of the price of anarchy, the ratio between total delay under selfish routing and under the best coordinated routing.
Core Claim
Let $t_e(f)$ be the travel time on link $e$ at flow $f$. In the standard Bureau of Public Roads form used throughout the Sioux Falls and Anaheim literature, $t_e(f) = t_e^0(1 + 0.15 (f/c_e)^4)$, where $t_e^0$ is free-flow time and $c_e$ is capacity. If the flow on a corridor is uncertain with mean $\bar f$ and variance $\mathrm{Var}(f)$, because demand fluctuates and compliance with advice is uncertain, a second-order expansion gives
$$\mathbb{E}[t_e(f)] \approx t_e(\bar f) + \tfrac{1}{2}\, t_e''(\bar f)\,\mathrm{Var}(f), \qquad t_e''(\bar f) = 1.8\, t_e^0\, \bar f^{2}/c_e^{4}.$$
The bias term is quadratic in the mean flow and linear in the variance. It is therefore largest exactly on the near-capacity corridors a guidance system is most tempted to recommend, and it vanishes when delay is linear in flow.
Our claim is that this term, not the mere presence of noise, explains a large share of the residual herding seen after anticipation. A guidance rule that solves for a self-consistent recommendation in expectation recovers most of the gap between partial-information routing and the system optimum. Here self-consistent means that the recommended split remains the best split once drivers follow it. The rule computes expectations with sigma points over a corridor-level flow vector of dimension $K$ (typically 3 to 8), not over all paths.
This connects three literatures that have not met. Gaussian Ensemble Belief Propagation shows that evaluating nonlinear models at the mean leaves a Jensen gap, and that propagating samples through the true model removes it. Its reported 1D-transport error is 0.167 versus 1.93 for linearized Gaussian belief propagation. Dual Estimation and the Unscented Transformation supplies the sigma-point construction we reuse. Improved Calibration of Numerical Integration Error in Sigma-Point Filters warns that fixed sigma-point rules can still be silently overconfident, which we treat as a constraint and test directly.
On the game side, two papers motivate the work by documenting that information itself causes harm. Combining Car-to-Infrastructure Communication and Multi-Agent Reinforcement Learning in Route Choice finds that full broadcast on Sioux Falls raises average travel time to 33.941 minutes. Information Design for Regulating Traffic Flows under Uncertain Network State finds that truthful full information produces 47% more spillover than an optimally designed signal. Neither asks how the provider's own prediction error contributes, and that is our question.
The topological piece gives the uncertainty a low-dimensional home. Search-Based Path Planning with Homotopy Class Constraints assigns each planar path an integer-like invariant, called an $L$-value, computed by a complex line integral around obstacle "poles." Embedding a road network in the plane and treating rivers, parks and large blocks as obstacles lets us label every route by its corridor. Flows within a corridor share bottlenecks and are strongly correlated. Across corridors, the belief over corridor flows is multimodal, because compliance switches whole groups of drivers between corridors. Within a corridor it is roughly unimodal. This is precisely the partitioning that MacKinlay et al. name as missing for multimodal problems.
Research Program
We will build a guidance provider that, at each decision epoch, holds a Gaussian belief over corridor flows. The belief is fed by noisy link counts and by a compliance model. The compliance model follows the bounded-detour idea of Reconciling Selfish Routing with Social Good: a driver accepts a recommendation if its believed latency is within a factor $\theta$ of the driver's own believed shortest path.
The provider outputs a randomized recommendation, meaning a probability of assigning each origin–destination group to each corridor, with ordinary shortest-path routing inside the chosen corridor. It chooses this lottery by solving a fixed point. The lottery must minimize expected total delay subject to each recommended corridor having expected latency within $\theta$ of the best alternative. Expectations are computed by pushing $2K+1$ sigma points of the corridor-flow belief through the exact link delay functions.
We solve the fixed point with a Frank–Wolfe-style iteration on the expected-cost objective, reusing the convexity-preserving construction of Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment. I-TAP blends user-equilibrium and system-optimal costs at the mean flow. We blend them on expected costs, which is the one change that matters.
The analysis component has three parts. We will derive how the deterministic-anticipation bias scales with the delay exponent and with flow variance, using the expansion above, which comes from a Taylor series of the delay function to second order. We will bound how much of the price of anarchy that bias can account for on two-route networks. We will also test whether the Bayes–Sard correction of Prüher et al. is needed when corridor flows sit near capacity, where the quartic is far from the polynomial order the unscented rule integrates exactly.
The testbeds are drawn from the file. The first is Sioux Falls, with the Bazzan et al. demand of over 360,000 trips across 528 origin–destination pairs, run in the dynamic mean-field setting of Solving N-player dynamic routing games with congestion, with 14,000 vehicles over 100 steps. The second is the Anaheim and Berlin sub-networks from I-TAP. The third is the Wu–Amin two-route spillover network, where effects can be computed in closed form. The fourth is the SUMO Beijing and Manhattan networks from AlphaRoute, which test whether static-assignment conclusions survive queue spillback.
Demand variance and compliance uncertainty are injected as controlled knobs. Each origin–destination demand is drawn per episode from a lognormal distribution with a set coefficient of variation, and the compliance threshold $\theta$ is drawn per driver.
The metrics are average travel time, realized price of anarchy, a herding index, prediction calibration, and fairness. Realized price of anarchy is total delay divided by the system-optimal delay computed with the realized demand. The herding index is the largest corridor share relative to its system-optimal share. Prediction calibration is the coverage of the provider's latency intervals, together with signed bias. Fairness uses the unfairness measure from I-TAP.
Baselines
The naive reference points are no guidance and full broadcast of the current shortest path. Full broadcast is the configuration Bazzan et al. show collapsing on Sioux Falls, at 33.941 minutes average travel time versus 21.9 with no communication.
The strongest reported competitor in the file is partial broadcast. Bazzan et al. report 21.265 minutes average travel time on Sioux Falls when a quarter of vehicles receive guidance, against a theoretical user equilibrium of about 20.76 minutes. Their drivers are reinforcement learners, not our compliance model. So we will re-run partial broadcast inside our simulator with the broadcast fraction tuned by grid search on held-out demand draws, giving it the same tuning budget as our method's single parameter $\theta$. We will also report their published number as an external anchor.
The baseline that isolates our key ingredient is deterministic anticipation. It is identical to our method, with the same corridors, compliance model and fixed-point solver, but evaluates delays at the mean corridor flow. No reported result found on Lacuna for deterministic anticipatory guidance on these networks. The only difference from our method is the Jensen-gap correction, so beating it is the central test.
We also run a Monte Carlo ensemble version with hundreds of samples per iteration, in the spirit of GEnBP. It serves as an accuracy ceiling and cost reference: our method should match its travel time at a small fraction of its compute. Finally, centralized I-TAP at its best interpolation weight, assuming full compliance, serves as an upper reference rather than a competitor. Its reported "50% reduction in unfairness with only a ~2% increase in total travel time" tells us what an unconstrained planner achieves. On Berlin we add the single-alternative-path method of A Strategic Routing Framework and Algorithms for Computing Alternative Paths, which reports roughly a 50% travel-time reduction over all-shortest-path assignment.
All methods share demand draws, sensor noise, compliance model and wall-clock budget per decision epoch. Beating the field means two things. First, a statistically significant reduction in realized price of anarchy relative to both tuned partial broadcast and deterministic anticipation across at least 20 demand seeds. Second, prediction intervals whose coverage stays near nominal where deterministic anticipation shows a negative signed bias on its recommended corridor.
Why not just…?
Why not just broadcast to a tuned fraction of drivers, as Bazzan et al. do? It works in their study, and it is a genuine threat. But the right fraction depends on demand level and variance, and nothing in the method tells you how to set it when either changes. Our experiments retune partial broadcast on one demand regime and test on others. If its advantage survives regime shift, our method's value reduces to robustness, and we will report it that way.
Why not just anticipate the response deterministically, which already removes naive herding? This is the closest alternative, and the bias formula predicts exactly where it fails: near-capacity corridors under high demand variance with steep delay curves. If the bias formula is right, the gap between the two methods should grow with the coefficient of variation and with the delay exponent, and disappear at exponent 1. If no such gap appears, the core claim is wrong.
Why not just use an extended Kalman filter with inflated noise covariance? Inflation widens the error bars but does not move the mean. The Jensen term is a signed shift, so the recommendation is still biased toward the busy corridor. We include an inflated-covariance variant tuned for calibration and expect it to match our coverage but not our travel time. MacKinlay et al.'s order-of-magnitude error gap between linearized and sample-propagated inference suggests why.
Why not just cluster routes by shared links, or use k-shortest paths, instead of homotopy classes? This may work nearly as well, and we test it head on. Corridors defined by link-overlap clustering, by Yen-style k-shortest paths, and by $L$-value homotopy classes all feed the identical sigma-point solver. Topology earns its place only if homotopy corridors give lower correlation of flows across corridors, and hence better-calibrated beliefs at the same $K$. If overlap clustering ties, we will say that corridors matter and topology is one convenient way to define them.
Decisive Experiments
The cleanest check is a dose–response sweep on the Wu–Amin two-route network and on Sioux Falls. We vary the delay exponent over 1, 2, and 4, and the demand coefficient of variation from 0 to 0.4. The theory makes three predictions. At exponent 1, or zero variance, our method and deterministic anticipation should coincide, because the second derivative or the variance is zero. The gap should grow roughly as variance times mean flow squared, the scaling of the second-order bias term. Deterministic anticipation's signed latency bias on its recommended corridor should be negative and should predict the herding index.
The second check runs on SUMO Beijing and Manhattan. It asks whether these static-assignment gains persist under queue spillback, and whether the Bayes–Sard correction is needed when corridors run near capacity. We compare against AlphaRoute's reported 12.88% latency improvement over minimum-distance routing on Beijing as an external yardstick.
The third check is the corridor ablation described above. It decides whether topological path diversity is a necessary ingredient or a replaceable convenience.
References
- Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional, Black-box Systems
- Dual Estimation and the Unscented Transformation
- Improved Calibration of Numerical Integration Error in Sigma-Point Filters
- Combining Car-to-Infrastructure Communication and Multi-Agent Reinforcement Learning in Route Choice
- Information Design for Regulating Traffic Flows under Uncertain Network State
- Search-Based Path Planning with Homotopy Class Constraints
- Reconciling Selfish Routing with Social Good
- Balancing fairness and efficiency in traffic routing via interpolated traffic assignment
- Solving N-Player Dynamic Routing Games with Congestion: A Mean-Field Approach
- AlphaRoute: Large-Scale Coordinated Route Planning via Monte Carlo Tree Search
- A Strategic Routing Framework and Algorithms for Computing Alternative Paths