論文の概要: Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
- arxiv url: http://arxiv.org/abs/2606.25997v2
- Date: Tue, 30 Jun 2026 20:59:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-02 15:15:53.047885
- Title: Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
- Title（参考訳）: マルチプレイヤー不完全情報ゲームにおけるナッシュ平衡計算のための可変境界強調
- Abstract要約: マルチプレイヤー不完全情報ゲームにおけるナッシュ均衡の近似手法を提案する。
非線形相補性定式化におけるスラック変数と乗算変数の有限境界を導出する。
提案した境界が3人プレイヤのクーンポーカーの正確なナッシュ平衡に与える影響を実証する。
- 参考スコア（独自算出の注目度）: 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. Recently, an approach has been presented for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically constrained program based on a nonlinear complementarity problem formulation derived from the sequence-form game representation. This formulation was solved using Gurobi's nonconvex quadratic solver, which employs spatial branch-and-bound to iteratively refine variable bounds by solving convex relaxations of bilinear terms via McCormick envelopes. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal MIQCP reformulation. This approach was demonstrated to outperform prior algorithms from the Gambit software suite and quickly solve three-player Kuhn poker after removal of dominated actions; however, the algorithm was not able to solve the full version of the game within 24 hours. In this paper, we derive finite bounds on slack and multiplier variables in the nonlinear complementarity formulation. These bounds strengthen the convex relaxations used within spatial branch-and-bound and lead to substantial computational improvements. We demonstrate the impact of the proposed bounds on exact Nash equilibrium computation in three-player Kuhn poker.
- Abstract（参考訳）: 大規模2プレイヤーゼロサム不完全情報ゲームにおけるナッシュ均衡の近似と,マルチプレイヤー戦略形式ゲームにおけるナッシュ均衡の正確な計算に関するアルゴリズムが,近年顕著に進歩している。
反事実的後悔の最小化と架空の遊びは、大きなゲームに対してスケーラブルであり、2つのプレイヤーゼロサムゲームにおいて収束を保証するが、それらはマルチプレイヤーゲームにおいてナッシュ均衡への収束を保証するものではない。
近年, 逐次形式ゲーム表現から導出した非線形相補性問題の定式化に基づいて, 二次的に制約されたプログラムを解くマルチプレイヤー不完全情報ゲームにおいて, ナッシュ均衡の正確な計算法が提案されている。
この定式化は、グロビの非凸二次解法(英語版)を用いて解決され、これは空間分岐とバウンドを用いて、マッコーミックエンベロープ(英語版)を介して双線型項の凸緩和を解くことで、反復的に洗練された可変境界を解く。
事前解決の間、グロビは補助変数を導入し、場合によってはバイナリ変数を導入し、内部のMIQCPの再構成に繋がる。
このアプローチはガンビットのソフトウェアスイートから先行するアルゴリズムより優れており、支配的なアクションの除去後に3人のプレイヤーであるクーンポーカーを素早く解くことができたが、アルゴリズムは24時間以内にゲームの全バージョンを解くことができなかった。
本稿では,非線形相補性定式化におけるスラック変数と乗算変数の有限境界を導出する。
これらの境界は空間的分岐とバウンド内で使われる凸緩和を強化し、かなりの計算改善をもたらす。
提案した境界が3人プレイヤのクーンポーカーの正確なナッシュ平衡計算に与える影響を実証する。
関連論文リスト
- Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
本稿では,非線形近似に基づく2次制約付きプログラムを解くマルチプレイヤー不完全情報ゲームにおける近似手法を提案する。
また,マルチプレイヤー戦略型ゲームにおけるナッシュ均衡の計算手法も提案した。
論文 参考訳（メタデータ） (2025-09-30T00:28:21Z) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳（メタデータ） (2023-03-31T22:50:47Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳（メタデータ） (2023-01-26T17:25:45Z) - 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) - 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) - Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。
正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
論文 参考訳（メタデータ） (2021-05-27T06:10:24Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。