精选理由
这篇论文给Gurobi求解多人博弈纳什均衡时加了变量界，让之前一天算不完的三玩家Kuhn扑克能更快解出来，做博弈算法的人可以看看。
该论文针对多人不完美信息博弈的纳什均衡精确计算问题，基于序列形式的非线性互补问题，使用Gurobi的非凸二次求解器并通过McCormick包络进行空间分支定界。此前该方法无法在24小时内解决完整三玩家Kuhn扑克。本文导出了松弛变量和乘子变量的有限界，从而加强凸松弛，显著提升计算效率。在三人Kuhn扑克实验中验证了该方法的改进效果。
AI 翻译 · 中文
该论文针对多人不完美信息博弈的纳什均衡精确计算问题，基于序列形式的非线性互补问题，使用Gurobi的非凸二次求解器并通过McCormick包络进行空间分支定界。此前该方法无法在24小时内解决完整三玩家Kuhn扑克。本文导出了松弛变量和乘子变量的有限界，从而加强凸松弛，显著提升计算效率。在三人Kuhn扑克实验中验证了该方法的改进效果。
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-f…