arXiv cs.MA· Sam Ganzfried·· 10 小时前AI 评分18
多人不完全信息博弈纳什均衡计算中的变量边界收紧方法
Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
AI 导读
研究者为多人不完全信息博弈的纳什均衡精确计算提出变量边界收紧方法，对非线性互补形式中的松弛变量和乘子变量推导出有限边界，用于强化空间分支定界中的凸松弛。在完整三人 Kuhn 扑克上，全部 8 种带边界配置均在 17 秒内返回数值验证的均衡，而无边界形式在 300 秒内找不到可行解；最紧的边界并未带来最快计算。
正文 · AI 翻译
摘要：近期，在大型两人零和不完全信息博弈中纳什均衡的近似算法，以及多人策略式博弈中纳什均衡的精确计算方面，取得了显著进展。反事实遗憾最小化和虚拟博弈虽然可扩展到大型博弈，并在两人零和博弈中具有收敛保证，但它们不能保证在多人博弈中收敛到纳什均衡。最近，有人提出了一种用于精确计算多人不完全信息博弈中纳什均衡的方法，该方法基于由序列式博弈表示导出的非线性互补问题公式，求解一个二次约束规划。该公式使用 Gurobi 的非凸二次求解器求解，该求解器采用空间分支定界，通过求解双线性项的凸松弛来迭代细化变量边界。在预处理期间，Gurobi 引入辅助变量，并在某些情况下引入二元变量，从而形成一个内部混合整数二次约束规划。该方法已被证明优于 Gambit 软件套件中的先前算法，并在移除被支配动作后快速求解三人库恩扑克；然而，该算法无法在 24 小时内求解该游戏的完整版本。在本文中，我们推导了非线性互补公式中松弛变量和乘子变量的有限边界。这些边界可以加强空间分支定界中使用的凸松弛。我们在完整的三人库恩扑克上比较了统一推论边界与更精细的命题边界。所有八种有界配置均在 17 秒内返回经数值验证的均衡，而无界公式在 300 秒内找不到可行解。最精细的边界并不总是带来最快的计算速度。
| 评论： | arXiv 管理员注：与 arXiv:2509.25618 存在大量文本重叠 |
| 主题： | 计算机科学与博弈论 (cs.GT)；人工智能 (cs.AI)；多智能体系统 (cs.MA)；理论经济学 (econ.TH)；优化与控制 (math.OC) |
| 引用为： | arXiv:2606.25997 [cs.GT] |
| （或 arXiv:2606.25997v3 [cs.GT] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2606.25997 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Sam Ganzfried [查看电子邮件]
[v1]
2026年6月24日星期三 16:08:33 UTC (12 KB)
[v2]
2026年6月30日星期二 20:59:44 UTC (12 KB)
[v3]
2026年11月4日星期三 01:28:30 UTC (13 KB)
来源：arXiv cs.MA · arxiv.org