arXiv:2602.23277cs.GTcs.LG2026-02被引 1

无需梯度计算,快速优化交通网络中的拥堵均衡问题。

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

  • 用零阶优化避开求解均衡的复杂导数计算
  • 实测速度比传统方法快上百倍,收敛到最优均衡
  • 适合交通调度、网络资源分配等实际场景

我们研究组合式拥堵博弈中领导者通过调节收费、容量或激励来优化网络性能的问题。用户以自利方式选择离散路径,在达到拥堵均衡时,系统目标函数(如总通行时间)通常非光滑,因使用路径集合可能突变。本文提出 ZO-Stackelberg 算法,将无投影的 Frank-Wolfe 均衡求解器与零阶外层更新结合,避免对均衡进行反向传播。理论上证明其可收敛至真实均衡目标的广义 Goldstein 静止点,且误差依赖于均衡近似精度。分析了子采样代理:若以概率 $κ_m$ 采到精确最小化器,则 Frank-Wolfe 误差以 $\mathcal{O}(1/(κ_m T))$ 衰减。提出分层采样策略,防止关键路径类集中导致 $κ_m$ 过小。在真实网络上的实验表明,该方法相比基于梯度的基线实现数量级提速,并成功收敛至跟随者均衡。

原文摘要 · Abstract (English)

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.

博弈论交通优化零阶优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。