論文の概要: Paradoxes of Game Theoretic Equilibria and Price of Anarchy

• arxiv url: http://arxiv.org/abs/2607.11752v1
• Date: Mon, 13 Jul 2026 16:09:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-14 17:47:21.546767
• Title: Paradoxes of Game Theoretic Equilibria and Price of Anarchy
• Title（参考訳）: ゲーム理論平衡のパラドックスとアナーキの価格
• Abstract要約: マルチエージェント学習を均衡に還元することは、動的不均衡とゲーム論的境界の基盤を曖昧にすることを示す。 最悪の純粋なナッシュ均衡は、ロバストなアナーキー境界のプライスを、トポロジカルに不安定な厳密なサドルとして表している。 学習軌跡を関連遊びの離散的単純度に投影することは、体系的に非合理的な振る舞いを許容する。
• 参考スコア（独自算出の注目度）: 36.44731230315158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For decades, static solution concepts (Nash, Correlated, and Coarse Correlated Equilibria) and the Price of Anarchy (PoA) have formed the bedrock of algorithmic game theory, with no-regret learning proving fast convergence to such game-theoretic equilibria. We show that reducing multi-agent learning to static equilibrium and black-box regret analysis obscures underlying dynamic disequilibrium and game theoretic bounds. First, interior Nash equilibria lack $C^1$ vector field information, meaning agents cannot distinguish aligned from strictly opposing incentives. Inheriting this geometry, the worst-case pure Nash equilibria dictating robust PoA bounds manifest as topologically unstable strict saddles, and in canonical congestion games, as global repellers supported on almost everywhere strictly dominated strategies. Anchoring efficiency guarantees to these unstable states causes algebraic sensitivity; we prove that accommodating all strictly positive affine costs renders the PoA unbounded. Furthermore, projecting learning trajectories onto the discrete simplex of correlated play systematically accommodates non-rationalizable behavior. Evaluating dynamics via Coarse Correlated Equilibria or proximal refinements fails to preclude strictly dominated strategies. Moreover, optimal $O(1/T)$ swap-regret minimization does not preclude macroscopic turbulence, manifesting as chaotic limit sets even in minimal games. Finally, we examine the non-atomic limit of congestion games. Though considered highly stable with tight sub-linear $Θ(p/\ln p)$ PoA bounds (where $p$ is the polynomial degree), we prove that under discrete-time learning, the unique equilibrium destabilizes into Li-Yorke chaos and global attractors whose time-averaged inefficiency degrades exponentially as $2^p$. These results necessitate re-evaluating worst-case equilibrium frameworks for dynamically grounded metrics.
• Abstract（参考訳）: 何十年もの間、静的解の概念 (Nash, Correlated, and Coarse Correlated Equilibria) とPrice of Anarchy (PoA) はアルゴリズムゲーム理論の基盤を形成してきた。 我々は,マルチエージェント学習を静的平衡とブラックボックス後悔分析に還元することは,動的不平衡とゲーム理論の境界を曖昧にすることを示した。 第一に、内部のナッシュ平衡にはベクトル場の情報がないため、エージェントは厳密に反対のインセンティブとは区別できない。 この幾何学を継承し、最悪の純粋なナッシュ均衡は、ポア境界を強固に定めているポア境界を位相的に不安定な厳密なサドルとして表し、大域的なレペラーがほぼ至る所で厳密に支配された戦略を支持しているため、カノニカルな混雑ゲームで表している。 これらの不安定な状態に対するアンコリング効率の保証は代数的感度を生じさせ、全ての厳密な正のアフィンコストを調節することで、PoAは非有界であることが証明される。 さらに、関連遊びの離散的単純度に学習軌跡を投影することは、非合理的な振る舞いを体系的に許容する。 粗相関平衡(英語版)または近位改良(英語版)による力学の評価は、厳密に支配された戦略を妨げない。 さらに、最適$O(1/T)$ swap-regret 最小化は、最小のゲームでもカオス極限セットとして現れる、マクロな乱流を妨げない。 最後に,混雑ゲームにおける非原子的限界について検討する。 厳密な線形部分線型(英語版)(p/\ln p)$ PoA 境界(英語版)(ここで$p$は多項式の次数)で非常に安定であると考えられるが、離散時間学習においては、一意の平衡がLi-Yorkeカオスや大域的誘引子へと不安定化し、平均的な非効率性は指数関数的に 2^p$ となることを証明している。 これらの結果は、動的に接地されたメトリクスに対する最悪の平衡フレームワークを再評価する必要がある。

関連論文リスト

• Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria [3.061219970798378]
  現実世界のマルチエージェントシステムは、個々のインセンティブが集団福祉と矛盾する一般的なサムゲームとしてモデル化されることが多い。 標準深層マルチエージェント強化学習法(MARL)はこの問題に対処する。 提案する$-Actor-Critic($-AC)は,スワップリミスの最小化を利用して,高次相関均衡に向けて学習を行うフレームワークである。
  論文  参考訳（メタデータ） (2026-06-09T16:40:26Z)
• Zeroth-Order Stackelberg Control in Combinatorial Congestion Games [24.797303933023567]
  渋滞ゲームにおけるネットワークパラメータのStackelbergチューニングについて検討する。 ZO-StackelbergはプロジェクションフリーのFrank-Wolfe平衡解法とゼロ階外更新を結合する。 実世界のネットワークにおける実験により,本手法が微分ベースライン上での次数-次数-次数高速化を実現することを示す。
  論文  参考訳（メタデータ） (2026-02-26T17:52:08Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。 我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。 重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
  論文  参考訳（メタデータ） (2026-02-24T05:32:03Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy [8.430481660019451]
  本稿では,非直交スワップ後悔を線形上界で最小化するための効率的なアルゴリズムを提案する。 我々は、ベイズ-ナッシュ均衡から平衡への滑らかさの議論に基づいて、アナーキーの価格に関する既存の下限を拡大する。
  論文  参考訳（メタデータ） (2023-04-11T06:22:51Z)
• Follow-the-Regularized-Leader Routes to Chaos in Routing Games [23.497377573947382]
  ゲームにおけるフォロー・ザ・レギュラライズ・リーダー(FoReL)ダイナミクスのカオス行動の出現について検討する。 安定なナッシュ平衡の共存や同じゲームにおけるカオスなど、新しい非標準現象の存在を示す。 FoReLダイナミクスは奇妙で非平衡ですが、我々は時間平均が学習率の選択とコストのあらゆるスケールのために正確な平衡にまだ収束していることを証明します。
  論文  参考訳（メタデータ） (2021-02-16T06:40:31Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)

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

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