# Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

arXiv: https://arxiv.org/abs/2602.23277 · HTML: https://mlsanity.com/paper/2602.23277/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 15 of 15)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Improved Rates for Derivative Free Gradient Play in Strongly Monotone Games](https://mlsanity.com/paper/2111.09456/) (2021)
- [Frank-Wolfe with Subsampling Oracle](https://mlsanity.com/paper/1803.07348/) (2018)
- [Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization](https://mlsanity.com/paper/2506.04587/) (2025)
- [Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions (Extended Version)](https://mlsanity.com/paper/1905.13108/) (2019)
- [Superquantile-Gibbs Relaxation for Minima-selection in Bilevel Optimization](https://mlsanity.com/paper/2505.05991/) (2025)
- [Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games](https://mlsanity.com/paper/2110.01773/) (2021)
- [Cost Minimization for Equilibrium Transition](https://mlsanity.com/paper/2312.07603/) (2023)

## Abstract (arXiv)

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 kappam, then the Frank--Wolfe error decays as O(1/(kappam T)). We also propose stratified sampling as a practical way to avoid a vanishing kappam 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.