論文の概要: Public Information Representation for Adversarial Team Games

• arxiv url: http://arxiv.org/abs/2201.10377v1
• Date: Tue, 25 Jan 2022 15:07:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-26 16:10:48.065037
• Title: Public Information Representation for Adversarial Team Games
• Title（参考訳）: 対人チームゲームのための公開情報表現
• Authors: Luca Carminati, Federico Cacciamani, Marco Ciccone, Nicola Gatti
• Abstract要約: 対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
• 参考スコア（独自算出の注目度）: 31.29335755664997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The peculiarity of adversarial team games resides in the asymmetric information available to the team members during the play, which makes the equilibrium computation problem hard even with zero-sum payoffs. The algorithms available in the literature work with implicit representations of the strategy space and mainly resort to Linear Programming and column generation techniques to enlarge incrementally the strategy space. Such representations prevent the adoption of standard tools such as abstraction generation, game solving, and subgame solving, which demonstrated to be crucial when solving huge, real-world two-player zero-sum games. Differently from these works, we answer the question of whether there is any suitable game representation enabling the adoption of those tools. In particular, our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. In this converted game, the team is transformed into a single coordinator player who only knows information common to the whole team and prescribes to the players an action for any possible private state. Interestingly, we show that our game is more expressive than the original extensive-form game as any state/action abstraction of the extensive-form game can be captured by our representation, while the reverse does not hold. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one. To limit this explosion, we provide three algorithms, each returning an information-lossless abstraction that dramatically reduces the size of the tree. These abstractions can be produced without generating the original game tree. Finally, we show the effectiveness of the proposed approach by presenting experimental results on Kuhn and Leduc Poker games, obtained by applying state-of-art algorithms for two-player zero-sum games on the converted games
• Abstract（参考訳）: 対戦チームゲームの特異性は、プレイ中にチームメンバーが利用可能な非対称情報の中に存在し、ゼロサムのペイオフであっても平衡計算問題を難しくする。 文献で利用可能なアルゴリズムは戦略空間を暗黙的に表現し、主に戦略空間を漸進的に拡大するために線形プログラミングと列生成技術を利用する。 このような表現は、抽象化生成、ゲーム解決、サブゲーム解決といった標準的なツールの採用を妨げる。 これらの作品とは違って、我々はこれらのツールの採用を可能にする適切なゲーム表現が存在するかどうかという疑問に答える。 特に,我々のアルゴリズムは,対戦相手を持つシーケンシャルなチームゲームから古典的な2プレーヤゼロサムゲームに変換する。 この変換ゲームでは、チームはチーム全体に共通する情報しか知らない単一のコーディネータプレーヤーに変換され、プレイヤーに可能なプライベート状態のアクションを割り当てる。 興味深いことに、我々のゲームはオリジナルの拡張フォームゲームよりも表現力が高く、一方、逆は保持されないので、拡張フォームゲームの状態や動作の抽象化は我々の表現によってキャプチャできる。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。 この爆発を抑えるために、我々は3つのアルゴリズムを提供し、それぞれが木のサイズを劇的に削減する情報ロスレス抽象化を返す。 これらの抽象化は、元のゲームツリーを生成することなく生成できる。 最後に,両プレイヤーゼロサムゲームに対する最先端のアルゴリズムを適用したKuhn と Leduc Poker のゲームに対して実験結果を提示し,提案手法の有効性を示す。

関連論文リスト

• Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach [2.908482270923597]
  本稿では,階層的な情報共有の下での最適性を維持しつつ,決定変数をアンタングルにする方法を示す。 我々のアプローチでは、広義のゲームは常に単一ステージのサブゲームに対する解決策として存在し、時間的複雑さを著しく減少させる。
  論文  参考訳（メタデータ） (2024-02-05T12:33:05Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
  論文  参考訳（メタデータ） (2023-01-22T16:54:06Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving [31.29335755664997]
  emphExのアンテ相関は、プレイヤーのチームがゼロサムゲームで別のチームと対決する、後続のチームゲームにおいて主流のアプローチになりつつある。 本研究は, 連勝チームゲームと2プレーヤゲームとのギャップを埋めることで, この弱点から回復できることを示す。 我々は,emphteam-public-informationと呼ばれる新しいゲーム表現を提案し,チーム全体で共通する情報のみを知り,各メンバーに可能なプライベートな状態に対するアクションを指示する単一コーディネータとして表現する。
  論文  参考訳（メタデータ） (2022-06-18T10:02:08Z)
• Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms [0.6749750044497732]
  不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、大きなゲームで顕著な成功を収めている。 これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化する。 プレイヤー固有の情報状態木に基づく特殊表現の使用が,一般的な回避策であることを示す。
  論文  参考訳（メタデータ） (2021-12-20T22:34:19Z)
• Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion [10.817873935576412]
  本稿では, 負の外部性を持つゲームにおいて, 共用信号と共用信号の両方のアルゴリズム情報設計を開始する。 公開信号とプライベート信号の両方に対して、資源の数が一定である場合に最適な情報設計を効率的に計算できることが示される。
  論文  参考訳（メタデータ） (2021-09-25T22:02:32Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  明示的な人間設計なしに更新ルールの発見を自動化するフレームワークであるLMACを導入する。 意外なことに、人間のデザインがなくても、発見されたMARLアルゴリズムは競争力や性能が向上する。 LMAC は,例えば Kuhn Poker のトレーニングやPSRO の成績など,小型ゲームから大規模ゲームへの一般化が可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-04T22:30:25Z)
• 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)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

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

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