Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

We study Stackelberg (leader--follower) control of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose \emph{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 can be nonsmooth because the set of used strategies can change abruptly. We propose \textsc{Zeroth-order Stackelberg} (\textsc{ZOS}), 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 the sampled candidate set contains an LMO minimizer with probability $\kappa_m$, then the Frank--Wolfe error decays as $\mathcal{O}(1/(\kappa_m T))$. We also propose stratified sampling as a practical way to avoid a vanishing $\kappa_m$ when LMO minimizers concentrate in strata defined by simple features such as path length. In public road-network experiments covering large strategy spaces requiring subsampled oracles, \textsc{ZOS} reaches small follower-equilibrium gaps and final social costs comparable to differentiation-based methods, while reducing runtime per outer iteration by $20$--$1000\times$ and using much less peak memory.