Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
| Authors | Saeed Masiha et al. |
| Year | 2026 |
| Field | AI / ML |
| arXiv | 2602.23277 |
| Download | |
| Categories | cs.GT, cs.LG |
Abstract
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 , 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 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.
Engineering Breakdown
Plain English
This paper tackles the problem of optimizing network parameters (like tolls and capacities) in congestion games where users selfishly choose discrete routes and reach equilibrium—a common scenario in traffic networks and resource allocation systems. The core challenge is that the system-level objective (e.g., minimizing total travel time) is nonsmooth because small parameter changes can cause users to suddenly switch routes, making the objective landscape discontinuous and hard to optimize. The authors propose ZO-Stackelberg, an algorithm that avoids the need to differentiate through equilibria (which is intractable) by using zeroth-order optimization coupled with a Frank-Wolfe equilibrium solver. They prove their method converges to generalized Goldstein stationary points of the true objective, with explicit bounds on how approximation error in the equilibrium solution affects convergence.
Core Technical Contribution
The key innovation is decoupling the leader's optimization from equilibrium computation by using zeroth-order (gradient-free) updates instead of differentiating through the equilibrium solution. Prior work either assumed smooth objectives or required implicit differentiation through equilibria, which is computationally expensive and unstable when strategies change discretely. ZO-Stackelberg combines two previously separate components: a projection-free Frank-Wolfe algorithm for computing approximate Nash equilibria on the inner loop, and zeroth-order gradient estimation on the outer loop for tuning leader parameters. This design enables convergence guarantees even when the equilibrium objective is nonsmooth, with explicit dependence on equilibrium approximation quality—a theoretical contribution that formally connects inner-loop solution quality to outer-loop convergence rates.
How It Works
The algorithm operates as a two-loop nested procedure. The outer loop performs zeroth-order optimization on the leader's objective: it estimates gradients using function evaluations at perturbed parameter values (e.g., by evaluating the system at slightly different toll values) without computing explicit derivatives. For each outer-loop iteration, the inner loop solves for the equilibrium that users reach given the current parameters using a projection-free Frank-Wolfe method—this iteratively updates the set of active strategies (routes) used by players, driving the system toward a congestion equilibrium. After computing an approximate equilibrium (within some error tolerance), the outer loop uses the zeroth-order gradient estimate to update the leader's parameters in a direction that reduces the system objective. The algorithm terminates when it reaches a generalized Goldstein stationary point, a weaker optimality condition appropriate for nonsmooth objectives. The key insight is that by using zeroth-order updates, the algorithm never needs to backpropagate through the equilibrium computation, which would be intractable in discrete strategy spaces.
Production Impact
For teams building traffic management systems, toll optimization platforms, or resource allocation networks, this approach enables parameter tuning in highly nonsmooth domains where standard gradient-based methods fail. Instead of hand-tuning tolls or capacities based on domain expertise, engineers can run ZO-Stackelberg to automatically optimize these parameters for system-level goals (e.g., minimizing congestion) while accounting for selfish user behavior. The main production trade-off is computational cost: the zeroth-order method requires many function evaluations (evaluating the system at different parameter settings and computing equilibria), so it suits offline planning scenarios (weekly or daily toll adjustments) rather than real-time control. Integration into existing systems requires: (1) a fast equilibrium solver for your specific game (congestion games on road networks, cloud resource markets, etc.), (2) the ability to simulate or evaluate system performance under different parameters, and (3) tolerance for convergence to stationary points rather than global optima. The method's strength is robustness to nonsmooth transitions—when a route becomes faster and users switch, the algorithm adapts naturally without breaking.
Limitations and When Not to Use This
The algorithm's convergence guarantees are to stationary points of a nonsmooth objective, not to global optima, meaning final solutions may be locally optimal or saddle points. The inner-loop equilibrium computation adds significant overhead; if your equilibrium solver is slow or approximate, convergence to the outer-loop objective is slower—the paper makes explicit but pessimistic bounds on this trade-off. The approach assumes users play pure strategy Nash equilibria or ε-Nash equilibria, which may not hold in real networks with heterogeneous user types or learning dynamics; if users employ mixed strategies or take time to converge, the equilibrium assumption breaks down. The paper focuses on convex feasible regions for leader parameters and may not extend naturally to discrete parameter spaces (e.g., choosing toll values from a discrete set). Open questions remain on computational complexity—how fast can you solve equilibria in large-scale games?—and on robustness to model mismatch (what if user behavior deviates from the congestion game model?).
Research Context
This work sits at the intersection of game theory (Stackelberg games, congestion games) and zeroth-order optimization. It builds on decades of research in algorithmic game theory (computing equilibria in congestion games via Frank-Wolfe methods) and recent advances in zeroth-order optimization for nonsmooth objectives. The contribution directly addresses a gap: while much prior work studies smooth Stackelberg problems or assumes black-box equilibrium access, this paper provides the first convergence analysis for zeroth-order Stackelberg control where equilibria are themselves computed iteratively and nonsmooth objective transitions occur. The result opens directions for applying zeroth-order methods to other bilevel problems with discrete-choice inner loops (e.g., mechanism design, hyperparameter tuning under strategic behavior, and network design under selfish routing).
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::