論文の概要: Fixed Sets and the Hardness of Computing Correlated Equilibria
- arxiv url: http://arxiv.org/abs/2610.28141v2
- Date: Wed, 21 Oct 2026 13:06:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-23 00:40:06.091603
- Title: Fixed Sets and the Hardness of Computing Correlated Equilibria
- Title（参考訳）: 固定集合と計算関連平衡の硬さ
- Abstract要約: ポリトープゲームの近似相関平衡の計算はPPAD完全であることを示す。
このことは、相関平衡はナッシュ平衡よりもトラクタブル対象である、というゲーム理論の従来の見解に挑戦する。
- 参考スコア（独自算出の注目度）: 87.25174053648612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function $f$ is a nonempty finite set $S$ such that $S \subseteq \operatorname{conv} f(S)$. Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.
- Abstract（参考訳）: ポリトープゲームの近似相関平衡の計算はPPAD完全であり、したがって多項式時間でナッシュ平衡を求めることに等しいことを示す。
このことは、相関平衡はナッシュ平衡よりもトラクタブル対象である、というゲーム理論の従来の見解に挑戦する。
概念的観点から、同値平衡を固定点の自然な一般化と結び付け、固定集合と呼ぶ。
連続函数の固定集合 $f$ は空でない有限集合 $S$ であり、$S \subseteq \operatorname{conv} f(S)$ である。
我々の主な技術的貢献は、固定集合の計算が逆多項式精度においてもPPADハードであることを証明することである。
関連論文リスト
- Normal-Form Correlation in Markov Games [87.25174053648612]
我々は,一定数のプレイヤーを持つ有限ホライゾンゲームにおいて,NFCEの最初の効率的なアルゴリズムを確立する。
PPAD完全性(PPAD-completeness)、すなわち、多人数ゲームにおいて、あるいは指数的に精度が小さい場合に、ナッシュ平衡と計算等価性を示す。
論文 参考訳（メタデータ） (2026-10-02T17:18:51Z) - Paradoxes of Game Theoretic Equilibria and Price of Anarchy [36.44731230315158]
マルチエージェント学習を均衡に還元することは、動的不均衡とゲーム論的境界の基盤を曖昧にすることを示す。
最悪の純粋なナッシュ均衡は、ロバストなアナーキー境界のプライスを、トポロジカルに不安定な厳密なサドルとして表している。
学習軌跡を関連遊びの離散的単純度に投影することは、体系的に非合理的な振る舞いを許容する。
論文 参考訳（メタデータ） (2026-07-13T16:09:35Z) - On the Computational Complexity of Performative Prediction [59.584063949469645]
我々は、$$-performatively stable pointの計算がPPAD完全であることを示す。
我々の重要な技術的貢献の1つは、PPAD-hardnessの結果を一般的な凸領域に拡張することである。
論文 参考訳（メタデータ） (2026-01-28T02:26:35Z) - Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation [8.784438985280092]
プレイヤーの戦略が共有結合制約を受ける連続静的ゲームにおけるナッシュ均衡の存在と計算について検討する。
具体的には、プレイヤーワイド・コンケーブユーティリティとプレイヤーワイド・コンケーブ制約によって許容されるゲームのクラスに焦点を当てる。
論文 参考訳（メタデータ） (2025-09-17T14:33:49Z) - Games played by Exponential Weights Algorithms [0.0]
各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。
厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
論文 参考訳（メタデータ） (2024-07-09T08:49:51Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。
純粋なナッシュ平衡は存在せず、従って近似平衡を考える。
与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
論文 参考訳（メタデータ） (2021-12-14T14:47:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。