論文の概要: The Computational Complexity of Single-Player Imperfect-Recall Games
- arxiv url: http://arxiv.org/abs/2305.17805v1
- Date: Sun, 28 May 2023 19:41:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 16:38:25.682471
- Title: The Computational Complexity of Single-Player Imperfect-Recall Games
- Title（参考訳）: シングルプレイヤー不完全リコールゲームの計算複雑性
- Authors: Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg
- Abstract要約: 本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。
そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
- 参考スコア（独自算出の注目度）: 37.550554344575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study single-player extensive-form games with imperfect recall, such as
the Sleeping Beauty problem or the Absentminded Driver game. For such games,
two natural equilibrium concepts have been proposed as alternative solution
concepts to ex-ante optimality. One equilibrium concept uses generalized double
halving (GDH) as a belief system and evidential decision theory (EDT), and
another one uses generalized thirding (GT) as a belief system and causal
decision theory (CDT). Our findings relate those three solution concepts of a
game to solution concepts of a polynomial maximization problem: global optima,
optimal points with respect to subsets of variables and Karush-Kuhn-Tucker
(KKT) points. Based on these correspondences, we are able to settle various
complexity-theoretic questions on the computation of such strategies. For
ex-ante optimality and (EDT,GDH)-equilibria, we obtain NP-hardness and
inapproximability, and for (CDT,GT)-equilibria we obtain CLS-completeness
results.
- Abstract（参考訳）: 睡眠美観問題や欠席ドライバゲームなど,不完全なリコールを伴うシングルプレイヤーの広範型ゲームについて検討した。
そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
1つの平衡概念は、一般化二重半減法(gdh)を信念体系と証拠決定理論(edt)とし、もう1つは一般化三分法(gt)を信念体系と因果決定理論(cdt)として用いる。
本研究は,多項式最大化問題の解概念である大域最適点,変数の部分集合に対する最適点,KKT(Karush-Kuhn-Tucker)点の3つの解概念について考察した。
これらの対応に基づいて,これらの戦略の計算に関する様々な複雑性理論的な疑問を解決できる。
元アンティー最適性と(EDT,GDH)-平衡についてはNP硬度と不適応性を求め,(CDT,GT)-平衡についてはCLS完全性を求める。
関連論文リスト
- Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。
不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
論文 参考訳（メタデータ） (2024-06-23T00:27:28Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - 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) - Equilibrium Design for Concurrent Games [5.9873770241999]
ゲーム理論において、メカニズム設計は、ゲームの望ましい結果を達成するためのインセンティブの設計に関係している。
インセンティブの設計について検討し、例えば、所与の時間論理的性質を満たす平衡を求める。
応用として、平衡設計は、並列ゲームに対する合理的な合成と検証問題の代替解として用いられる。
論文 参考訳（メタデータ） (2021-06-18T15:45:45Z) - Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers [21.462231105582347]
本稿では,n-player, general-sum extensive form game におけるエージェントのトレーニングアルゴリズムを提案する。
また,メタソリューションとして相関平衡(CE)を提案するとともに,新しい解法概念であるGini Correlated Equilibrium(MGCE)を提案する。
JPSROのためのCEメタソルバを用いていくつかの実験を行い、n-player, general-sumゲーム上で収束を示す。
論文 参考訳（メタデータ） (2021-06-17T12:34:18Z) - Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。
我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。
本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
論文 参考訳（メタデータ） (2020-12-10T18:30:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。