Poster
in
Workshop: Gamification and Multiagent Solutions
Finding and only finding local Nash equilibria by both pretending to be a follower
Xuchan Bao · Guodong Zhang
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 whose attracting critical points are equivalent to differential Nash equilibria in general-sum two-player differential 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.