論文の概要: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
- arxiv url: http://arxiv.org/abs/2301.09159v1
- Date: Sun, 22 Jan 2023 16:54:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 14:46:50.257485
- Title: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
- Title(参考訳): ツープレイヤーゼロサムゲームにおける不完全情報の抽象化
- Authors: Samuel Sokota, Ryan D'Orazio, Chun Kai Ling, David J. Wu, J. Zico
Kolter, Noam Brown
- Abstract要約: この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームの解法に対する新たな視点への扉を開く。
- 参考スコア(独自算出の注目度): 85.27865680662973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In their seminal work, Nayyar et al. (2013) showed that imperfect information
can be abstracted away from common-payoff games by having players publicly
announce their policies as they play. This insight underpins sound solvers and
decision-time planning algorithms for common-payoff games. Unfortunately, a
naive application of the same insight to two-player zero-sum games fails
because Nash equilibria of the game with public policy announcements may not
correspond to Nash equilibria of the original game. As a consequence, existing
sound decision-time planning algorithms require complicated additional
mechanisms that have unappealing properties. The main contribution of this work
is showing that certain regularized equilibria do not possess the
aforementioned non-correspondence problem -- thus, computing them can be
treated as perfect information problems. Because these regularized equilibria
can be made arbitrarily close to Nash equilibria, our result opens the door to
a new perspective on solving two-player zero-sum games and, in particular,
yields a simplified framework for decision-time planning in two-player zero-sum
games, void of the unappealing properties that plague existing decision-time
planning approaches.
- Abstract(参考訳): Nayyar et al. (2013)では、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この洞察は、コモンペイオフゲームのためのサウンドソルバと意思決定時間計画アルゴリズムの基礎となる。
残念なことに、2人のプレイヤーのゼロサムゲームに対する同じ洞察のナッシュな応用は、ナッシュ均衡と公開ポリシーの発表が元のゲームのナッシュ均衡に合致しない可能性があるため失敗する。
その結果、既存の音響決定時間計画アルゴリズムは、未適用特性を持つ複雑な追加メカニズムを必要とする。
この研究の主な貢献は、ある正規化された平衡が上記の非対応問題を持たないことを示しており、計算は完全な情報問題として扱うことができる。
これらの正規化平衡はnash平衡に任意に近づくことができるため、この結果は2人プレイのゼロサムゲームを解くための新しい視点への扉を開き、特に、2人プレイのゼロサムゲームにおける意思決定時間計画のための簡易なフレームワークを提供する。
関連論文リスト
- Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳(メタデータ) (2022-11-29T05:16:41Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳(メタデータ) (2022-10-24T09:32:40Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳(メタデータ) (2022-08-22T08:31:46Z) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
論文 参考訳(メタデータ) (2022-08-03T16:41:01Z) - Algorithmic Information Design in Multi-Player Games: Possibility and
Limits in Singleton Congestion [10.817873935576412]
本稿では, 負の外部性を持つゲームにおいて, 共用信号と共用信号の両方のアルゴリズム情報設計を開始する。
公開信号とプライベート信号の両方に対して、資源の数が一定である場合に最適な情報設計を効率的に計算できることが示される。
論文 参考訳(メタデータ) (2021-09-25T22:02:32Z) - Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。
ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
論文 参考訳(メタデータ) (2021-08-17T07:06:46Z) - Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games
with Persistent Imperfect Information [1.7132914341329848]
永続的不完全情報を持つマルチプレイヤー汎用ゲームにおいて,ナッシュ均衡を近似するアルゴリズムを提案する。
新たな手法を用いることで,本ゲームにおけるナッシュ均衡を近似した戦略をアルゴリズムで計算できることが証明できる。
論文 参考訳(メタデータ) (2020-10-26T19:27:26Z) - From Poincar\'e Recurrence to Convergence in Imperfect Information
Games: Finding Equilibrium via Regularization [49.368421783733815]
モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。
また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
論文 参考訳(メタデータ) (2020-02-19T21:36:58Z) - Signaling in Bayesian Network Congestion Games: the Subtle Power of
Symmetry [66.82463322411614]
本論文は, 最適遠点透過型シグナリング方式の問題点に焦点をあて, 対称性がその解法において重要な性質であることを示す。
プレイヤーが対称でアフィンコスト関数を持つとき,最適なエクアント説得スキームが計算可能であることを示す。
論文 参考訳(メタデータ) (2020-02-12T19:38:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。