Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Accepted at NeurIPS 2026
TL;DR: We study Stackelberg control in combinatorial congestion games and propose Zeroth-order Stackelberg (ZOS), a method that avoids differentiating through nonsmooth equilibria by combining a Frank-Wolfe inner solver with zeroth-order outer updates. On transportation-network benchmarks, exact and length-stratified variants achieve competitive social costs and small equilibrium gaps with substantially lower runtime and memory use than a differentiation-based baseline.
Summary: When a leader tunes tolls, capacities, or incentives in a network, the followers choose discrete routes or other combinatorial strategies and then settle at Wardrop equilibrium. Small changes in the leader parameters can switch which strategies are active, so the true objective can be nonsmooth and difficult to optimize by backpropagating through the equilibrium computation. We instead use exact or subsampled combinatorial oracles inside a Frank-Wolfe solver and update the leader with zeroth-order objective queries, without differentiating through the inner solves. This yields one framework for shortest-path, exact ZDD, and sampled ZDD regimes, with convergence guarantees that account for equilibrium approximation error. On TNTP-derived networks from Winnipeg, Chicago, and Philadelphia, exact-oracle ZOS is approximately 23× and 61× faster per outer iteration in the first two scenarios, with comparable social costs and much lower peak memory. In the large-ZDD scenario, length-stratified subsampling approaches exact-oracle solution quality while reducing runtime; the differentiation-based baseline completes only five outer iterations within 10 hours.
