Efficient Differentiable Path-Following Methods for Computing Nash Equilibria

Abstract The concept of Nash equilibrium, widely regarded as one of the fundamental and elegant ideas in game theory, holds great significance in various domains such as economic analysis and decision-making. Nonetheless, it remains a challenging problem to efficiently compute a Nash equilibrium in normal-form games especially when dealing with large problem sizes. To tackle this challenge, our paper delves into the exploration of various interior-point differentiable path-following methods. These methods are developed by creating three artificial games that integrate entropy-barrier, square-root-barrier, and logarithmic-barrier terms into payoff functions with an extra variable. Through the application of optimality conditions to these artificial games, in conjunction with equilibrium conditions and system variations, we derive nine equilibrium systems, specifying nine smooth paths. These paths start from a totally mixed strategy profile and approach a Nash equilibrium as the extra variable goes to zero. Through comprehensive numerical comparisons, we demonstrate the significant superiority of a logarithmic-barrier method and an entropy-barrier method that we developed over the existing four methods.