論文の概要: Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
- arxiv url: http://arxiv.org/abs/2203.07181v1
- Date: Mon, 14 Mar 2022 15:21:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-15 14:37:59.436877
- Title: Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
- Title(参考訳): 一般集中型ゲームにおける最適相関平衡:固定パラメータアルゴリズム、硬度および2次元カラム生成
- Authors: Brian Zhang, Gabriele Farina, Andrea Celli, Tuomas Sandholm
- Abstract要約: 様々な種類の最適相関平衡を求める問題について検討する。
本稿では,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。
また、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという2つの新しいベンチマークゲームも導入した。
- 参考スコア(独自算出の注目度): 99.00383370823839
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of finding optimal correlated equilibria of various
sorts: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse
correlated equilibrium (EFCCE), and extensive-form correlated equilibrium
(EFCE). This is NP-hard in the general case and has been studied in special
cases, most notably triangle-free games, which include all two-player games
with public chance moves. However, the general case is not well understood, and
algorithms usually scale poorly. First, we introduce the correlation DAG, a
representation of the space of correlated strategies whose size is dependent on
the specific solution concept. It extends the team belief DAG of Zhang et al.
to general-sum games. For each of the three solution concepts, its size depends
exponentially only on a parameter related to the game's information structure.
We also prove a fundamental complexity gap: while our size bounds for NFCCE are
similar to those achieved in the case of team games by Zhang et al., this is
impossible to achieve for the other two concepts under standard complexity
assumptions. Second, we propose a two-sided column generation approach to
compute optimal correlated strategies. Our algorithm improves upon the
one-sided approach of Farina et al. by means of a new decomposition of
correlated strategies which allows players to re-optimize their sequence-form
strategies with respect to correlation plans which were previously added to the
support. Our techniques outperform the prior state of the art for computing
optimal general-sum correlated equilibria. For team games, the two-sided column
generation approach vastly outperforms standard column generation approaches,
making it the state of the art algorithm when the parameter is large. Along the
way we also introduce two new benchmark games: a trick-taking game that
emulates the endgame phase of the card game bridge, and a ride-sharing game.
- Abstract(参考訳): 本研究では, 正規形粗相関平衡 (NFCCE) , 広範形粗相関平衡 (EFCCE) , 広範形粗相関平衡 (EFCE) の3種類の最適相関平衡を求める問題について検討した。
これは一般的な場合ではnp-hardであり、特に三角形のないゲームで研究されている。
しかし、一般的なケースはよく理解されておらず、アルゴリズムは通常、不十分にスケールする。
まず,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。
これは Zhang らのチーム信念 DAG を一般ゲームに拡張する。
3つの解の概念それぞれについて、その大きさはゲームの情報構造に関連するパラメータに指数関数的にのみ依存する。
nfcceのサイズ境界はzhangらによるチームゲームで達成されたものと似ているが、標準的な複雑性仮定の下で他の2つの概念で達成することは不可能である。
次に,最適相関戦略を計算するための2面列生成手法を提案する。
このアルゴリズムは,従来サポートに追加された相関計画に関して,プレイヤーがシーケンシャルな戦略を再最適化することを可能にする相関戦略の新たな分解によって,farinaら片面的アプローチを改善している。
本手法は,最適一般対等平衡計算における先行技術よりも優れている。
チームゲームでは、双方向コラム生成アプローチは標準的なコラム生成アプローチを大きく上回り、パラメータが大きい場合はartアルゴリズムの状態となる。
その過程で、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという、2つの新しいベンチマークゲームも導入しました。
関連論文リスト
- The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。
そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
論文 参考訳(メタデータ) (2023-05-28T19:41:25Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳(メタデータ) (2023-01-26T17:25:45Z) - Safe Subgame Resolving for Extensive Form Correlated Equilibrium [47.155175336085364]
相関平衡(Correlated Equilibrium)は、ナッシュ平衡(NE)よりも一般的な解概念であり、社会福祉の改善につながる。
テキストサブゲーム解決は,ゼロサムゲームにおけるNEの発見に極めて成功した手法であり,一般サム EFCE の解法である。
サブゲーム解決は、テキストトン方式で相関計画を洗練させる: ゲーム全体を前もって解決するのではなく、実際のプレイで到達したサブゲームにおける戦略のためにのみ解決する。
論文 参考訳(メタデータ) (2022-12-29T14:20:48Z) - Learning in Multi-Player Stochastic Games [1.0878040851638]
有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。
ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。
我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
論文 参考訳(メタデータ) (2022-10-25T19:02:03Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-09-21T17:51:57Z) - Polynomial-Time Computation of Optimal Correlated Equilibria in
Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
本研究では,公的なチャンス移動を伴う2人プレイヤゲームにおいて,最適相関平衡が時間内に計算可能であることを示す。
この結果、10年以上にわたる広範な形式の相関を取り巻く最大の正の複雑性結果が得られた。
論文 参考訳(メタデータ) (2020-09-09T14:51:58Z) - No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。
広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。
提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
論文 参考訳(メタデータ) (2020-04-01T17:39:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。