論文の概要: Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond

• arxiv url: http://arxiv.org/abs/2009.04336v1
• Date: Wed, 9 Sep 2020 14:51:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-20 11:48:38.973124
• Title: Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond
• Title（参考訳）: 公的なチャンス移動を含む2人プレイ型ゲームにおける最適相関平衡の多項式時間計算
• Authors: Gabriele Farina and Tuomas Sandholm
• Abstract要約: 本研究では,公的なチャンス移動を伴う2人プレイヤゲームにおいて,最適相関平衡が時間内に計算可能であることを示す。 この結果、10年以上にわたる広範な形式の相関を取り巻く最大の正の複雑性結果が得られた。
• 参考スコア（独自算出の注目度）: 107.14897720357631
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Unlike normal-form games, where correlated equilibria have been studied for more than 45 years, extensive-form correlation is still generally not well understood. Part of the reason for this gap is that the sequential nature of extensive-form games allows for a richness of behaviors and incentives that are not possible in normal-form settings. This richness translates to a significantly different complexity landscape surrounding extensive-form correlated equilibria. As of today, it is known that finding an optimal extensive-form correlated equilibrium (EFCE), extensive-form coarse correlated equilibrium (EFCCE), or normal-form coarse correlated equilibrium (NFCCE) in a two-player extensive-form game is computationally tractable when the game does not include chance moves, and intractable when the game involves chance moves. In this paper we significantly refine this complexity threshold by showing that, in two-player games, an optimal correlated equilibrium can be computed in polynomial time, provided that a certain condition is satisfied. We show that the condition holds, for example, when all chance moves are public, that is, both players observe all chance moves. This implies that an optimal EFCE, EFCCE and NFCCE can be computed in polynomial time in the game size in two-player games with public chance moves, providing the biggest positive complexity result surrounding extensive-form correlation in more than a decade.
• Abstract（参考訳）: 相関平衡が45年以上研究されてきた通常のゲームとは異なり、広範囲な相関関係は一般にはよく分かっていない。 このギャップの理由の1つは、広範囲なフォームゲームのシーケンシャルな性質が、通常のフォーム設定では不可能である行動やインセンティブの豊かさを可能にするためである。 この豊かさは、広義の相関平衡を取り巻く非常に異なる複雑さの風景へと変換される。 現在では、2プレイヤーの広角ゲームにおいて、最適な広角相関平衡(EFCE)、広角相関平衡(EFCCE)、正規形式相関平衡(NFCCE)の発見は、ゲームがチャンス移動を含まない場合、計算可能であり、ゲームがチャンス移動を伴わない場合には、抽出可能であることが知られている。 本稿では,2人プレイゲームにおいて,ある条件を満たせば最適な相関平衡を多項式時間で計算できることを示すことにより,この複雑性閾値を大幅に改善する。 条件は、例えば、すべてのチャンスが公にされている場合、つまり、両方のプレイヤーがすべてのチャンスの動きを観察する。 これは、EFCE, EFCCE, NFCCEが公的なチャンス移動を持つ2人のプレイヤーゲームにおいて、ゲームサイズにおいて多項式時間で計算できることを示唆し、10年以上にわたって広範囲な形式相関を取り巻く最大の正の複雑性結果を与える。

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
  本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。 そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
  論文  参考訳（メタデータ） (2023-05-28T19:41:25Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
  論文  参考訳（メタデータ） (2020-04-01T17:39:00Z)

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

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