論文の概要: Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
- arxiv url: http://arxiv.org/abs/2509.25618v1
- Date: Tue, 30 Sep 2025 00:28:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-01 14:44:59.96747
- Title: Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
- Title（参考訳）: マルチプレイヤー不完全情報ゲームにおけるナッシュ平衡計算のための二次計画法
- Authors: Sam Ganzfried,
- Abstract要約: 本稿では,非線形近似に基づく2次制約付きプログラムを解くマルチプレイヤー不完全情報ゲームにおける近似手法を提案する。
また,マルチプレイヤー戦略型ゲームにおけるナッシュ均衡の計算手法も提案した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.
- Abstract（参考訳）: 大規模2プレイヤーゼロサム不完全情報ゲームにおけるナッシュ均衡の近似と,マルチプレイヤー戦略形式ゲームにおけるナッシュ均衡の正確な計算に関するアルゴリズムが,近年顕著に進歩している。
反事実的後悔の最小化と架空の遊びは、大きなゲームに対してスケーラブルであり、2つのプレイヤーゼロサムゲームにおいて収束を保証するが、それらはマルチプレイヤーゲームにおいてナッシュ均衡への収束を保証するものではない。
本稿では, 逐次形式ゲーム表現からの非線形相補性問題の定式化に基づいて, 二次的に制約されたプログラムを解くマルチプレイヤー不完全情報ゲームにおけるナッシュ均衡の正確な計算手法を提案する。
このアプローチは、非凸二次プログラムを解くための最近の進歩を生かしている。
我々のアルゴリズムは、支配的なアクションを除去した後、三人組のクーンポーカーを迅速に解くことができる。
Gambitソフトウェアスイートで利用可能なアルゴリズムのうち、ロジット量子応答アプローチのみがこのゲームを解くのに成功しているが、この手法は我々のアルゴリズムよりも長くかかり、近似の程度も伴う。
我々の定式化はまた、従来の2次制約付きプログラム定式化よりも優れていることを示すマルチプレイヤー戦略形式のゲームにおいて、ナッシュ均衡を計算するための新しいアプローチをもたらす。
関連論文リスト
- Approximating Nash Equilibria in General-Sum Games via Meta-Learning [18.688759383834345]
我々はメタラーニングを用いて、後悔の最小化による戦略の相関を最小化する。
我々のアルゴリズムは、最先端の後悔最小化手法よりも、ナッシュ平衡の近似がはるかに優れている。
論文 参考訳（メタデータ） (2025-04-26T09:33:50Z) - 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) - 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) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - 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) - Algorithm for Computing Approximate Nash Equilibrium in Continuous Games
with Application to Continuous Blotto [1.7132914341329848]
連続ゲームにおけるナッシュ均衡戦略を近似する新しいアルゴリズムを提案する。
また,2プレイヤーゼロサムゲームに加えて,マルチプレイヤーゲームや不完全な情報を持つゲームにも適用できる。
論文 参考訳（メタデータ） (2020-06-12T19:53:18Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。