arXiv cs.MA· Sam Ganzfried·· 11 小时前AI 评分18
多人不完全信息博弈纳什均衡计算中的变量边界收紧方法
Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
AI 导读
研究者为多人不完全信息博弈的纳什均衡精确计算提出变量边界收紧方法，对非线性互补形式中的松弛变量和乘子变量推导出有限边界，用于强化空间分支定界中的凸松弛。在完整三人 Kuhn 扑克上，全部 8 种带边界配置均在 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.MA · arxiv.org