Paolo Zappalà
email: paolo.zappala@orange.com

Amal Benhamiche
email: amal.benhamiche@orange.com

Matthieu Chardy
email: matthieu.chardy@orange.com

Francesco De Pellegrini
email: francesco.de-pellegrini@univ-avignon.fr

Rosa Figueiredo
email: rosa.figueiredo@univ-avignon.fr

Graph-based approach for enumerating the Nash equilibria of a two-player extensive-form game

Keywords: extensive-form games, nash equilibria, graph algorithm

Enumerating the Nash equilibria of a game is a known problem of game theory. We take into account twoplayer extensive-form games with perfect information and perfect recall. Based on the notion of compatibility of strategies, a new graph representation permits to devise a new lightweight algorithm to enumerate all of its Nash equilibria. It is the first of its kind not to use brute force. The method provides also intermediate results, like upper (lower) bounds to the value of the utility of Nash equilibria or the enumeration of Nash equilibria that fulfill any given constraints (possibly, unconstrained) on their values. We compare our method to the only existing formulation providing an upper bound to the value of the utility of any Nash equilibrium.

The experiments show that our method is faster by some orders of magnitude. We also test the method to enumerate the Nash equilibria on a new library, that we introduce as benchmark for representing all structures and properties of extensive-form games.

Introduction

In this paper, we consider games in extensive form and provide explicit solution methods for the enumeration of the pure Nash equilibria in the 2-player game case. In a generic game each player has available a set of strategies. In a 2-player game, every couple of strategies, one for each player, defines an outcome of the game, which is evaluated by means of a utility function. Every outcome is assigned a pair of numerical values, which represent the values given to the outcome by each Uploaded to HAL; manuscript no. 1 player. A Nash equilibrium is a couple of strategies in which none of the players has an incentive to change unilaterally her own strategy, i.e., the chosen strategy unilaterally maximises the value of the outcome at the equilibrium, assuming that the strategy of the other player does not change.

Identifying a Nash equilibrium for a generic game belongs to the class of PPAD-complete problems (cf. [START_REF] Daskalakis | The complexity of computing a nash equilibrium[END_REF]), introduced by [START_REF] Papadimitriou | On inefficient proofs of existence and complexity classes[END_REF]. The most known algorithm to identify a Nash equilibrium is the Lemke-Howson algorithm (cf. [START_REF] Lemke | Equilibrium points of bimatrix games[END_REF]), that consists in identifying a completely labeled pair of vertices of two polytopes representing the game.

Enumerating the Nash equilibria of a game corresponds to enumerating all the completely labeled pair of vertices of the two polytopes. Methods to solve such problem are inefficient and require a large amount of memory (cf. [START_REF] Avis | A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra[END_REF]). Recent algorithms have proven to be space efficient (cf. [START_REF] Avis | Enumeration of nash equilibria for two-player games[END_REF]), while others resort to parallel computing to overcome such issue (cf. [START_REF] Widger | Parallel computation of nash equilibria in n-player games[END_REF]).

Extensive-form games. Extensive-form games with perfect information and perfect recall are a category of games that represent players acting in sequence one after another (cf. [START_REF] Kuhn | Contributions to the Theory of Games[END_REF]). We consider extensive-form games with two players. One of the two players acts first: she has available a set of actions, among which she picks one. The second player observes the action chosen by the first player and has thus available a different set of actions, among which she also picks one. In a recursive way every player in turn observes the sequence of actions taken, has available a new set of actions and picks one. The game ends when the set of actions available to both players is empty. A sequence of actions that ends a game is an outcome of the game. The number of outcomes is called the size of the game. In an extensive-form game a pure strategy of a player is a function that gives an action to her to play for every sequence of actions she could observe in the past. In a generic extensive-form game the number of pure strategies available to a player is typically exponential in the size of the game (cf. Von Stengel (1996)). Using a classic method to enumerate Nash equilibria is therefore highly inefficient, because it relies on the enumeration of the strategies of the players. The structure of extensive-form games can be exploited to introduce more efficient algorithms. A Mixed Integer Linear model introduced by [START_REF] Koller | Efficient computation of equilibria for extensive two-person games[END_REF] provides one Nash equilibrium and is linear in the size of the game. However, no information is provided on possible other Nash equilibria. This method proves to be highly efficient in zero-sum games (cf.

Von Stengel (1996)), but it might have exponential time complexity in a generic game. A variant of this method (cf. [START_REF] Audet | A new sequence form approach for the enumeration and refinement of all extreme nash equilibria for extensive form games[END_REF]) allows to find the extreme Nash equilibria, which are identified by all the vertices of the polytope corresponding to a Mixed Integer Linear model.

Further methods. Much of the literature deals with solution concepts which are a refinement of Nash equilibria. The most known of such solutions is the subgame-perfect equilibrium, which guarantees an equilibrium in every subgame, i.e., in every game created starting from a node. The subgame-perfect equilibria are identified by an algorithm known as backward induction (cf. [START_REF] Selten | Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit: Teil i: Bestimmung des dynamischen preisgleichgewichts[END_REF]), which explores every possible sequence of the game and deduces recursively the optimal choice. Backward induction is difficult to parallelize (cf. [START_REF] Szymanik | Backward induction is ptime-complete[END_REF]), which makes it not efficient for large games. Moreover, backward induction cannot exploit regularities in the structure of the game nor provides intermediate results if interrupted. Different methods have been developed to provide bounds to the subgame-perfect equilibrium in large games; for instance, regret methods (cf. [START_REF] Johanson | Finding optimal abstract strategies in extensive-form games[END_REF]), gradient based algorithms (cf. [START_REF] Hoda | Smoothing techniques for computing nash equilibria of sequential games[END_REF]) or Monte-Carlo sampling (cf. [START_REF] Dudík | A sampling-based approach to computing equilibria in succinct extensive-form games[END_REF]).

Contributions. We provide a method that enumerates the Nash equilibria of a 2-player extensiveform game. Our method can be used to identify if an outcome is the realisation of a Nash equilibria.

Since the utility of every outcome is known, it is possible to determine upper (resp., lower) bounds to the utility of Nash equilibria for any player by checking them in order from the best to the worst (resp., from worst to best), rather the enumerating them all. Moreover, it is possible to enumerate the Nash equilibria whose realisations fit any given constraints on the utility by simply checking during our enumerating procedure those outcomes that meet such constraints. The method decreases its complexity when the games have specific structures. Indeed, it performs very well in games where outcomes can be compared without explicitly constructing the sequences of actions Uploaded to HAL; manuscript no. 1 that lead to them, which is the case of games with a regular structure; some examples of such games are provided later in the manuscript.

Summary. The paper is structured as follows. Section 2.1 presents extensive-form games with a generic number of players. We introduce a simplified notation to analyse extensive-form games with perfect recall and perfect information. In Section 2.2 we describe a known method to bound the utility of the Nash equilibria of a two-player game. Section 3 introduces a new graph formulation of extensive-form games that allows a new characterisation of Nash equilibria in two-player games.

An equivalent formulation is discussed in Section 3.3 and used in Section 4 to develop methods to identify a Nash equilibrium, to enumerate all Nash equilibria, to find an upper bound to their utility which is compared to the methods in literature (cf. Von Stengel (1996)) and to identify the best and the worst Nash equilibrium for a player. Section 5 presents extensive computational experiments of such methods on a given dataset of games. Section 6 ends the paper with some insights and possible research directions.

Extensive-form games

Notation. In this text we will use the following notation for vectors. A vector a = (a 1 , . . . , a n ) is an ordered sequence of elements a k with k ∈ {1, . . . , n}. Given two vectors a = (a 1 , . . . , a n ) and b = (b 1 , . . . b n ), a concatenation of vectors a + b = (a 1 , . . . , a n , b 1 , . . . , b n ) is represented by the operator +. Given a concatenation of vectors a + b, we say that a is a prefix of a + b, and that a ≤ a + b.

A vector with no elements is called the empty vector ∅ and ∅ ≤ a for all a. Two vectors a and a ′ might have a same common prefix. We denote by c = a ∩ a ′ the longest common prefix of a and a ′ , i.e., the longest sequence such that c ≤ a and c ≤ a ′ .

Definitions

We take into account situations in which a set of agents I = {1, . . . , N }, hereafter called players, act one after another, after observing the other players' actions at each moment. Such situations are represented in the literature by extensive-form games with perfect recall and perfect information (cf. [START_REF] Kuhn | Contributions to the Theory of Games[END_REF], [START_REF] Fudenberg | Game theory[END_REF]). These games can be represented with fewer pieces of information in comparison with a generic extensive-form game. However, no specific definition has been given to this class of games in the literature. In this section, we provide definitions that are written specifically for this class of games and that fall along the lines of the literature (cf. [START_REF] Kreps | Sequential equilibria[END_REF], [START_REF] Fudenberg | Subgame-perfect equilibria of finite-and infinite-horizon games[END_REF], [START_REF] Koller | The complexity of two-person zero-sum games in extensive form[END_REF]).

In the following we report the definitions for a generic number N players, even if in the analysis and in the examples we let N = 2, as the present work treats the 2-player case. At time 0, the first player to act observes no actions h 0 = ∅ and thus can act within a set of M actions A(h 0 ) = {a 0 1 , . . . , a 0 M }. Let us say that for instance she picks a 0 = a 0 m ∈ A(h 0 ); the second player observes h 1 = (a 0 ) and can thus pick an action a 1 ∈ A(h 1 ). For every moment k the player acting at k observes a history of actions h k and picks an action a k ∈ A(h k ). This procedure defines a set of histories

H ′ = {∅, h 0 , h 1 , . . . , h k , . . . }. There is a function A : h ′ ∈ H ′ → A that maps every history h ′
to the set of actions A available to the player observing the history h ′ . As stated before, the game ends when there is no actions left. Formally, there is a subset H ⊂ H ′ such that A(h) = ∅ for all h ∈ H. Such histories are called outcomes. Every outcome h ∈ H is evaluated by a function u i that maps it to the value u i (h) ∈ R assigned by player i to h.

Definition 1 (extensive-form game). An extensive-form game is a tuple Γ = ⟨I, A, H ′ , H, P, u⟩, where:

• I = {1, . . . , N } is the set of players; • H ′ is the set of histories with ∅ ∈ H ′ ; • A : h ′ ∈ H ′ →
A is a function that provides for every history a set of actions, i.e., for all

a ∈ A = A(h ′ ), we have h ′ + (a) ∈ H ′ ; • H = {h ∈ H ′ |A(h) = ∅} ⊂ H ′
is the set of outcomes;

• P : H ′ \ H → I is a function that indicates which player P (h ′ ) ∈ I acts after observing the history h ′ ∈ H ′ \ H;

• u = (u i ) i∈I , with u i : H → R, is the utility function.
Uploaded to HAL; manuscript no. 1

Remark. In the following sections games will also be represented by the tuple Γ = ⟨I, H ′ , u⟩ or Γ = ⟨I, H, u⟩, whenever all the missing parameters can be retrieved by the ones in the reduced notation.

Remark. In the literature the representation of the game is the game-tree of possible histories.

We thus alternatively call node a history observed by a player.

Example

h 3 = (a 1 , b 2 , a 3 , b 3 ), h 4 = (a 1 , b 2 , a 3 , b 4 ), h 5 = (a 1 , b 2 , a 4 , b 5 ), h 6 = (a 1 , b 2 , a 4 , b 6 ).
The set of outcomes is therefore

H = {h 1 , h 2 , h 3 , h 4 , h 5 , h 6 }. The set of histories is instead H ′ = {∅, h 1 , (a 1 ), h 2 , (a 1 , b 2 ), (a 1 , b 2 , a 3 ), (a 1 , b 2 , a 4 ), h 3 , h 4 , h 5 , h 6 }.
The function P maps respectively H ′ \ H = {∅, (a 1 ), (a 1 , b 2 ), (a 1 , b 2 , a 3 ), (a 1 , b 2 , a 4 )} to the players acting at such nodes {1, 2, 1, 2, 2}. The utility function u : H → R 2 evaluates the outcomes. For instance, we can have u(h 1 ) = (2, 0), where u 1 (h 1 ) = 2 is the evaluation given to h 1 by the first player and u 2 (h 1 ) = 0 is the one given by the second player. For the game in Figure 1 we assume that u(h 2 ) = (3, 4), u(h 3 ) = (8, 11), u(h 4 ) = (1, 9), u(h 5 ) = (5, 1), u(h 6 ) = (9, 3). The value of the utility allows to understand which outcomes are preferred by the players. For instance, the second player prefers

h 3 to h 6 because u 2 (h 3 ) = 11 > 3 = u 2 (h 6 ). We write alternatively h ≻ i h ′ to show that u i (h) > u i (h ′ ).
In the caption of Figure 1 all the preferences among the outcomes are given, based on the values assigned by the utility function.

We would like to understand which action a rational player picks after observing a history of previous actions. We therefore introduce the concept of pure strategy, which embeds the single choice made by a player for any observed history.

Definition 2 (pure strategy). Given a game Γ = ⟨I, A, H ′ , H, P, u⟩ and a player i ∈ I, we pick all the histories at which the player acts:

H i = {h ′ ∈ H ′ \ H|P (h ′ ) = i}. A pure strategy s i is a function s i : h ′ ∈ H i → a ∈ A(h ′
) that maps every observed history h ′ ∈ H i to one of the actions a ∈ A(h) available to the player. Let S i denote the set of all strategies of player i.

Example. In the game of Figure 1 the first player acts at two different moments in which she observes respectively ∅ and (a 1 , b 2 ): we have thus

H 1 = {∅, (a 1 , b 2 )}.
According to Definition 2, a pure strategy for player 1 is a function that maps every history observed in H 1 to an action that can be chosen by her. In Figure 1 the choices of the players are marked by thicker arrows. In the example, the first player picks strategy s 1 , where s 1 (∅) = a 1 and s 1 (a

H 2 = {(a 1 ), (a 1 , b 2 , a 3 ), (a 1 , b 2 , a 4 )}.
In Figure 1 the second player picks strategy s 2 , where:

s 2 (a 1 ) = b 1 ; s 2 (a 1 , b 2 , a 3 ) = b 3 ; s 2 (a 1 , b 2 , a 4 ) = b 6 .
If every player picks a strategy, we have a tuple of strategies s = ⟨s 1 , s 2 , . . . , s N ⟩, that we call strategy profile. If we consider a strategy profile, for every history there will be an action to be played. Eventually, this sequence of actions makes an outcome. Such outcome is defined as the realisation of the strategy profile and described in Algorithm 1. In Figure 1 the realisation of the aforementioned strategy profile (s 1 , s 2 ) is the outcome h 2 ∈ H.

Algorithm 1 Realisation of a strategy profile INPUT: A game Γ = ⟨I, A, H ′ , P, u⟩ and a strategy profile s = ⟨s 1 , s 2 , . . . , s N ⟩.

h ′ ← ∅ while A(h ′ ) ̸ = ∅ do h ′ ← h ′ + (s P (h ′ ) (h ′ ))
OUTPUT: h ← h ′ , the realisation of strategy profile s (also noted s → h).

In the following sections we write s → h to identify the unique realisation h of the strategy profile s. Moreover, with some abuse of notation, we write u(s), i.e., the utility of a strategy profile s, to indicate u(s) = u(h : s → h).

Uploaded to HAL; manuscript no. 1

We now introduce the concept of mixed strategy as vector of probabilities over the set of the pure strategies.

Definition 3 (mixed strategy). Given a game Γ = ⟨I, H, u⟩, a player i ∈ I and her associated set of pure strategies S i , we define a mixed strategy σ i as a probability distribution over the set of pure strategies, i.e., σ i : S i → [0, 1] such that s i ∈S i σ i (s i ) = 1. We denote with Σ i the set of mixed strategies of player i and with Σ = × i∈I Σ i the set of mixed strategy profiles.

By extension, the utility u : Σ → R N of a mixed strategy profile σ = ⟨σ 1 , σ 2 , . . . , σ N ⟩ is defined as the expected utility of its realisations:

u(σ) = s 1 ∈S 1 • • • s N ∈S N σ 1 (s 1 ) • . . . • σ N (s N ) • u(s 1 , . . . , s N ).
We would like the players to pick strategies that they do not want to change. This corresponds in literature to the concept of equilibrium. The Nash Equilibrium is a combination of strategies for which the players find it convenient not to deviate unilaterally. More specifically, if the other players do not change their strategies σ -i = (σ j ) j∈I\{i} , the player i has no interest in changing her own strategy σ i because she would not improve her utility. This concept of Nash equilibrium is hereafter defined.

Definition 4 (Nash equilibrium). Given a game Γ = ⟨I, H, u⟩, we say that a mixed strategy profile ⟨σ i ⟩ i∈I is a Nash equilibrium if for every i ∈ I and for all σ i ∈ Σ i :

u i (σ i , σ -i ) ≥ u i (σ i , σ -i ).
Mixed strategies are necessary to prove the existence of the Nash equilibrium (cf. Nash Jr (1950)), however we will not use such notation because it is cumbersome and it is not necessary for the developments in this work. Indeed, we will only consider Nash equilibrium in pure strategies, i.e., those in which mixed strategies have probability equal to 1 for a single pure strategy. It is proven that in an extensive-form game with perfect recall and perfect information all Nash equilibria are affine combination of all the Nash equilibria in pure strategies (cf. Theorem 1 of [START_REF] Audet | A new sequence form approach for the enumeration and refinement of all extreme nash equilibria for extensive form games[END_REF]). Therefore we will focus on introducing methods to identify all the Nash equilibria in pure strategies.

In the following sections, in order to identify a strategy profile s ∈ S = × i∈I S i , we will alternatively use the notation of its corresponding pure strategy σ ∈ Σ : σ i (s i ) = 1, ∀i ∈ I when the argument is made for general mixed strategies. For instance, let us consider the previous example of Figure 1 in which strategy s 2 ∈ S 2 is so that s 2 (a 1 ) = b 1 ; from now on we will alternatively write

σ 2 ∈ Σ 2 is so that σ 2 (a 1 ) = b 1 .

Bounds for Nash equilibria in two-player games

Enumerating the Nash equilibria requires to list the strategies of all the players, which are often exponentially in the number of outcomes (cf. Von Stengel (1996)). The most efficient methods to provide a bound to the utility of Nash equilibria have been introduced for two-player extensiveform games. We suppose that the games are not zero-sum, since such subcategory of games has already been fully studied (cf. Von Stengel (1996)).

Given a two-player extensive-form game Γ = ⟨I = {1, 2}, A, H ′ , P, u⟩, we consider the following optimization problem [ST]:

[ST ] :

σ 1 ∈ arg max σ 1 ∈Σ 1 u 1 (σ 1 , σ 2 ) s.t. σ 2 ∈ arg max σ 2 ∈Σ 2 u 2 (σ 1 , σ 2 ).
This bilevel optimization problem has linear complexity in the number of the strategies of the game, which might still be exponential in its size. Indeed, let us for instance consider a complete binary tree, i.e., a game in which every node has two actions. Given |H ′ \ H| the number of non-leaf nodes of the game tree, it is easy to show that there are 2 An optimal solution of [ST] provides an upper bound to the utility of the first player of all the Nash equilibria of the game (cf. [START_REF] Zappalà | A timing game approach for the roll-out of new mobile technologies[END_REF]).

Theorem 1. Let us consider Σ the set of feasible solutions σ = (σ 1 , σ 2 ) ∈ Σ 1 × Σ 2 of [ST] and the optimum value U 1 = sup σ∈Σ u 1 (σ). Given a Nash equilibrium σ * ∈ Σ 1 × Σ 2 of the game Γ, it holds:

U 1 ≥ u 1 (σ * ).
Proof. It is enough to prove that any Nash equilibrium is a feasible solution of [ST]. Indeed, since σ * is a Nash Equilibrium, we have that for all σ 2 ∈ Σ 2 :

u 2 (σ * 1 , σ * 2 ) ≥ u 2 (σ * 1 , σ 2 ). Therefore it holds that σ * 2 = arg max σ 2 ∈Σ 2 u 2 (σ * 1 , σ 2 ).
Example. We can verify for the game of Figure 1 that the set of the outcomes of Nash equilibria is {h 2 , h 3 }. If we compute the solution of [ST ] for such game, we get (σ 1 , σ 2 ) ∈ Σ 1 × Σ 2 , where

σ 1 (∅) = a 1 , σ 1 (a 1 , b 2 ) = a 3 , σ 2 (a 1 ) = b 2 and σ 2 (a 1 , b 2 , a 3 ) = b 3 .
The realisation of the strategy profile (σ 1 , σ 2 ) is h 3 . Coherently with Theorem 1, the solution u 1 (h 3 ) is, indeed, an upper bound for the utility of every outcome in the set of Nash equilibria {h 2 , h 3 }.

Graph form

A representation of extensive-form games as graphs of outcomes

In this section, we introduce a new representation of a game in extensive form with perfect information and perfect recall as an undirected graph.

As anticipated in Section 2, we take into account only pure strategies, to which we refer to as strategies from now on. If a player chooses a strategy, she limits the number of outcomes that are reachable by the other player. We formalise this observation by associating a strategy to a subset of outcomes that represent it. We recall that every strategy profile (s 1 , s 2 ) ∈ S 1 × S 2 can be mapped to its realisation h : (s 1 , s 2 ) → h. Given a strategy s 1 ∈ S 1 , we consider the set of possible outcomes H(s 1 ) which are a realisation of a strategy profile (s 1 , s 2 ) which includes s 1 ∈ S 1 as a strategy of the first player and any s 2 ∈ S 2 as a strategy of the second player.

Definition 5 (outcomes of a strategy). Given a two-player game Γ = ⟨I = {1, 2}, H, u⟩ and a strategy s 1 ∈ S 1 , the set of outcomes H(s 1 ) ⊂ H of strategy s 1 is:

H(s 1 ) = {h ∈ H|∃s 2 ∈ S 2 : (s 1 , s 2 ) → h}.
In order to understand which elements belong to the set of outcomes of a strategy, we introduce a new property, called compatibility. This property allows to to identify two outcomes that can be obtained by the same strategy chosen by a given player. Since we discuss only two-player games, i.e., I = {1, 2}, we arbitrarily choose one player to be the first player (e.g., i 1 = 1) and one to be the second player (e.g. i 2 = 2). Later in this section it is shown that such choice can be arbitrary.

Definition 6 (compatibility). Given a two-player game Γ = ⟨I = {1, 2}, H, u⟩, we say that two outcomes h, h ′ ∈ H are compatible for player i ∈ I if there is a strategy

s i ∈ S i such that h ∈ H(s i ) and h ′ ∈ H(s i ).
Remark. If not specified, we refer to two outcomes as compatible if they are compatible for player 1. If two outcomes h, h ′ ∈ H are compatible, there are a strategy s 1 ∈ S 1 and two strategies

s 2 , s ′ 2 ∈ S 2 such that (s 1 , s 2 ) → h and (s 1 , s ′ 2 ) → h ′ .
If two outcomes can be produced by the same strategy, the first player always takes the same decisions at every node. Lemma 1 proves that this condition is not only necessary but sufficient.

Formally, given two outcomes h, h ′ ∈ H it is necessary to observe at which node the history starts to be different; such node is identified by their longest common prefix h ∩ h ′ .

Lemma 1. We consider a two-player game

Γ = ⟨I = {1, 2}, H, P, u⟩. Two outcomes h, h ′ ∈ H are compatible if and only if P (h ∩ h ′ ) = 2.
Proof. (i) First we prove that P (h ∩ h ′ ) = 2 implies that h and h ′ are compatible, then (ii) we prove that P (h ∩ h ′ ) = 1 implies that h and h ′ are not compatible.

(i) Let us suppose that P (h ∩ h ′ ) = 2. We need to define

s 1 ∈ S 1 and s 2 , s ′ 2 ∈ S 2 such that (s 1 , s 2 ) → h and (s 1 , s ′ 2 ) → h ′ .
We recall that a strategy of the first player is a function associating an action to each partial history h k ∈ H ′ in the tree observed by the first player, i.e., such that P (h k ) = 1.

Uploaded to HAL; manuscript no. 1

For each

h k ≤ h (h k ≤ h ′ ) if P (h k ) = 1 we define a strategy s 1 ∈ S 1 such that h k + (s 1 (h k )) ≤ h (h k + (s 1 (h k )) ≤ h ′ ).
Analogously, we define a strategy s 2 ∈ S 2 , such that for each h k ≤ h with

P (h k ) = 2 we have h k + (s 2 (h k )) ≤ h, and a strategy s ′ 2 ∈ S 2 , such that for each h k ≤ h ′ with P (h k ) = 2 we have h k + (s ′ 2 (h k )) ≤ h ′ .
For any other h k ≰ h and h k ≰ h ′ we take an arbitrary decision for defining s 1 , s 2 , s ′ 2 . By construction, we have (s

1 , s 2 ) → h and (s 1 , s ′ 2 ) → h ′ . (ii) Let us now suppose that P (h ∩ h ′ ) = 1. Let (s 1 , s 2 ) and (s ′ 1 , s ′ 2 ) be two profile strategies such that (s 1 , s 2 ) → h and (s ′ 1 , s ′ 2 ) → h ′ . It is impossible to have s 1 = s ′ 1 since P (h ∩ h ′ ) = 1 implies s 1 (h ∩ h ′ ) ̸ = s ′ 1 (h ∩ h ′ )
, from which we can conclude that h and h ′ are not compatible.

Based on the definition of compatibility it is possible to build a graph of compatibilities among all the outcomes of a game Γ, or the graph form for short.

Definition 7 (graph form). The graph of compatibility of a two-player game Γ = ⟨I = {1, 2}, H, u⟩ is a tuple Γ = ⟨H, E, u⟩, where H is the set of outcomes as nodes of the graph, E ⊂ H 2 is the set of edges connecting any two compatible outcomes and u : H → R 2 is the utility function that assigns a pair of weights to every node.

Remark. In the following of the article sometimes we omit the transformation of an extensive-form game Γ into its graph form ⟨H, E, u⟩ and therefore we introduce the game by directly representing it in its graph form Γ = ⟨H, E, u⟩.

Example. We take into account the game of Figure 1 with its corresponding graph form in Figure 2a). Let us show, for instance, that outcomes h 2 and h 4 are compatible. Let us define:

s 1 ∈ S 1 such that s 1 (∅) = a 1 and s 1 (a 1 , b 2 ) = a 3 ; s 2 ∈ S 2 such that s 2 (a 1 ) = b 1 ; s ′ 2 ∈ S 2 such that s ′ 2 (a 1 ) = b 2 and s ′ 2 (a 1 , b 2 , a 3 ) = b 4 . We have that (s 1 , s 2 ) → h 2 and (s 1 , s ′ 2 ) → h 4 : they are therefore compatible.
On the other hand there is no strategy of the first player that can lead to both h 2 and h 1 , because different actions would occur at the beginning of the game, i.e., at node ∅. With similar arguments, it is possible to build all the graph form of the game.

Characterisation of Nash equilibria in the graph form of the game

Given a game Γ, let us characterise the outcomes H(s 1 ) of a strategy s 1 ∈ S 1 on its graph form. By definition, such outcomes should all be compatible among themselves. Let us consider the nodes on the graph corresponding to the outcomes H(s 1 ); they induce a clique and, as we show next, such clique is maximal.

Lemma 2. Consider a two-player game Γ = ⟨I = {1, 2}, H, u⟩ with its graph form Γ = ⟨H, E, u⟩.

For every strategy s 1 ∈ S 1 , the set H(s 1 ) ⊂ H forms a maximal clique of the graph ⟨H, E, u⟩.

Proof. According to Definition 6, we have that H(s 1 ) induces a clique on the graph. Consider

any outcome h ∈ H \ H(s 1 ). Since h / ∈ H(s 1 ) there is a partial history h k ∈ H ′ , with h k ≤ h and P (h k ) = 1, such that the subsequent action a k+1 ∈ A(h k ) is not chosen by strategy s 1 , i.e., a k+1 ̸ = s 1 (h k ). Consider now an outcome h ′ ∈ H(s 1 ) such that h k + (s 1 (h k )) ≤ h ′ . Since P (h ∩ h ′ ) = 1, from
Lemma 1 h and h ′ are not compatible. Since this is true for every h ∈ H \ H(s 1 ), we have that H(s 1 ) forms a maximal clique.

Example. We consider the game of Figure 1 and a strategy s 1 ∈ S 1 such that s 1 (∅) = a 1 and

s 1 (a 1 , b 2 ) = a 4
. By definition we have that H(s 1 ) = {h 2 , h 5 , h 6 }, which induces indeed a maximal clique in the graph of Figure 2a). Four different strategies are available in S 1 to the first player, since we have two different actions that can be played for every node ∅ and (a 1 , b 2 ). There are 3 maximal cliques in graph ⟨H, E⟩, i.e., those induced by the sets of outcomes {h 1 }, {h 2 , h 3 , h 4 } and {h 2 , h 5 , h 6 }, respectively. This small example shows that the graph form is a less redundant representation of the strategies of the players. In fact, two different strategies induce the set of outcomes {h 1 }.

However, we observe that to every maximal clique of the graph there is at least one strategy whose set of outcomes corresponds to it. We prove that it is always true in Lemma 3.

Lemma 3. Let us consider a two-player game Γ = ⟨I = {1, 2}, H, u⟩ with its graph form Γ =

⟨H, E, u⟩. For every set of vertices C that induces a maximal clique on the graph ⟨H, E⟩, there is a strategy s 1 ∈ S 1 such that C = H(s 1 ).

Uploaded to HAL; manuscript no. 1

Proof. We first show that C ⊂ H(s 1 ) for a given s 1 ∈ S 1 . For this, we consider a strategy s 1 ∈ S 1

such that for all h ∈ C and all h k ≤ h such that P (h k ) = 1 we have that h k + s 1 (h k ) ≤ h. Such strategy exists and it is defined by applying a procedure similar to the one used in the proof of Lemma 1; we recall that P (h ∩ h ′ ) = 2 for each pair of compatible h, h ′ ∈ C. Therefore C ⊆ H(s 1 ).

But, from Lemma 2, H(s 1 ) induces a maximal clique and thus C = H(s 1 ).

Lemmas 2 and 3 establish that there exists a bijection between a partition of the set of strategies of the game and the set of maximal cliques in the graph form. An illustration is given in Figure 2b).

A similar result is obtained for the set of strategies of the second player on the complementary graph.

Lemma 4. For every two-player game Γ = ⟨I = {1, 2}, H, P, u⟩ with its graph form Γ = ⟨H, E, u⟩, there is a bijection between a partition of the set of strategies of the second player S 2 and the set of maximal cliques of the complementary graph ⟨H, E C ⟩, where

E C = {(h, h ′ ) ∈ H 2 |h ̸ = h ′ , (h, h ′ ) / ∈ E}. Proof. Given two outcomes h, h ′ ∈ H, we have that P (h ∩ h ′ ) ∈ {1, 2}. Therefore P (h ∩ h ′ ) = 2 if
and only if P (h ∩ h ′ ) ̸ = 1. Lemma 1 thus determines that the graph form with respect to the second player is complementary to the first player's. The result follows from Lemmas 2 and 3.

Choosing a strategy for the first player is equivalent to picking a maximal clique in the graph ⟨H, E⟩. Furthermore, one can observe that with an analogous method it is possible to build a graph for the strategies of the second player. However, thanks to Lemma 4 it is not necessary to perform further computations, because such graph is complementary to ⟨H, E⟩.

As anticipated in Section 2, we are interested in identifying Nash equilibria in pure strategies.

We recall that a Nash equilibrium is a strategy profile in which none of the players is interested in changing her own strategy unilaterally.

Best responses and outcomes. The standard way to define a best response for an extensive-form game entails to refer to its equivalent strategic form. In this case, if a player picks a strategy, the other player will choose a best response, i.e., a strategy such that her utility is maximized. A Nash equilibrium can be identified as a mutual best response accordingly. We now provide a connection between this fundamental definition of equilibrium based on the strategic form and properties of the outcomes in the graph form of the game. In fact, every tagged outcome h corresponds to one or more strategies s 1 for the first player identified by a maximal clique C 1 on the graph form which includes h. In turn, for every element h ′ ∈ C We would like to know if a tagged outcome h is the realisation of a Nash equilibrium. Hence, a maximal clique including the corresponding vertex h and excluding

X h = {h ′ ∈ H|u 2 (h ′ ) > u 2 (h)}
ensures that the first player has a strategy to induce the second player onto the desired outcome h.

Uploaded to HAL; manuscript no. 1

Example. In the game of Figure 1 the second player prefers X h = {h 2 , h 3 , h 4 } to h = h 6 . In the graph of Figure 2a) we observe that there is no maximal clique including h 6 and excluding all the elements of X h . Therefore h 6 cannot correspond to a best response of the second player.

Furthermore, by applying the same arguments on the complementary graph we conclude that it is possible to determine whether an outcome is a best response also of the first player. Specifically, it is necessary to identify a maximal clique on the complementary graph such that the vertices corresponding to the outcomes preferred by the first player are excluded.

Example. In the graph of Figure 2a) the first player prefers

X h = {h 2 , h 3 , h 5 , h 6 } to h = h 1 .
There is no maximal clique on the complementary graph of Figure 2a), i.e., there is no independent set, that includes h 1 and none of the elements in X h . Therefore h 1 cannot be a best response of the first player.

Theorem 2 combines these findings and provides a characterisation of a Nash equilibrium in the graph form.

Theorem 2. Let us consider a two-player game in its graph form Γ = ⟨H, E, u⟩ and an outcome

h ∈ H. We consider X h 1 = {h ′ ∈ H|u 1 (h ′ ) > u 1 (h)} and X h 2 = {h ′ ∈ H|u 2 (h ′ ) > u 2 (h)},
as input ⟨H, E, h, X h 2 ⟩ and ⟨H, E C , h, X h 1 ⟩.
The proof is provided in Appendix A. Such result allows us to develop methods that compute Nash equilibria without listing all the strategies of the players, which are often in exponential number with respect to the size of the game (cf. Section 2). Such methods will be discussed in the following sections.

Analysis of the main problem and its complexity

The complexity of identifying a Nash equilibrium on a game in graph form depends on the com- Example. Indeed let us consider the problem [M C] depicted in Figure 3a) and its restriction to the neighborhood of h of Figure 3b). The problem [M C] requires to identify a maximal clique that has no elements in X h and includes h, such as {h, h 2 , h 3 , h 4 } or {h, h 1 , h 2 }. The problem [EC] Uploaded to HAL; manuscript no. 1

requires to identify a vertex set C ′ on V = {h 1 , h 2 , h 3 , h 4 } that induces a clique such that for all elements in X = {h 6 , h 7 , h 9 } there is at least one element in C ′ not connected to it. Such cliques are {h 1 }, {h 1 , h 2 }, {h 2 , h 3 }, {h 3 , h 4 } and {h 2 , h 3 , h 4 }. For instance, let us consider {h 2 , h 3 }: the vertex h 6 is not connected to h 3 , while the vertices h 7 and h 8 are not connected to h 2 .

Theorem 3. Let us consider a graph ⟨H, E⟩, a subset of vertices X h ⊂ H and a vertex h ∈ H \ X h . QUESTION: Is there a vertex set C ⊂ H that induces a clique on the graph such that for every (i, j) ∈ E. From (a) and the definition of sets V and E ′ , there is a copy of C ⊂ V defining a clique in graph ⟨V ∪ X, E ′ ⟩. Also, from the definition of E ′ and from (b), for each j ∈ X there is a i ∈ C

Let us define

V h = {h ′ |(h, h ′ ) ∈ E}, X = X h ∩ V h , V = V h \ X and E| V ∪X = {(h ′ , h ′′ ) ∈ E|h ′ ∈ V, h ′′ ∈ V ∩ X}. The problem [M C] with input ⟨H, E, h, X h ⟩
vertex h ′′ ∈ H \ C there is a vertex h ′ ∈ C such that (h ′ , h ′′ ) ∈ E?
E ′ = {(i, j)|i, j ∈ V, (i, j) ∈ E} ∪ {(i, j)|i ∈ V, j ∈ X, (i, j) / ∈ E}.
such that (i, j) / ∈ E ′ . Therefore C provides also an answer true for [EC].

We now prove that an answer true for [EC] provides an answer true also to [DC]. A vertex set C ⊂ V that induces a clique on ⟨V ∪ X, E ′ ⟩, clearly defines a clique on ⟨H, E⟩. It holds that for all j ∈ X there is i ∈ C such that (i, j) / ∈ E ′ . Since X = H and V = H, with H and H copies of H, we have that for all j ∈ H \ C there is a vertex i ∈ C such that (i, j) ∈ E. Therefore C provides also a solution true for [DC].

On the graph of an extensive-form game. We have just proved that problem [EC] is NP-complete for a generic graph. However, the graph generated by an extensive-form game is not a generic one.

Indeed, it is possible to identify a graph that corresponds to no extensive-form games. The graph ⟨H, E⟩ of Figure 5 does not represent any extensive-form game (cf. Appendix C).

New methods for the identification of Nash equilibria

In this section, the theoretical results introduced in Section 3 are applied to derive new methods for the computation of Nash equilibria in two-player extensive-form games with perfect information and perfect recall. Theorem 2 provides a necessary and sufficient condition for an outcome to be a realisation of a Nash equilibrium. This result is the pillar for the development of methods to the following questions: (i) whether it is possible to enumerate the Nash equilibria and (ii) whether the realisation of Nash equilibria can achieve a value of utility with a given range of values.

In what follows, we exploit the results of Section 3.3 and introduce a linear system that allows to determine if an outcome is the realisation of a Nash equilibrium. Starting from this linear system, we introduce a method to enumerate all Nash equilibria in Section 4.1, a method to provide an upper bound to their utility in Section 4.2 and a method to provide the best or worst Nash equilibrium for a player in Section 4.3. The latter is compared to the one provided by the optimization problem by Von Stengel (1996).

Uploaded to HAL; manuscript no. 1

Nash equilibrium

Theorem 2 provides a necessary and sufficient condition to verify if an outcome is the realisation of a Nash equilibrium. According to Theorem 2, such condition requires to solve two instances of problem [EC] with input ⟨V ∪ X, E⟩ such that V ∩ X = ∅. We recall that the solution obtained by the problem allows to identify some possible outcomes C ⊂ V of a strategy within the set V such that we have the guarantee that the elements X preferred by the opponent are not included. We provide a formulation [CL] of problem [EC]:

[CL] :

x i + x i ′ ≤ 1, ∀i, i ′ ∈ V, (i, i ′ ) / ∈ E, (CL-1) i∈V |(i,j) / ∈E x i ≥ 1, ∀j ∈ X, (CL-2) x i ∈ {0, 1}, ∀i ∈ V. (CL-3)
Formulation [CL] models any feasible solution of problem [EC]:

x i = 1 if and only if i ∈ C.
Constraints (CL -1) impose that C induces a clique, while constraints (CL -2) guarantee that every vertex j ∈ J is not connected to at least one vertex i ∈ C. Any solution to the linear system

[CL] provides a solution to problem [EC] with input ⟨V ∪ X, E⟩.

Theorem 2 imposes us to solve two instances of the problem [M C] to determine if an outcome is the realisation of a Nash equilibrium. We thus exploit the fact that the problem [M C] can be modeled by formulation [EC] and define a unique linear system [N E] that allows to determine if an outcome is the realisation of a Nash equilibrium. Let us consider a two-player game in its graph form Γ = ⟨H, E, u⟩ and an outcome h ∈ H. Let us define the following sets:

• X 1 = {h ′ ∈ H|(h ′ , h) / ∈ E, u 1 (h ′ ) > u 1 (h)}
, the set of outcomes compatible to h in the complementary graph preferred by the first player to h;

• X 2 = {h ′′ ∈ H|(h ′′ , h) ∈ E, u 2 (h ′′ ) > u 2 (h)}
, the set of outcomes compatible to h preferred by the second player to h;

• V 1 = {h ′ ∈ H \ X 2 |(h ′ , h) ∈ E},
the set of outcomes compatible to h where h is preferred;

• V 2 = {h ′′ ∈ H \ X 1 |(h ′′ , h) /
∈ E}, the set of outcomes compatible to h in the complementary graph where h is preferred.

The outcome h ∈ H is a realisation of a Nash equilibrium if and only if the system [N E] provides a solution:

[N E] :

x i + x i ′ ≤ 1, ∀i, i ′ ∈ V 1 , (i, i ′ ) / ∈ E, x i + x i ′ ≤ 1, ∀i, i ′ ∈ V 2 , (i, i ′ ) ∈ E, i∈V 1 ,(i,j) / ∈E x i ≥ 1, ∀j ∈ X 2 , i∈V 2 ,(i,j)∈E x i ≥ 1, ∀j ∈ X 1 , x i ∈ {0, 1}, ∀i ∈ V 1 ∪ V 2 .
Given a game Γ = ⟨H, E, u⟩ and an outcome h ∈ H, by applying [N E] to every h ∈ H it is possible to enumerate all the realisation of the Nash equilibria of the game. In the following, we propose an enumeration algorithm [EA] that iterates over all the outcomes and then solves [N E] for every outcome.

Algorithm 2 [EA] Enumeration Algorithm INPUT: Game in graph form Γ = ⟨H, E, u⟩

N E ← ∅

for h ∈ H do ▷ for every outcome of the game

X 1 = {h ′ ∈ H|(h ′ , h) / ∈ E, u 1 (h ′ ) > u 1 (h)}
▷ vertex sets and excluding sets

X 2 = {h ′′ ∈ H|(h ′′ , h) ∈ E, u 2 (h ′′ ) > u 2 (h)} ▷ for player 1 and player 2 V 1 = {h ′ ∈ H \ X 2 |(h ′ , h) ∈ E} V 2 = {h ′′ ∈ H \ X 1 |(h ′′ , h) / ∈ E} solve [N E] giving ⟨V 1 , V 2 , X

Upper bounds for Nash equilibria

In this section, we compare two methods to compute upper bounds for the utility of the first player when a Nash equilibrium is played. The most known formulation for extensive-form games is the one introduced by Von Stengel (1996), which provides a Nash equilibrium for zero-sum games.

Recently, this formulation has been proven to provide an upper bound to the utility of the first player of any Nash equilibrium (cf. [START_REF] Zappalà | A timing game approach for the roll-out of new mobile technologies[END_REF]). This method is based on the concept of sequence, which is a vector of actions played by a same player. Given a game Γ = ⟨I, A, H ′ , P, u⟩ and a history h ′ ∈ H ′ , we denote by seq i = (h ik ) a sequence of actions played by player i according to h ′ . We write h ′ = (seq 1 , seq 2 ) to show that to every history h ′ correspond two sequences seq 1 and seq 2 . We consider Λ 1 and Λ 2 , respectively, the set of all sequences of the first and second player.

Let x ∈ {0, 1} |Λ 1 | and y ∈ {0, 1} |Λ 2 | be the vectors defining the probability for a sequence to be played. We define the matrix U i : Λ 1 × Λ 2 → R that maps each couple of sequences to the utility of player i:

U i seq 1 ,seq 2 = u i (h) for all h = (seq 1 , seq 2 ) ∈ H; U i seq 1 ,seq 2 = 0 if h ′ = (seq 1 , seq 2 ) / ∈ H.
The utilities of the players can thus be written in the form x T U 1 y and x T U 2 y. The formulation defining the set of possible sequences is constrained by the fact that if an action is taken at a node of the game, such decision must be considered also in the following ones. For instance, let us consider the game of Figure 1. The sequences of the first player are Λ 1 = {∅, (a 1 ), (a 2 ), (a 1 , a 3 ), (a 1 , a 4 )},

y (b 2 ) = y (b 2 ,b 3 ) + y (b 2 ,b 4 ) + y (b 2 ,b 5 ) + y (b 2 ,b 6
) . All such causal constraints, written Ex = e and F y = f , respectively, for the first and the second player, will be built according to the same principle.

Finally, the upper bound of any Nash equilibrium is given by the solution of the following bilevel problem denoted by [V S].

[V S] :

u V S 1 = max x x T U 1 y s.t. Ex = e, x ∈ [0, 1] |Λ 1 | , y = arg max y x T U 2 y s.t. F y = f, y ∈ [0, 1] |Λ 2 | .
The optimization problem [V S] has size O(|H|) (cf. Von Stengel (1996)). We now formulate [V S] as a linear optimization problem. Note that, as anticipated in Section 2, we are only interested in solutions corresponding to pure strategies. Therefore we can add the integral constraints:

x j ∈ {0, 1} ∀j ∈ Λ 1 , (1)
y k ∈ {0, 1} ∀k ∈ Λ 2 . (2)
We will also introduce the variable w jk ∈ [0, 1], which allows to linearise the formulation by rewriting

x j • y k = w jk as:

x j ≥ w jk ∀j ∈ Λ 1 , k ∈ Λ 2 , (3)
y k ≥ w jk ∀j ∈ Λ 1 , k ∈ Λ 2 , (4)
x j + y k ≤ 1 + w jk ∀j ∈ Λ 1 , k ∈ Λ 2 , (5)
w jk ∈ [0, 1] ∀j ∈ Λ 1 , k ∈ Λ 2 . ( 6
)
In the second level of problem [V S] the optimal u := u 2 (y) ∈ R is achieved for some k ∈ Λ 2 , i.e., we can write

u = max k∈Λ 2 j∈Λ 1 U 2 jk • x j , u ∈ R. (7)
Since only one sequence k ∈ Λ 2 must be chosen, the constraint F y = f is replaced by

k∈Λ 2 y k = 1. ( 8
)
Uploaded to HAL; manuscript no. 1

The constraint Ex = e when written explicitly corresponds to:

j∈Λ 1 E lj • x j = 0 ∀l. ( 9
)
We now reformulate the second level of [V S], using a set of linear constraints. Let us denote by u ∈ R the maximum utility for the second player. Also, we set a large value M > 0 to use the following classical big-M constraints:

j∈Λ 1 U 2 jk • x j ≤ u, ∀k ∈ Λ 2 , ( 10
)
j∈Λ 1 U 2 jk • x j ≥ u -M (1 -y k ), ∀k ∈ Λ 2 . ( 11
)
The bilevel problem [V S] is then denoted by [V S -L], and written as follows:

[V S -L] : u V S 1 = max x,y,w j∈Λ 1 k∈Λ 2 U 1 jk • w jk s.t. (1 -11)
Note that adding a constant value to the utility function does not change the solution, therefore we can assume U 2 jk > 1 for all j ∈ Λ 1 and k ∈ Λ 2 . Under this assumption, we can add the following inequality:

y k ≤ j∈Λ 1 U 2 jk • x j ∀k ∈ Λ 2 , ( 12
) which is valid for [V S], since y k = 0 ⇐⇒ j∈Λ 1 U 2 jk • x j = 0 and y k = 1 ⇐⇒ ∃j ∈ Λ 1 such that x j = 1.
Let us denote by [V S -L2] the resulting formulation:

[V S -L2] : u V S 1 = max x,y,w j∈Λ 1 k∈Λ 2 U 1 jk • w jk s.t. (1 -12).
In what follows, we introduce a new algorithm, called [U BA] and described in Algorithm 3, that allows to compute an upper bound of the utility of the first player when a Nash equilibrium is Proof. We define the set of all the outcomes that can be a best response of the second player to a strategy of the first player,

BR 2 = {h ∈ H|∃s 1 ∈ S 1 , h = arg max h ′ ∈H(s 1 ) u 2 (h ′ )}. We show that u V S 1 = u U BA 1 = max h∈BR 2 u 1 (h)
. First, we observe that BR 2 corresponds to the set of feasible solutions of [V S] and thus u

V S 1 = max h∈BR 2 u 1 (h). Let us prove that u U BA 1 = max h∈BR 2 u 1 (h). Given h ∈ H, X = {h ′ ∈ H|(h ′ , h) ∈ E, u 1 (h ′ ) > u 1 (h)} and V = {h ′ ∈ H \ X|(h ′ , h) ∈ E},
: h ⪰ 1 h ′ iff u 1 (h) ≥ u 1 (h ′ ) index = 0
▷ Start with the smallest utility for player 1

do h = H(index) ▷ Select the outcome corresponding to index u U BA 1 = u 1 (h) V 1 = {h ′ ∈ H \ X 2 |(h ′ , h) ∈ E} ▷ vertex set for player 1 X 2 = {h ′′ ∈ H|(h ′′ , h) ∈ E, u 2 (h ′′ ) > u 2 (h)} ▷ excluding set for player 1 solve [CL] giving ⟨V 1 , X 2 , E⟩ as input index = index + 1 while [CL] has no solution OUTPUT: u U BA

Numerical results

In this section, we assess the performance of the methods introduced in Section 4 through several series of experiments. To our knowledge, there is no standard library of extensive-form games in the literature. For this reason, we developed a new library presented in Section 5.1. The methods that provide bounds to the utility of Nash equilibria and those who enumerate them are analysed separately, respectively in Section 5.2 and in Section 5.3. The experimental study was conducted on a Intel Xeon CPU 2.20 GHz with 13 GB RAM. The algorithm were implemented in Python 3.8.

The solver used to solve all Mixed-Integer Linear Programming problems is GLPK (cf. Makhorin ( 2008)).

Library of extensive-form games

Extensive-form games with perfect recall and perfect information have never been categorised. We thus introduce a new classification of games based on three key features: the structure of the gametree, the size of the game and the utility function. This allows to challenge our algorithms on a wide range of game instances and analyse their efficiency. The proposed classification will be used to create a new library of extensive-form games. More precisely, the structure of a game captures the properties of the shape of the game-tree. The size of the game (i.e., the number of outcomes) allows us to better assess the scalability of methods. Finally, once structure and size are fixed, the only parameter that varies in a game is the utility function, for which we provide different families of functions.

Each instance of the dataset thus formed is referred to with a specific name encoding the three key features of the game. Such encoding is shown in zero-sum and the winner has a utility chosen randomly from a discrete set U({1, . . . , 10}); F if the utility is chosen randomly from U([0, 1]) at every outcome and it is the same for every player; E if every utility of every outcome is a constant. The latest value of a label is the size of the game. An instance of game labeled C4E100 has 100 outcomes, every node has 4 actions (C) and utility is a constant function (E).

The library is publicly accessible (cf. Zappalà ( 2023)) and composed of three distinct datasets.

Dataset 1 contains 21 extensive-form games which vary in their structure, within the range {R, C, U }, and in their size {100, 216, 324, 400, 512, 625, 729}, but not in their utility, which is always Random R. Dataset 1 has games of smaller size, i.e., small enough to manage methods already known in the literature, that provide bounds to the utility of Nash equilibria; Dataset 1 is used in

Bounds to the utility of Nash equilibria

We first test the methods introduced in Section 4.2 and in Section 4.3 on Dataset 1. The reference methods known in literature, i.e., the branch and bound algorithms used to solve formulations [V S -L] and [V S -L2], are compared to algorithm [U BA]: they all provide the same upper bound to the utility of the first player in a Nash equilibrium. We recall that the proposed algorithms

[BN E] and [W N E] provide the tightest (respectively, upper and lower) bounds to the utility of every Nash equilibrium. Table 1 reports the computation time for every instance of each algorithm as well as the number of iterations of the three iterative algorithms perform 17% to more than 99% faster on structures C and U than those of type R; we ascribe this to the fact that the games present fewer nodes and thus require fewer constraints in the linear formulation. first checks the outcomes with lowest utility for the first player, those are unlikely to correspond to the best response of the first player. It takes thus far more time to identify an outcome which is a best response for both players.

[U BA], [BN E] and [W N E]. Comparison [U BA] vs [V S -L] vs [V S -L2].
Comparison [U BA] vs [BN E] vs [W N E]. Algorithm [BN E]

Enumeration of realisations of Nash equilibria

In the next experiment, we tested the methods introduced in Section 4.1 on Dataset 2 and on Dataset 3. We have measured the performance of Algorithm [EA] while enumerating the Nash equilibria of every instance.

Uploaded to HAL; manuscript no. 1

Analysis on Dataset 2. For the space's sake, in Table 2 we display only the results for all the games' instances with size 729. More precisely, for each game, we show how many outcomes are the realisations of Nash equilibria N E, the average size X avg of all sets X 1 and X 2 , the total time required to run the algorithm t tot , the average time t avg and the maximal time t max for an outcome of the game. In addition, Figure 9 displays the average time and the maximal time required to execute the algorithm on a game outcome, and the percentage of Nash equilibria identified among all the game's outcomes.

Impact of the size on performance. As expected, the computation time increases with the size of the game (cf. Figure 9). Algorithm [EA] iterates over the outcomes and requires to solve system

[N E] at each instance. When the size of the game increases, on average the size of system [N E] increases accordingly. However, if the size is fixed, the structure and the utility function have a fundamental impact onto the computation time.

Impact of the utility function on performance. In the degenerate case E, when outcomes all have same utility value, solving system [N E] gets trivial for each outcome and thus the computation time of each iteration is negligible (cf. Table 2). Indeed, the sets of outcomes to be excluded X 1 and X 2 are empty at every iteration. For such case building the graph is not even necessary. We observe that the computation time is lower for the case Z, as the size of X 1 and X 2 is smaller.

We cannot infer significant correlations on the other cases (R, D, A, F ) and we thus defer such analysis to Dataset 3.

Impact of structure on performance. The structure of the game influences the efficiency of the average time necessary to verify if an outcome is the realisation of a Nash equilibrium. Indeed, we observe in Figure 9 that in games with the same size those whose nodes have the same number of children (structure coding C) require more time on average to compute an equilibrium. This is due to the fact that the neighborhoods of an outcome V 1 ∪ X 2 and V 2 ∪ X 1 in the graph and its complementary have always the same size in both parts of system [N E]. On the other hand, in games with more asymmetrical structure (structure coding R and U ) one of the two graphs is often smaller and thus much easier to be solved.

Analysis of Dataset 3. Table 3 shows the average of performances on 5 sample games for each one of the 15 patterns. Every curve of Figure 10 shows the computation time distribution of [N E]

for an outcome of a game. The 15 curves provide such result for the 15 games having the same utility coding. Namely, every line appearing in the plots shows for every game type Γ = ⟨I, H, u⟩ the function f (t) = P(t(h) ≤ t|h ∈ H), i.e., the probability that the algorithm solving system [N E]

takes less than t seconds to determine if h is the realisation of a Nash Equilibrium.

Impact of the structure on performance. These numerical results show empirically that the structure is the main factor influencing the performance of the algorithm solving system [N E]. Indeed, on a game with totally unbalanced (U ) structure it takes a negligible time for the vast majority (around 99%) of the outcomes of a game instance (cf. Figure 10). On the other hand, on a game with complete (C) structure the algorithm such percentage decreases to 20 -50%. The algorithm performs in between the two extremes for a game with random (R) structure.

Impact of the utility on performance. We observe on Table 3 that the best performances are obtained for zero-sum games (coding utility Z) for the same structure. This is due to the fact that when the utility is equal to 1 the set of outcomes to be excluded X is empty (cf. Table 2). One of the two sides of the problem is always trivial. If the game switches from utility Z to A, i.e., if the player that wins gains a value between 1 and 10 instead of just 1, the property that makes one of the problems trivial is lost. Indeed, games with coding A have performances comparable to those with other utility codings (R, D, F ). One might thus assume that increasing the granularity of the utility might make the algorithm less efficient. However, we do not observe any significant difference in the computation time while comparing (D) (u i ∼ U({1, . . . , 10})) to (R) (u i ∼ U(0, 1)).

Obtaining insights on Nash equilibria of extensive-form games

To the best of our knowledge, Algorithm [EA] is the first one proposed to enumerate the Nash equilibria of an extensive-form game that does not resort to brute force. Besides the analysis of its complexity, we can also provide further insights of the numerosity of Nash equilibria in a game.

Uploaded to HAL; manuscript no. 1

The number of possible realisations of a Nash equilibria can vary from 1 to the number of outcomes of a game. The latter case implies that the utility function is constant (case E). However, in the generic case the number of Nash equilibria highly depends on the structure of the game-tree.

We observe from Section 5.3 that games with a totally unbalanced structure (U ) tend to host fewer Nash equilibria. This is due to the fact that if there is an outcome with great value to a player, she might choose to stick to it, and the opponent has few options to build a strategy that redirects her to an outcome that lies deeper in the tree. If an outcome with great value happens to lie at a very high level of the tree, the lower levels hardly host other realisations of Nash equilibria. The converse tends to occur as well, i.e., in a generic game with a complete structure (C) we typically observe many more Nash equilibria than in the unbalanced case. This follows the intuition that in a complete game structure a player can find more combination of strategies to convince the opponent to switch her best response to a different outcome.

Conclusions

In this paper, we introduce a new representation for a two-player extensive-form game as a graph of its outcomes. We prove that identifying a Nash equilibrium of an extensive-form game corresponds to identifying two cliques on such graph and its complementary. Thanks to this result, we introduce the first method of the literature to determine if an outcome of an extensive-form game is a realisation of a Nash equilibrium. Such method allows to define the first algorithm to enumerate the realisations of all Nash equilibria of an extensive-form game. The algorithm performs very well on a sample dataset of games of different shapes and sizes. Moreover, it is possible to reframe the algorithm so that it provides any given bound to the utility of all Nash equilibria. Such algorithm performs significantly better than the most known method in literature, which provides a (not always the tightest) upper bound to the utility of Nash equilibria.

We foresee several possible extensions of this work. First, we do not fully exploit the properties of the graph form to improve the efficiency of the proposed algorithms. Second, it would be interesting to devise methods to parallelize the computation of the Nash equilibria in large instances. Finally, the categorisation of extensive-form games suggests that more efficient methods can be designed for some specific classes of games. For instance, customized algorithms can be written to compute the compatibility of two outcomes, possibly extending the numerical results to larger games with more than two players.

that (h ′ , h ′′ ) / ∈ E| V ∪X . Let us consider C ′′ = C ′ ∪ {h}, which induces a clique on graph ⟨H, E⟩. For all h ′′ ∈ X h either (a) h ′′ ∈ X and thus there is an element h

′ ∈ C ′ such that (h ′ , h ′′ ) / ∈ E or (b) h ′′ ∈ X h \ X and thus (h, h ′′ ) / ∈ E. Therefore for all h ′′ ∈ X h there is h ′ ∈ C ′′ = C ′ ∪ {h} such that (h ′ , h ′′ ) / ∈ E. If C ′′

C. Graph that represents no game

Let us consider the graph ⟨H, E⟩ of Figure 5 and show that it is not the graph form of an extensiveform game. If it were the graph form of an extensive-form game, any preferences could be assigned by the players to the outcomes, i.e. any utility function u can be chosen. We consider a utility function such that the preferences over the outcomes are respectively u 1 :

h A ≻ 1 h C ≻ 1 h D ≻ 1 h B and u 2 : h B ≻ 2 h C ≻ 2 h A ≻ 2 h D .
E C ⟩ is {h A , h C }, but h A ≻ 1 h C . Analogously, in problem [EC] defined for h C in graph ⟨H, E C ⟩ we have V = ∅.
Therefore there is no outcome corresponding to a Nash equilibrium, which is a contradiction. This graph represents no extensive-form game.

D. Didactic example of application of Theorem 2

We consider the game in extensive form of Figure 6a) game which can be solved by direct inspection of the graph. Indeed, let us enumerate the realisations of Nash equilibria of the game by applying Theorem 2 to every outcome. In this example, the preferences of the players over the outcomes are respectively u 1 :

h 3 ≻ 1 h 4 ≻ 1 h 5 ≻ 1 h 6 ≻ 1 h 8 ≻ 1 h 7 ≻ 1 h 2 ≻ 1 h 1 and u 2 : h 1 ≻ 2 h 2 ≻ 2 h 4 ≻ 2 h 8 ≻ 2 h 5 ≻ 2 h 6 ≻ 2 h 7 ≻ 2 h 3 .
In order to apply Theorem 2 we consider the graph ⟨H, E⟩ of the game depicted in Figure 6b). By directly inspecting this graph, we achieve the following results.

Uploaded to HAL; manuscript no. 1

• h 1 is not an outcome of a Nash equilibrium: h 1 is the outcome least preferred by the first player.

There is no strategy of the second player, i.e., there is no maximal clique on the complementary graph ⟨H, E C ⟩ which includes h 1 alone;

• h 2 is not an outcome of a Nash equilibrium: the only maximal cliques on the complementary graphs including it are {h 2 , h 5 }, {h 2 , h 6 } and {h 2 , h 7 , h 8 }, but in none of these cases h 2 is the favourite outcome by the first player. This means that there is no strategy of the second player such that h 2 is the outcome of the best response of the first player;

• h 3 is not an outcome of a Nash equilibrium: it is the least preferred outcome by the second player. Any maximal clique on the complementary graph which includes h 3 also includes another outcome which is preferred by the second player to h 3 ;

• h 4 is not an outcome of a Nash equilibrium: every maximal clique on the complementary graph which includes h 4 also includes h 3 , which is preferred by the first player to h 4 ;

• h 5 is a possible outcome of a Nash equilibrium: we identify the maximal cliques {h 5 , h 6 , h 7 } and {h 1 , h 2 , h 5 } respectively on the graph and its complementary. In both cases h 5 is the preferred outcome, respectively by the second and the first player;

• h 6 is not an outcome of a Nash equilibrium: every maximal clique in ⟨H, E⟩ which includes h 6 also includes h 5 , which is preferred by the second player to h 6 ;

• h 7 is not an outcome of a Nash equilibrium: every maximal clique on ⟨H, E C ⟩ which includes h 7 also includes h 8 , which is preferred by the first player to h 7 ;

• h 8 is a possible outcome of a Nash equilibrium: we identify the maximal cliques {h 5 , h 6 , h 8 } and {h 1 , h 2 , h 7 , h 8 } respectively on the graph ⟨H, E⟩ and its complementary ⟨H, E C ⟩. In both cases h 5 is the preferred outcome, respectively by the second and the first player.

The only two outcomes which are possible realisations of Nash equilibrium are thus h 5 and h 8 .

It is interesting to notice that they are not Pareto-optimal, since h 4 is preferred by both players.

The Subgame Perfect Equilibrium of a game is also a Nash equilibrium, therefore it must be either of the two outcomes. Indeed, by backward induction it is proven to be h 8 .

E. Example of formulation of [CL]

Let us consider the graph ⟨H, E⟩ of Figure 7 and evaluate h as possible realisation of a Nash equilibrium. We would like to answer if h is the best response for a player i (it is not necessary to specify which player in this mock example), i.e. h to be the best outcome of a strategy. We assume given that h 1 ≻ i h and h 5 ≻ i h.

In order to answer this question, we would like to solve the problem [M C] with input ⟨H, E, h, X h ⟩, where X h = {h 1 , h 5 } and h is just a parameter of the problem. This corresponds to solve the problem [EC] with input ⟨V, X, E⟩, where V = {h 2 , h 3 , h 4 } and X = {h 1 , h 5 }. We thus look for some elements in V that could guarantee the existence of a strategy that includes h and none of the elements in X. We apply the system [CL]. For every vertex i ∈ V let us introduce the variable x i ∈ {0, 1} which is

x i = 1 if vertex i ∈ V is included in the clique.
The vertex h 2 is not connected neither to h 3 nor to h 4 , therefore the constraints x 2 + x 3 ≤ 1 and x 2 + x 4 ≤ 1 are added. The only vertex not connected to h 1 is vertex h 4 , therefore it must be included in the clique: x 4 ≥ 1. Both vertices h 2 and h 3 are connected to h 5 , therefore at least one of them must be included in the clique: x 2 + x 3 ≥ 1. The system [CL] for the graph of Figure 7 is thus:

x 2 + x 3 ≤ 1, ▷ (h 2 , h 3 ) / ∈ E x 2 + x 4 ≤ 1, ▷ (h 2 , h 4 ) / ∈ E x 4 ≥ 1, ▷ (h 4 , h 1 ) / ∈ E x 2 + x 3 ≥ 1, ▷ (h 2 , h 5 ) / ∈ E, (h 3 , h 5 ) / ∈ E
x 2 , x 3 , x 4 ∈ {0, 1}.

F. [VS] does not provide the tightest bound

Let us apply [V S] to the game of Figure 8a). The sequences are respectively Λ

1 = {∅, a 1 , a 2 , a 1 a 3 , a 1 a 4 } and Λ 2 = {∅, b 1 , b 2 }. The optimal values are x a 1 = 1, x a 1 a 3 = 1, y b 2 = 1 and u V S 1 = u 1 (h 4 ).
Therefore the utility of the first player for outcome h 4 provides an upper bound to the utility of the first player for any Nash equilibrium. However, h 4 is not the realisation of a Nash equilibrium: since h 3 ≻ 1 h 4 , the first player would never choose action a 4 over a 3 in a Nash equilibrium. The reader can verify, by using Algorithm [EA] on the graph of Figure 8b), that h 2 is the only realisation of a Nash equilibrium.

: h ⪰ 1 h ′ iff u 1 (h) ≥ u 1 (h ′ ) [iff u 1 (h) ≤ u 1 (h ′ )] index = 0 do h = H(index) ▷ Consider outcome h X 1 = {h ′ ∈ H|(h ′ , h) / ∈ E, u 1 (h ′ ) > u 1 (h)}
▷ Init vertex sets and excluding sets (2, 0)

X 2 = {h ′′ ∈ H|(h ′′ , h) ∈ E, u 2 (h ′′ ) > u 2 (h)} V 1 = {h ′ ∈ H \ X 2 |(h ′ , h) ∈ E} V 2 = {h ′′ ∈ H \ X 1 |(h ′′ , h) / ∈ E} solve [N E] giving ⟨V 1 , V 2 , X
(3, 4) (8, 11) (1, 9) (5, 1) (9, 3)

Figure 1 An extensive-form game in its representation as a tree. Preferences. The order of preference for the first player is: h6 ≻1 h3 ≻1 h5 ≻1 h2 ≻1 h1 ≻1 h4. The order of preference for the second player is:

h3 ≻2 h4 ≻2 h2 ≻2 h6 ≻2 h5 ≻2 h1.
Strategies. The two players choose respectively s1 and s2 as strategies.

At nodes ∅ and (a1, b2) the first player chooses respectively s1(∅) = a1 and s1(a1, b2) = a4. At nodes (a1), (a1, b2, a3) and (a1, b2, a4) the second player chooses respectively s2(a1) = b1, s2(a1, b2, a3) = b3 and s2(a1, b2, a4) = b6.

A h B h C h D ⟨H, E⟩ ⟨H, E C ⟩ h V X V X h A ∅ {h B } {h C , h D } ∅ h B {h A , h C } ∅ ∅ {h D } h C {h D } {h B } ∅ {h A } h D ∅ {h C } {h B } {h A }

.

  For sake of clarity, let us consider an example of extensive-form game, whose representation is the tree of Figure 1. The game Γ = ⟨I, H, u⟩ with two players I = {1, 2} is represented by a tree, which allows to show all the possible actions. The first player observes no actions ∅ and she picks an action in the set A(∅) = {a 1 , a 2 }. If she picks action a 2 , the game arrives to the outcome h 1 = (a 2 ) ∈ H. On the other hand, if she picks action a 1 , the second player observes it and picks an action from the set A(a 1 ) = {b 1 , b 2 }. If the second player picks action b 1 , she gets to the outcome h 2 = (a 1 , b 1 ) ∈ H. Analogously it is possible to get all the other outcomes of the game:

  has true as answer if and only if the problem [EC] with input ⟨V, X, E| V ∩X ⟩ has. The proof is provided in Appendix B. We observe that problem [EC] requires to prove the existence of a clique rather than identifying a maximal clique, as in problem [M C]. Moreover, the input of [EC] is a smaller graph induced by the neighborhood of one vertex, h, in graph of [M C]. Therefore, from now on, let us focus on the analysis of [EC]. In the following theorem, we prove that [EC] is NP-complete. Indeed, we reduce it to the problem of the existence of the dominating clique [DC], which is known to be NP-complete (cf. Kratsch and Liedloff (2007)). Problem 3. [DC] Existence of a dominating clique INSTANCE: A graph ⟨H, E⟩.

Theorem 4 .

 4 In a generic graph the problem [EC] is NP-complete. Proof. We present next a polynomial reduction from [DC] to [EC]. The argument of the proof is illustrated in Figure 4. We consider the problem [DC] with input ⟨H, E⟩ and define two vertex sets V = H and X = H, where H and H are copies of set H. Let us also define a set of edges

  while the sequences of the second player are Λ 2 = {∅, (b 1 ), (b 2 ), (b 2 , b 3 ), (b 2 , b 4 ), (b 2 , b 5 ), (b 2 , b 6 )}. If the first player chooses action a 1 , she must choose either action a 3 or a 4 . Therefore the constraint x (a 1 ) = x (a 1 ,a 3 ) + x (a 1 ,a 4 ) is added to the formulation. Similarly, if the second player chooses action b 2 , she must choose at least one action among {b 3 , b 4 , b 5 , b 6 }. Therefore we add the constraint

1 and u U BA 1 be 1 =

 111 played. We show that such upper bound is the same as the one provided by [V S]. The algorithm starts by ordering the outcomes in decreasing order of utility of the first player. Every outcome is then evaluated by solving problem [EC] with input ⟨V 1 , X 2 , E⟩. If the existence of a clique is proven for[CL] the algorithm stops and an upper bound is found. As remarked previously, since the procedure tests a necessary and yet not sufficient condition, the outcome found is not necessarily a realisation of a Nash equilibrium. Both [V S] and [U BA] provide the best outcome for the first player that can be a best response of a strategy of the second player, a necessary condition for the outcome to be a realisation of a Nash equilibrium. Theorem 5 thus proves that the two methods provide the same upper bound.Theorem 5. Consider a game Γ = ⟨I, A, H, P, u⟩ and its graph form ⟨H, E, u⟩. Let u V S the optimal values obtained when [V S] and [U BA] are applied to game Γ, then we have u V S

1 4. 3 .

 13 Best and Worst Nash equilibriumNote that the algorithms [V S] and [U BA] introduced in Section 2.2 do not provide the tightest upper bound to the utility of the Nash equilibria (cf. Appendix F). In this section, we introduce an algorithm that provides the Nash equilibrium whose utility is the highest for the first player. The algorithm [BN E] consists in ordering the outcomes from best to worst following the utility function of the first player and then picking the first of them that is a realisation of Nash equilibrium, i.e., that solves [N E]. Analogously, it is possible to identify the Nash equilibrium with the lowest utility for the first player, by ordering in reverse order the outcomes. The algorithm [W N E] is presented together with [BN E] in Appendix G.

  Section 5.2. Dataset 2 has 72 extensive-form games which vary in their structure {R, C, U }, size {256, 729, 1296, 2401} and utility {R, D, Z, A, F , E}. Dataset 3 has 75 extensive-form games of size 729 which vary in structures {R, C, U } and utility {R, D, Z, A, F }. Dataset 2 and 3 have games of larger size, that are used to assess the method to enumerate the Nash equilibria. They are used in Section 5.3. Dataset 2 includes games with different characteristics; it allows us to assess the method on a large variety of games. Dataset 3 includes 75 games with size 729, gathered in 15 groups, each one with 5 games having the same encoding. The 15 groups are built alternating 3 different structures {R3 * 729, C3 * 729, U 5 * 729} and 5 different utilities ′ * ′ ∈ {R, D, Z, A, F }. The utility E has been discarded, as we show next that it does not need further analyses. The analysis performed on Dataset 3 allows to understand the variability of the results obtained for Dataset 2.

  First and main result is that the algorithm [U BA] overcomes the methods relying on [V S -L] and [V S -L2] by some orders of magnitude. The method [U BA] computes the upper bound to the utility of Nash equilibria at least > 40 times faster than [V S -L] and [V S -L2]. Second, we highlight the quality of the valid inequality added in [V S -L2]. Indeed, we observe that it improves the computation time with respect to [V S -L] in 10 out of 21 instances and reduces of around 30% the computation time in instances like R6R512 and C2R512, which require more than 25 minutes for [V S -L]. Both [V S -L] and [V S -L2]

  allows us to tighten the upper bound in 4 instances out of 21, thus showing that [U BA], [V S -L] and [V S -L2] do not always achieve the tighest bound. In Table 1, the few instances in which [BN E] tightens the bound are underlined, whereas in the other 17 out of 21 instances the number of iterations does not change. As predicted, [BN E] is slower than [U BA], but still performs more than 6 times faster than both [V S -L] and [V S -L2]. Algorithm [W N E] requires a larger computation time than [BN E] in 19 out of 21 instances. In fact, it always has a larger number of iterations than [BN E]. Indeed, [W N E]

  induces not only a clique, but a maximal one on ⟨H, E⟩ we have the proof. If C ′′ induces a non-maximal clique, there is a vertex set C ′′′ such that C ′′ ⊂ C ′′′ that induces a maximal clique on ⟨H, E⟩. By construction C ′′′ ∩ X = ∅, which completes the proof.

1 : 1 : 1 :

 111 Figure 2 Strategies as maximal cliques. a) Graph representation of the game of Figure 1. b) Every strategy for the first player correspond to a maximal clique of the graph.

  Figure 4 Reduction. a) Problem [DC] with H = {hA, hB, hC , hD, hE} and solution C = {hB, hD}; b) Problem [CL] with V = H and X = H; the solution is given by C = { hB, hD} ⊂ V .

  h

Figure 5

 5 Figure 5Counterexample. Preferences of the players over the outcomes are respectively u1 : hA ≻1 hC ≻1 hD ≻1 hB and u2 : hB ≻2 hC ≻2 hA ≻2 hD.

  Figure 7Example. System [CL-1] is applied to the graph in figure, with V = {h2, h3, h4} and X = {h1, h5}.

Figure 9

 9 Figure 9 Application of Algorithm [EA] to Dataset 2. Times are in seconds. Structure of the game is identified by colour and shape: blue circle (Random), red plus (Complete), green cross (totally Unbalanced).

  |H ′ \H| strategy profiles and |H ′ \ H| + 1

	Uploaded to HAL; manuscript no. 1
	outcomes. However, a different formulation of [ST] introduced in Von Stengel (1996) can be written
	in the form of a bi-level linear program with a number of variables and a number of constraint
	inequalities that are linear in the tree size. Such formulation, which considers mixed strategies, is
	discussed in details in Section 4.2 and it is adapted to pure strategies.

  1 , the second player can choose a strategy s 2 whose corresponding set of outcomes C 2 on the complementary graph includes h ′ ∈ C 2 . The second player has an incentive to pick the element within C 1 that maximises her utility, a condition that thus h must fulfill in order to avoid deviations from the second player. A similar argument can be put forward by inverting the players. Note that a single outcome may correspond to multiple strategy

pairs. Thus, in the graph form, determining if an outcome corresponds to a Nash equilibrium means to answer to the question if there exists at least a pair of maximal cliques respectively on the graph and on the complementary graph such that their intersection is a mutual best response in the corresponding strategic form.

The best response of the second player leads to the outcome which is preferred the most by the second player within the maximal clique C 1 chosen by the first player. If a vertex h ∈ H corresponds to the outcome of a best response of the second player, there must be a maximal clique C 1 which includes it, i.e., h ∈ C 1 , and excludes all the nodes X h which are preferred to h by the second player.

Whether such clique exists is the problem [MC] formalised hereafter.

Problem 1. [MC] Existence of a maximal clique including h and excluding

X h . INSTANCE: ⟨H, E, h, X h ⟩ defining a graph ⟨H, E⟩, a vertex h ∈ H and a subset of vertices X h ⊂ H with h / ∈ X h .

QUESTION: Is there a vertex set C ⊂ H \ X h with h ∈ C that induces a maximal clique on ⟨H, E⟩?

  E, h, X h 2 ⟩, as defined in the previous section. In this section, we evaluate the complexity of problem [M C] with input ⟨H, E, h, X h ⟩ for a generic graph ⟨H, E⟩. More specifically, we first define a reduced version[EC] of problem [M C] and then we show that the two problems are equivalent, i.e., that a solution of problem [EC] provides a solution of problem [M C] and vice versa.Let us consider a generic problem [M C] with input ⟨H, E, h, X h ⟩. First, we argue that when solving [M C] the problem can be restricted to the neighbourhood of h ∈ H, V h = {h ′ , (h, h ′ ) ∈ E}.Indeed, let us suppose that there is a maximal clique induced by a vertex set C ⊂ H with h ∈ C excluding X h ⊂ H. Since the clique is maximal, it must hold that every vertex h ′ ∈ X h there is at least one vertex h ∈ C which is not connected to h Theorem 3 shows that the problem [M C] with input ⟨H, E, h, X h ⟩ can be solved by means of problem [EC] with a different input derived by the input of problem [M C].

plexity of solving two instances of problem [M C]: one with input ⟨H, E C , h, X h input ⟨H, ′ , i.e., such that (h, h ′ ) / ∈ E. Those vertices in X h who are not in the neighborhood V h always fulfill this property, as h ∈ C. Therefore, instead of considering all the vertices in X h , we can restrict the problem to X = X h ∩ V h . With this argument, we conclude that the vertex set C belongs to the neighborhood V h .

Example. Consider the graph of Figure

3a

), in which the set C = {h, h 2 , h 3 , h 4 } induces a maximal clique. The vertices X h \ V h = {h 5 , h 10 } are not connected to h and the vertex H \ X h \ V h = {h 9 } can never belong to the vertex set C that induces the maximal clique. Therefore we can restrict the problem from H to {h 1 , h 2 , h 3 , h 4 , h 6 , h 7 , h 8 }.

Let us thus consider a slightly different problem

[EC]

.

Problem 2.

[EC] Existence of an excluding clique.

INSTANCE: ⟨V, X, E⟩ defining a graph ⟨V ∪ X, E⟩ with V ∩ X = ∅.

QUESTION: Is there a vertex set C ⊂ V that induces a clique on ⟨V, E⟩ that is maximal in ⟨C ∪ X, E⟩?

  We prove now that [DC] admits answer true if and only if the same happens for [EC] with input ⟨V, X, E ′ ⟩. If [DC] has answer true, there exists a vertex set C ⊂ H that: (a) induces a clique on ⟨H, E⟩; (b) and such that, for each j ∈ H \ C, there is a i ∈ C such that

We consider the problem [EC] with input ⟨V, X, E ′ ⟩. By construction, the input has size O(|H| 2 ), i.e., it is polynomial in the size of the input of problem [DC].

  let us consider H CL the set of h ∈ H such that problem [CL] with input ⟨V, H, E⟩ has answer true. Then we have u U BA By definition of H CL for each h ∈ H CL we have h = arg max h Algorithm 3 [UBA] Upper Bound Algorithm INPUT: Game in graph form Γ = ⟨H, E, u⟩ H = order(H, ⪰ 1 ) ▷ Elements are ordered w.r.t. player 1

	1	=
	max h∈H CL u 1 (h). Moreover, for all h ∈ H CL let us consider a strategy s h 1 ∈ S 1 such that V ⊂ H(s h 1 )
	and H(s h 1 ) ∩ X = ∅.

′ ∈H(s h 1 ) u 1 (h), which implies h ∈ BR 2 . Analogously, if h / ∈ H CL there is no s 1 ∈ S 1 such that h = arg max h ′ ∈H(s 1 ) u 1 (h) and thus h / ∈ BR 2 . Since H CL = BR 2 , we have u U BA 1 = max h∈BR 2 u 1 (h).

Uploaded to HAL; manuscript no. 1

Table 4 .

 4 The games' structure is encoded as follows: Rn indicates that the number of actions at every child of a node h ′ ∈ H is chosen uniformly at random U({0, . . . , n • |A(h ′ )|}), given the constraint that they have on average n actions; Cn indicates that every node has the same number of actions, with n actions per node; and finally U n indicates that at every node all actions but one lead to an outcome, with n actions per node. The players' utility is encoded as follows: R if the utility of an outcome is chosen uniformly at random

U

([0, 1]

) in the interval [0, 1]; D if the utility is chosen randomly from a discrete set U({1, . . . , 10}), namely a natural number between 1 and 10; Z if the game is zero-sum, i.e., at every node h ∈ H the winner is chosen at random i ∈ {1, 2} and gets u i (h) = 1, while the loser 0; A if the game is Uploaded to HAL; manuscript no. 1

  We show that if this graph were generated by a game, it would have no Nash equilibria. This is a contradiction, because every extensive-form game has at least one Nash equilibrium. The table of Figure5shows the analysis for every outcome h ∈ {h A , h B , h C , h D }.

Every line of the table shows that the composition of the vertex sets V and X for any pair of problems

[EC]

given ⟨H, E⟩ and its complementary ⟨H, E C ⟩ as input. For no outcome h, i.e. for no pair of problems at any given line, both problems has answer true. Indeed, neither h B nor h D can be the outcome of a Nash equilibrium, because they are the least favoured respectively by the first and by the second player, and there is no maximal clique on ⟨H, E⟩ and on ⟨H, E C ⟩ that consists of the singleton including them, i.e. {h B } and {h D } are not maximal cliques. In problem

[EC]

for h D in graph ⟨H, E⟩ we have that V = ∅, as well as for h B in graph ⟨H, E C ⟩. Outcome h A also is not a Nash equilibrium, because the only maximal clique on the graph which includes it is {h A , h B }, but h B ≻ 2 h A . We observe that in problem [EC] defined for h A in graph ⟨H, E⟩ we have V = ∅. Finally, outcome h C is not a Nash equilibrium, because the only maximal clique on the graph defined from ⟨H,

  G. Best and worst Nash equilibrium Algorithm 4 [BNE] (WNE) Best (Worst) Nash Equilibrium INPUT: Game in graph form Γ = ⟨H, E, u⟩ H = order(H, ⪰ 1 ) ▷ Elements h ∈ H are ordered from best to worst [from worst to best] w.r.t.

	player 1

Table 1

 1 Comparison of the CPU time for computation of Algorithms providing bounds to the utility of NE. Every line is an instance. Running time is measured in seconds. Time limit is set to 1 hour (> 1h indicates that such limit is achieved). The instances in which [BN E] tightens the bound of [U BA] are underlined.

		Game			Computation time (s)			Iterations
	Label	Size Structure [VS-L] [VS-L2] [UBA] [BNE] [WNE] [UBA] [BNE] [WNE]
	R4R100 100	R	4.85	3.69	0.09	0.14	0.98	12	12	69
	C10R100 100	C	0.32	0.46	<0.01 <0.01 0.10	1	1	30
	U4R100 100	U	2.22	2.75	0.02	0.18	0.57	29	29	35
	R4R216 216	R	51.34	44.23 <0.01 <0.01 1.53	2	2	124
	C6R216 216	C	10.45	22.87	0.04	0.38	9.97	6	7	164
	U6R216 216	U	19.43	12.03	0.06	0.61	2.24	39	39	178
	R5R324 324	R	324.76 282.29	0.04	2.93	9.35	5	5	287
	C18R324 324	C	2.11	2.97	0.01	0.28	0.22	5	5	57
	U18R324 324	U	26.42	25.37	0.03	1.48	5.22	13	13	312
	R5R400 400	R	512.75 461.24	2.20	2.71	9.49	32	32	334
	C20R400 400	C	2.83	2.83	0.03	0.46	0.27	12	12	69
	U4R400 400	U	234.33 248.02	0.27	2.21	5.68	60	60	341
	R6R512 512	R	1918.39 1469.56 0.53	4.12	26.97	47	78	428
	C2R512 512	C	1594.47 1114.76 0.25	0.38 161.49	1	1	317
	U8R512 512	U	192.89 176.96	0.27	3.50	16.66	63	89	424
	R6R625 625	R	> 1h	> 1h	0.11	7.18	24.97	15	15	558
	C5R625 625	C	95.0	95.92	0.30	2.08	7.77	22	22	182
	U4R625 625	U	818.2	854.45	0.04	7.94	29.96	4	4	622
	R7R729 729	R	> 1h	> 1h	11.13 9.31	24.71	56	56	419
	C3R729 729	C	104.33 126.89	0.02	3.02	32.75	3	3	244
	U14R729 729	U	255.96	247.0	0.17 15.19 29.92	30	45	685

1 , X 2 , E⟩ as input index = index + 1 while [N E] has no solution OUTPUT: h

Table 2

 2 Application of Algorithm [EA] on games of Dataset 2 with size 729. Every line is an instance. Computation time is in seconds.

	Label Structure Utility NE	t tot	t avg t max
	R3R729	R	R	17.2 206.61 0.28 7.11
	C3R729	C		75.2 883.40 1.21 28.89
	U5R729	U		2.0	47.42 0.06 9.72
	R3D729	R	D	38.6 149.10 0.20 5.39
	C3D729	C		101.8 1240.58 1.70 69.77
	U5D729	U		8.0	12.96 0.02 4.37
	R3Z729	R	Z	31.4	70.24 0.10 4.01
	C3Z729	C		276.6 654.16 0.90 26.68
	U5Z729	U		1.8	4.34	0.01 0.02
	R3A729	R	A	10.0 250.22 0.34 4.96
	C3A729	C		95.4 1523.49 2.10 167.65
	U5A729	U		1.8	40.07 0.06 7.74
	R3F729	R	F	91.4 364.85 0.50 6.86
	C3F729	C		132.8 1354.45 1.86 121.96
	U5F729	U		8.8	58.53 0.08 7.72

Table 3

 3 Application of Algorithms of [EA] to Dataset 3. Every line shows the average value of 5 instances having the same label. All games have size 729. Computation time is in seconds.

Appendix

A. Proof of Theorem 2.

(i) We prove first that for any Nash equilibrium the two maximal cliques in the statement do exist.

If h is a realisation of a Nash equilibrium (s 1 , s 2 ) ∈ S 1 × S 2 we have that for all s 1 ∈ S 1 and s 2 ∈ S 2 :

We consider H(s 1 ) ⊂ H. By Lemma 2, H(s 1 ) forms a maximal clique in graph ⟨H, E⟩. We thus

2 and, as a consequence, the vertex set

, then h is a realisation of a Nash equilibrium. By Lemma 3, we have that there are

) ∩ H(s 2 ), the strategy profile (s 1 , s 2 ) has realisation h satisfying:

Analogously, we prove that for all s 1 ∈ S 1 :

Therefore (s 1 , s 2 ) is a Nash equilibrium and h is its realisation.

B. Proof of Theorem 3.

(i) First, let us suppose that the problem [M C] has true as answer, i.e. there is a vertex set C ⊂ H \ X h with h ∈ C that induces a maximal clique on ⟨H, E⟩. By construction, C ⊂ V induces a clique on ⟨V ∪ X, E| V ∪X ⟩. Moreover, the clique is maximal, i.e. there is no h ′′ ∈ H \ C such that for all h ′ ∈ C we have (h ′ , h ′′ ) ∈ E. Therefore for all h ′′ ∈ X there is h

(ii) Let us suppose now that the problem [EC] has true as answer, i.e. there is a vertex set

Every node has a random number of actions.

C Complete

Every node has the same number of actions.

U Totally Unbalanced

At every node all children but one are outcomes.