Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
This work provides a more efficient method for optimizing network parameters in combinatorial congestion games, which is relevant for urban planners and network designers dealing with traffic management or resource allocation.
This paper addresses the problem of Stackelberg control in combinatorial congestion games, where a leader tunes network parameters to optimize a system-level objective while users choose discrete routes and reach a congestion equilibrium. The proposed ZO-Stackelberg method, which combines a projection-free Frank-Wolfe equilibrium solver with a zeroth-order outer update, achieves orders-of-magnitude speedups over differentiation-based baselines while converging to follower equilibria.
We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (or other combinatorial strategies) and settle at a congestion equilibrium. The leader minimizes a system-level objective (e.g., total travel time) evaluated at equilibrium, but this objective is typically nonsmooth because the set of used strategies can change abruptly. We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update, avoiding differentiation through equilibria. We prove convergence to generalized Goldstein stationary points of the true equilibrium objective, with explicit dependence on the equilibrium approximation error, and analyze subsampled oracles: if an exact minimizer is sampled with probability $κ_m$, then the Frank--Wolfe error decays as $\mathcal{O}(1/(κ_m T))$. We also propose stratified sampling as a practical way to avoid a vanishing $κ_m$ when the strategies that matter most for the Wardrop equilibrium concentrate in a few dominant combinatorial classes (e.g., short paths). Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline while converging to follower equilibria.