A sequence-form differentiable path-following method to compute Nash equilibria

The sequence-form representation has shown remarkable efficacy in computing Nash equilibria for two-player extensive-form games with perfect recall. Nonetheless, devising an efficient algorithm for n-player games using the sequence form remains a substantial challenge. To bridge this gap, we establish a necessary and sufficient condition, characterized by a polynomial system, for Nash equilibrium within the sequence-form framework. Building upon this, we develop a sequence-form differentiable path-following method for computing a Nash equilibrium. This method involves constructing an artificial logarithmic-barrier game in sequence form, where two functions of an auxiliary variable are introduced to incorporate logarithmic-barrier terms into the payoff functions and construct the strategy space. Afterward, we prove the existence of a smooth path determined by the artificial game, originating from an arbitrary totally mixed behavioral-strategy profile and converging to a Nash equilibrium of the original game as the auxiliary variable approaches zero. In addition, a convex-quadratic-penalty method and a variant of linear tracing procedure in sequence form are presented as two alternative techniques for computing a Nash equilibrium. Numerical comparisons further illuminate the effectiveness and efficiency of these methods.