A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
David Yang, Yuan Gao, Tianyi Lin, Christian Kroer
Abstract
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.
BibTeX
@inproceedings{
yang2026a,
title={A Direct Second-Order Method for Solving Two-Player Zero-Sum Games},
author={David Yang and Yuan Gao and Tianyi Lin and Christian Kroer},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=jn7gGAya5h}
}