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

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.