How Much of Risk-Averse Traffic Inefficiency Can Tolls Actually Remove?

Congestion pricing, which charges drivers for using busy roads, is usually designed with a simple model of driver behavior: each driver picks the route with the lowest average travel time plus toll. Real drivers on unreliable roads behave differently. They pad their plans against bad days and choose routes by something like "mean time plus a safety margin times the standard deviation." That margin does not add up road by road. The spread of a whole trip grows like the square root of the summed per-road variances, so a route's risk penalty is not the sum of its roads' penalties. The standard result that per-road charges can push selfish traffic to the system optimum relies on that additivity. Once additivity fails, part of the inefficiency caused by selfish, risk-averse drivers may be out of reach of any per-road toll.

This note proposes to measure that part. We pose the question as a leader–follower ("bilevel") program: the city picks tolls, and drivers respond by reaching an equilibrium. We then flatten it into a single optimization by writing the drivers' equilibrium as its optimality conditions, the Karush–Kuhn–Tucker (KKT) conditions. On small and medium networks this gives globally optimal tolls with a certificate. With a certified best toll in hand, we can split the price of anarchy (the ratio of selfish-equilibrium cost to the best coordinated cost) into the share tolls can remove and the share they cannot. The certificates then become ground truth for checking whether fast local methods, which do scale to city networks, are leaving value on the table.

Core Claim

Let $\mu_a(x_a)$ and $\sigma_a^2(x_a)$ be the mean and variance of travel time on road $a$ at flow $x_a$, and let $\tau_a$ be its toll. A risk-averse driver with safety margin $\alpha$ evaluates path $p$ at

$$C_p(f,\tau)=\sum_{a\in p}\big(\mu_a(x_a)+\tau_a\big)+\alpha\sqrt{\textstyle\sum_{a\in p}\sigma_a^2(x_a)},$$

where $f$ is the vector of path flows and $x_a$ is the total flow they induce on road $a$. Write $\mathcal{C}$ for total risk-adjusted cost, which is flow times $C_p$ excluding tolls, summed over paths. The equilibrium conditions under this cost are the standard ones: every used path has minimal $C_p$ within its origin–destination pair. These conditions are complementarity constraints, and because path costs are non-additive they must be written over paths rather than roads.

Our central quantity is the toll-irreducible share

$$R=\frac{\mathcal{C}(\mathrm{UE}_{\tau^\star})-\mathcal{C}(\mathrm{SO})}{\mathcal{C}(\mathrm{UE}_{0})-\mathcal{C}(\mathrm{SO})}.$$

Here $\mathrm{UE}_\tau$ is the equilibrium under tolls $\tau$, $\mathrm{UE}_0$ is the untolled equilibrium, $\tau^\star$ is the globally best toll vector, and $\mathrm{SO}$ is the system optimum. With deterministic or link-additive costs, marginal-cost tolls give $R=0$. We hypothesize three things. First, $R$ is positive and grows with $\alpha$ and with link-variance correlation. Second, tolls designed for risk-neutral drivers, applied to a risk-averse population, recover markedly less than $1-R$ of the closable gap. Third, $R$ can only be stated with confidence when $\tau^\star$ is certified global, which is the job of the KKT reduction.

Research Program

The method draws directly on three KKT-reduction papers. Yao et al.'s incentive-aware EV routing replaces customer best responses with KKT conditions, linearizes complementarity with binary variables and big-M bounds, and solves the result as a mixed-integer linear program. Its travel times are deterministic, and the authors list stochastic travel times as future work. The convex formulation of game-theoretic hierarchical routing does the same for a lower-level trajectory game, reaching a convex mixed-integer quadratic program with deterministic dynamics. Joint estimation of OD demands and cost functions uses KKT conditions of a Wardrop equilibrium for calibration rather than pricing.

We extend this to non-additive risk-averse path costs. We place one binary variable per candidate path on each complementarity pair. We represent $\mu_a$ and $\sigma_a^2$ by piecewise-linear approximations of flow. The square-root term is handled exactly by a second-order cone constraint (a constraint that is linear in the variables of a cone and still solvable by commercial solvers), with the rest of the program solved by spatial branch-and-bound. Correlated variances enter as $\sqrt{v_p^\top\Sigma v_p}$, where $v_p$ is the vector of road standard deviations on path $p$ and $\Sigma$ is the matrix of correlations between roads.

The known weakness of big-M reformulations is that they blow up combinatorially and are numerically fragile. To limit the number of binaries, we generate path sets by column generation. We tighten big-M constants with bounds derived from the untolled and maximum-toll equilibria, and we report the remaining optimality gap whenever the solver does not close it. Because risk-averse equilibria need not be unique, we solve separately for the optimistic toll (drivers settle on the equilibrium best for the city) and the pessimistic toll (worst for the city). The difference between them is a second quantity that first-order methods cannot produce.

At city scale we do not attempt exact solutions. Instead we build a risk-aware variant of the unrolled-dynamics method of Liu et al.. That method differentiates through simulated driver route-switching dynamics to tune tolls, and their dynamics are already path-based, so the non-additive cost drops in directly. We judge it against the exact certificates on networks where both run.

Variance data come from two sources. Following the safety-margin model of Chen et al., whose Wuhan study found that ignoring reliability overstates accessibility by 24.4%, we fit a variance-versus-volume/capacity relation from PeMS sensor data in the LargeST benchmark. We transplant that relation onto the standard test networks and sweep its scale as a sensitivity parameter. We expect this fit to be imperfect; the sweep shows whether the conclusions depend on it. Correlation strength is also swept, motivated by Huo et al.'s finding that downstream blockage accounts for roughly half of delay variance at dense stops. That finding contradicts the independence assumption that Lim et al. acknowledge in their fast stochastic shortest-path queries.

Baselines

The naive reference is no toll. It gives $\mathcal{C}(\mathrm{UE}_0)$ and hence the risk-adjusted price of anarchy on each network.

The strongest existing tolling method is the penalized block coordinate descent of Guo et al.. It chooses which roads to toll under a cardinality budget by collapsing the bilevel problem with a value-function gap and converging to stationary points. Guo et al. report three results: excessive delay reduced to 25% versus 33% for the best heuristic on Sioux Falls at κ=10, Chicago-Sketch solved in 18–24 minutes, and tolling 500 links recovering 93% of maximal savings. We run it in two ways. The first optimizes tolls for risk-neutral drivers, as published, and evaluates them on the risk-averse population; this is what a city using today's tools would do. The second feeds it the closest link-additive surrogate, mean plus $\alpha$ times variance per road, which is a fair, separable approximation that its method supports. Beating it means certifying a toll with at least 10% lower risk-adjusted excess cost on Sioux Falls at the same κ, using the same networks, demands and cost curves, with each method given the same wall-clock budget. No reported result was found on Lacuna for any method under risk-averse followers, so all risk-averse numbers will be produced here.

The scalable competitor is risk-aware unrolled dynamics in the style of Liu et al.. Liu et al. report about 1.5 hours on Chicago-Sketch and results up to 100x faster than dual annealing in the deterministic case. We give it the same path sets and many random restarts. The comparison here is not about speed. It asks how often, and by how much, its best restart falls short of the certified optimum.

We also include marginal-cost tolls computed from the risk-adjusted social cost; this is the textbook fix and is exact when costs are additive. Two ablations isolate the key ingredient. The first is our own exact solver with the square-root term replaced by its link-additive surrogate, which tests whether path-level non-additivity drives $R$. The second runs our solver with correlations set to zero.

Why not just…?

Why not just plug a per-road risk penalty into existing tolling solvers? This is the most serious threat. If mean-plus-variance per road approximates driver behavior well enough, $R$ is near zero and the existing machinery suffices. The surrogate ablation and the link-additive Guo et al. baseline settle this directly. If their tolls come within a few percent of the certified optimum across the $\alpha$ and correlation sweeps, we will report that as the main finding: a negative result showing that city tolling can safely ignore non-additivity. The certificate is what makes either outcome credible.

Why not just unroll risk-aware dynamics and skip integer programming? At Chicago scale this is what we recommend. Liu et al. state, however, that the approach guarantees only local optima, and it cannot separate the optimistic from the pessimistic equilibrium. The exact comparisons on Hearn's network and Sioux Falls measure its realized gap. A consistently small gap would be a useful license to use it; a large or erratic gap would show where it is unsafe.

Why not just use a simple static or uniform toll? Jalota et al. show that static tolls capture 80–90% of dynamic revenue with system costs only 8–20% above optimal on NYC and Bay Bridge calibrations. They also state explicitly that delay variance and demand shocks are excluded from their model. We include the best uniform cordon-style toll on each network. If it matches the optimized link tolls under risk aversion, that strengthens their conclusion beyond the deterministic setting.

Why not just broadcast accurate travel-time distributions? Herding results argue against this as a substitute for pricing: Liebig, Bazzan et al., and the 47% spillover reduction from withholding full information in Wu and Amin. Our equilibrium model already assumes drivers know the distributions, so information provision is the regime we analyze, not an alternative to it.

Proposed Experiments

On the Braess network (5 links) and Hearn's network (18 links), exact solutions close fully. There we verify the reduction against brute-force toll enumeration, as Guo et al. did for the deterministic case. We then trace $R$ and the optimistic-to-pessimistic gap as $\alpha$ runs from 0 to 2 and correlation from 0 to 0.6.

On Sioux Falls (76 links), we run the exact solver on column-generated path sets with a four-hour limit per instance and report certified gaps. The decisive check is whether risk-neutral Guo et al. tolls, the link-additive surrogate, and unrolled dynamics each fall more than 10% short of the certified optimum in closable excess cost at moderate $\alpha$, and whether that shortfall grows with correlation.

On Chicago-Sketch (2,950 links, 93,512 OD pairs) exact certification is out of reach. We compare the scalable methods on risk-adjusted system cost and on the 95th-percentile trip time of travelers, and use the Sioux Falls gaps to judge how far to trust each method.

The project fails cleanly in one of two ways. The first is that $R$ stays below about 2% everywhere and surrogate tolls match the certificates, in which case risk aversion is a reweighting that existing tools already handle. The second is that the exact solver cannot certify Sioux Falls within a 5% gap, in which case the KKT route is too weak to referee the scalable methods.