A Direct Second-Order Method for Solving Two-Player Zero-Sum Games

We introduce, to our knowledge, the first direct second-order method for computing Nash equilibria in two-player zero-sum games. To do so, we construct a Douglas-Rachford-style splitting formulation, which we then solve with a semi-smooth Newton (SSN) method. We show that our algorithm enjoys local superlinear convergence. To augment the fast local behavior of our SSN method with global efficiency guarantees, we develop a hybrid method that combines our SSN method with the state-of-the-art first-order method for game solving, Predictive Regret Matching (PRM$^+$). Our hybrid algorithm leverages the global progress provided by PRM$^+$ while achieving a local superlinear convergence rate once it switches to SSN near a Nash equilibrium. Numerical experiments on matrix games demonstrate order-of-magnitude speedups over PRM$^+$ for high-precision solutions.

Many strategic problems involve direct competition, where one player’s gain is exactly the other player’s loss. These problems are modeled as two-player zero-sum games, which capture settings ranging from simple games like rock-paper-scissors to more complex applications such as heads-up poker and security planning. Our work focuses on these games and addresses a fundamental question: how to efficiently compute a Nash equilibrium, a stable pair of strategies in which neither player can improve by changing their strategy alone. Existing methods for finding Nash equilibria in large zero-sum games rely primarily on first-order information, which makes them scalable and reliable. However, many state-of-the-art methods are not fully understood theoretically and can struggle to find highly accurate solutions which would closely match true optimal strategies. We introduce a hybrid method that leverages both first-order and second-order information to compute high-accuracy solutions more efficiently. The method first uses a standard first-order method to make reliable progress toward an equilibrium, then switches to a second-order method to refine the solution more quickly. We develop an innovative framework allowing us to connect progress in these two regimes, and numerical experiments show that our hybrid method can outperform existing state-of-the-art algorithms for finding Nash equilibria.