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

Yuqing Hou (), Yiyin Cao (), Chuangyin Dang () and Yong Wang ()
Additional contact information
Yuqing Hou: University of Science and Technology of China
Yiyin Cao: Xi’an Jiaotong University
Chuangyin Dang: City University of Hong Kong
Yong Wang: University of Science and Technology of China

Computational Optimization and Applications, 2025, vol. 92, issue 1, No 8, 265-300

Abstract: Abstract 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.

Keywords: Extensive-form game; Sequence form; Nash equilibrium; Differentiable path-following method (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-025-00702-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:92:y:2025:i:1:d:10.1007_s10589-025-00702-y

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-025-00702-y

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().