論文の概要: Computing Equilibrium beyond Unilateral Deviation
- arxiv url: http://arxiv.org/abs/2604.28186v1
- Date: Thu, 30 Apr 2026 17:59:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-01 16:31:54.249113
- Title: Computing Equilibrium beyond Unilateral Deviation
- Title（参考訳）: 片側偏差を超えた計算平衡
- Authors: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar,
- Abstract要約: 我々は、連立偏差のインセンティブを最小限に抑える、代替ソリューションの概念を研究している。
具体的には、逸脱する連立の平均利得を最小化することに集中し、枠組みを重み付き平均利得と最大結束利得に拡張する。
平均ゲインと最大ゲインの目的に対して、そのような平衡計算の複雑さの低いバウンダリを証明し、このバウンダリに一致するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.786964046329455
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes solution concepts that provide stability against multilateral deviations (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish, and is therefore guaranteed to exist. Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains. In contrast, the minimum-gain analogue is shown to be computationally intractable. For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound. Finally, we use our framework to solve the \emph{Exploitability Welfare Frontier} (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).
- Abstract（参考訳）: ナッシュや相関平衡のようなよく知られた平衡概念は、一方的に逸脱することで、一人のプレイヤーが有用性を向上できないことを保証している。
彼らは、連立政権による利益の協調的逸脱に対する保証を提供していない。
文献では、多角偏差に対する安定性を提供する解の概念 (\emph{e g }, strong Nash and coalition-proof equilibrium) が提案されているが、これらは一般には存在しない。
本稿では,連立偏差インセンティブを最小化する代替ソリューションの概念について検討する。
具体的には、逸脱する連立の平均利得を最小化することに集中し、枠組みを重み付き平均利得と最大結束利得に拡張する。
対照的に、最小利得アナログは計算的に難解であることが示される。
平均ゲインと最大ゲインの目的に対して、そのような平衡計算の複雑さの低いバウンダリを証明し、このバウンダリに一致するアルゴリズムを提案する。
最後に、我々の枠組みを用いて、与えられた搾取性(全一方的偏差に対する最大利得)に基づく達成可能な社会福祉の最大化である「emph{Exploitability Welfare Frontier} (EWF)」を解決する。
関連論文リスト
- Maximin Relative Improvement: Fair Learning as a Bargaining Problem [24.940259610524482]
グループフェアネスをサブ集団間の交渉問題として解釈するアプローチを根本的に異なるアプローチで提案する。
このゲーム理論的な観点は、最悪のグループ損失の最小化や後悔の最小化のような既存の堅牢な最適化手法が古典的なバリ取り解に対応していることを示している。
そこで我々は,Kalai-Smorodinsky溶液を回収するベースライン予測器によるリスク低減と潜在的な低減の相対的改善を提案する。
論文 参考訳（メタデータ） (2026-02-04T02:44:56Z) - Attack-Resistant Uniform Fairness for Linear and Smooth Contextual Bandits [21.090584232258056]
我々は,線形および滑らかな報酬関数に対して,最小限の後悔を解く新しいアルゴリズムを開発した。
最小限の$tildeO(1)の予算を持つ敵は、従来の攻撃のように全体的な性能を低下させるだけでなく、悪質なフェアネス固有の障害を選択的に誘発できることを示す。
論文 参考訳（メタデータ） (2026-02-04T01:37:47Z) - Toward a Sustainable Federated Learning Ecosystem: A Practical Least Core Mechanism for Payoff Allocation [71.86087908416255]
最小コア(LC)概念に基づく配当フレームワークを提案する。
従来の方法とは異なり、LCは最大の不満を最小限に抑えてフェデレーションの凝集を優先する。
統合侵入検知におけるケーススタディは、我々のメカニズムが重要な貢献者や戦略的提携を正しく識別できることを実証している。
論文 参考訳（メタデータ） (2026-02-03T11:10:50Z) - From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium [52.28048367430481]
マルチエージェントフレームワークは、大規模言語モデル(LLM)の推論能力を高めることができるが、通常は計算コストと収束保証が欠如している。
我々は、不完全情報ゲームとしてマルチLLMコーディネーションをリキャストし、ベイズナッシュ均衡(BNE)を求める。
我々は、分散推論と集中的な最終出力を結合する階層的強化学習パラダイムである、Nash Equilibrium (ECON)による効率的なコーディネーションを導入する。
論文 参考訳（メタデータ） (2025-06-09T23:49:14Z) - Vairiational Stochastic Games [1.6703448188585752]
本稿では分散型マルチエージェントシステムに適した新しい変分推論フレームワークを提案する。
我々のフレームワークは、非定常性と非整合エージェントの目的によって引き起こされる課題に対処する。
提案した分散アルゴリズムに対する理論的収束保証を示す。
論文 参考訳（メタデータ） (2025-03-08T03:21:23Z) - Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems [4.243592852049963]
一般化されたナッシュ均衡ゲームのための新しいオンライン実現可能な点法を提案する。
エージェント間の通信が制限されているという仮定の下で、本手法は実現可能性を保証する。
我々は、我々の方法の平衡への収束が保証される良性一般化ナッシュ均衡問題のクラスを特定する。
論文 参考訳（メタデータ） (2024-10-03T11:27:55Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。
低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。
上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
論文 参考訳（メタデータ） (2023-02-20T16:05:04Z) - Linear Regression Games: Convergence Guarantees to Approximate
Out-of-Distribution Solutions [35.313551211453266]
本研究では,アンサンブルゲームに$ell_infty$の球体を投影することにより,線形回帰に対するAhuja et al.のフレームワークを拡張した。
このような予測は、完全な不変性を達成していないにもかかわらず、非自明なOOD保証を達成するのに有効であることを示す。
論文 参考訳（メタデータ） (2020-10-28T21:10:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。