Search papers, labs, and topics across Lattice.
This paper introduces a novel method for computing Nash equilibria in multiplayer imperfect-information games by deriving finite bounds on slack and multiplier variables in a nonlinear complementarity formulation. By enhancing the convex relaxations used in spatial branch-and-bound, the authors achieve significant computational improvements, outperforming existing algorithms such as those in the Gambit software suite. The method demonstrates its effectiveness in solving three-player Kuhn poker, showcasing its potential for more complex game scenarios despite limitations in solving the full game version within a practical timeframe.
Strengthening variable bounds can dramatically enhance the efficiency of Nash equilibrium computation in multiplayer games, pushing the boundaries of what鈥檚 computationally feasible.
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 via McCormick envelopes. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal MIQCP reformulation. 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 strengthen the convex relaxations used within spatial branch-and-bound and lead to substantial computational improvements. We demonstrate the impact of the proposed bounds on exact Nash equilibrium computation in three-player Kuhn poker.
