Two Sequence-Form Interior-Point Differentiable Path-Following Method to Compute Nash Equilibria
Provides a new computational method for Nash equilibrium in extensive-form games, offering improved numerical stability and convergence, though incremental over existing sequence-form approaches.
The paper develops a direct sequence-form definition of Nash equilibrium for finite n-player extensive-form games with perfect recall, and proposes a single-stage interior-point differentiable path-following method that uses logarithmic-barrier regularization. Numerical results demonstrate effectiveness and computational efficiency.
Nash equilibrium is a fundamental solution concept in extensive-form games, while its efficient computation is still far from straightforward. This paper considers finite $n$-player extensive-form games with perfect recall under the sequence-form representation. Unlike existing approaches, which mainly treat the sequence form as a compact computational reformulation, we develop a direct sequence-form definition of Nash equilibrium. Building on this, we rigorously establish the associated sequence-form Nash equilibrium system through an equivalence proof with mixed-strategy Nash equilibrium. On this basis, we propose a single-stage interior-point differentiable path-following method for equilibrium computation. The method uses logarithmic-barrier regularization to generate a differentiable equilibrium path in the interior of the realization-plan space, leading to favorable numerical stability and convergence properties. Numerical results show that the proposed method is effective and computationally efficient.