Finding and Only Finding Local Nash Equilibria by Both Pretending to Be a Follower

Abstract

Finding local Nash equilibria in two-player differentiable games is a classical problem in game theory with important relevance in machine learning. We propose double Follow-the-Ridge (double-FTR), an algorithm that locally converges to and only to local Nash equilibria in general-sum two-player differentiable games. To our knowledge, double-FTR is the first algorithm with such guarantees for general-sum games. Furthermore, we show that by varying its preconditioner, double-FTR leads to a broader family of algorithms with the same properties. Double-FTR avoids oscillation near equilibria due to the real-eigenvalues of its Jacobian at critical points. Finally, we empirically verify the effectiveness of double-FTR in finding local Nash equilibria in two simple examples.