Guillaume Vigeral
email: vigeral@ceremade.dauphine.fr

Yannick Viossat
email: viossat@ceremade.dauphine.fr

SEMI-ALGEBRAIC SETS AND EQUILIBRIA OF BINARY GAMES

Keywords: semi-algebraic sets, Nash equilibria, equilibrium payoffs, binary games

Any nonempty, compact, semi-algebraic set in [0, 1] n is the projection of the set of mixed equilibria of a finite game with 2 actions per player on its first n coordinates. A similar result follows for sets of equilibrium payoffs. The proofs are constructive and elementary.

Introduction

In bimatrix games, the structure of the set of Nash equilibria is relatively well understood: this is a finite union of convex polytopes (Jansen, 1981 [7]). Moreover, the possible sets of Nash equilibrium payoffs have been characterized by [START_REF] Lehrer | Equilibrium payoffs of finite games[END_REF] [START_REF] Lehrer | Equilibrium payoffs of finite games[END_REF]: a subset E of R 2 is the set of Nash equilibrium payoffs of a bimatrix game if and only if this is a finite union of rectangles with edges parallel to the axes; that is, of the form:

E = ∪ 1≤i≤m [a i , b i ] × [c i , d i ]
, where m ∈ N and a i , b i , c i , d i ∈ R, with a i ≤ b i , c i ≤ d i .

For finite games with 3-players or more, the picture is much less clear. It is easily seen that the set of Nash equilibria or of Nash equilibrium payoffs is nonempty, compact and semi-algebraic; however, which semi-algebraic sets really arise as sets of Nash equilibria or of Nash equilibrium payoffs is not known. A few results have been obtained. For instance, [START_REF] Datta | Universality of Nash equilibria[END_REF] [START_REF] Datta | Universality of Nash equilibria[END_REF] showed that any real algebraic variety is isomorphic to the set of completely mixed Nash equilibria of a 3-player game, and also to the set of completely mixed equilibria of an N -player game in which each player has two strategies. More recently, Balkenborg and Vermeulen (2014, Theorem 6.1) [START_REF] Balkenborg | Universality of Nash components[END_REF] showed that any nonempty connected compact semialgebraic set is homeomorphic to a connected component of the set of Nash equilibria of a finite game in which each player has only two strategies, all players have the same payoffs, and pure strategy payoffs are either 0 or 1. These results show that, modulo isomorphisms or homeomorphisms, and a focus on completely mixed equilibria or connected components of equilibria, all algebraic or nonempty compact semi-algebraic sets may be encoded as sets of Nash equilibria. We provide another result in this direction.

Since the set of Nash equilibria of an N -player finite game is a nonempty compact semi-algebraic subset of some R k , it follows from Tarski-Seidenberg's theorem that the projection of such a set on a subspace R n , n < k, satisfies the same properties. We prove a kind of converse of this fact: for any nonempty compact semi-algebraic set E, there exists a finite game with N > n players, each having only two pure strategies, such that E is precisely the projection of the set of Nash equilibria of this game on its first n coordinates (those of the first n players). In this statement, we see a mixed strategy of an N -player game with two strategies per player as a vector (x 1 , ..., x N ) in [0, 1] N ; that is, we identify the strategy of the i th player with the probability x i that it assigns to the first of its two strategies.

The above result implies a similar result on equilibrium payoffs, as opposed to equilibria: for any nonempty compact semi-algebraic set E in R n , there exists a finite game with N > n players, each having only two pure strategies, such that E is precisely the set of Nash equilibrium payoffs of the first n players; that is, the projection of the set of Nash equilibrium payoffs on its first n coordinates (as will become clear, the "first n players" in our result on equilibrium payoffs have payoffs given by affine transformations of the strategies of the "first n players" in our result on equilibria). As discussed further in the next section, the result on equilibria has been obtained independently by Yehuda John Levy [START_REF] Levy | Projections and functions of Nash equilibria[END_REF], who also obtained more general results on semi-algebraic functions and correspondences, but our techniques and precise results are different.

Some differences with [START_REF] Datta | Universality of Nash equilibria[END_REF] [START_REF] Datta | Universality of Nash equilibria[END_REF] and Balkenborg and Vermeulen (2014) [START_REF] Balkenborg | Universality of Nash components[END_REF] should be stressed. First, in our result, there is no isomorphism or homeomorphism involved, but a projection on the first n players. Second, our results do not concern the set of completely mixed Nash equilibria, or a connected component of equilibria, but the whole set of equilibria. These are not related to algebraic varieties or to connected semi-algebraic sets, but to (nonempty compact) semi-algebraic sets, which need not be connected. Also note that there is a fundamental difference between the set of completely mixed Nash equilibria and the set of Nash equilibria: the first may be empty while the second cannot. This represents a conceptual difficulty: any construction needs to check at some point the nonemptiness of the input set. Third, our proofs are fully elementary. To be more precise, given a set and certificates of semialgebraicity, closedness and nonemptiness, our construction does not use any results from real algebraic geometry. Starting with a game with n players with two strategies each and choosing their first strategies with probabilities x 1 , ..., x n , we show how to add additional players with two strategies such that in equilibrium, these additional players choose their first strategies with probabilities that are powers of the x i , and how yet additional players then allow to build and combine any polynomial in x 1 ,..., x n in order to obtain that the set of equilibrium strategies of the initial n players is a given (nonempty compact) semi-algebraic set in [0, 1] n . A small modification of the game then allows to obtain a given (nonempty compact) semi-algebraic set in R n as the set of Nash equilibrium payoffs of n players of this game. Note that, by contrast with the work of Yehuda John Levy, we provide a bound on the number of additional players in our construction, which is not far from being tight. Once again, this bound is obtained only by elementary arguments. Finally, when the semi-algebraic set is defined by polynomials with integer coefficients, we prove a more precise result ensuring that the constructed game has integer pure payoffs, at the cost of additional players. Once again the construction (given certificates) is elementary, but the bound on the number of players and on the size of the integer payoffs depends on precise results of algebraic geometry.

Note that if additional players are not restricted to have only two actions, Yehuda John Levy proved that only three such additional players are needed [START_REF] Levy | Projections and functions of Nash equilibria[END_REF].

The remainder of this note is organized as follows: we introduce some definitions and prove our main results in Section 2. Section 3 compares our work to that of Yehuda John Levy. Extensions are discussed in Section 4. Section 5 concludes.

Definition and main results

A subset of R n is semi-algebraic if it may be obtained by finitely many unions and intersections of sets defined by a polynomial equality or strict inequality. By the finiteness theorem (see for example Proposition 5.1 in [START_REF] Bochnak | Real algebraic geometry and the 17th Hilbert problem[END_REF]), a closed semi-algebraic subset of R n may also be described by finitely many unions and intersections of sets defined by a polynomial weak inequality. In particular, a compact subset E of R n is semi-algebraic if and only if there exist positive integers A and B and polynomials in n variables P ab , 1 ≤ a ≤ A, 1 ≤ b ≤ B such that:

(1)

E = A a=1 B b=1 {x ∈ R n , P ab (x) ≤ 0}
Let us say that a game is binary if each player has only two pure strategies. Note that our notion of binary games is weaker than the notion used by Balkenborg and Vermeulen (2014) [START_REF] Balkenborg | Universality of Nash components[END_REF]: they define a game to be binary if each player has two pure strategies, and if in addition, this is a common interest game (all players have the same payoff), with pure strategy payoffs always equal to 0 or 1. Our first result is on equilibria. As before, we identify in its statement the mixed strategy of the i th player with the probability x i that it assigns to the first of her two pure actions. Proposition 1. If E is a nonempty compact semi-algebraic subset of [0, 1] n , then there exists an N -player binary game (with N > n) such that the projection of its set of Nash equilibria on its first n coordinates (those of the first n players) is equal to E.

Our second result, a byproduct of our proof of Proposition 1, is on equilibrium payoffs. Proposition 2. If E is a nonempty compact semi-algebraic subset of R n , then there exists an N -player binary game (with N > n) such that the projection of its set of Nash equilibrium payoffs on its first n coordinates is equal to E.

Essentially the same results have been independently obtained by Yehuda John Levy [START_REF] Levy | Projections and functions of Nash equilibria[END_REF], but our techniques are different. Moreover, while the results of Yehuda John Levy are stronger in that Proposition 1 appears as a corollary of a more general result on semi-algebraic functions and correspondences, our proof is more elementary and we obtain a bound on the number of players needed: if E is described by (1), then both in Propositions 1 and 2,

N ≤ 1 + AB + n(3 + 2 ln 2 (d))
where d is such that each P ab is of degree at most d in each variable.

The proof is constructive. It relies on appropriate gadget games, in the sense of algorithmic game theory. Before introducing these gadgets, we need to clarify our notation. We only consider binary games and we denote the two pure strategies of each player by Top and Bottom. It will be convenient to use the same piece of notation for the name of a player and its probability to play Top except that, to be able to distinguish between players and strategies, we use uppercase letters for players. Thus, the n basic players of the game bear the admittedly unusual names of players X 1 , X 2 ,..., X n , and x i is the probability that player X i plays Top. The players we need to add are called players X ik , Y ik , S ab or U . Player X ik will be such that, in equilibrium, its probability x ik of playing Top is equal to (x i ) 2 k . Since any positive integer is a sum of powers of 2, products of x ik allow to obtain any power (x i ) q as the value in equilibrium of a multiaffine function of the probabilities used by the players of the game (where by multiaffine, we mean affine in each variable). Adding and multiplying such quantities allow to obtain the quantities P ab (x), where x = (x 1 , ..., x n ), as the value in equilibrium of the probability that an additional player S ab plays Top. An additional gadget game then forces an additional player U to play Top when

(x 1 , • • • , x n ) / ∈ E.
Finally, the payoffs of the original players X 1 , ..., X n are defined in such a way that, at any equilibrium in which U plays Top, (x 1 , ..., x n ) = (z 1 , ..., z n ) where z = (z 1 , ..., z n ) is a fixed arbitrary element of the nonempty set E. Hence, at any equilibrium, if x / ∈ E then x = z ∈ E a contradiction. The converse, that is the fact that each x ∈ E appears in an equilibrium, is an easy byproduct of the construction.

We define our binary games by giving the payoff of each player when she chooses Top or Bottom, as a function of the mixed strategy profiles of her opponents (more precisely, of their probabilities to play Top). These expressions will always be multiaffine in the probabilities of playing Top of the opponents (that is affine with respect to the probability to play Top of each opponent), ensuring that they correspond to payoffs in the mixed extension of a binary game. For instance, our first gadget game will have (at least) two players, say X α and X β , playing Top with probability x α and x β respectively, and with payoffs if they play Top or Bottom described by the following tables:

(2) Player X α T x B x β Player X β T x α B x
where x is a real number in [0, 1]. This means that the payoffs of players X α and X β are respectively

x α x + (1 -x α )x β and x β x α + (1 -x β )x.
Letting Player X α be the row player and Player X β the column player, the corresponding payoff matrix would be

T B T B
x, 1 x, x 1, 0 0, x independently of any other player's action.

Lemma 3. Let x ∈ [0, 1].
In any game with 2 players whose payoffs are given by (2), and an arbitrary number of other players with unspecified payoffs, we have: in any equilibrium, x α = x.

Proof. Assume x α > x. Then Player X β plays Top, hence x β = 1. So x β > x, thus Player X α plays Bottom and x α = 0. Since x ∈ [0, 1], this contradicts x α > x. Similarly if x α < x, then x β = 0 hence x α = 1, a contradiction. Lemma 4. Let i ∈ {1, ..., n}. Consider a game with n basic players X 1 ,...,X n , and (at least) 2q additional players X ik , Y ik , 0 ≤ k ≤ q -1, whose payoffs are given by the following tables (where, as in all subsequent payoff tables, T and B correspond to the actions of the player whose payoff is given in the table).

(3)

Player X ik T x i k-1 j=0 x ij B y ik Player Y ik T x ik B x i k-1 j=0 x ij
In any equilibrium, for any k in {0, ..., q -1},

x ik = (x i ) 2 k .
Proof. The proof is by induction on q. The case q = 1 is Lemma 3 applied to players X i0 and Y i0 with x α = x i0 , x β = y i0 , and x = x i . Assume the result is true when adding 2(q -1) players. To show that the result is still true when adding 2q players, it suffices to show that we then have in equilibrium x i(q-1) = (x i ) 2 q-1 . But letting k = q -1, the induction hypothesis and Lemma 3 applied to players X ik and Y ik with x α = x ik , x β = y ik and x = x i k-1 j=0 x ij show that in any equilibrium

x ik = x i k-1 j=0 x ij = x i k-1 j=0 (x i ) 2 j = (x i ) 2 k
as required.

The following basic lemma transforms a polynomial in x 1 ,..., x n into a multiaffine map in the (x i ) 2 k , i = 1 to n, k = 0 to q -1. Due to the previous lemma, this will allow us, for any polynomial P ab , to add a player whose payoff at equilibrium when playing Top is equal to P ab (x 1 , ..., x n ).

Lemma 5. Let P be a polynomial in the variables x 1 , • • • , x n , with degree strictly less than 2 q in each variable. Then there exists a multiaffine map f : R nq → R such that for every

(x 1 , • • • , x n ) ∈ R n P (x 1 , • • • , x n ) = f (x 2 0 1 , ..., x 2 q-1 1 , ..., x 2 0 n , ..., x 2 q-1 n ).
Proof. Recall that any positive integer m may be written as a sum of powers of 2 (this is the binary development of m). Thus if m < 2 q , there exist numbers ε 0 (m),...,

ε q (m) in {0, 1} such that m = q k=0 ε k (m)2 k hence x m i = q-1 k=0 (x 2 k i ) ε k (m) .
Thus if we replace any x m i that appears in the polynomial P by q-1 k=0 (x 2 k i ) ε k , and denote the resulting expression by f (x 2 0 1 , ..., x 2 q-1 1 , ..., x 2 0 n , ..., x q-1 n ), this defines a map f : R nq → R such that

P (x 1 , • • • , x n ) = f (x 2 0 1 , ..., x 2 q-1 1 , ..., x 2 0 n , ..., x q-1 n ) for every (x 1 , • • • , x n ) ∈ R n .
Since every ε k (m) either 0 or 1 the map f is affine in each variable.

Proof of Proposition 1. Let d < 2 q . Start with a game with n basic players X 1 ,..., X n , and, for each i ∈ {1, ..., n}, 2q additional players with payoffs (3). Denote x = (x 10 , ..., x 1(q-1) , ..., x n0 , ..., x n(q-1) ). For any polynomial P ab , define f ab as in Lemma 5. Remark that by Lemmas 4 and 5, at equilibrium

P ab (x 1 , • • • , x n ) = f ab (x)
. Since f ab is multiaffine, we may add a player S ab , playing T with probability s ab , and with payoff

Player S ab T f ab (x) B 0
Add also a player U , playing Top with probability u, and with payoff

Player U T A a=1 B b=1 s ab B 0
Finally, let z = (z 1 , • • • , z n ) be any element of E and give to the initial n players (players X i ) the payoffs

Player X i T (z i -x i0 )u B 0
Thus the game has (1+AB) additional players, plus 2(1 + ln 2 (d)) for each player to construct the X i , hence

N ≤ 1 + AB + n(3 + 2 ln 2 (d)).
More precisely, if d(i) is the maximal degree in x i of the polynomials P ab , then we need at most N = 1 + AB + 3n + 2 i ln 2 (d(i)) players.

Let x = (x 1 , • • • , x n ) be the n first coordinates of an equilibrium and assume x / ∈ E. At equilibrium, f ab (x) = P ab (x). Moreover, since x / ∈ E, for each a, there is a b such that P ab (x) > 0 and thus s ab = 1. Hence A a=1 B b=1 s ab > 0 and u = 1 as well. Since z ∈ E, there must be an i such that x i = z i . Recall that in any equilibrium x i = x i0 . However, x i0 < z i implies (z i -x i0 )u > 0 and x i = 1 ≥ z i , while x i0 > z i implies (z i -x i0 )u < 0 and x i = 0 ≤ z i . We get a contradiction in either case.

Let now x be in E. Consider the following profile : x ik = y ik = (x i ) 2 k for all i and k, u = 0, s ab = 0 if P ab (x) ≤ 0 and 1 otherwise. All players X ik and Y ik are indifferent, and players X i as well since u = 0. Players s ab have no profitable deviations by construction. Finally, since x ∈ E, there exists a such that for every b, s ab = 0, hence Remark 6. Any compact semi-algebraic set E may be written as in [START_REF] Balkenborg | Universality of Nash components[END_REF], but it may be that E is naturally described in some other way, and that putting it in form ( 1) is computationally expensive. Thus, it is interesting to note that if

E = ∩ A a=1 ∪ B b=1 {x ∈ R n , P ab (x) ≤ 0},
T Q(p 1 , • • • , p C ) B 0
shows that there exists an N -player game with 2 actions for each player and

N ≤ 1 + C + n(3 + 2 ln 2 (d))
such that the projection of the set of its equilibria on the first n coordinates is precisely E.

Proof of Proposition 2

Remark that in our construction, at any equilibrium, the payoff of Player Y i0 is x i . Hence if E ∈ [0, 1] n our previous construction works (considering players Y 10 , ..., Y n0 as the first n players of the game). For a general E ∈ [-D, D] n , with D > 0, apply the construction to

E ′ := {x ∈ R n | -D + 2Dx ∈ E} ⊂ [0, 1] n ,
replacing the payoff of Player Y i0 by the strategically equivalent payoff:

T -D + 2Dx i0 B -D + 2Dx i 3.
Comparison to results in [START_REF] Levy | Projections and functions of Nash equilibria[END_REF] We compare here the present paper to [START_REF] Levy | Projections and functions of Nash equilibria[END_REF] which was written independently by Yehuda John Levy. Briefly speaking, Proposition 1 is less general but the proof is constructive and gives an explicit bound on the number of additional players. More precisely, Yehuda John Levy obtain three different kind of results related to Proposition 1, that we give with increasing order of generality. a) Our Proposition 1 is "Theorem 3.1 with binary players" in his paper. His proof is fundamentally different from ours, relying on the triangulation of semi-algebraic sets, and does not provide bounds. b) A slight generalization is to drop the condition that the original players are binary (but still requiring the additional players to be): this is his Theorem 3.1. His proof relies on the previous binary case and an additional Lemma 4.15. He also remarks that the bounds in our Proposition 1, combined with his Lemma 4.15, yield bounds in this more general case.

For the sake of completeness we point out that our explicit construction extends directly to that case, yielding a very slightly better bound that the one obtained in [START_REF] Levy | Projections and functions of Nash equilibria[END_REF]. Consider n finite sets T i of cardinal t i , a nonempty closed semi-algebraic set E in Π n i=1 ∆(T i ), and denote by x i,j the probability that Player X i assigns to its jth pure action τ i j . As in the proof of Proposition 1, add binary players X i,j,k that will play T with probability x 2 k i,j at equilibrium, add players S ab and U according to the definition of E, and choose an arbitrary z in E. The payoff of player X i is now defined as (z i,j -x i,j,0 )u when playing pure action τ i j and all the elements of the proof still hold (note that at any equilibrium in which u = 1, z i,j < x i,j = x i,j,0 would imply x i,j = 0, a contradiction). This gives a bound of 1 + AB + n + 2(1 + ln 2 (d)) i t i for the number of players. Actually, using j x i,j = 1, one can replace t i by t i -1 in this formula, recovering the bound N ≤ 1 + AB + n(3 + 2 ln 2 (d)) when t i = 2 for all i. c) Levy's Theorems 3.2 and 3.3 are far more general, dealing with representations of semi-algebraic functions or correspondences. It does not seem that our techniques can be applied in this more general context.

We also point out that Yehuda John Levy obtains interesting results in two other directions : when the additional players are not restricted to be binary (Theorem 5.5), and when there are countably many original players (Theorems 5.3 and 5.4).

Extensions

In the previous construction, if all P ab have coefficients in Q, the constructed game may not have all pure profile payoffs in Q, since there is no reason one can find z ∈ E ∩ Q n . In this section we show that it is however possible to construct such a game, at the cost of additional players. The natural idea is to choose a z ∈ E whose coordinates z i are algebraic, with minimal polynomial R i ∈ Q[X], and to change the payoff of Player X i to T f i (x)u B 0 where the f i are defined from the R i in Lemma 5 ; that is, such that f i (x) = R i (x i ). There are however two difficulties to overcome:

-firstly, if we want to give a bound on the number of additional players, we need to know the degree of the R i , which may be considerably larger than d. This is given by Lemma 7 below.

-secondly, it may well be that the z i have algebraic conjugates in [0, 1] that are not coordinates of elements of E. Thus f i (x) = 0 (the analog of

z i = x i0 ) would imply R i (x i ) = R i (z i ) = 0 but not x i = z i ,
hence would not lead to a contradiction. We thus need to translate those variables in intervals in which the z i are the only zeroes of R i . This will be done by means of additional players V i .

We will need the two following technical lemmas to provide a precise bound on the number of additional players. The first one in a particular case of Algorithm 14.16 in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF], while the second one is Theorem (B) in [START_REF] Bugeaud | On the distance between roots of integer polynomials[END_REF]. Beware that in Lemma 7, d is the degree in each variable, while in the result we use (Algorithm 14.16 in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]), it is the total degree. Lemma 7. There exists a universal constant K such that, for every nonempty semi-algebraic set

E = ∪ A a=1 ∩ B b=1 {x ∈ R n , P ab (x) ≤ 0} ⊂ [0, 1] n where each P ab ∈ Z[x 1 , • • • , x n ],
is of degree at most d ≥ 2 in each variable, and with coefficients bounded by M , there exists z ∈ E such that all coordinates z i are zeroes of some R i ∈ Z[X] with degree less than (nd) Kn and coefficients less than (M + 1) (nd) Kn . Lemma 8. Let P ∈ Z[X] be a polynomial with no multiple roots, with degree d ≥ 2 and coefficients bounded by M . Then the minimal distance between two roots is greater than

√ 3(d + 1) -2d+1 2 M 1-d > d -2d M -d .
We can now prove :

Proposition 9. Let d ≥ 2.
There exists a universal constant K ′ such that, for every nonempty semi-

algebraic set E = ∪ A a=1 ∩ B b=1 {x ∈ R n , P ab (x) ≤ 0} in [0, 1] n , where each P ab ∈ Z[x 1 , • • • , x n ],
is of degree at most d in each variable, and with coefficients bounded by M , there exists a binary N -player game with integer pure payoffs bounded by (nd(M + 1)) (nd) K ′ n , and N ≤ 1 + AB + K ′ n 2 ln 2 (nd) such that the projection of the set of its equilibria on the first n coordinates is precisely E.

Proof. Let z = (z 1 , • • • , z n ) ∈ E such that every z i is algebraic. Let R i ∈ Z[X]
be the minimal polynomial of z i . By Lemma 7, we may choose z such that R i is of degree less than d 1 = (nd) Kn and with coefficients less than M 1 = (M + 1) (nd) Kn = (M + 1) d1 . Define M 2 = (nd(M + 1)) (nd) 2Kn = (nd(M + 1))

d 2 1 ≥ d 2d1 1 M d1 1
(the inequality holds provided K ≥ 1, which we may assume without loss of generality). Since R i is minimal it has no multiple roots hence by Lemma 8 there exists an nonnegative integer

α i < M 2 such that z i is the only zero of R i in αi M2 , 1+αi M2 . Let Q i (x) = M 2 d1 R i x+αi M2
. Then Q i has degree at most d 1 , and its only zero in [0, 1] is M 2 z i -α i . Moreover, for any l ≤ d, the coefficient of x l is an integer and bounded by

M d1 2 d1 j=l M 1 j l α j-l i M j 2 ≤ M 1 M d1 2 2 d1 ≤ (2(M + 1)) d1 (nd(M + 1)) d 3 1 ≤ (nd(M + 1)) d1+d 3 1 := M 3 .
Finally, up to a change of sign, we may assume Q i (0) ≥ 0 and Q i (1) ≤ 0. Define players X ik , S ab and U as in the proof of Proposition 1. Consider now n additional players V i that play Top with probability v i and with payoffs to be defined later on. Denote by D the integer part of ln 2 (d 1 ) ; for any i defines as in Lemma 4 some additional players V ik (playing a role with respect to the v i similar to the X ik with respect to the x i ) and W ik (playing a role similar to the Y ik ) for k = 0 to D. Thus at equilibrium v ik = (v i ) 2 k . For any Q i one defines some multiaffine f i as in Lemma 5. This allows us to define the payoff of player V i as

T uf i (v i0 , • • • , v iD ) B
0 Finally, define the payoff of the n original players X i as well as yet n additional players Y i as

Player X i T (1 -u)x i0 + u v i + α i M 2 B y i Player Y i T x i B (1 -u)x i0 + u v i + α i M 2 Let x = (x 1 , • • • , x n ) be
the n first coordinates of an equilibrium and assume x / ∈ E. As in the proof of Proposition 1, one has u = 1. Also, since we are at equilibrium Lemmas 4 and 5 imply that

Q i (v i ) = f i (v i0 , • • • , v iD ). Thus Q i (v i ) > 0 implies v i = 1 thus Q i (v i ) ≤ 0, while Q i (v i ) < 0 implies v i = 0 thus Q i (v i ) ≥ 0, in both cases a contradiction. Hence Q i (v i ) = 0 and v i = M 2 z i -α i . Since u = 1, (1 -u)x i0 + u vi+αi M2 = z i ∈ [0, 1]
, so applying Lemma 3 to the payoffs of players X i and Y i yields x i = z i and x = z ∈ E, a contradiction.

Let now x be in E and consider the profile where v ik = w ik = x ik = y ik = (x i ) 2 k for all i and k, v i = y i = x i , u = 0, and s ab = 0 if P ab (x) ≤ 0 and 1 otherwise. Then all players are indifferent, except some S ab but those have no profitable deviation by construction.

The total number of players is less than 1 + AB + n(5

+ 2 ln 2 (d)) + 2n(1 + ln 2 (d 1 )) ≤ 1 + AB + 11Kn 2 ln 2 (nd).
The pure payoffs of all players except X i and Y i are integers; for players X i and Y i this is also the case provided one multiplies all their payoffs by M 2 (which gives a strategically equivalent game). Clearly the only players which may have a large payoff are the V i . Their payoffs are defined as multiaffine functions with d 2 = (1 + ln 2 (d 1 )) variables in [0, 1] and coefficients smaller than M 3 . In the payoff there is thus an addition of at most 2 d2 terms each less than M 3 . The maximal payoff is thus less than 2 d2 M 3 ≤ (nd(M + 1)) d1 M 3 = (nd(M + 1)) 2d1+d 3 1 ≤ (nd(M + 1)) d 4 1 = (nd(M + 1)) (nd) 4Kn .

Remarks

5.1.

Optimality of the construction. The bound we obtained in Section 2 on the number of additional players is almost optimal in n and d. Precisely, we obtained a bound in n ln d and it is not possible to do better than n ln d ln(n ln d) . Indeed, recall the following bound on the number of connected components of a semi algebraic set [START_REF] Coste | An introduction to semialgebraic geometry[END_REF] : Lemma 10. Let E be a semi-algebraic set defined by unions and intersections of s polynomial inequalities in r variables of total degree D ≥ 2. Then its number of connected components is less than (2D -1)D r+s-1 .

Corollary 11. The set of equilibria of a binary game with N players has at most 2N 7N connected components.

Proof. The bound is trivial for N = 1 or 2 so assume N ≥ 3. Let x i be the probability that Player i plays his first action and denote the payoff of Player i if he plays his first (resp. second) action g

i (x 1 , • • • , x i-1 , x i+1 , • • • , x N ) (resp. h i (x 1 , • • • , x i-1 , x i+1 , • • • , x N
)) where g i and h i are multiaffine. Since for instance

x i > 0 ⇒ g i (x -i ) ≥ h i (x -i ) ⇔ x i ≤ 0 or g i (x -i ) ≥ h i (x -i ) , the set of equilibria may be written as

i∈N {x i ≥ 1} ∪ {g i (x -i ) ≤ h i (x -i )} ∩ {x i ≤ 0} ∪ {g i (x -i ) ≥ h i (x -i )} ∩ ({x i ≥ 0} ∩ {x i ≤ 1}) .
where we wrote, e.g., {x i ≥ 0} instead of {x ∈ R n |x i ≥ 0}. By the previous lemma, this set has at most (2N -3)(N -1) N +6N -1 < 2N 7N connected components.

Corollary 12. For every n ≥ 2 and d ≥ 2, there exists a basic semi-algebraic set described by a polynomial inequality with n variables and degree 2d which is not the set of equilibria (or equilibrium payoffs) of the first n players of any binary game with less than n ln d 5.2. Simplicity of the construction. Our construction does not depend on Tarski-Seidenberg and real algebraic geometry at all, and is easily seen to take a polynomial time in the data. Of course, all this assumes that we are given certificates of semi-algebraicity and closedness (formula 1), of nonemptiness (the coordinates of a point in E or the description of the coordinates of an algebraic point in E), as well as a bound on E in the case of Proposition 2.

If not, it is possible to find such certificates but this uses real algebraic techniques (see for example [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]) and is typically at least exponential in the data. So, from a constructive viewpoint, we have cut the problem in two parts :

1) Preprocessing : find certificates. This is in full generality hard and time-consuming, but for specific examples it may be very easy and short, even if the set is itself very complex.

2) Use these certificates to construct a game. This is quite easy and not time-consuming.

  exactly the same proof would work, replacing the payoff of Player U by T A a=1 B b=1 s ab B 0 More generally, assume E is defined by unions and intersections (in any order) of C sets E c = {x, P c (x) ≤ 0}. In this definition, replace any E c by p c , any ∩ by a +, any ∪ by a * , and denote by Q(p 1 , • • • , p C ) the resulting expression. Then the same proof, replacing the payoff of Player U by

  7 ln(n ln d) players. Proof. Let (α 1 , • • • , α d ) be d arbitrary numbers in [0, 1] and consider the set E= {x ∈ R n , P (x 1 , • • • , x n ) ≤ 0} where P (x 1 , • • • , x n ) := n i=1 Π d j=1 (x i -α j ) 2 . E is clearly finite with cardinal d n .Assume by contradiction that E is the set of equilibria (or equilibrium payoffs) of the first n players of some binary game Γ with less than N := n ln d 7 ln(n ln d) players. Since taking projections or applying the payoff functions can only decrease the number of connected components, the number of connected components of the equilibrium set of Γ is at least d n . However, by the previous corollary, it is at most2N 7N ≤ (2N ) 7N =2n ln d 7 ln(n ln d) n ln d ln(n ln d) < (n ln d) n ln d ln(n ln d) = e n ln d = d n a contradiction. The strict inequality uses that 2/7 ln(n ln d) < 1 as soon as d n > exp(e 2/7 ) ≃ 3, 78.

Acknowledments

We thank Sylvain Sorin for helpful remarks and Yehuda John Levy for extensive discussions and for sending us a draft of his article "Projection and Functions of Nash Equilibria". This research was supported by grant ANR-13-JS01-0004-01 (France).