![[2602.23277] Zeroth-Order Stackelberg Control in Combinatorial Congestion Games](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.23277] Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Summary
This article presents the ZO-Stackelberg method for optimizing network parameters in combinatorial congestion games, enhancing efficiency in achieving equilibrium without requiring differentiation through equilibria.
Why It Matters
The study addresses a significant challenge in game theory and network optimization by proposing a novel approach that improves computational efficiency. This has practical implications for traffic management and resource allocation in complex systems, making it relevant for researchers and practitioners in computer science and operations research.
Key Takeaways
- Introduces ZO-Stackelberg, a method for optimizing network parameters in congestion games.
- Avoids differentiation through equilibria, enhancing computational efficiency.
- Proves convergence to generalized Goldstein stationary points.
- Demonstrates significant speedups in real-world network experiments.
- Highlights the importance of stratified sampling in improving outcomes.
Computer Science > Computer Science and Game Theory arXiv:2602.23277 (cs) [Submitted on 26 Feb 2026] Title:Zeroth-Order Stackelberg Control in Combinatorial Congestion Games Authors:Saeed Masiha, Sepehr Elahi, Negar Kiyavash, Patrick Thiran View a PDF of the paper titled Zeroth-Order Stackelberg Control in Combinatorial Congestion Games, by Saeed Masiha and 3 other authors View PDF HTML (experimental) 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 $\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 the strategies that matter most for the War...
