論文の概要: Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
- arxiv url: http://arxiv.org/abs/2406.15970v1
- Date: Sun, 23 Jun 2024 00:27:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-25 19:43:16.036981
- Title: Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
- Title（参考訳）: 不完全なリコールゲーム:平衡概念とその複雑さ
- Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul W. Goldberg, Vincent Conitzer,
- Abstract要約: エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
- 参考スコア（独自算出の注目度）: 74.01381499760288
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes P, PPAD, PLS, $\Sigma_2^P$ , $\exists$R, and $\exists \forall$R.
- Abstract（参考訳）: エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
例えば、欠席したドライバーゲームや、メンバーが限られたコミュニケーション能力を持つチームゲームである。
不完全なリコールを伴う広範形式のゲームフレームワークにおいて、我々は3つの異なる解概念(ナッシュ、明示的決定理論(EDT)に基づくマルチセル、因果的決定理論(CDT)に基づくマルチセル)にまたがるマルチプレイヤー設定における平衡を求める計算複雑性を解析した。
我々は正確な解計算と近似解計算の両方に興味を持っている。
特殊な場合として,(1)単プレイヤーゲーム,(2)二プレイヤーゼロサムゲーム,および最大値との関係,(3)外因性確率性のないゲーム(チャンスノード)を考える。
これらの問題を複雑性クラス P, PPAD, PLS, $\Sigma_2^P$, $\exists$R, $\exists \forall$R に関連付ける。
関連論文リスト
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。
本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。
我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-06-06T15:59:17Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。
そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
論文 参考訳（メタデータ） (2023-05-28T19:41:25Z) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
論文 参考訳（メタデータ） (2023-01-22T16:54:06Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳（メタデータ） (2021-11-07T21:15:35Z) - Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games
with Persistent Imperfect Information [1.7132914341329848]
永続的不完全情報を持つマルチプレイヤー汎用ゲームにおいて,ナッシュ均衡を近似するアルゴリズムを提案する。
新たな手法を用いることで,本ゲームにおけるナッシュ均衡を近似した戦略をアルゴリズムで計算できることが証明できる。
論文 参考訳（メタデータ） (2020-10-26T19:27:26Z) - Signaling in Bayesian Network Congestion Games: the Subtle Power of
Symmetry [66.82463322411614]
本論文は, 最適遠点透過型シグナリング方式の問題点に焦点をあて, 対称性がその解法において重要な性質であることを示す。
プレイヤーが対称でアフィンコスト関数を持つとき,最適なエクアント説得スキームが計算可能であることを示す。
論文 参考訳（メタデータ） (2020-02-12T19:38:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。