Analysis and Computation of the Outcomes of Pure Nash Equilibria in Two-Player Extensive-Form Games

Paolo Zappalà (), Amal Benhamiche (), Matthieu Chardy (), Francesco De Pellegrini () and Rosa Figueiredo ()
Additional contact information
Paolo Zappalà: Orange
Amal Benhamiche: Orange
Matthieu Chardy: Orange
Francesco De Pellegrini: Avignon Université, Campus Jean Henri Fabre
Rosa Figueiredo: Avignon Université, Campus Jean Henri Fabre

Dynamic Games and Applications, 2025, vol. 15, issue 3, No 7, 872-905

Abstract: Abstract The outcomes of extensive-form games are the realisation of an exponential number of distinct strategies, which may or may not be Nash equilibria. The aim of this work is to determine whether an outcome of an extensive-form game can be the realisation of a Nash equilibrium, without recurring to the cumbersome notion of normal-form strategy. We focus on the minimal example of pure Nash equilibria in two-player extensive-form games with perfect information. We introduce a new representation of an extensive-form game as a graph of its outcomes and we provide a new lightweight algorithm to enumerate the realisations of Nash equilibria. It is the first of its kind not to use normal-form brute force. The algorithm can be easily modified to provide intermediate results, such as lower and upper bounds to the value of the utility of Nash equilibria. We compare this modified algorithm to the only existing method providing an upper bound to the utility of any outcome of a Nash equilibrium. The experiments show that our algorithm is faster by some orders of magnitude. We finally test the method to enumerate the Nash equilibria on a new instances library, that we introduce as benchmark for representing all structures and properties of two-player extensive-form games.

Keywords: Extensive-form games; Nash equilibria; Graph algorithm; Complexity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-024-00587-2 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:dyngam:v:15:y:2025:i:3:d:10.1007_s13235-024-00587-2

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

DOI: 10.1007/s13235-024-00587-2

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

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