Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

• URL: http://arxiv.org/abs/2602.23277v1
• Date: Thu, 26 Feb 2026 17:52:08 GMT
• Title: Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
• Authors: Saeed Masiha, Sepehr Elahi, Negar Kiyavash, Patrick Thiran,
• Abstract summary: We study Stackelberg (leader--follower) tuning of network parameters in congestion games.<n>We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update.<n> Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline.
• Score: 24.797303933023567
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $κ_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.

Related papers

• Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An $α$-Potential Approach [1.4576165959001435]
  We analyze independent policy-gradient (PG) learning in $N$player linear-quadratic (LQ) differential games.<n>For asymmetric interactions, we prove that independent projected PG algorithms converge linearly to an approximate equilibrium.
  arXiv  Detail & Related papers  (2026-02-18T15:55:13Z)
• Learning Equilibria in Matching Games with Bandit Feedback [2.5015086558362247]
  We investigate the problem of learning an equilibrium in a generalized two-sided matching market.<n>We propose a UCB algorithm in which agents form preferences and select actions based on optimistic estimates of the game payoffs.
  arXiv  Detail & Related papers  (2025-06-04T10:15:51Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  We study tractable $Phi$-equilibria in non-concave games.<n>We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• Adaptively Perturbed Mirror Descent for Learning in Games [10.868347525353293]
  We propose a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone. We show that our algorithm exhibits significantly accelerated convergence.
  arXiv  Detail & Related papers  (2023-05-26T04:02:54Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way. We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
  arXiv  Detail & Related papers  (2023-02-20T16:05:04Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game. Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning. We propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming. The second algorithm adds a twist by cutting short the followers' evolution trajectory.
  arXiv  Detail & Related papers  (2022-09-15T21:32:23Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• Optimization Induced Equilibrium Networks [76.05825996887573]
  Implicit equilibrium models, i.e., deep neural networks (DNNs) defined by implicit equations, have been becoming more and more attractive recently. We show that deep OptEq outperforms previous implicit models even with fewer parameters.
  arXiv  Detail & Related papers  (2021-05-27T15:17:41Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.