Two Sequence-Form Interior-Point Differentiable Path-Following Method to Compute Nash Equilibria

Two Sequence-Form Interior-Point Differentiable Path-Following Method to Compute Nash Equilibria

Introduction and Motivation

This paper presents an advanced approach to computing Nash equilibria (NE) in finite $n$-player extensive-form games (EFGs) with perfect recall, leveraging the sequence-form representation. Traditional computational methods exploit sequence form merely as a dimensionality reduction mechanism, relying on behavioral-strategy Nash equilibrium or as an equivalent variable substitution. This work departs from that paradigm by formalizing and rigorously deriving a notion of Nash equilibrium uniquely defined in terms of sequence form, and then establishes its equivalence to the standard mixed-strategy Nash equilibrium. This provides a theoretical clarification and unification that is required for the systematic analysis of equilibria in EFGs.

Following the theoretical developments, the paper introduces and analyzes a single-stage interior-point differentiable path-following algorithmic framework. This method integrates logarithmic-barrier regularization into the payoff structure to induce a differentiable path within the feasible set of strictly positive realization plans, thus facilitating stable numerical path tracing to a NE. Comparative experiments on EFG benchmarks and randomly generated games validate the effectiveness, numerical stability, and efficiency of the proposed algorithms.

Sequence-Form Nash Equilibrium: Theory and Equivalence

The paper formalizes the notion of sequence-form Nash equilibrium (SFNE). In the sequence form, decision variables are realization plans (i.e., consistent marginals on action sequences) rather than strategies over full normal-form supports. The authors define "best-response sequences" and establish that a SFNE is a realization plan profile $\gamma^*$ such that a sequence $\varpi^i$ is played with positive probability only if it is not strictly dominated in terms of maximal expected payoff achievable compatibly with $\gamma^{*-i}$.

Through constructive equivalence proofs, it is rigorously shown that the set of sequence-form Nash equilibria coincides with the set of mixed-strategy Nash equilibria. This is established by demonstrating correspondence between realization plans and mixed strategies, and by showing that equilibrium-supporting realization plans identify exactly the same set of rationalizable strategy profiles as in the mixed-strategy domain.

Equilibrium Characterization as a Polynomial System

The best-response conditions in sequence form are shown to correspond to a system of polynomial equations and inequalities—specifically, the KKT conditions arising from each player's best-response linear program given the other players' realization plans. This enables the NE computation problem to be recast as that of finding zeros of a polynomial system over the domain of valid realization plans. A critical technical observation is that the realization equivalence induced by perfect recall ensures these computations are free from degeneracies that plague the normal-form approach.

Interior-Point Differentiable Path-Following Methods

Building on the equilibrium characterization, the authors develop two interior-point path-following methods. The unifying principle is the incorporation of logarithmic-barrier regularization into each player's payoff objective, parameterized by a homotopy parameter $t \in (0,1]$. When $t=1$, the system admits a unique analytic solution interior to the feasible polytope (fully mixed realization plans). As $t \to 0$, the path-following system converges to points satisfying the original (non-regularized) best-response conditions, i.e., a NE. The key results include:

• Existence proofs for a unique regularized solution at $t=1$.
• Topological arguments (employing Browder’s fixed-point theorem) and transversality results guaranteeing the existence of a connected, smooth solution path from $t=1$ to $t=0$.
• Equivalence transformations that reduce the number of variables, thus improving computational practicality.

The paper distinguishes between two barrier constructions: one using direct logarithmic penalties and another employing a relative entropy-like contrastive regularization between child and parent sequences.

Numerical Experiments

Empirical validation is conducted on classic EFG test cases (including canonical games from Myerson and Mas-Colell et al.) and large-scale randomly generated games exhibiting various branching and information structures. Predictor-corrector path-tracing is used to numerically follow the regularized homotopy. Convergence to Nash equilibria is robustly observed in all instances.

The key performance measures include iteration counts, computational time, and algorithmic failure rates across a range of problem sizes and structures. The proposed methods show high reliability (often 100% success), low median iteration counts, and strong scaling with respect to both game tree depth and branching factor, and significantly outperform several benchmark smoothing and path-following schemes.

Figure 2: An extensive-form game from Myerson (2604.12558) that serves as one of the testbeds for demonstrating the effectiveness of the sequence-form path-following methods.

Figure 1: Example of a randomly generated extensive-form game (Type 1), illustrating the complex information set merging for empirical performance evaluation.

Implications and Future Directions

This work bridges equilibrium representation and computation for extensive-form games under the sequence form, removing ambiguities and redundancies that arise in normal-form analysis. The theoretical contribution—the equivalence of sequence-form and mixed-strategy Nash equilibrium with an explicit polynomial characterization—enables new classes of algorithmic strategies for large-scale multi-agent and economic applications, including robust and refinement-sensitive equilibrium computation.

The differentiable path-following paradigm is highly promising for integration into modern differentiable optimization frameworks and may be particularly relevant to end-to-end learning in multi-agent reinforcement learning, mechanism design, and large-scale robust game-theoretic model fitting. Extensions to refined equilibrium concepts (e.g., perfect or quasi-perfect equilibrium), improved large-scale implementations, and further investigations into the theoretical properties of solution paths in non-perfect recall games constitute immediate directions for future work.

Conclusion

The paper provides a rigorous sequence-form-based equilibrium characterization for extensive-form games and introduces a robust, scalable, and fully differentiable path-following computational framework. The convergence guarantees, strong empirical performance, and descriptive power of the approach constitute a significant advance in the algorithmic analysis of strategic multi-agent environments. The theoretical and computational foundation established here substantially broadens the applicability of sequence-form representations beyond compactness to a tool for equilibrium computation and systematic equilibrium refinement analysis.

(2604.12558)