A Path-following Polynomial Equations Systems Approach for Computing Nash Equilibria

This paper presents a path-following combinatorial framework based on systems of polynomial equations to compute a mixed Nash equilibrium in 𝑁-person games. We provide the first detailed implementable description of Wilson's path-following method, extending Lemke-Howson's algorithm to N-person games and handling degenerate games. Our approach resembles, in some respects, support enumeration methods. We thus compare both approaches, theoretically and experimentally. Then, we show that the pathfollowing approach allows to deal with a large family of succinctly expressed games: hypergraphical games, graphical games and polymatrix games. The described algorithms have been implemented in Python, making use of Sagemath libraries to solve systems of polynomial equations, allowing an experimental comparison of the different combinatorial approaches on a large variety of games.