Restricted Congestion Tolling Through the Equilibrium Value Function

When drivers pick routes selfishly, a road network settles into a Wardrop equilibrium, a state where no driver can shorten their own trip by switching routes. Total delay in that state can be far worse than what a central planner would achieve. On subnetworks of Eastern Massachusetts the ratio between the two, called the price of anarchy, was measured at about 1.5 (The Price of Anarchy in Transportation Networks). Textbook theory says marginal-cost tolls remove this gap. That only holds if every link can be tolled, tolls can be any sign and size, and demand is known. Real planners can toll a handful of links, must keep tolls non-negative and capped, and face fluctuating demand. Once those constraints apply, choosing tolls becomes a genuine leader–follower (bilevel) problem. The planner moves first, and the drivers' equilibrium responds. The current tools for it are poor. Exact single-level rewrites using Karush–Kuhn–Tucker (KKT) optimality conditions and binary "big-M" variables only scale to small instances. Differentiating through the equilibrium solver needed up to 194 GiB of memory and timed out on Philadelphia. The best large-scale method falls back on noisy finite-difference gradients (Stackelberg Control in Combinatorial Congestion Games without Differentiating Through Equilibria).

This note proposes a fourth route that uses a structural fact specific to tolling. The drivers' equilibrium minimizes a potential function, and tolls enter that potential linearly. As a result, the best achievable potential, viewed as a function of tolls, is concave. Its gradient is simply the equilibrium link flow, which the standard Frank–Wolfe traffic-assignment solver already outputs. Rewriting the bilevel problem with this "value function" as a single constraint gives a single-level program. Every quantity it needs comes from a shortest-path (or general linear-minimization) oracle: no Hessians, no unrolled solver iterations, no binary variables, and no finite differences. The concavity also holds in combinatorial strategy spaces where active-set switches put kinks into the planner's objective.

Core Claim

Let $c_e$ be the increasing cost (travel-time) function of link $e$, $x \in X$ the vector of link flows feasible for the given demand, and $\tau \in T$ the tolls allowed by the planner. $T$ might encode non-negativity, caps, a budget, or "only links in set $S$". The toll-shifted Beckmann potential is

$$B(x,\tau) = \sum_e \int_0^{x_e} c_e(s)\,ds + \sum_e \tau_e x_e, \qquad \varphi(\tau) = \min_{x \in X} B(x,\tau).$$

Its minimizers are exactly the Wardrop equilibria under tolls $\tau$. Because $B$ is affine in $\tau$, $\varphi$ is a minimum of affine functions and therefore concave. By Danskin's theorem, the equilibrium flow $x^*(\tau)$ is a supergradient of $\varphi$. The restricted toll-design problem becomes

$$\min_{\tau \in T,\; x \in X} \; \sum_e x_e c_e(x_e) \quad \text{s.t.} \quad q(x,\tau) = B(x,\tau) - \varphi(\tau) \le 0.$$

The constraint gradients are $\nabla_\tau q = x - x^*(\tau)$ and $\nabla_x q = c(x) + \tau$. The first needs one equilibrium solve. The second needs nothing beyond evaluating link costs.

The claim has two parts. First, a dynamic-barrier first-order method on this program finds tolls whose induced equilibrium has a lower system cost than zeroth-order Stackelberg search for the same number of equilibrium solves, at comparable memory. Second, on instances small enough to solve exactly, it lands within a small gap of the global optimum computed by a KKT/big-M mixed-integer program. Concavity is what makes the first part plausible: the information the planner needs about how equilibria move is exact, not estimated.

Note what Danskin does not give. It does not give the derivative of the planner's objective $\tau \mapsto SC(x^*(\tau))$, which can be kinked and nonconvex. The value-function reformulation is what turns the cheap Danskin information into a usable search direction.

Research Program

The method reuses the value-function reformulation and dynamic-barrier update of BOME!. BOME replaces the inner argmin with $g \le g^*$ and descends with a stop-gradient on the inner optimum. It was only tested on smooth machine-learning problems, and its theory needs inner iterations growing with outer iterations, while practice uses a fixed $T=10$. The tolling setting closes that gap. The inner problem is solved by Frank–Wolfe, whose duality gap is an explicit, computable upper bound on the error in $\varphi(\tau)$. We can therefore run the inner solver to a gap tolerance tied to the outer step, rather than for a fixed iteration count. We will prove convergence to a stationary point of the reformulated program under that adaptive rule, using the concavity of $\varphi$. This is a cleaner object than the Goldstein-stationarity of a smoothed surrogate obtained by zeroth-order Stackelberg control. The $x$-update stays inside $X$ by taking conditional-gradient steps with the same oracle, either Dijkstra for ordinary paths or the zero-suppressed decision diagrams of Stackelberg Control in Combinatorial Congestion Games for Hamiltonian paths and Steiner cycles.

The KKT direction plays two roles. First, it supplies ground truth. On Braess and on Sioux-Falls-scale subnetworks with piecewise-linearized costs, we write the drivers' KKT conditions (which are exactly Wardrop's conditions), linearize complementarity with big-M binaries as in Incentive-aware Electric Vehicle Routing and Proactive Demand Response for Data Centers, and solve to global optimality. Second, it supplies an ablation. The Frank–Wolfe gap $\max_{s \in X}(c(x)+\tau)^\top(x-s)$ measures how badly the KKT complementarity is violated. It can replace $q$ as a single scalar constraint that needs only one oracle call and no inner solve at all. Comparing the value-function constraint with this gap-function constraint shows whether solving the inner equilibrium buys anything.

The price-of-anarchy direction defines the objective and the regime. We report residual price of anarchy: the system cost at the induced equilibrium divided by system-optimal cost, both recomputed independently to tight tolerance. We study regimes where the closed-form answers fail. These include partial tolling, non-negative capped tolls on networks with directed cycles (where Demand-Independent Tolls shows demand-independent optimality needs subsidies), and heterogeneous cost exponents across links (where that paper proves no demand-independent optimal toll exists). For the last regime we optimize the average over sampled demand scales. Each scenario contributes its own concave $\varphi$, so the structure survives. Optimal Taxes in Atomic Congestion Games shows marginal-cost pricing can be worse than no toll in atomic games. We restrict to non-atomic flows, where the potential argument is exact, and say so as a scope limit.

Baselines

The naive reference points are no toll, which gives the untolled equilibrium's price of anarchy, and projected marginal-cost tolls. The latter computes the system-optimal marginal tolls $x_e c_e'(x_e)$ and then clips them to the allowed set $T$ (zero on untollable links, capped, non-negative). It is what a practitioner would deploy tomorrow. Any proposed method must beat it clearly in the restricted regimes. With unrestricted tolls it is exactly optimal, which gives a sanity check our method must reproduce.

The strongest competitor is ZO-Stackelberg (Stackelberg Control in Combinatorial Congestion Games). It uses an inner Frank–Wolfe equilibrium solver and an outer two-point finite-difference gradient. It is the only method in the file shown to work on Winnipeg, Chicago-Sketch and Philadelphia with combinatorial strategies. That paper reports 20× to 1000× faster outer iterations than differentiable baselines and peak memory never above 1.7 GiB, versus 10–194 GiB. No reported result was found on Lacuna for its final residual price of anarchy or system cost on these networks, so we will rerun it ourselves. Fairness is enforced in four ways. Both methods use the identical Frank–Wolfe solver, oracle, and inner tolerance schedule. Both get the same budget of equilibrium solves. Each gets an equal hyperparameter-search budget over step sizes. Final tolls from both are evaluated by the same high-accuracy equilibrium solve. Beating it means lower residual price of anarchy at equal equilibrium-solve budget on at least two of the three networks, without exceeding its memory by more than a small constant factor.

The differentiable softmin baseline (Diff) from the same paper is included on Winnipeg only, since it times out elsewhere. The KKT/big-M mixed-integer program serves as an exact upper bound on attainable quality for small instances.

Two ablations isolate the key ingredient. In the first, the Danskin supergradient $x^*(\tau)$ is replaced with a finite-difference estimate of $\nabla\varphi$ inside the same value-function method. This tests whether exactness of the hyper-information, rather than the reformulation, drives the gain. In the second, the value-function constraint is replaced with the gap-function constraint, and adaptive inner tolerance is replaced with BOME's fixed $T=10$.

Why not just…?

Why not just use marginal-cost tolls? They are optimal only when every link is tollable without caps and demand is known. Demand-Independent Tolls shows that with heterogeneous exponents no single toll vector is optimal across demands. On cyclic networks it may need negative tolls. Clipping marginal tolls to a feasible set has no optimality guarantee and ignores how drivers reroute around untolled links. Our projected-marginal baseline measures exactly how much that costs. If it matches our method within noise in the restricted regimes, the proposal fails, and we will report that.

Why not just run ZO-Stackelberg, which already scales? It is the real threat. It treats the equilibrium as a black box and pays variance for it, needing stratified sampling over strategy lengths on large spaces. It also converges only to Goldstein-stationary points of a smoothed surrogate. Our method uses the same oracle calls but extracts an exact supergradient of $\varphi$ from each solve. The finite-difference ablation answers this question directly. If finite differences inside our reformulation perform as well as Danskin, the advantage lies in the reformulation alone. If ZO-Stackelberg itself matches us at equal budget, our method adds nothing on these benchmarks.

Why not just write the KKT conditions and hand the big-M program to Gurobi? Exact reductions of this kind solve medium electric-vehicle instances in around 340 seconds (Incentive-aware Electric Vehicle Routing). The hierarchical-routing reduction of A Convex Formulation of Game-Theoretic Hierarchical Routing handles two or three vehicles. One binary per link–path complementarity on Winnipeg-scale networks, plus piecewise-linearized costs, is far beyond that. We use the mixed-integer program where it works, as ground truth, and measure its time-to-optimality as instance size grows to show where it stops.

Why not just apply BOME or a penalty method off the shelf? Our method is BOME's reformulation, so this is less an alternative than a question of what the specialization adds. The concave toll value function, the oracle-only gradients, and the Frank–Wolfe duality gap as an inner-accuracy certificate are what let it run on discrete strategy spaces. The fixed-$T$ ablation tests whether the adaptive certificate matters. Penalty Method for Inversion-Free Deep Bilevel Optimization penalizes $\|\nabla_x B\|^2$. That penalty is meaningless when $x$ is constrained to a polytope, because equilibria sit where that gradient is nonzero.

Proposed Experiments

Correctness checks. On the Braess network, used in Joint Estimation of OD Demands and Cost Functions and Demand-Independent Tolls, we check two things. With all links tollable, the method must recover system-optimal flow (residual price of anarchy at 1 up to solver tolerance). With only one link tollable, it must match the KKT/big-M global optimum. We repeat this on small TNTP subnetworks with random restricted toll sets and caps. We report the gap to the mixed-integer optimum and the mixed-integer solve time as size grows.

Main comparison. On the TNTP scenarios of Stackelberg Control in Combinatorial Congestion Games (Winnipeg with ordinary paths, Chicago-Sketch with Hamiltonian paths, Philadelphia with Steiner cycles), we toll 5%, 20% and 100% of links under non-negative caps. We plot residual price of anarchy against equilibrium solves, wall-clock time and peak memory for our method, ZO-Stackelberg, projected marginal tolls, and no toll. Diff is included on Winnipeg only.

Demand uncertainty. We assign heterogeneous BPR exponents on Anaheim and Winnipeg so that no demand-independent optimal toll exists. We then optimize expected system cost over sampled demand scales and evaluate on held-out scales against tolls tuned for mean demand.

Ablations and decisive outcomes. The finite-difference and gap-function ablations run on all three networks. The result that would sink the proposal is ZO-Stackelberg matching our residual price of anarchy at equal budget on Chicago-Sketch and Philadelphia, where active-set kinks are worst. The result that would confirm it is a consistent gap there, together with a near-zero gap to the exact optimum on small instances.