多人不完全信息博弈 Nash 均衡计算的变量界收紧方法
Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
AI 导读
Sam Ganzfried 等提出在多人不完全信息博弈 Nash 均衡精确计算中，对非线性互补性规划中的松弛变量与乘子变量给出有限界，以增强空间分支定界中的凸松弛。在完整三人 Kuhn poker 上，全部八种加界配置均在 17 秒内返回数值可验证的均衡，而无界形式在 300 秒内找不到可行解；最细的界并不总是最快。
正文 · 原文
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. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal mixed-integer quadratically constrained program. 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 can strengthen the convex relaxations used within spatial branch-and-bound. We compare uniform corollary bounds with finer proposition-based bounds on full three-player Kuhn poker. All eight bounded configurations return numerically verified equilibria in under 17 seconds, while the unbounded formulation finds no feasible solution within 300 seconds. The finest bounds do not consistently yield the fastest computation.
| Comments: | arXiv admin note: substantial text overlap with arXiv:2509.25618 |
| Subjects: | Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA); Theoretical Economics (econ.TH); Optimization and Control (math.OC) |
| Cite as: | arXiv:2606.25997 [cs.GT] |
| (or arXiv:2606.25997v3 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2606.25997 arXiv-issued DOI via DataCite |
Submission history
From: Sam Ganzfried [view email]
[v1]
Wed, 24 Jun 2026 16:08:33 UTC (12 KB)
[v2]
Tue, 30 Jun 2026 20:59:44 UTC (12 KB)
[v3]
Wed, 4 Nov 2026 01:28:30 UTC (13 KB)
来源：arXiv cs.AI · arxiv.org