提出新方法精确求解多玩家不完美信息博弈纳什均衡
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
- 基于序列形式博弈构建二次约束规划模型
- 三玩家克鲁斯扑克去支配策略后可快速求解
- 比现有工具更快更准，适合博弈论研究者
近年来，针对大规模双人零和不完美信息博弈的纳什均衡近似算法和多人策略型博弈的精确计算算法取得了显著进展。尽管回溯遗憾最小化和虚构对手迭代在双人零和博弈中具有可扩展性和收敛性保证，但在多人博弈中无法保证收敛到纳什均衡。本文提出一种基于序列形式博弈表示的非线性互补问题的二次约束规划方法，用于精确计算多人不完美信息博弈的纳什均衡。该方法利用近期非凸二次规划求解技术。我们的算法在去除支配策略后的三玩家克鲁斯扑克上可快速求解。Gambit软件套件中唯一能成功求解该游戏的是对数几率量化响应法，但耗时更长且存在近似误差。此外，该公式还为多人策略型博弈提供了新的纳什均衡计算方法，实验证明其优于先前的二次约束规划方法。
原文摘要 · Abstract (English)
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. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。