論文の概要: Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

• arxiv url: http://arxiv.org/abs/2602.23277v1
• Date: Thu, 26 Feb 2026 17:52:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-27 18:41:22.821466
• Title: Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
• Title（参考訳）: コンビネーションゲームにおけるゼロ階スタックルバーグ制御
• Authors: Saeed Masiha, Sepehr Elahi, Negar Kiyavash, Patrick Thiran,
• Abstract要約: 渋滞ゲームにおけるネットワークパラメータのStackelbergチューニングについて検討する。 ZO-StackelbergはプロジェクションフリーのFrank-Wolfe平衡解法とゼロ階外更新を結合する。 実世界のネットワークにおける実験により,本手法が微分ベースライン上での次数-次数-次数高速化を実現することを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: コングレーションゲームにおけるネットワークパラメータ(トール,キャパシティ,インセンティブ)を,利己的なユーザが個別のルート(あるいは他の組合せ戦略)を選択し,コングレーション均衡に落ち着くように調整する。 リーダーは平衡で評価されるシステムレベルの目標(例えば全旅行時間)を最小化するが、この目的は通常、使用戦略の集合が突然変化するため、非滑らかである。 プロジェクションフリーのFrank-Wolfe平衡解法をゼロ階外更新と組み合わせたZO-Stackelbergを提案する。 我々は、真の平衡目標の一般化されたゴールドスタイン定常点への収束を、平衡近似誤差に明示的に依存して証明し、サブサンプリングされたオラクルを解析する: 正確な最小値が確率$κ_m$でサンプリングされた場合、フランク=ウルフ誤差は$\mathcal{O}(1/(κ_m T))$として崩壊する。 また、ウォードロップ均衡に最も重要となる戦略がいくつかの支配的な組合せ類(例えば、短い経路)に集中する場合に、κ_m$の消滅を避けるための実践的な方法として成層サンプリングを提案する。 実世界のネットワークにおける実験により,本手法は従属平衡に収束しながら,微分ベースライン上での次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数-次数

関連論文リスト

• Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An $α$-Potential Approach [1.4576165959001435]
  我々は$N$player linear-quadratic (LQ) 差分ゲームにおける独立ポリシー勾配学習を解析する。 非対称相互作用に対しては、独立射影PGアルゴリズムが近似平衡に線形に収束することが証明される。
  論文  参考訳（メタデータ） (2026-02-18T15:55:13Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• Adaptively Perturbed Mirror Descent for Learning in Games [10.868347525353293]
  本稿では,ペイオフ関数の勾配が単調なゲームにおいて,ミラーDescent(MD)アルゴリズムに対するペイオフ摂動手法を提案する。 その結果,アルゴリズムの収束が著しく加速していることが判明した。
  論文  参考訳（メタデータ） (2023-05-26T04:02:54Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。 第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
  論文  参考訳（メタデータ） (2022-09-15T21:32:23Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。