A Sequence-Form Characterization and Differentiable Path-Following Computation of Normal-Form Perfect Equilibria in Extensive-Form Games

Abstract: The sequence form, owing to its compact and holistic strategy representation, has demonstrated significant efficiency in computing normal-form perfect equilibria for two-player extensive-form games with perfect recall. Nevertheless, the examination of $n$-player games remains underexplored. To tackle this challenge, we present a sequence-form characterization of normal-form perfect equilibria for $n$-player extensive-form games, achieved through a class of perturbed games formulated in sequence form. Based on this characterization, we develop a differentiable path-following method for computing normal-form perfect equilibria and prove its convergence. This method involves constructing an artificial logarithmic-barrier game in sequence form, where an additional variable is incorporated to regulate the influence of logarithmic-barrier terms to the payoff functions, as well as the transition of the strategy space. We prove the existence of a smooth equilibrium path defined by the artificial game, starting from an arbitrary positive realization plan and converging to a normal-form perfect equilibrium of the original game as the additional variable approaches zero. Furthermore, we extend Harsanyi's linear and logarithmic tracing procedures to the sequence form and develop two alternative methods for computing normal-form perfect equilibria. Numerical experiments further substantiate the effectiveness and efficiency of our methods.