{'fraction_non_alphanumeric': 0.06060663399496679, 'fraction_numerical': 0.014342750099339628, 'mean_word_length': 3.4769165607793306, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 97, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A parametric representation of totally mixed Nash equilibria

We compute a parametric description of the totally mixed Nash equilibria of a generic game in normal form with pre-fixed structure. Using this representation, we show conditions under which a game has the maximum possible number of this kind of equilibria. Then, we present a symbolic procedure that allows us to describe and estimate the number of isolated totally mixed Nash equilibria of an arbitrary game. Under certain assumptions, the algorithm computes the exact number of these equilibria.


Introduction
Noncooperative game theory is used to model and analyze strategic interaction situations. Among its most outstanding applications, we can mention the fundamental role this theory has played in economics (see, for example, the classical reference book [31]). Moreover, game theory has also been applied to politics, sociology and psychology, and to biology and evolution as well.
One of the main concepts in this theory is a Nash equilibrium, which consists in a situation in which no player can increase his payoff by unilaterally changing his strategy. Since within this theory the players cannot communicate in order to decide a simultaneous change of strategies, in a Nash equilibrium the game stabilizes. In [22], it is proved that any noncooperative game in normal form has at least one Nash equilibrium. However, the proof is not constructive and does not give any information about the existence of more than one Nash equilibrium. The question posed is how to compute algorithmically Nash equilibria and to determine the number of them in a given game.
Nash equilibria of noncooperative games in normal form can be regarded as real solutions to systems of polynomial equations and inequalities (see, for instance, [29,Chapter 6]). In the case of two players, each equilibrium is the solution of a linear system of equations, and therefore, equilibria may be found exactly by using simplex type algorithms (see, for instance, [15]); however, there is no polynomial time algorithm solving the problem (see [32]). In the general case of a game with more than two players, the polynomials appearing are multilinear. To solve the problem of finding one equilibrium, some numerical methods have been applied successfully (for example, some methods derived from Scarf's algorithm, [26]). Nevertheless, sometimes it is not sufficient to compute only one equilibrium because, depending on the problem to be solved, not all the equilibria of a game are equally interesting and the methods developed to compute only one equilibrium do not allow us to decide beforehand whether it fulfills some additional properties or to compare different equilibria.
A comparative study of different known methods for the computation of all the Nash equilibria of a game may be found in [7]. In [12], a new algorithm solving this problem for generic games by means of homotopy methods is presented, but no complexity bounds are shown. In addition, the application of symbolic algorithms solving systems of equations and inequalities over the real numbers is being studied in this context, motivated by the characterization of the set of all the Nash equilibria of a game as a semi-algebraic set (an example of this fact is the application of quantifier elimination algorithms over the real numbers to compute approximated equilibria in [16]; see also the survey [17]). However, up to now, no significative result had been obtained concerning the adaptation of these algorithms in order to profit from the particular properties of the algebraic systems arising in game theory.
In this paper, we study totally mixed Nash equilibria, that is to say, Nash equilibria in which every player allocates a positive probability to each of his available strategies. Note that a procedure to compute these equilibria can be used as a subroutine to compute all Nash equilibria of the game by recursing over all possible subsets of used strategies. We present a symbolic method to find a parametric description of the set of totally mixed Nash equilibria of a generic game with a pre-fixed structure. This method is based on a symbolic procedure for the computation of multihomogeneous resultants with complexity polynomial in the degree and the number of variables of the resultant ( [13]). Using the description previously obtained, we show conditions (given by polynomial inequalities on the payoff values) under which a game with the given pre-fixed structure will have the maximum number of such equilibria. The next step is to give a similar parametric description for particular games. First, we solve this problem under some genericity assumptions implying, in particular, that the number of totally mixed Nash equilibria of the game is finite, and we show how to compute this number. Then, we consider the general case, in which we give a parametric description of a finite set of points including all the isolated (in the complex space) totally mixed Nash equilibria of the game, which enables us to bound the number of these isolated equilibria. All our algorithms have a complexity polynomial in the number of pure strategies of each player, and the number of totally mixed Nash equilibria of a generic game with the given structure.
This paper is organized in the following way: In Section 2, we introduce some basic notions on game theory, the description of the algorithmic model we are going to use and a mathematical formulation for the totally mixed Nash equilibria of a game in normal form as the set of solutions of a system of multihomogeneous polynomial equations. In Section 3, the algorithmic description of the totally mixed Nash equilibria of a generic game is given, and it is used to find conditions under which a game has the maximum number of these equilibria. In Section 4 we deal with the totally mixed Nash equilibria of particular games. Finally, the last section is devoted to proving some results about the algorithmic computation of multihomogeneous resultants and upper bounds for their degrees which are used throughout the paper.

Basic facts
Throughout this paper Q denotes the field of rational numbers, N denotes the set of positive integers and N 0 := N ∪ {0}.
If K is a field, we denote an algebraic closure of K by K. The ring of polynomials in the variables x 1 , . . . , x n with coefficients in K is denoted by K[x 1 , . . . , x n ]. For a polynomial f ∈ K[x 1 , . . . , x n ] we write deg f to refer to the total degree of f and deg x i f to refer to the degree of f in the variable x i .
For n ∈ N and an algebraically closed field k, we denote by A n (k) and P n (k) (or simply by A n or P n if the base field is clear from the context) the n-dimensional affine space and projective space over k respectively, equipped with their Zariski topologies.
We adopt the usual notions of dimension and degree of an algebraic variety V , which will be denoted by dim V and deg V respectively. See for instance [27] and [9] for the definitions of these notions.

Game theory
In this section we present some basic game theory concepts. For a more detailed account on the subject we refer the reader to any standard game theory text such as [24].
We consider non-cooperative games in normal form; that is to say, games in which there is only one time step at which all the players move simultaneously without communicating among themselves. We will assume that there are r players in the game having n 1 + 1, . . . , n r + 1 distinct available pure strategies respectively (n 1 , . . . , n r ∈ N).
For i = 1, . . . , r: • c (i) := (c (i) j 1 ...jr ) 0≤j k ≤n k is the given payoff matrix of player i, where c (i) j 1 ...jr is the payoff to player i if, for every 1 ≤ k ≤ r, player k chooses the strategy j k .
• X i := (x i0 , x i1 , . . . , x in i ) is a vector representing a mixed strategy of the ith player, which is a probability distribution on his set of pure strategies (that is to say, x ij is the probability that the ith player allocates to his jth pure strategy).
With these notations, for every 1 ≤ i ≤ r, the payoff to player i if the mixed strategies X 1 , . . . , X r are played is: A Nash equilibrium is a vector of mixed strategies such that no player can increase his payoff by changing unilaterally to another strategy while the other players keep their strategies fixed; that is to say, a vector of mixed strategies X 1 , . . . , X r satisfying for every mixed strategy X ′ i . A totally mixed Nash equilibrium is a Nash equilibrium in which each pure strategy is assigned a positive probability, that is, one that satisfies x ij > 0 for every 1 ≤ i ≤ r, 0 ≤ j ≤ n i .

Data structure, algorithms and complexity
The algorithms we consider in this paper are described by arithmetic networks over the base field Q (see [33]). An arithmetic network is represented by means of a directed acyclic graph. The external nodes of the graph correspond to the input and output of the algorithm. Each of the internal nodes of the graph is associated with either an arithmetic operation in Q or a comparison between two elements in Q followed by a selection of another node. These are the only operations allowed in our algorithms.
We assume that the cost of each operation in the algorithm is 1 and so, we define the complexity of the algorithm as the number of internal nodes of its associated graph.
The objects our algorithms deal with are polynomials with coefficients in Q. We represent each of them by means of one of the following data structures: • Dense form, that is, as the array of all its coefficients (including zeroes) in a pre-fixed order of all monomials of degree at most d, where d is an upper bound for the degree of the polynomial. The size of this representation equals the number of monomials of degree at most d.
• Sparse encoding, that is, as an array of the coefficients corresponding to monomials in a fixed set, provided that we know in advance that the coefficient of any other monomial of the polynomial must be zero. The size in this case is the cardinal of the fixed set of monomials.
• Straight-line programs, which are arithmetic circuits (i.e. networks without branches). Roughly speaking, a straight-line program (or slp, for short) over Q encoding a polynomial f ∈ Q[x 1 , . . . , x n ] is a program which enables us to evaluate the polynomial f at any given point in Q n . Each of the instructions in this program is an addition, subtraction or multiplication between two pre-calculated elements in Q[x 1 , . . . , x n ], or an addition or multiplication by a scalar. The number of instructions in the program is called the length of the slp. For a precise definition of straight-line programs we refer to [5,Definition 4.2] (see also [11]).

Polynomial equations for totally mixed Nash equilibria
Now, we show that the totally mixed Nash equilibria of an r-person game in normal form can be regarded as real solutions to a polynomial equation system (see [29,Sec. 6.3]). Let us observe that, if the payoff matrix of player i is c (i) (1 ≤ i ≤ r), given mixed strategies X 1 , . . . , X r , the payoff to player i is j is the (j + 1)th vector of the canonical basis of R n i +1 . Now, if (X 1 , . . . , X r ) is a totally mixed Nash equilibrium, we have that x ij > 0 for every i, j. Then, in order that π i (X 1 , . . . , X i−1 , · , X i+1 , . . . , X n ) attains a maximum at X i = (x i0 , . . . , x in i ) (among all the different probability distributions), a necessary and sufficient condition is that (1) In fact, assuming that this condition does not hold for some 1 ≤ i ≤ r, let j max and j min denote the indices of pure strategies leading to maximum and minimum payoffs to player i respectively. Then, taking ε > 0 with ε < min{x ij min , 1 − x ijmax } and changing to the (totally) mixed strategy j min ) the ith player can increase his payoff by j min , X i+1 , . . . , X r )) > 0, contradicting the fact that the vector is a totally mixed Nash equilibrium for the game.
Conversely, for a vector of totally mixed strategies (X 1 , . . . , X r ) such that all the identities (1) hold for every 1 ≤ i ≤ r, we have that π i (X 1 , . . . , X ′ i , . . . , X r ) = π i (X 1 , . . . , X i , . . . , X r ) for every mixed strategy X ′ i and so, player i (1 ≤ i ≤ r) cannot increase his payoff by unilaterally changing his strategy, which implies that (X 1 , . . . , X r ) is a Nash equilibrium for the game.
We conclude that the totally mixed Nash equilibria of the game are those vectors (X 1 , . . . , X r ) with X i := (x i0 , . . . , x in i ) for every 1 ≤ i ≤ r satisfying: (a) x ij > 0 for i = 1, . . . , r and j = 0, . . . , n i , . . x rjr = 0 for i = 1, . . . , r and k = 1, . . . , n i , where the sum runs over all J −i := j 1 . . . j i−1 j i+1 . . . j r with 0 ≤ j t ≤ n t for every t = i and a (ik) Let us observe that (c) is a system of n := n 1 + · · · + n r multihomogeneous polynomial equations in the r groups of variables X 1 , . . . , X r with n 1 + 1, . . . , n r + 1 variables respectively (with degrees 1 or 0 with respect to each group) and, therefore, it defines a (possibly empty) projective variety in P n 1 (C) × · · · × P nr (C). The complex solutions to the polynomial equation system (c) will be called quasi-equilibria of the game (see [7]), and those solutions not lying in any of the infinite hyperplanes {x i0 = 0} (1 ≤ i ≤ r) will be called affine quasi-equilibria of the game.
Every quasi-equilibrium ξ := (ξ 1 , . . . , ξ r ) ∈ P n 1 (C) × · · · × P nr (C) determines at most one totally mixed Nash equilibrium of the game: for every 1 ≤ i ≤ r, let s ξ i := 0≤j≤n i ξ ij be the sum of the coordinates of ξ i . If s ξ i = 0 for every 1 ≤ i ≤ r, the unique associated representation of ξ whose coordinates satisfy condition (b) is (ξ 1 /s ξ 1 , . . . , ξ r /s ξr ), and it will be a totally mixed Nash equilibrium if and only if all its coordinates are positive real numbers.

On the number of solutions to a multihomogeneous system
Let r ∈ N be a positive integer. Fix positive integers n 1 , . . . , n r and consider r groups of variables X j := (x j0 , . . . , x j n j ), j = 1, . . . , r. We say that the polynomial F ∈ K[X 1 , . . . , X r ] is multihomogeneous of multi-degree v := (v 1 , . . . , v r ), where v 1 , . . . , v r are non-negative integers, if F is homogeneous of degree v j in the group of variables X j for every 1 ≤ j ≤ r.
Set n := r j=1 n j . The classical Multihomogeneous Bézout Theorem, which follows from the intersection theory for divisors (see for instance [27,Chapter 4]), states that the set of common zeroes (over an algebraically closed field) in the projective variety P n 1 × · · · × P nr of n generic multihomogeneous polynomials F 1 , . . . , F n with multi-degrees ν i := (ν i1 , . . . , ν ir ) for i = 1, . . . , n is a zero-dimensional variety with Bez n 1 ...,nr (ν 1 ; . . . ; ν n ) := For an alternative proof of this result using deformation techniques, we refer the reader to [21], [19] and [10]. Note that this can be seen as a particular case of Bernstein's theorem on the number of common roots of sparse systems [3]. The quantity Bez n 1 ...,nr (ν 1 ; . . . ; ν n ) is called the Bézout number of the generic multihomogeneous polynomial system. If k 1 , . . . , k t are positive integers with t i=1 k i = n, we will use the notation Bez n 1 ,...,nr (ν 1 , k 1 ; . . . ; ν t , k t ) for the Bézout number of a multihomogeneous system with k i polynomials of multi-degree ν i for every 1 ≤ i ≤ t.
We are going to deal with the case in which δ > 0. This inequality can be determined by considering the set of exponents appearing with non-zero coefficients in each of the polynomials in the system (see [23, Chapter IV, Proposition 2.3]) and in our particular case, it is equivalent to the fact that n j ≤ 1≤k≤r, k =j n k = n − n j for every 1 ≤ j ≤ r. From now on, we will assume that these inequalities hold.
Taking into account that d ii = 0 for every 1 ≤ i ≤ r, the only n-tuples contributing to the sum (3) are those where j ik = i for every 1 ≤ k ≤ n i , and for each of them, the corresponding term of the sum equals 1. Therefore, δ equals the cardinality of the set

Geometric resolutions
A way of representing zero-dimensional affine varieties which is widely used in computer algebra nowadays is a geometric resolution. This notion was first introduced in the works of Kronecker and König in the last years of the XIXth century [14]. Roughly speaking, it consists in a parametric description of the variety in which the parameter values range over the set of roots of a univariate polynomial. Now, we give the precise definition we are going to use.
In our particular setting of totally mixed Nash equilibria computation, we will not only deal with zero-dimensional varieties in an affine space, but we will also consider zero-dimensional subvarieties of P n 1 × · · · × P nr .

On the totally mixed Nash equilibria of a generic game
This section is devoted to the study of totally mixed Nash equilibria of generic games. In order to do this, we will begin by treating the payoff values as parameters and computing a geometric resolution of the set of quasi-equilibria of the associated generic game. This geometric resolution will provide a rational formula of the parameters which, for generic values of them, represents the totally mixed Nash equilibria of the game. Then, we will obtain a finite number of generic conditions ensuring that a specific game has the maximum possible number of totally mixed Nash equilibria. Under these conditions, the Nash equilibria of the game can be described by the geometric resolution obtained by substituting the given payoffs for the parameters in our generic formulas.

The set of quasi-equilibria of a generic game
Here we are going to compute a geometric resolution of the set of quasi-equilibria of a generic game with r players with n 1 + 1, . . . , n r + 1 pure strategies respectively, where n i ∈ N for every 1 ≤ i ≤ r.
where the sum runs over all are new variables that are regarded as parameters representing the generic payoffs of the game, from the polynomials introduced in (5), we can obtain the polynomials defining the quasi-equilibria of the generic game by substituting for every 1 ≤ i ≤ r, 1 ≤ k ≤ n i and each J −i = j 1 . . . j i−1 j i+1 . . . j r with 0 ≤ j t ≤ n t for every t = i. Thus, we are going to compute a geometric resolution of the solution set of the generic polynomial system F (i) k = 0, 1 ≤ i ≤ r, 1 ≤ k ≤ n i , and then, we will make the substitution (6) in the result to get the desired geometric resolution of the quasi-equilibria of the generic game.
Our main result is the following: Theorem 1 Let notations be as in Section 2. There is an algorithm which computes a geometric resolution of the set of quasi-equilibria of a generic game with r players having n 1 + 1, . . . , n r +1 pure strategies respectively, within complexity O(D 2 (D+n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))), where

The algorithm obtains polynomials
Proof. The geometric resolution of the system F (i) k = 0, 1 ≤ i ≤ r, 1 ≤ k ≤ n i , will be obtained by means of multihomogeneous resultant computations. More precisely, we are going to obtain the geometric resolution associated to a linear form ℓ which separates the points of the generic system by computing the resultant of our system and a generic linear form. The minimal polynomial of ℓ and the polynomials W ij will be obtained by specializing the resultant and some of its partial derivatives in the coefficients of ℓ.
We introduce a set of new indeterminates , and we consider the multilinear polynomial which is obtained by homogenizing the generic affine linear form with respect to each group of variables X 1 , . . . , X r .
The first step of the algorithm consists in the computation of the polynomial resultant R = Res(F 0 , F . . , 1, 0) for 1 ≤ j ≤ n r , in which all the coefficients of the polynomial of multi-degree d 0 corresponding to monomials not appearing in F 0 are substituted for 0. Thus, in order to obtain the polynomial R we apply an adapted version of the algorithm underlying the proof of [13, Theorem 5] (see Subsection 5.1). With our previous notation, the complexity of this algorithm is of order O(D 2 (D + n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))) and it computes a straight-line program for R whose length is of the same order.
Then, a standard procedure enables us to compute a geometric resolution of the zerodimensional variety defined by the system F (i) from the polynomial R: the polynomials giving the parametrization of the points in the variety are obtained from the partial derivatives which we compute from the straight-line program representing R within the same complexity order as in the first step. These partial derivatives are encoded by straight-line programs of length of the same order as for the straight-line program encoding R (see [5]).
in R. Since the resultant R is in the ideal (F 0 , F , then substituting L for T in P L , we obtain a polynomial P which is in the ideal (F . Taking into account that deg T (P L ) = δ, which is the number of solutions of the system F (i) k = 0, it follows that P L is a multiple by a nonzero factor in Q[A (ik) ] of the minimal polynomial of L. On the other hand, taking the partial derivative of P with respect to the variable L ij , we get We conclude that making the substitution (7) in we obtain polynomials which complete the geometric resolution of the variety defined by F Finally, in order to obtain a geometric resolution for the zero set of the generic system, we choose a separating linear form and we substitute its coefficients for the parameters L ij . As the multihomogeneous system F (i) k = 0 is generic, it has no zeroes in the hyperplanes x i0 = 0 (1 ≤ i ≤ r) and we can consider its zeroes as affine points by setting x i0 = 1 (1 ≤ i ≤ r). Let us show that the linear form ℓ := 1≤i≤r x i1 separates these affine points. To this end, it is enough to show the existence of a choice of coefficients such that the induced polynomial system has the maximum number of affine roots and that ℓ separates those roots. To see this, choose coefficient vectors for the polynomials F (i) k so as to obtain a specific system f (i) k with the maximum number of affine solutions, and take a linear form l ∈ Q[x ij ; 1 ≤ i ≤ r, 1 ≤ j ≤ n i ] separating the common affine roots of the polynomials f (i) k . Now, making a linear change of variables in each group X i (1 ≤ i ≤ r), the linear form l maps to ℓ and the specific system considered leads to a polynomial system of the same structure in the new variables, which is the particular system we were looking for.
Hence, the algorithm proceeds to specialize in the polynomials R, R 0 and R ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i ) to obtain new polynomials giving the geometric resolution of the set of common zeros of the polynomials F are the parameters representing the generic payoffs of a game with the given structure, in order to obtain the geometric resolution of the set of its quasiequilibria it suffices to substitute C such that the set of quasi-equilibria of the generic game in P n 1 × · · · × P nr is represented as follows: ..jr ). The polynomials P , ∂P/∂T and W ij are encoded by straightline programs of length O(D 2 (D + n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))) over Q, which is also the order of complexity of the whole computation. The upper bounds deg T P ≤ δ and deg T W ij < δ follow from the stated upper bounds for the degrees of R and R ij in the variable A

Games with the maximum number of totally mixed Nash equilibria
The existence of games with the maximum possible number of totally mixed Nash equilibria, namely the multihomogeneous Bézout number δ of the associated polynomial equation system, was proved in [18]. However, no characterization of those games has been provided. In this subsection, we will obtain a finite family of polynomial conditions (inequalities over the reals) ensuring that a given game satisfying those conditions has δ totally mixed Nash equilibria. We keep our previous assumptions and notation. Let be polynomials, as in Theorem 1, which give a geometric resolution of the set of quasi-equilibria (see (8)) of a game with r players with n 1 + 1, . . . , n r + 1 strategies and generic payoffs (C Consider a specific choice of payoff values c := (c (i) j 1 ...jr ) 1≤i≤r, 0≤jt≤nt over R and assume that the polynomials P (c)(T ) and W ij (c)(T ) obtained from P (T ) and W ij (T ) by specializing the parameters at c provide a geometric resolution of the set of quasi-equilibria of the game with the given payoffs. Then, the arguments in the last paragraph of subsection 2.3 imply that the totally mixed Nash equilibria of the game are those points (ξ 1 , . . . , ξ r ) ∈ R n 1 +1 × · · · × R nr+1 of the form where P ′ := ∂P/∂T and S i := P ′ + 1≤j≤n i W ij , having all their coordinates real and positive; that is, with t belonging to Equivalently, t must belong to the intersection Thus, our polynomial conditions on the payoff vector c which imply that the associated game has δ totally mixed Nash equilibria will state, on the one hand, that the generic geometric resolution can be specialized into c leading to a geometric resolution of the set of quasi-equilibria of the game with the given payoffs and, on the other hand, that the cardinality of the set introduced in (9) equals δ.
Note that each of the sets appearing in the intersection defined in (9) is described by means of one equality and one inequality of univariate polynomials over R. In order to estimate the cardinality of one of these sets, we will apply the following well-known result due to Hermite (see, for example, [ The main result of this section is the following: Theorem 3 Under the previous assumptions and notations, there is a family of nδ + 1 the game with r players with n 1 + 1, . . . , n r + 1 pure strategies and payoff values given by c has δ totally mixed Nash equilibria. The polynomials S 0 and S (h) ij can be obtained algorithmically within complexity O(δ 2 (nδ 2 + L)) from a straight-line program of length L encoding polynomials P, W ij as in Theorem 1. The algorithm computes straight-line programs of length O(δ 2 (δ 2 + L)) which encode these polynomials. (5)) by means of the substitution stated in (6). The system G (i) k = 0 (1 ≤ i ≤ r, 1 ≤ k ≤ n i ) defines the quasi-equilibria of a generic game with r players and n 1 + 1, . . . , n r + 1 pure strategies respectively.
Let P (T ) and Let us observe that, for every real vector c = (c (i) j 1 ...jr ) 1≤i≤r, 0≤jt≤nt with S 0 (c) = 0, the polynomial P (c)(T ) obtained by specializing all the coefficients of P (T ) at c is a non-zero square-free polynomial of degree δ. Furthermore, the solution set of the system G (i) k (c) = 0, 1 ≤ i ≤ r, 1 ≤ k ≤ n i , is a zero-dimensional sub-variety of P n 1 × · · · × P nr with δ distinct points and the polynomials P (c)(T ), W ij (c)(T ) (1 ≤ i ≤ r, 1 ≤ j ≤ n i ) give a geometric resolution of this variety.
Therefore, if the condition S 0 (c) = 0 holds, taking into account that deg T (P (c)(T )) = δ, the arguments at the beginning of this subsection imply that the game with payoff vector c will have δ distinct totally mixed Nash equilibria if and only if every root t of P (c) is real and satisfies (P ′ (c)W ij (c))(t) > 0 for every 1 ≤ i ≤ r, 1 ≤ j ≤ n i (see (9)). This additional condition can be restated as Since deg T P = δ, this last condition is equivalent to Note that for any fixed pair of indices i, j, being S P ′ W ij (c) a bilinear form defined over a vector space of dimension δ, the equality Signature(S P ′ W ij (c) ) = δ holds if and only if all the eigenvalues of the matrix of S P ′ W ij (c) in an arbitrary basis of the space are positive, which is in turn equivalent to the fact that the coefficient sequence of the characteristic polynomial of this matrix, whose roots are all real, has δ sign changes. The conditions stating these sign changes will be the inequalities ensuring that the game has the maximum number of totally mixed Nash equilibria. Now, we will obtain the polynomials S (h) ij giving the inequalities in the statement of the theorem by considering the bilinear forms S P ′ W ij for generic payoffs and performing all our computations over the parameter field K = Q(C (i) j 1 ...jr ), that is, we will consider the bilinear form S P ′ W ij : Actually, to deal with polynomials instead of rational functions of the parameters, we will not compute the matrices M (ij) of the bilinear forms S P ′ W ij but (scalar) multiples of them with polynomial entries. In what follows, we will first show how to obtain these matrices. Then, we will compute the coefficients of their characteristic polynomials, and we will estimate their degrees and the overall complexity for their computation.
Before proceeding, we are going to make some remarks about the denominator-free computation of traces of multiplication maps in K In order not to deal with denominators in our computations in the case when H ∈ Q[C (i) j 1 ...jr ][T ], we will consider the multiplication map M p δ T , whose matrix in the basis B is ) and, therefore, we can obtain a multiple of Trace(M H ) working over the polynomial ring Q[C (i) j 1 ...jr ] due to the following identity which holds for every K ≥ d: Taking into account the previous remark, we are able to obtain a multiple of the matrix M (ij) by a sufficiently big power of the leading coefficient p δ with all its entries in Q[C (i) j 1 ...jr ] by working over this polynomial ring: for every 1 ≤ α, β ≤ δ, we have that and then, as deg T (P ′ ) < δ and deg T (W ij ) < δ, the upper bound deg(T α−1 P ′ W ij T β−1 ) ≤ 4δ − 4 holds. We conclude that the matrix p 4δ−4 δ M (ij) has all its entries in the polynomial Moreover, as we are multiplying the matrix M (ij) by an even power of p δ , for every payoff vector c with S 0 (c) = 0, the identity holds (note that S 0 (c) = 0 implies p δ (c) = 0). Therefore, our algorithm will compute the matrices p 4δ−4 δ M (ij) and then, their char- for every 1 ≤ i ≤ r, 1 ≤ j ≤ n i . Our previous arguments imply that for a payoff vector c with S 0 (c) = 0, condition (10) is equivalent to Now we detail the successive steps of the algorithm, we estimate its complexity and the length of a straight-line program encoding the output polynomials S (h) ij , and we give an upper bound for the degrees of these polynomials.
The entries of the matrices p 4δ−4 δ M (ij) are obtained according to identities (12) and (11).
First, from a straight-line program of length L encoding the polynomials P and W ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i ), we obtain a straight-line program of length O(δ 2 L) for the coefficients of P in the variable T and a straight-line program of length O(δ 2 (L + n)) for the coefficients of all the polynomials P ′ W ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i ) in the variable T within complexity O(δ 2 (L + n)) (see [5,Lema 21.25]).
Then, using the coefficients of P , the matrix M ∈ Q[C . Finally, we apply the division-free algorithm described in [2] in order to compute the coefficients of the characteristic polynomial X ij of each of these matrices. For every 1 ≤ i ≤ r, 1 ≤ j ≤ n i , the algorithm produces straight-line programs of length O(δ 2 (δ 2 +L+n)) encoding these coefficients within complexity O(δ 4 ).
The overall complexity of the algorithm is O(δ 2 (nδ 2 + L)). Note that, with the same notation as in the previous theorem, for a generic game with the given structure (namely, any game whose payoff vector c satisfies S 0 (c) = 0) the conditions S

The set of totally mixed Nash equilibria of an arbitrary game
When dealing with a particular game with specific payoff values, the geometric resolution of the set of quasi-equilibria of a generic game with the same structure might not be useful in order to describe the quasi-equilibria of the given game. For instance, the minimal polynomial P (T ) or its derivative ∂P ∂T (T ) computed by the algorithm shown in Theorem 1 could vanish identically when specialized at the considered payoff values. This section is aimed at adapting the procedures previously developed in order to handle these particular situations.
First, we show an algorithm computing a geometric resolution of the set of affine quasiequilibria of the game provided that it has a zero-dimensional set of quasi-equilibria. In a second step, this algorithm is extended to find all isolated affine quasi-equilibria of an arbitrary game.
Once a finite set of affine quasi-equilibria of a game including the isolated ones is computed, we apply standard algorithms of semialgebraic geometry to estimate the number of isolated totally mixed Nash equilibria of the game.

Games with a zero-dimensional set of quasi-equilibria
As in the previous sections, we consider an r-person non-cooperative game in normal form in which the players have n 1 + 1, . . . , n r + 1 distinct available pure strategies each. Let c (i) := (c Thus, if a := (a (ik) ) 1≤i≤r, 1≤k≤n i , the set of quasi-equilibria of the game is the algebraic variety V a := {ξ := (ξ 1 , . . . , ξ r ) ∈ P n 1 × · · · × P nr / F In this section we consider the case when V a is zero-dimensional. In order to decide whether this is the case for given payoff values, we study the non vanishing of an adequate multihomogeneous resultant. More precisely, we consider a generic polynomial of multidegree d 0 := (1, . . . , 1) in the groups of variables X 1 , . . . , X r , Proof. If V a is empty, the result is straightforward. If V a is zero-dimensional, there exists a multilinear polynomial f 0 ∈ Q[X 1 , . . . , X r ] which does not vanish at any of the (finitely many) points of V a and therefore, R a does not vanish at the coefficients of f 0 .
On the other hand, if the projective variety V a has positive dimension, any multilinear polynomial f 0 has zeros in V a . Therefore, R a is identically zero. Now we will show how to decide whether R a is identically zero algorithmically and we will estimate the complexity of this procedure.
First, we compute the multihomogeneous resultant R by means of the algorithm described in [13] adapted according to Subsection 5.1 below. Thus, a straight-line program of length L := O(D 2 (D + n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))) encoding R is obtained within complexity of the same order as L. The specialization A (ik) := a (ik) which leads us to the polynomial R a does not modify this complexity order.
Since R a is a multivariate polynomial in 1≤i≤r (n i +1) variables encoded by a straightline program, we do not know its coefficients; moreover, the complexity to compute them is exponential. Therefore, in order to decide whether it is the zero polynomial or not, we will make a suitable specialization so that solving this problem amounts to solving the same problem in the univariate setting.
More precisely, we specialize the variable coefficients A (0) j 1 ...jr into successive powers of a new variable t, that is, ..jr = t j 1 +(n 1 +1)j 2 +(n 1 +1)(n 2 +1)j 3 +···+( Making this specialization in F 0 , we obtain a new polynomial f 0 ∈ Q[t][X 1 , . . . , X r ]. Let us show that if V a consists of finitely many points, there is a polynomial f 0 (t 0 ) with coefficients of this type (namely, successive powers of the same scalar t 0 ) which does not vanish at any point of V a . For every ξ := (ξ 1 , . . . , ξ r ) ∈ P n 1 × · · · × P nr , we have which is a non-zero polynomial, due to the fact that there exists at least one choice of j 1 , . . . , j r for which the product ξ 1j 1 . . . ξ rjr is not 0. Now, if V a is a finite set, we may consider the polynomial ∆(t) := ξ∈Va f 0 (ξ)(t). Note that ∆ ∈ C[t] is a non-zero polynomial and, therefore, there exists t 0 ∈ Q with ∆(t 0 ) = 0. Due to the definition of ∆, the polynomial f 0 (t 0 ) ∈ Q[X 1 , . . . , X r ] does not vanish at any point of V a . This implies that the resultant of f 0 (t 0 ), F is not zero, that is, the polynomial R a,t ∈ Q[t] obtained by specializing R a following (13) does not vanish at t 0 . We conclude that R a,t is not the zero polynomial.
Therefore, in order to decide whether R a ∈ Q[A (0) j 1 ...jr ] is zero or not, it suffices to decide whether the associated polynomial R a,t ∈ Q[t] is zero or not. Taking into account that deg(R a,t ) ≤ ( 1≤i≤r (n i + 1) − 1)δ, it follows that this task can be achieved by evaluating R a,t at ( 1≤i≤r (n i + 1))δ distinct values of t, which is done by substituting the powers of these values for the variables A (0) j 1 ...jr according to (13) in the straight-line program for R a . The overall complexity of this procedure is ( 1≤i≤r (n i + 1)) + L ( 1≤i≤r (n i + 1))δ = O(D 2 (n 1 . . . n r ) 2 δ(D + n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))).
Assume now that the set of quasi-equilibria of the given game is finite, that is, the polynomial R a is not identically zero.
Proposition 5 Following the previous assumptions and notation, there is an algorithm which computes a geometric resolution of the set of affine quasi-equilibria of a game with r players having n 1 + 1, . . . , n r + 1 pure strategies respectively within complexity O(δ 8 D 2 (D + n 1 . . . n r δ log(D)r 2 n 5 (n 3 + rN ))) provided that the associated set of quasi-equilibria V a is zero-dimensional.
Proof. We will obtain the desired geometric resolution from the specialized resultant R a . In order to do this, we first show that this specialized resultant factorizes as follows: . For a given coefficient vector a (0) , we have that F a (a (0) ) = 0 if and only if there is a point ξ ∈ V a such that F 0 (a (0) , ξ) = 0; that is, if and only if F 0 (a (0) ), F 1 (a (11) ), . . . , F (r) nr (a (rnr) ) have a common root in P n 1 × · · · × P nr . But this last condition is equivalent to the fact that the resultant Res(F 0 , F 1 , . . . , F (r) nr ) vanishes at a (0) , a (11) , . . . , a (rnr) or, equivalently, that R a (a (0) ) = 0. We conclude that the polynomials F a and R a have the same zero set and so, they have the same irreducible factors, which proves our assertion.
We are interested in describing the set of affine quasi-equilibria of the game, that is, the variety V aff a := {ξ ∈ V a : ξ i0 = 0 ∀ 1 ≤ i ≤ r}. For this reason, we are going to compute the polynomial R aff a := ξ∈V aff where R aff a = ξ∈V aff a F 0 (ξ) m ξ is monic in the variable A After specializing R aff a as follows: 0...0 ) da of R a and we obtain R aff a by dividing R a by this coefficient. As the divisor does not vanish when its variables are specialized in the successive powers of t 0 , this polynomial division can be done within complexity O(δ 4 L), and produces an slp of the same order ( [28]).
Computation of the polynomial P a : We obtain P a as the quotient P a /gcd( P a , ∂ e Pa ∂A The specialization in (15) gives an slp for P a without modifying the previous length.
To obtain the square-free part of P a , we apply a well-known subresultant-based procedure for the computation of the gcd of two polynomials (see, for instance, [4]). We proceed as before by specializing all the variables in P a , except for the main variable A (0) 0 into the successive powers of a new variable t and deal with the polynomial we obtain in ]. We will use the following notation: ij ], F (t) will denote the polynomial obtained from F by doing the previously mentioned specialization.
Let G = gcd( P a , ∂ e Pa ∂A (0) 0 ). As, for ξ 1 = ξ 2 we have that f Then, we can obtaind a := deg(gcd( P a , ∂ e Pa ∂A (0) 0 )) using the polynomials P Finally, the polynomial P a is obtained by dividing sr a P a by G. Note that we already know a point τ where sr a does not vanish (τ is the value obtained in the previous step when computingd a ). Then, if we consider the nonzero polynomial of degreed a , by evaluating it in at mostd a + 1 elements in Q, we obtain a (0) 0 ∈ Q such that G (t) (a (0) 0 , τ ) = 0. This enables us to compute the quotient P a by applying the classical division avoiding algorithm in [28]. The complexity of this step is of order O(δ 8 L).
Observe that the linear form ℓ whose coefficients are (−τ k ) 0≤k≤n−1 is a separating linear form for V aff a . To compute the required geometric resolution associated with ℓ from the polynomial P a we proceed as in the proof of Theorem 1: we specialize P a and its partial derivatives at the coefficients of ℓ.
The overall complexity of the algorithm is O(δ 8 Ln+δ 4 n 2 ) = O(δ 8 D 2 (D+n 1 . . . n r δ log(D)r 2 n 5 (n 3 + rN ))). Now, we are able to compute the number of totally mixed Nash equilibria of a game with zero-dimensional set of quasi-equilibria from the geometric resolution given by Proposition 5.
Let p and w ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i ) be the polynomials giving the geometric resolution of V aff a . Then, the totally mixed Nash equilibria of the game are the points (ξ 1 , . . . , ξ r ) with ξ i = (p ′ (t)/s i (t), w i1 (t)/s i (t), . . . , w ir (t)/s i (t)), where s i = p ′ + n i j=1 w ij for i = 1, . . . , r, and t is a root of p, having all their coordinates real and positive.
Then, the number of totally mixed Nash equilibria of the game equals the cardinality of the union of the sets Once we have the polynomials p, p ′ and w ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i }) encoded in dense form, by using the algorithm in [6,Section 3.3], it is possible to compute this cardinality within complexity O(nδ 3 ).
Therefore we have: Proposition 6 Following the previous assumptions and notation, there is an algorithm which computes the number of totally mixed Nash equilibria of a game with r players having n 1 +1, . . . , n r +1 pure strategies respectively within complexity O(δ 8 D 2 (D+n 1 . . . n r δ log(D)r 2 n 5 (n 3 + rN ))) provided that the associated set of quasi-equilibria of the game is zero-dimensional.

Computing the isolated affine quasi-equilibria of an arbitrary game
When we are dealing with an arbitrary game, it may happen that the set V a of its quasiequilibria has positive dimension and, therefore, the polynomial R a introduced in the previous subsection is identically zero. In this case, we are going to use a procedure applied in [10] to obtain a non-zero multiple of the minimal polynomial of a generic linear form over the isolated points of the set V aff a of affine quasi-equilibria. For the sake of completeness, we are going to explain this procedure briefly.
We consider a sufficiently generic coefficient vector b := (b (ik) ) 1≤i≤r,1≤k≤n i such that R b ≡ 0 (we remark that the vector b can be chosen at random or effectively constructed as the coefficient vector a system with δ many common roots). Then, if τ is a new variable, the polynomial R a+τ (b−a) is non-zero. If f be the polynomial obtained from R a+τ (b−a) by specializing it as in (15) and let L : We are going to show that this polynomial P is a multiple of the minimal polynomial of L over the set of isolated points of V aff a . Since the polynomial R is a linear combination of F 0 , F Now, taking into account that the number of variables τ, x ij (1 ≤ i ≤ r, 1 ≤ j ≤ n i ) is greater than the number of generators of the ideal ( f (i) k : 1 ≤ i ≤ r, 1 ≤ k ≤ n i ), we deduce that each irreducible component of the variety V τ defined by this ideal in A n+1 has dimension at least 1. Then, for each isolated point ξ of V aff a , the point (0, ξ) ∈ A n+1 lies in an irreducible component C of V τ such that τ / ∈ I(C). Therefore P | A (0) 0 =−L ∈ I(C) and P | T =L vanishes at ξ. Now, we are going to show how to compute the polynomial P .
The procedure for the computation of P from a straight-line program encoding R runs as follows: (1) Obtain an slp for P a+τ (b−a) .
Now, we are going to estimate the complexity of this procedure. Let L be the length of a straight-line program encoding R.
In step (1), we compute first a + τ (b − a) with 3N operations and then, we specialize the slp for R according to (15). We obtain an slp of length 3N + L for P a+τ (b−a) . The interpolation in step (2) takes O(δ 2 (N + L)) operations. The complexity of step (3.a) is of order O(D 2 δ 2 (N +L)). In order to determine whether each of the multivariate polynomials ij ] encoded by an slp is zero or not, we apply the probabilistic Zippel-Schwartz zero test (see [34]). The overall complexity of step (3) is O(D 2 δ 3 (N + L)).
Step (4) does not modify the order of the complexity.
From the polynomial P we have computed we can obtain a geometric resolution for a finite set of points including the isolated points of V aff a in the same way we showed in the proof of Theorem 1, obtaining a description for the isolated affine quasi-equilibria of the game. Therefore, we have: Theorem 7 Let notations be as in Theorem 1. There is a probabilistic algorithm which computes, given a game with r players having n 1 +1, . . . , n r +1 pure strategies respectively, a geometric resolution of a finite set of points including the isolated affine quasi-equilibria of the game within complexity O(D 4 δ 3 (D + n 1 . . . n r δ log(D)r 2 n 4 (n 3 + rN ))).
Proceeding as in the previous section, from the geometric resolution given by this theorem, we are able to obtain an upper bound on the number of isolated (in the complex space) totally mixed Nash equilibria of the game within the same order of complexity as in the previous theorem.

Computing resultants
In this subsection we are going to show how the algorithm in [13] can be adapted in order to compute the multihomogeneous resultants we use. That procedure computes multihomogeneous resultants under the assumption that the coordinates of each multidegree are all positive and this is not the case in our situation.
First, we will prove that the multihomogeneous resultant we want to compute is a non-constant polynomial and then, we will show how to modify the Poisson formula on which the algorithm in [13] relies All the computations required once the Poisson formula is recursively applied run in the same way as in [13].
In order to do this, we are going to use the theory in [30] and [20]. We can apply these results to our situation because the multihomogeneous resultant of a family of multihomogeneous polynomials G 0 , . . . , G n in r groups of variables X j = (x j0 , . . . , x jn j ), with r j=1 n j = n, coincides with the sparse resultant of the dehomogenized polynomials g 0 , . . . , g n obtained by setting x j0 = 1 for every 1 ≤ j ≤ r.
Let A 0 , . . . , A n ⊂ Z n be finite sets and let g 0 , . . . , g n be polynomials with supports A 0 , . . . , A n respectively.
For any subset J ⊆ {0, . . . , n}, let L J be the lattice generated by j∈J A j . Following [30], if I ⊂ {0, . . . , n}, the collection of supports {A i } i∈I is said to be essential if rank(L I ) = #I − 1 and rank(L J ) ≥ #J for each proper subset J of I.
If there is a unique subcollection {A i } i∈I which is essential, the resultant Res(g 0 , . . . , g n ) coincides with the resultant Res(g i ; i ∈ I).
In our particular case, we will deal with families of multihomogeneous polynomials in r groups of m 1 + 1, . . . , m r + 1 variables respectively and multidegrees (1, . . . First, note that rank(L I ) = m = #I − 1. Let J be a proper subset of I. If there exist (i, k), (i ′ , k ′ ) in J with i = i ′ , then rank(L J ) = m ≥ #J and the same holds if (0, 0) ∈ J. On the other hand, if J ⊂ {(i, k) : 1 ≤ k ≤ m i } for a fixed i = 0, then rank(L J ) = j =i m j ≥ m i ≥ #J. Therefore, the set of all supports is the unique essential subset. So, the resultant is not constant and the following identity holds: 0 is the dehomogeneized polynomial obtained from G  If, for every 2 ≤ i ≤ r, m i < 1≤j≤r, j =i m j , since m 1 = 1 we deduce that m i ≤ 2≤j≤r, j =i m j and so, the polynomial system obtained is of the form (I) but with one group of variables less than the original one.
On the other hand, if m i = 1 + 2≤j≤r, j =i m j for some 2 ≤ i ≤ r, we have that m j < m i for every j = i. Therefore, the unique essential subset is {(i, k) : 1 ≤ k ≤ m i } and the resultant to be computed is the resultant of the corresponding family of m i polynomials of multidegree (1, . . . , 1) in r − 2 groups of m 2 + 1, . . . , m i−1 + 1, m i+1 + 1, . . . , m r + 1 variables each, which is the situation in (II).
If the polynomials involved satisfy the conditions in (II), all the coordinates of their multidegrees are not zero and so, we can apply the algorithm in [13] for the computation of their resultant.
To analyze (III), let us consider first the case when r = 2. Here, the assumption on the numbers m i implies that m 1 = m 2 := M . Assume now that r > 2. Note that the equality m i = j =i m j may be valid for at most one value i. If, on the contrary, m i 1 = j =i 1 m j and m i 2 = j =i 2 m j hold for i 1 = i 2 , it follows that j =i 1 ,i 2 m j = 0, which implies r = 2. Let G (III.c) If m 1 ≥ 2 and m i = j =i m j for some 2 ≤ i ≤ r, the set {(i, k) : 1 ≤ k ≤ m i } is essential. The assumption r > 2 implies that it is the unique essential subset. Then, the resultant we compute is that of m i multilinear polynomials of multidegrees (1, . . . , 1) in r − 1 groups of m 1 , m 2 + 1, . . . , m i−1 + 1, m i+1 + 1 . . . , m r + 1 variables respectively. Thus, we are in situation (II).
(III.d) If m 1 ≥ 2 and m i < j =i m j for every 2 ≤ i ≤ r, we deduce that m i ≤ m 1 − 1 + j =1,i m j for every 2 ≤ i ≤ r. Therefore, the unique essential subset is the whole family of polynomials and applying Poisson's formula we obtain: Res((G     . . , m ′ l−1 + 1, m ′ l , m ′ l+1 + 1, . . . , m ′ r + 1 variables each with m ′ i polynomials of multidegree d i for every 1 ≤ i ≤ r. We have m ′ 1 ≤ j =1 m ′ j and, for i = 1, the condition m i < j =i m j implies that m ′ i ≤ j =i m ′ j ; therefore, renaming variables and polynomials, we are again under the assumptions of (III).

A bound for the degree of the resultant
This section is devoted to proving an upper bound for the degree D of the resultant of multi-linear polynomials appearing in our previous computations in terms of the total number n of strategies available to the players and the number δ of totally mixed Nash equilibria of a generic game with the given structure.
As before, we assume n = n 1 + · · · + n r with n i ∈ N for every 1 ≤ i ≤ r. We consider the resultant R of a family of n + 1 multi-linear polynomials in r groups of n 1 + 1, . . . , n r + 1 variables each, consisting of a polynomial F 0 of multi-degree d 0 := (1, . . . , 1) and, for every 1 ≤ i ≤ r, a set of n i polynomials F Throughout this section, we will denote δ i := Bez n 1 ,...,nr (d 0 , 1; d 1 , n 1 ; . . . ; d i , n i − 1; . . . ; d r , n r ), i = 1, . . . , r, the number of solutions to a generic polynomial system of the indicated multi-degrees.
Recall that δ = Bez n 1 ,...,nr (d 1 , n 1 ; . . . ; d r , n r ). The resultant R is a multihomogeneous polynomial in the coefficients of F 0 , F (i) k of degree δ in the coefficients of F 0 and δ i in the coefficients of F (i) k for every 1 ≤ i ≤ r, 1 ≤ k ≤ n i (see, for instance, [25]). Therefore, the total degree of R equals The following result provides an upper bound for δ i which will allow us to deduce an upper bound for D.
In order to finish the proof, we will show that #J 1 ≤ n 1 δ. Since δ equals the cardinality of the set J 0 introduced in (4), we will compare the cardinalities of both sets J 1 and J 0 . To this end, we define the following map from J 1 to J 0 : with a given n-tuple j := (1, j 12 , . . . , j 1n 1 , . . . , j r1 , . . . , j rnr ) ∈ J 1 we associate the n-tuple j ′ ∈ J 0 which is obtained by exchanging the first coordinate of j (which equals 1) with the first one which is different from 1 and is located beyond the n 1 th coordinate. Note that a necessary condition for two distinct n-tuples in J 1 to lead to the same n-tuple in J 0 by means of this assignment is that they coincide in all of their coordinates except for two of them located among the n 1 coordinates n 1 + 1, . . . , 2n 1 . Moreover, the vector consisting of these n 1 coordinates must be of the form (1, . . . , 1, j hk , . . . ) for both of them (possibly with no 1 at the beginning) and so, they can only differ in the length of the string of 1's in this vector, which ranges between 0 and n 1 − 1. We conclude that each element of J 0 is the image of at most n 1 elements of(1) J 1 . It follows that #J 1 ≤ n 1 #J 0 . Therefore, we have that δ 1 ≤ δ + n 1 δ = (n 1 + 1)δ.
Using the previous result along with identity (16) for the degree D of the resultant, we conclude: Corollary 9 With the previous assumptions and notations, D ≤ 1 + 1≤i≤r n i (n i + 1) δ ≤ n 2 δ.

Remark 10
The bound stated in Corollary 9 shows that all the algorithms presented in this paper are polynomial in the number of strategies n 1 , . . . , n r of the r players, and the generic number δ of totally mixed Nash equilibria of a game with the considered structure.