# Oddness of the number of Nash equilibria: the case of polynomial payoff functions

Philippe Bich, Julien Fixary

<figure><img src="image_1.png" /></figure>

## To cite this version:

Philippe Bich, Julien Fixary. Oddness of the number of Nash equilibria: the case of polynomial payoff functions. 2021. halshs-03354269

HAL Id: halshs-03354269

https://shs.hal.science/halshs-03354269

Submitted on 24 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CES

Centre d'Économie de la Sorbonne
UMR 8174

# Oddness of the Number of Nash Equilibria: The Case of Polynomial Payoff Functions

Philippe BICH, Julien FIXARY

2021.27
ODDNESS OF THE NUMBER OF NASH EQUILIBRIA:
THE CASE OF POLYNOMIAL PAYOFF FUNCTIONS

PHILIPPE BICH* AND JULIEN FIXARY†

30th August 2021

Abstract

In 1971, Robert Wilson ([19]) proved that “almost all” finite games have an odd number of mixed Nash equilibria (oddness theorem). Since then, several other proofs have been given, but always for mixed extensions of finite games. In this paper, we prove oddness theorem for large classes of polynomial payoff functions and semi-algebraic sets of strategies, and we provide some applications to recent models.

KEYWORDS: Nash equilibria, polynomial payoff functions, generic oddness.

JEL CLASSIFICATION: C02, C62, C72, D85.

<footnote>*Paris School of Economics, Université Paris 1 Panthéon-Sorbonne UMR 8074 Centre d'Economie de la Sorbonne.
E-mail: bich@univ-paris1.fr</footnote>

<footnote>†Université Paris 1 Panthéon-Sorbonne UMR 8074 Centre d'Economie de la Sorbonne. E-mail: julien.fixary@univ-paris1.fr</footnote>
# 1 INTRODUCTION

In 1971, Robert Wilson ([19]) proved the so-called oddness theorem: generically, finite games have an odd number of mixed Nash equilibria. Since then, several other proofs have been given, but always for mixed extensions of finite games (see for example [3, 6, 7, 8, 10, 14, 16, 19]). The purpose of this paper is to prove oddness theorem for large classes of polynomial payoff functions and semi-algebraic sets of strategies (a subset $S$ of $\mathbb{R}^m$ is semi-algebraic if it is defined by finitely many polynomial inequalities). For example, we prove that when payoff functions are polynomial and concave in players' own strategies, and when the sets of strategies are semi-algebraic, then oddness theorem holds. Our results give new insights on the set of Nash equilibria for many recent models, for example models of network formation such as Patacchini-Zenou's model about juvenile delinquency and conformism ([15]), Calvó-Armengol-Patacchini-Zenou's model about social networks in education ([5]), Konig-Liu-Zenou's model about R&D networks ([13]), Helsley-Zenou's model about social networks and interactions in cities ([9]), etc.

Oddness theorem proved by Wilson is known to be a corollary of Kohlberg-Mertens' structure theorem ([12]). If we denote by

$$ \mathcal{N} = \{(u, \sigma) \in \mathcal{F} \times \Sigma : \sigma \text{ is a Nash equilibrium of } u\} $$

the graph of Nash equilibria (where $\mathcal{F}$ is the set of games, i.e. the set of profiles of mixed payoff functions associated to finite games, and $\Sigma$ is the set of profiles of mixed strategies), by $N(u)$ the set of Nash equilibria of each game $u \in \mathcal{F}$ and by $\pi: \mathcal{N} \to \mathcal{F}$ the projection on the first factor, then we have $\pi^{-1}(u) = \{u\} \times N(u)$. Kohlberg-Mertens' theorem ([12]) states that $\pi$ is properly homotopic to some homeomorphism $\eta$ from $\mathcal{N}$ to $\mathcal{F}$, where $\mathcal{F}$ is itself homeomorphic to some Euclidean space. In particular, applying topological degree to $\pi$, it can be obtained that the number of Nash equilibria of $u$ is generically odd.<fnref n="1" />

In this paper, we extend oddness theorem to general subclasses $\mathcal{U}$ of polynomial payoffs functions of fixed maximal degrees, which are own-strategy concave<fnref n="2" />, and satisfying the following simple conditions:

1. The set $S$ of all coefficients of elements in $\mathcal{U}$ has to be semi-algebraic.

2. Adding the set of linear functions to $\mathcal{U}$ should not modify the dimension of $S$ (this is true, for example, if $\mathcal{U}$ is stable with respect to addition of linear functions.)

The main difficulty in our proof is that in general, $\mathcal{U}$ is not homeomorphic to some Euclidean space: actually, $\mathcal{U}$ is not even always a topological manifold, which implies that there is no clear and tractable definition of topological degree anymore on $\mathcal{U}$, and the standard proof recalled above cannot be applied. For example, when there is only one player and $\mathcal{U} = \{x \in [0, 1] \mapsto ax^2 + bx + c : a = 0 \text{ or } [a < 0 \text{ and } c = 0]\}$, then $\mathcal{U}$ is homeomorphic to $S = \{(a, b, c) \in \mathbb{R}^3 : a = 0 \text{ or } [a < 0 \text{ and } c = 0]\}$ which is not a topological manifold. Yet, in this example, it is true that for “almost all” admissible parameters $(a, b, c) \in S$, there exists an odd number of Nash equilibria.<fnref n="3" />

To address this shortcoming, the main ingredient of our proof is to decompose $\mathcal{U}$ into a union of subsets $\mathcal{U}^k$ to which the method above can be applied, restricting payoff functions to each $\mathcal{U}^k$. In particular,

<footnote n="1">¹Hereafter is a sketch of the proof: from invariance of topological degree, the topological degree of $\pi$ is equal to the topological degree of $\eta$, and since $\eta$ is a proper homeomorphism from $\mathcal{N}$ to $\mathcal{F}$ ($\mathcal{F}$ being homeomorphic to some Euclidean space), its topological degree is equal to 1 or -1. From some covering space property, there exists a generic subset $G \in \mathcal{G}$ in the set of finite games, such that for every profile of mixed payoff functions $u = (u_1, \dots, u_n)$ of $g \in \mathcal{G}$, $\pi^{-1}(u)$ is a finite set $\{(u, \sigma^1), \dots, (u, \sigma^k)\}$. The same covering space property gives that $\pi$ is a local homeomorphism at each $(u, \sigma^p)$, $p \in \{1, \dots, k\}$, hence the local degree of $\pi$ at $(u, \sigma^p)$ has to be equal to 1 or -1. Last, the sum of local degrees of $\pi$ is equal to the degree of $\pi$, which finally ends the proof.</footnote>

<footnote n="2">²Convexity (or at least quasiconcavity) of payoff functions $u_i(x_i, x_{-i})$ of each player $i$ with respect to $x_i$ is a standard assumption in the literature when considering conditions for the existence of a Nash equilibrium.</footnote>

<footnote n="3">³Indeed, each function in $\mathcal{U}$ has a unique maximum except for $(a, b) = (0, 0)$, $c \in \mathbb{R}$, for which any $x \in [0, 1]$ is a maximum.</footnote>
this requires to be able to prove some extension of Kohlberg-Mertens' theorem ([12]) applied to each $\mathcal{U}^k$, which can be done by an adequate choice of these sets (applying Tarski-Seidenberg's theorem),<fnref n="4" /> and by some application of a recent result of Predtetchinsky ([17, 18]).<fnref n="5" />

Our paper is organized as follows. In Section 2, we recall the extension of Kohlberg-Mertens' theorem by Predtetchinsky, with a slight extension (useful for our main result). In Section 3, we state oddness theorem for our classes of polynomial payoff functions (Subsection 3.1) and we provide some applications (Subsection 3.2). Finally, in Section 4, we provide the proofs, together with some useful material related to semi-algebraic sets and topological degree.

## 2 STRUCTURE THEOREM

Throughout this paper,<fnref n="6" /> we fix some integer $n \ge 1$, and we define $N = [1, n]$, called the set of players. For every $i \in N$, let $X_i$ be a nonempty, convex and compact semi-algebraic subset of $\mathbb{R}^{k_i}$ called the set of strategies of player i, where $k_i$ is a positive integer, and let $X = \prod_{i \in N} X_i$ be the set of strategy profiles.

**Definition 2.1.** A (strategic-form) game is an element $u = (u_1, \dots, u_n) \in \mathcal{F}(X, \mathbb{R})^n$, where each mapping $u_i$ is called the payoff function of player $i \in N$.

**Notations.** For every player $i \in N$, an element $x_i \in X_i$ is also denoted $x_i = (x_{i,1}, \dots, x_{i,k_i})$. We denote $X_{-i} = \prod_{j \neq i} X_j$ and $x_{-i} = (x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) \in X_{-i}$ the vector derived from $(x_1, \dots, x_n) \in X$ by deleting the $i$-th coordinate. We adopt the usual notation $u_i(x) = u_i(x_i, x_{-i})$ for every $x \in X$ and every payoff function $u_i$ of player $i$, where $x_i \in X_i$ is the strategy of player $i$ and $x_{-i} \in X_{-i}$ is the vector of strategies of all players except player $i$.

We now recall the seminal concept of Nash equilibrium:

**Definition 2.2.** A profile of strategies $x = (x_1, \dots, x_n) \in X$ is a Nash equilibrium of the game $u = (u_1, \dots, u_n)$ if for every $i \in N$ and every $d_i \in X_i$, $u_i(d_i, x_{-i}) \le u_i(x)$. The set of Nash equilibria of the game $u$ is denoted $N(u)$.

The payoff functions considered in this paper satisfy some concavity assumption and some differentiability assumption.<fnref n="7" /> More precisely, for every $i \in N$, let

$$ \mathcal{F}_i = \{u_i \in \mathcal{C}^0(X, \mathbb{R}) : \forall x_{-i} \in X_{-i}, x_i \mapsto u_i(x_i, x_{-i}) \text{ is concave and } \mathcal{C}^1\} $$

and $\mathcal{F} = \prod_{i \in N} \mathcal{F}_i$. For every $i \in N$, we consider on $\tilde{\mathcal{F}}_i := \{u_i \in \mathcal{C}^0(X, \mathbb{R}) : \forall x_{-i} \in X_{-i}, x_i \mapsto u_i(x_i, x_{-i}) \text{ is } \mathcal{C}^1\}$ the topology generated by all subsets of the form $\{u_i \in \tilde{\mathcal{F}}_i : \forall x = (x_i, x_{-i}) \in K, u_i(x) \in$

<footnote n="4">⁴Tarski-Seidenberg's theorem states that the projection of a semi-algebraic subset is semi-algebraic.</footnote>

<footnote n="5">⁵Remark that in [2] is proved a similar oddness result for pairwise stable networks instead of Nash equilibria.</footnote>

<footnote n="6">⁶Let us recall some mathematical definitions or notations used in this paper. For every positive integer $m$, we recall that a semi-algebraic subset of $\mathbb{R}^m$ is a subset of the form $\bigcup_{i=1}^s \bigcap_{j=1}^{r_i} \{x \in \mathbb{R}^m : f_{i,j} \star_{i,j} 0\}$, where $\star_{i,j}$ denotes either $<$ or $=$ and $f_{i,j} \in \mathbb{R}[X_1, \dots, X_m]$ for every $i = 1, \dots, s$ and every $j = 1, \dots, r_i$ (see Bochnak [4]). For every sets $X$ and $Y$, both $\mathcal{F}(X, Y)$ and $Y^X$ denote the set of mappings from $X$ to $Y$. For every finite set $X$, card($X$) denotes the cardinal of $X$. A correspondence $\Phi$ from a set $X$ to another set $Y$ is a mapping from $X$ to the set of all subsets of $Y$, and we denote it by $\Phi : X \to Y$. A mapping $f$ from a topological space $X$ to another topological space $Y$ is proper if for every compact subset $K$ of $Y$, $f^{-1}(K)$ is compact in $X$. For every topological spaces $X$ and $Y$, a homotopy from a continuous mapping $f : X \to Y$ to another continuous mapping $g : X \to Y$ is a continuous mapping $H : [0, 1] \times X \to Y$ such that $H(0, \cdot) = f$ and $H(1, \cdot) = g$. We say that (1) $f$ and $g$ are homotopic if there exists a homotopy from $f$ to $g$, (2) $f$ and $g$ are properly homotopic if there exists a homotopy $H$ from $f$ to $g$ such that $H^{-1}(K)$ is compact for every compact subset $K$ of $Y$. Every cartesian product of any family of topological spaces is endowed with the product topology. Moreover, for every positive integer $m$, $\mathbb{R}^m$ is endowed with its usual Euclidean topology; for every $x = (x_1, \dots, x_m) \in \mathbb{R}^m$, the Euclidean norm $\|x\|$ of $x$ is defined by $\|x\| = \sqrt{\sum_{i=1}^m x_i^2}$.</footnote>

<footnote n="7">⁷A function $f$ from an arbitrary subset $X$ of $\mathbb{R}^m$ to $\mathbb{R}$ is said to be $\mathcal{C}^1$ if for every $x \in X$, there exists an open subset $U$ of $\mathbb{R}^m$ containing $x$ and a $\mathcal{C}^1$ function $g : U \to \mathbb{R}$ such that $g|_{U \cap X} = f|_{U \cap X}$.</footnote>
$U$ and $\nabla_{x_i} u_i(\cdot, x_{-i}) \in U'$}, for some compact subspace $K$ of $X$, some open subset $U$ of $\mathbb{R}$ and some open subset $U'$ of $\mathbb{R}^{k_i}$, and where $\nabla_{x_i} u_i(\cdot, x_{-i})$ denotes the gradient of $u_i(\cdot, x_{-i})$ at the point $x_i$. The set $\mathcal{F}_i \subset \tilde{\mathcal{F}}_i$ is endowed with the induced topology.

**Definition 2.3.** The Nash correspondence is the correspondence

$$ \left\{ \begin{array}{rcl} \Phi: & \mathcal{F} & \to X \\ & u & \mapsto N(u) \end{array} \right. $$

and the graph of the Nash correspondence (sometimes called simply the *graph of Nash equilibria*) is defined by

$$ \mathcal{N} := \mathrm{Gr}(\Phi) = \{(u, x) \in \mathcal{F} \times X : x \in N(u)\}. $$

We denote the projection from $\mathcal{N}$ to $\mathcal{F}$ by $\pi$, i.e. $\pi(u, x) = u$ for every $(u, x) \in \mathcal{N}$.

We now recall the following structure theorem due to Predtetchinsky ([17, 18]):

**Theorem 2.1.** The projection mapping $\pi: \mathcal{N} \to \mathcal{F}$ is properly homotopic to some homeomorphism $\eta: \mathcal{N} \to \mathcal{F}$.

The proof can be found in [17, 18], which is an extension of Kohlberg-Mertens’ structure theorem ([12]). For completeness, we recall that the homeomorphism $\eta: \mathcal{N} \to \mathcal{F}$ is defined as follows: for every $(u, x) \in \mathcal{N}$, $\eta(u, x) = (\eta_i(u, x))_{i \in \mathcal{N}}$, where for every $i \in \mathcal{N}$,

$$ \eta_i(u, x) : y \mapsto u_i(y) + \langle \nabla_{x_i} u_i(\cdot, x_{-i}) - \nabla_{x_i} u_i(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle, \quad (1) $$

where $x^0 \in X$ is a fixed strategy profile and where $\langle \cdot, \cdot \rangle$ denotes the Euclidean scalar product on $\mathbb{R}^{k_i}$.

The corollary below states that Theorem 2.1 remains true if we replace $\mathcal{F}$ by a subset of $\mathcal{F}$ satisfying some additional stability assumption: for every $i \in \mathcal{N}$, let

$$ \mathcal{A}_i = \{x \in X \mapsto \langle \alpha_i, x_i \rangle + c_i : \alpha_i \in \mathbb{R}^{k_i}, c_i \in \mathbb{R}\} \subset \mathcal{F}_i, $$

(that is to say, $u_i \in \mathcal{A}_i$ if $u_i$ is affine with respect to $x_i$ and does not depend on $x_{-i}$) and $\mathcal{A} = \prod_{i \in \mathcal{N}} \mathcal{A}_i$. For every subset $\mathcal{U}$ of $\mathcal{F}$, we define

$$ \mathcal{N}_{\mathcal{U}} := \{(u, x) \in \mathcal{N} : u \in \mathcal{U}\} $$

and we consider the restriction $\pi|_{\mathcal{N}_{\mathcal{U}}}$ of $\pi$ to $\mathcal{N}_{\mathcal{U}}$. Similarly, $\eta|_{\mathcal{N}_{\mathcal{U}}}$ denotes the restriction of $\eta$ (the mapping defined in the above theorem) to $\mathcal{N}_{\mathcal{U}}$.

**Corollary 2.1.** For every $\mathcal{U} \subset \mathcal{F}$ such that $\mathcal{U} + \mathcal{A} = \mathcal{U}$, $\eta|_{\mathcal{N}_{\mathcal{U}}}: \mathcal{N}_{\mathcal{U}} \to \mathcal{U}$ is a homeomorphism which is properly homotopic to $\pi|_{\mathcal{N}_{\mathcal{U}}}: \mathcal{N}_{\mathcal{U}} \to \mathcal{U}$.

The proof is given in Appendix 4.3.

# 3 GENERIC ODDNESS OF THE GRAPH OF NASH EQUILIBRIA

## 3.1 ODDNESS THEOREM

In this section, we prove that for some large classes of polynomial payoff functions (which we call *regular*), there exists an odd number of Nash equilibria.
From now on, for every player $i \in N$, we fix some integer $\delta_i \in \mathbb{N}$, and we consider the vector space$^8$
$\mathbb{R}_{\delta_i}[x]$ of polynomial functions whose degree is less or equal to $\delta_i$. In particular, any element $u_i \in \mathbb{R}_{\delta_i}[x]$ can be expressed as

$$u_i(x) = \sum_{k \in \mathbb{N}^{\Lambda}} \alpha_k^i x^k$$

where $\Lambda = \{(i,j) : i \in N, j \in \{1, \dots, k_i\}\}, x \in X, k = (k_{i,j})_{(i,j) \in \Lambda} \in \mathbb{N}^{\Lambda}$ is a multi-index (with $\alpha_k^i = 0$ if $\deg(k) := \sum_{(i,j) \in \Lambda} k_{i,j} > \delta_i$), and where $x^k := \prod_{(i,j) \in \Lambda} x_{i,j}^{k_{i,j}}$ is called a monomial.

We denote by $\varphi_i$ the isomorphism which associates to every payoff function $u_i \in \mathbb{R}_{\delta_i}[x]$ its coefficients (with respect to some predefined order on $\mathbb{N}^{\Lambda}$) in $\mathbb{R}^{m_i}$, for some integer $m_i$. In the following, we define $m := \sum_{i \in N} m_i$, $\varphi := \times_{i \in N} \varphi_i : \prod_{i \in N} \mathbb{R}_{\delta_i}[x] \to \mathbb{R}^m$ and for every subset $\mathcal{U}$ of $\prod_{i \in N} \mathbb{R}_{\delta_i}[x]$, $\mathcal{S} := \varphi(\mathcal{U})$. By abuse of notation, the restriction of $\varphi$ to any subset $\mathcal{U}$ of $\prod_{i \in N} \mathbb{R}_{\delta_i}[x]$ is also denoted $\varphi : \mathcal{U} \to \mathbb{R}^m$. In particular, this restriction is a homeomorphism from $\mathcal{U}$ to $\mathcal{S}$.

Moreover, for every player $i$, let

$$\mathcal{L}_i := \{x \in X \mapsto \langle \alpha_i, x_i \rangle : \alpha_i \in \mathbb{R}^{k_i} \} \subset \mathcal{F}_i$$

and $\mathcal{L} = \prod_{i \in N} \mathcal{L}_i$. In particular, for every $i \in N$, $\mathcal{A}_i = \mathcal{L}_i + \mathcal{C}$, where $\mathcal{C} := \{x \in X \mapsto c : c \in \mathbb{R}\} \subset \mathcal{F}_i$, and $\mathcal{A} = \mathcal{L} + \mathcal{C}^n$. Remark that for every game $u = (u_1, \dots, u_n)$ and every $c = (c_1, \dots, c_n) \in \mathcal{C}^n$, the set $\mathbb{N}(u)$ of Nash equilibria of $u$ and the set $\mathbb{N}(u+c)$ of Nash equilibria of $u+c$ are the same. Thus, we can focus only on games without constant part: for every $i \in N$, define $\mathbb{R}_{\delta_i}^0[x] = \{u_i \in \mathbb{R}_{\delta_i}[x] : u_i(0) = 0\}$.

The following definition of regularity plays a central role in our paper (see Appendix 4.1 for reminders about semi-algebraic sets, in particular for the definition of the dimension of a semi-algebraic set):

**Definition 3.1.** A set $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x]$ is said to be regular if the two following conditions are fulfilled:

1. (Semi-algebraicity assumption) $\mathcal{S} = \varphi(\mathcal{U})$ is a semi-algebraic set.

2. (Stability assumption) $\dim(\varphi(\mathcal{U} + \mathcal{L})) = \dim(\varphi(\mathcal{U}))$.

For example, $\prod_{i \in N}(\mathcal{F}_i \cap \mathbb{R}_{\delta_i}^0[x])$ is regular; see Section 3.2 for more examples.

To state our main result, we need to define formally the notion of genericity: for every semi-algebraic set $\mathcal{S}$, a semi-algebraic subset $S_0$ of $\mathcal{S}$ is said to be generic (in $\mathcal{S}$) if $S_0$ is open in $\mathcal{S}$ and if $\dim(S - S_0) < \dim(\mathcal{S})$. This definition allows to extend the definition of genericity to subsets of polynomial functions as follows:

**Definition 3.2.** Consider $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}[x]$. A subset $\mathcal{G}$ of $\mathcal{U}$ is said to be generic (in $\mathcal{U}$) if the set $\varphi(\mathcal{G})$ is generic in $\mathcal{S} = \varphi(\mathcal{U})$.

The following theorem is an extension Wilson's oddness theorem ([19]) to subsets of polynomial payoff functions satisfying the previous regularity condition:

**Theorem 3.1.** (Oddness theorem)

For every regular subset $\mathcal{U}$ of $\mathcal{F}$, there exists a generic subset $\mathcal{U}^*$ of $\mathcal{U}$ such that for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria.

## 3.2 SOME APPLICATIONS OF ODDNESS THEOREM

In this section, we suppose that for every player $i \in N$, the set $X_i$ of player $i$'s strategies is a compact interval of $\mathbb{R}$; when $X_i \subset [0, +\infty)$, a strategy $x_i \in X_i$ of player $i$ can be interpreted as an amount of time or effort to exert some activity.

<footnote>$^8$For every $i \in N$, the set $\mathbb{R}_{\delta_i}[x]$ is endowed with the topology induced by the topology of $\tilde{\mathcal{F}}_i$ (defined in the previous section). Endowed with this topology, $\mathbb{R}_{\delta_i}[x]$ is a finite-dimensional Hausdorff topological vector space, thus every linear mapping from $\mathbb{R}_{\delta_i}[x]$ to any other topological vector space is continuous.</footnote>
### 3.2.1 Linear perturbations

In this section, we prove that oddness theorem holds for generic linear perturbations of a given profile $\bar{u} = (\bar{u}_1, \dots, \bar{u}_n) \in \mathcal{F}$ of polynomial payoff functions such that for every $i \in N$, $\bar{u}_i(0) = 0$. Let $A \subset \mathbb{R}^n$ be some semi-algebraic set of parameters of dimension $n$ (a typical case is when $A$ is a product of intervals of nonempty interior), and consider the following family $\mathcal{U}$ of profiles of perturbed payoff functions:

$$ \mathcal{U} = \{ (x \mapsto u_i^{\alpha_i}(x) := \bar{u}_i(x) + \alpha_i x_i)_{i \in N} : \alpha = (\alpha_1, \dots, \alpha_n) \in A \}. $$

It is regular. Indeed:

1. First, $\mathcal{U} \subset (\prod_{i \in N} \mathbb{R}_{\delta_i}^0 [x]) \cap \mathcal{F}$ for some integers $\delta_i$, $i \in N$;

2. Second, $\mathcal{U}$ satisfies semi-algebraicity assumption (in Definition 3.1): indeed, $S = \varphi(\mathcal{U})$ is a semi-algebraic set, since $A$ is semi-algebraic;

3. Third, $\mathcal{U}$ satisfies stability assumption (in Definition 3.1): indeed, $\varphi(\mathcal{U})$ is semi-algebraically homeomorphic to $A$ (whose dimension is $n$ by assumption), and $\varphi(\mathcal{U} + \mathcal{L})$ is semi-algebraically homeomorphic to $\mathbb{R}^n$, which finally proves that $\dim\varphi(\mathcal{U} + \mathcal{L}) = \dim\varphi(\mathcal{U})$.

Thus, from Theorem 3.1, there exists a generic subset $G$ of $A$ such that for every $(\alpha_1, \dots, \alpha_n) \in G$, the game $(u_i^{\alpha_i})_{i \in N}$ has an odd number of Nash equilibria.

As an illustration, for $n = 2$, $X_1 = [0, 1]$ and $X_2 = [0, 1]$, given two polynomial payoff functions $\bar{u}_1 \in \mathcal{F}_1$ and $\bar{u}_2 \in \mathcal{F}_2$ such that $\bar{u}_1(0) = \bar{u}_2(0) = 0$, and assuming that the set of parameters is $A = \{(\alpha_1, \alpha_2) \in \mathbb{R}^2 : \alpha_1 \ge \alpha_2^2\}$, then we get that for a generic set of parameters $(\alpha_1, \alpha_2) \in A$, there exists an odd number of Nash equilibria of the game defined by $u_1(x_1, x_2) = \bar{u}_1(x_1, x_2) + \alpha_1 x_1$, $u_2(x_1, x_2) = \bar{u}_2(x_1, x_2) + \alpha_2 x_2$. Indeed, the set of parameters $A$ is semi-algebraic of dimension 2.

### 3.2.2 Quadratic perturbations

Similarly to the previous section, we now prove that oddness theorem holds for generic quadratic perturbations of a given profile $\bar{u} = (\bar{u}_1, \dots, \bar{u}_n) \in \mathcal{F}$ of polynomial payoff functions such that for every $i \in N$, $\bar{u}_i(0) = 0$. Consider two semi-algebraic sets of parameters $C \subset \mathbb{R}^n$ and $D \subset ([0, +\infty) \times \mathbb{R}^{n-1})^n$ such that $\dim(C) = n$. Consider the following family $\mathcal{U}$ of profiles of perturbed payoff functions:

$$ \mathcal{U} = \{ (x \mapsto u_i^{\alpha_i, \beta_i, \gamma_i}(x) := \bar{u}_i(x) - \alpha_i x_i^2 + \sum_{j \neq i} \beta_{i,j} x_i x_j + \gamma_i x_i)_{i \in N} : \gamma = (\gamma_1, \dots, \gamma_n) \in C, (\alpha_i, \beta_i)_{i \in N} \in D \} $$

where $\beta_i = (\beta_{i,j})_{j \neq i}$. It is regular. Indeed:

1. First, $\mathcal{U} \subset (\prod_{i \in N} \mathbb{R}_{\delta_i}^0 [x]) \cap \mathcal{F}$ for some integers $\delta_i$, $i \in N$;

2. Second, $\mathcal{U}$ satisfies semi-algebraicity assumption (in Definition 3.1): indeed, $S = \varphi(\mathcal{U})$ is a semi-algebraic set, since $C$ and $D$ are semi-algebraic;

3. Third, $\mathcal{U}$ satisfies stability assumption (in Definition 3.1): indeed, $\varphi(\mathcal{U})$ is semi-algebraically homeomorphic to $D \times C$ (thus its dimension is $\dim(D) + n$ by assumption), and $\varphi(\mathcal{U} + \mathcal{L})$ is semi-algebraically homeomorphic to $D \times \mathbb{R}^n$, which finally proves that $\dim\varphi(\mathcal{U} + \mathcal{L}) = \dim\varphi(\mathcal{U})$.

Thus, from Theorem 3.1, we get that there exists a generic subset $G$ of $D \times C$ such that for every $(\alpha_i, \beta_i, \gamma_i)_{i \in N} \in G$, the game $(u_i^{\alpha_i, \beta_i, \gamma_i})_{i \in N}$ has an odd number of Nash equilibria.
### 3.2.3 The benchmark quadratic model

As an application of the previous sections, we prove that there exists generically an odd number of Nash equilibria for several models introduced in network formation literature: Patacchini-Zenou's model about juvenile delinquency and conformism ([15]), Calvó-Armengol-Patacchini-Zenou's model about social networks in education ([5]), Konig-Liu-Zenou's model about R&D networks ([13]), Helsley-Zenou's model about social networks and interactions in cities ([9]), etc. These models are in fact particular cases of the benchmark quadratic model (see [11]). In the following, we consider $L = \{\{i, j\} \subset N : i \neq j\}$ is the set of (undirected) links, and the set $\mathbb{G} := \mathcal{F}(L, [0, 1])$ of weighted networks (here, the strength of any link $\{i, j\}$ in a network $g$, denoted $g_{ij}$, is measured by an element in $[0, 1]$).

**The benchmark quadratic model with ex ante heterogeneity.** Fix $\phi \in (0, +\infty)$, and suppose that for every player $i \in N$, and every strategy profile $x \in X$, payoff function of player $i$ is defined by

$$x \mapsto -\frac{1}{2}x_i^2 + \phi \sum_{j \neq i} g_{ij}x_ix_j + \gamma_ix_i,$$

where $g = (g_{ij})_{\{i,j\} \in \mathbb{G}} \in \mathbb{G}$, and for every player $i$, $g_i = (g_{ij})_{j \neq i}$ and $\gamma_i \in [0, +\infty)$. For every $i \in N$, we can rewrite the payoff function of player $i$ in the following way:

$$x \mapsto -\frac{1}{2}x_i^2 + \sum_{j \neq i} \beta_{ij}x_ix_j + \gamma_ix_i,$$

where for every $\{i, j\} \in L$, $\beta_{ij} = \phi g_{ij} \in [0, \phi]$. We can get two different generic existence results, depending on which parameters of the model are fixed:

1. We can first consider $u_i^{\beta_i, \gamma_i}(x) = -\frac{1}{2}x_i^2 + \sum_{j \neq i} \beta_{ij}x_ix_j + \gamma_ix_i$, where for every $i \in N$, $\beta_i = (\beta_{ij})_{j \neq i}$ and for every $\{i, j\} \in L$, $\beta_{ij} = \phi g_{ij} \in [0, \phi]$. As an application of Section 3.2.2, defining $D = \{(\alpha_i, \beta_i)_{i \in N} \in \mathbb{R}^n : \forall i \in N, \alpha_i = \frac{1}{2}, \forall j \neq i, \beta_{i,j} = \beta_{j,i} \in [0, \phi]\}$ and $C = [0, +\infty)^n$, we get that there exists a generic subset $G$ of $D \times C$ such that for every $(\alpha_i, (\beta_{i,j})_{j \neq i})_{i \in N} \in G$, the game $(u_i^{\beta_i, \gamma_i})_{i \in N}$ has an odd number of Nash equilibria. This implies the existence of an odd number of Nash equilibria for a generic subset of (undirected) networks $g$ and parameters $(\gamma_i)_{i \in N} \in C$ (because $x \in [0, \phi] \mapsto \frac{x}{\phi}$ is a semi-algebraic homeomorphism).

2. Second, we can consider, for $g$ fixed, $u_i^{\alpha_i}(x) = -\frac{1}{2}x_i^2 + \phi \sum_{j=1}^n g_{ij}x_ix_j + \alpha_ix_i$, where for every player $i$, $\alpha_i \in [0, +\infty)$. As an application of Section 3.2.1, defining $A = [0, +\infty)^n$, we get that there exists a generic subset $G$ of $A$ such that for every $(\alpha_1, \dots, \alpha_n) \in G$, the game $(u_i^{\alpha_i})_{i \in N}$ has an odd number of Nash equilibria. Remark that this result is not comparable to the previous one, since the generic set $G$ depends on $g$.

**The model with global congestion and ex ante heterogeneity.** Consider the benchmark quadratic model with ex ante heterogeneity, with the following modification:

$$u_i^{g_i, \gamma_i}(x) = -\frac{1}{2}x_i^2 + \phi \sum_{j \neq i} g_{ij}x_ix_j - \lambda \sum_{j \neq i} x_ix_j + \gamma_ix_i,$$

where $\lambda \in [0, +\infty[$, or equivalently,

$$u_i^{\beta_i, \gamma_i}(x) = -\frac{1}{2}x_i^2 + \sum_{j \neq i} \beta_{ij}x_ix_j + \gamma_ix_i,$$

where for every $i \in N$, $\beta_i = (\beta_{ij})_{j \neq i}$ and for every $\{i, j\} \in L$, $\beta_{ij} = \phi g_{ij} - \lambda \in [-\lambda, \phi - \lambda]$. Similarly to the previous section, applying Section 3.2.2, we get that there exists an odd number of Nash equilibria for a generic subset of (undirected) networks $g$ and parameters $(\gamma_i)_{i \in N} \in [0, +\infty)^n$.
# 4 APPENDIX

## 4.1 REMINDERS ABOUT REAL ALGEBRAIC GEOMETRY

**Proposition 4.1. (Tarski-Seidenberg)**

If $S$ is a semi-algebraic subset of $\mathbb{R}^{m+p}$ and $\Pi$ is the canonical projection from $\mathbb{R}^{m+p}$ to $\mathbb{R}^m$, then $\Pi(S)$ is a semi-algebraic subset of $\mathbb{R}^m$.

The following proposition (a consequence of Tarski-Seidenberg's result above) is a powerful way to prove that some sets are semi-algebraic. We first need the following definition:

**Definition 4.1.** A first-order formula of the language of ordered fields with parameters in $\mathbb{R}$ is a formula written with a finite number of conjunctions, disjunctions, negations, and universal or existential quantifiers on variables in semi-algebraic sets, starting from atomic formulas which are formulas of the kind $f(x_1, \dots, x_m) = 0$ or $g(x_1, \dots, x_m) > 0$, where $f$ and $g$ are polynomials with coefficients in $\mathbb{R}$.

**Proposition 4.2.** Let $\Phi(x_1, \dots, x_m)$ be a first-order formula of the language of ordered fields with parameters in $\mathbb{R}$. Then, $\{x \in \mathbb{R}^m : \Phi(x)\}$ is a semi-algebraic set.

For example, if $f$ is a polynomial with four variables and if $\mathbb{S}^1$ denotes the unit circle of $\mathbb{R}^2$, then the set $\{(x, y) \in \mathbb{R}^2 : \forall(z, t) \in \mathbb{S}^1, f(x, y, z, t) \ge 0\}$ is semi-algebraic (as $\mathbb{S}^1$ is itself a semi-algebraic set).

**Definition 4.2.** Let $S$ be a semi-algebraic subset of $\mathbb{R}^m$ and $T$ be a semi-algebraic subset of $\mathbb{R}^p$. A mapping $f : S \to T$ is semi-algebraic if its graph

$$ \mathrm{Gr}(f) = \{(x, f(x)) : x \in S\} $$

is a semi-algebraic subset of $\mathbb{R}^m \times \mathbb{R}^p$.

The following proposition is a consequence of Tarski-Seidenberg's theorem:

**Proposition 4.3.** Let $S$ be a semi-algebraic subset of $\mathbb{R}^m$ and $f : S \to \mathbb{R}^p$ be a semi-algebraic mapping. Then, $f(S)$ is a semi-algebraic subset of $\mathbb{R}^p$.

A semi-algebraic homeomorphism is a homeomorphism which is semi-algebraic (in that case, $f^{-1}$ is also semi-algebraic). We now define the dimension of a semi-algebraic set (see Bochnak [4], Theorem 2.3.6., p. 33, and Corollary 2.8.9., p. 53).

**Definition 4.3.** For every semi-algebraic subset $S$ of $\mathbb{R}^m$, there exists an increasing sequence of non-negative integers $d_0 \le d_1 \le \dots \le d_k$ such that

$$ S = \bigcup_{i=0}^{k} S_i, $$

the union being disjoint, where $S_i$ is semi-algebraically homeomorphic to $]0, 1]^{d_i}$ for every $i = 0, \dots, k$ (where, by convention, $]0, 1]^0$ is a point). The dimension of $S$ is defined as

$$ \dim(S) := \max\{d_0, d_1, \dots, d_k\} $$

(and does not depend on the decomposition of $S$). Remark also that for every $S_i$ in the above decomposition such that $\dim(S_i) = \dim(S)$, $S_i$ has to be open in $S$.

Then, we have the following properties:
**Proposition 4.4.** Let $S, S_1$ and $S_2$ be semi-algebraic subsets of $\mathbb{R}^m$:

1. If $f: S \to \mathbb{R}^p$ is semi-algebraic and is a bijection from $S$ to $f(S)$, then $\dim(S) = \dim(f(S))$.

2. If $S_1 \subset S_2$, then $\dim(S_1) \le \dim(S_2)$.

3. $\dim(S_1 \times S_2) = \dim(S_1) + \dim(S_2)$.

4. If $S_1 \subset S_2$ and $\dim(S_1) = \dim(S_2)$, then there exists $s \in S_1$ and $r > 0$ such that $B(s,r) \subset S_1$, where $B(s,r)$ is some open ball in $S_2$ centered at $s$ of radius $r$ with $\dim(B(s,r)) = \dim(S_2)$.

**Definition 4.4.** Let $S$ be a semi-algebraic set and $S_0$ be a semi-algebraic subset of $S$. We say that $S_0$ is a generic semi-algebraic subset of $S$ if $S_0$ is open in $S$ and if $\dim(S - S_0) < \dim(S)$.

**Theorem 4.1.** Let $S$ and $T$ be two semi-algebraic sets such that $\dim(S) \le \dim(T)$ and $f: S \to T$ be a surjective continuous semi-algebraic mapping. Then, there exists a generic semi-algebraic subset $T_0$ of $T$ such that for every $t_0 \in T_0$:

* $f^{-1}(t_0)$ is a (nonempty) finite set,

* there exists an open neighborhood $V_{t_0}$ of $t_0$ such that $f^{-1}(V_{t_0})$ is a finite union of pairwise disjoint open sets $(V_{t_0}^k)_{k \in K}$ (where $K$ is a finite set) such that for every $k \in K$, $f|_{V_{t_0}^k}$ is a homeomorphism between $V_{t_0}^k$ and $V_{t_0}$.

**Proof.** To prove this theorem, we use the following theorem (see Bochnak [4], p. 224):

**Theorem 4.2.** Let $S$ and $T$ be two semi-algebraic sets and $f: S \to T$ be a continuous semi-algebraic mapping. Then, there exists a generic semi-algebraic subset $T_0$ of $T$ such that $f$ has a semi-algebraic trivialization<fnref n="9" /> over each semi-algebraically connected component<fnref n="10" /> of $T_0$.

Now, to prove Theorem 4.1, let us consider $t_0 \in T_0$ and the connected component $C_0$ of $T_0$ which contains $t_0$. We apply the theorem above to $C_0$: thus, there exists a semi-algebraic trivialization of $f$ over $C_0$ with fiber $K$. In particular, $C_0 \times K$ and $f^{-1}(C_0)$ are semi-algebrically homeomorphic, thus we obtain that

$$ \dim(C_0 \times K) = \dim(C_0) + \dim(K) = \dim(f^{-1}(C_0)) $$

with $\dim(f^{-1}(C_0)) \le \dim(S)$ and $\dim(C_0) = \dim(T)$, since $f^{-1}(C_0) \subset S$ and since $T_0$ is open in $T$ (thus $C_0$ is also open in $T$). Now, $f^{-1}(t_0)$ is also semi-algebraically homeomorphic to $K$ (indeed, $K$ is semi-algebraically homeomorphic to $\{t_0\} \times K$ and $\theta_{|\{t_0\} \times K}$ is a semi-algebraic homeomorphism from $\{t_0\} \times K$ to $f^{-1}(t_0)$). In particular, $\dim(f^{-1}(t_0)) = \dim(K)$, thus from the above equality, we obtain that

$$ \dim(f^{-1}(t_0)) = \dim(f^{-1}(C_0)) - \dim(C_0) \le \dim(S) - \dim(T). $$

But, by assumption, $\dim(S) \le \dim(T)$, and in particular we obtain that $\dim(f^{-1}(t_0)) = 0$. Finally, as $f^{-1}(t_0)$ is a 0-dimensional semi-algebraic set, it is a finite (nonempty) set (see Bochnak [4], Theorem 2.3.6.) with the same cardinal as $K$. Then, defining $V_{t_0}$ an open neighborhood of $t_0$ included in $C_0$, and $V_{t_0}^k = \theta(V_{t_0} \times \{k\})$ for every $k \in K$, we easily get that:

1. The sets $V_{t_0}^k$, $k \in K$, are open (because $V_{t_0} \times \{k\}$ is open in $C_0 \times K$ and $\theta$ is a homeomorphism) and disjoint.

2. For every $k \in K$, $f|_{V_{t_0}^k}$ is a homeomorphism between $V_{t_0}^k$ and $V_{t_0}$, because $f|_{V_{t_0}^k} = \Pi \circ \theta_{|V_{t_0}^k}^{-1}$ (where $\Pi$ is the projection from $V_{t_0} \times \{k\}$ to $V_{t_0}$) and because both $\Pi$ and $\theta_{|V_{t_0}^k}$ are homeomorphisms.

<footnote n="9">⁹We recall that a semi-algebraic trivialization of $f$ over a semi-algebraically connected component $C$ of $T_0$ with fiber $K$ (where $K$ is a semi-algebraic set) is a semi-algebraic homeomorphism $\theta: C \times K \to f^{-1}(C)$ such that $f(\theta(c, x)) = c$ for every $(c, x) \in C \times K$. Remark that when $f^{-1}(C) = \emptyset$ this is automatically true, taking the empty mapping $\theta = \emptyset$.</footnote>

<footnote n="10">¹⁰Let us recall that in $\mathbb{R}^m$, a semi-algebraic set is semi-algebraically connected if and only if it is connected (see Bochnak [4], Theorem 2.4.5., p. 35).</footnote>
## 4.2 TOPOLOGICAL DEGREE OF A CONTINUOUS MAPPING

In this subsection, we gather all the properties of topological degree which are used in this paper (see Dold, Proposition 4.5, p. 268). To every proper continuous mapping $f: X \to Y$, where X and Y are oriented topological m-manifolds, Y being connected, one can associate an integer $deg(f) \in \mathbb{Z}$, called the degree of $f$ (or topological degree of $f$) which satisfies the following properties:

(i) **(Homotopy invariance).** For every continuous mapping $g: X \to Y$, if $f$ and $g$ are properly homotopic, then $deg(f) = deg(g)$ (see Dold [1], Exercise 3., p. 271).

(ii) **(Surjectivity).** If $deg(f) \neq 0$, then $f$ is surjective (see Dold [1], p. 267-268).

(iii) **(Homeomorphism).** If $f$ is a homeomorphism from some open subset $V$ of $X$ to $f(V)$, then $deg(f|_V) \in \{-1, 1\}$ (see Dold [1], just after Proposition 4.5, p. 268).

(iv) **(Additivity).** For every $y \in Y$, if $f^{-1}(y) = \{x_1, \dots, x_k\}$ (for some integer $k > 0$), then

$$ \deg(f) = \sum_{i=1}^{k} \deg(f|_{V_i}) $$

where for every $i = 1, \dots, k$, $V_i$ is an open subset of $X$ such that $V_i \cap f^{-1}(y) = \{x_i\}$ (see Dold [1], Proposition 4.7, p. 269).

In particular, from (iii) and (iv), if for every $i = 1, \dots, k$, $f$ is a homeomorphism from $V_i$ to $f(V_i)$ and if $deg(f) \in \{-1, 1\}$, then we get that $k$ is odd.

## 4.3 PROOF OF COROLLARY 2.1

First, we prove that $\eta(\mathcal{N}_U) \subset \mathcal{U}$. From Equation (1), for every $(u, x) \in \mathcal{N}_U$, we have $\eta(u, x) = (\eta_i(u, x))_{i \in N}$, where for every $i \in N$,

$$ \eta_i(u, x) : y \mapsto u_i(y) + \langle \nabla_{x_i} u_i(\cdot, x_{-i}) - \nabla_{x_i} u_i(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle. $$

Now, since $\eta_i(u, x)$ is equal to $u_i$ up to an element of $A_i$, we obtain that $\eta(u, x) \in \mathcal{U}$ (by assumption, as $\mathcal{U} + A = \mathcal{U}$), which implies that $\eta(\mathcal{N}_U) \subset \mathcal{U}$.

Second, we prove that $\eta^{-1}(\mathcal{U}) \subset \mathcal{N}_U$, where we recall (see [17, 18]) that for every $u \in \mathcal{U}$, we have $\eta^{-1}(u) = (\phi(u), \tilde{x}) = (\phi_i(u), \tilde{x}_i)_{i \in N}$, where for every $i \in N$,

$$ \phi_i(u) : y \mapsto u_i(y) - \langle \nabla_{\tilde{x}_i} u_i(\cdot, \tilde{x}_{-i}) - \nabla_{\tilde{x}_i} u_i(\cdot, x_{-i}^0), y_i - \tilde{x}_i \rangle - \langle \tilde{x}_i, y_i \rangle $$

and $\tilde{x}_i$ is the unique maximizer of the strictly concave mapping $x_i \in X_i \mapsto u_i(x_i, x_{-i}^0) - \frac{1}{2}\langle x_i, x_i \rangle$. For every $u \in \mathcal{U}$, the strategy profile $\tilde{x}$ is a Nash equilibrium of $\phi(u)$ (see [17, 18]), and since $\phi_i(u)$ is equal to $u_i$ up to an element of $A_i$, we obtain that $\phi(u) \in \mathcal{U}$ (by assumption, as $\mathcal{U} + A = \mathcal{U}$), which implies that $\eta^{-1}(\mathcal{U}) \subset \mathcal{N}_U$.

From the two last results and by continuity of $\eta$ and $\eta^{-1}$ (see [17, 18]), we obtain that the mapping $\eta|_{\mathcal{N}_U}: \mathcal{N}_U \to \mathcal{U}$, $(u, x) \mapsto \eta(u, x)$ is a homeomorphism.

Finally, we show that the mapping

$$ H|_{\mathcal{N}_U} : [0, 1] \times \mathcal{N}_U \to \mathcal{U} \\ (t, (u, x)) \mapsto t\eta|_{\mathcal{N}_U}(u, x) + (1-t)\pi|_{\mathcal{N}_U}(u, x) $$
is a proper homotopy between $\pi_{|\mathcal{N}_U}$ and $\eta_{|\mathcal{N}_U}$.<fnref n="11" /> First, $H_{|\mathcal{N}_U}$ is continuous as the sum of two continuous mappings. Second, $H_{|\mathcal{N}_U}(0, (u, x)) = \pi_{|\mathcal{N}_U}(u, x)$ and $H_{|\mathcal{N}_U}(1, (u, x)) = \eta_{|\mathcal{N}_U}(u, x)$, for every $(u, x) \in \mathcal{N}_U$. Last, we prove that $H_{|\mathcal{N}_U}$ is a proper mapping. Let

$$ \left\{ \begin{array}{rcl} G: & [0, 1] \times \mathcal{U} \times X & \to \\ & (t, u, x) & \mapsto \end{array} \right. \qquad \begin{array}{l} \mathcal{U} + \mathcal{A} = \mathcal{U} \\ (y \mapsto u_i(y) + t(\langle \nabla_{x_i} u_i(\cdot, x_{-i}) - \nabla_{x_i} u_i(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle))_{i \in N} . \end{array} $$

Remark that the restriction of $G$ to $[0, 1] \times \mathcal{N}_U$ is equal to $H_{|\mathcal{N}_U}$. Moreover, let $\psi : [0, 1] \times \mathcal{U} \times X \to [0, 1] \times \mathcal{U} \times X$, $(t, u, x) \mapsto (t, G(t, u, x), x)$. The mapping $\psi$ is invertible: for every $(t, u, x) \in [0, 1] \times \mathcal{U} \times X$, $\psi^{-1}(t, u, x) = (t, \hat{G}(t, u, x), x)$, where

$$ \left\{ \begin{array}{rcl} \hat{G}: & [0, 1] \times \mathcal{U} \times X & \to \\ & (t, u, x) & \mapsto \end{array} \right. \qquad \begin{array}{l} \mathcal{U} + \mathcal{A} = \mathcal{U} \\ (y \mapsto u_i(y) - t(\langle \nabla_{x_i} u_i(\cdot, x_{-i}) - \nabla_{x_i} u_i(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle))_{i \in N} . \end{array} $$

Moreover, both $\psi$ and $\psi^{-1}$ are continuous mappings (the proof is similar to the one of Theorem 2.1 in [18]). Now, let $K$ be a compact subspace of $\mathcal{U}$. By definition,

$$ \begin{aligned} H_{|\mathcal{N}_U}^{-1}(K) &= \{(t, (u, x)) \in [0, 1] \times \mathcal{N}_U : H_{|\mathcal{N}_U}(t, (u, x)) \in K\} \\ &= \{(t, (u, x)) \in [0, 1] \times \mathcal{N}_U : \psi(t, u, x) \in [0, 1] \times K \times X\} \\ &= \psi^{-1}([0, 1] \times K \times X) \cap ([0, 1] \times \mathcal{N}_U). \end{aligned} $$

Moreover, as $\mathcal{N}_U$ is a closed subset<fnref n="12" /> of $\mathcal{U} \times X$, we obtain that $[0, 1] \times \mathcal{N}_U$ is also closed in $[0, 1] \times \mathcal{U} \times X$, thus that $H_{|\mathcal{N}_U}^{-1}(K)$ is closed in $\psi^{-1}([0, 1] \times K \times X)$ which is compact (as $\psi^{-1}$ is continuous and as $[0, 1] \times K \times X$ is compact). This finally implies that $H_{|\mathcal{N}_U}^{-1}(K)$ is also compact, thus that $H_{|\mathcal{N}_U}$ is proper.

## 4.4 PROOF OF THEOREM 3.1

In Step I, we prove Theorem 3.1 when $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}[x] \cap \mathcal{F}$ instead of $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x] \cap \mathcal{F}$, and when stability assumption is replaced by the assumption that $\mathcal{U} + \mathcal{A} = \mathcal{U}$.

**Step I.** Consider $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}[x] \cap \mathcal{F}$ which satisfies semi-algebraicity assumption, and such that $\mathcal{U} + \mathcal{A} = \mathcal{U}$. Then, there exists a generic subset $\mathcal{U}^*$ of $\mathcal{U}$ such that for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria.

From Theorem 2.1, there exists a proper homeomorphism $\eta$ (defined in Equation (1)) from $\mathcal{N}$, the graph of Nash equilibria, to $\mathcal{F}$ (recall that $\pi : \mathcal{N} \to \mathcal{F}$ denotes the projection from $\mathcal{N}$ to $\mathcal{F}$). Since $\mathcal{U} \subset \mathcal{F}$ is such that $\mathcal{U} + \mathcal{A} = \mathcal{U}$, Corollary 2.1 implies that $\eta_{|\mathcal{N}_U}$, the restriction of $\eta$ to $\mathcal{N}_U$ (the graph of Nash equilibria restricted to $\mathcal{U}$), is a proper homeomorphism from $\mathcal{N}_U$ to $\mathcal{U}$.

The idea of the proof of Step I is to decompose $\mathcal{U}$ into a finite union of (non disjoint) subsets $\mathcal{V}^k$, each one being homeomorphic to some Euclidean space (Step 1), then to prove that for generic $v \in \mathcal{V}^k$, there exists an odd number of Nash equilibria (Steps 2-8), and finally we conclude in Step 9.

<footnote n="11">¹¹Notice that for every $(t, (u, x)) \in [0, 1] \times \mathcal{N}_U$, $H(t, (u, x)) = t\eta_{|\mathcal{N}_U}(u, x) + (1-t)\pi_{|\mathcal{N}_U}(u, x) = t(u+a) + (1-t)u = u+ta$ for some element $a \in \mathcal{A} = \prod_{i \in N} \mathcal{A}_i$ (from Equation (1)), thus $H(t, (u, x)) \in \mathcal{U}$, as $\mathcal{U} + \mathcal{A} = \mathcal{U}$.</footnote>

<footnote n="12">¹²Indeed, $(u, x) \in \mathcal{N}$ is equivalent to $(u, x) \in \bigcap_{i \in N, d_i \in X_i} \Psi_{i, d_i}^{-1}((-\infty, 0])$ where $\Psi_{i, d_i} : \mathcal{F} \times X \to \mathbb{R}$ is defined by $\Psi_{i, d_i}(u, x) = u_i(d_i, x_{-i}) - u_i(x)$ for every $(u, x) \in \mathcal{F} \times X$. Since $\Psi_{i, d_i}$ is continuous (see Preliminaries in [17]), we get that $\mathcal{N}$ is closed as an intersection of closed sets. Similarly, we get that $\mathcal{N}_U$ is closed in $\mathcal{U} \times X$.</footnote>
Step 1. A decomposition result.

We recall that for every $i \in N$, $\mathbb{R}_{\delta_i}[x]$ is the vector space of polynomial functions whose degree is less or equal to $\delta_i \in N$, that $\varphi_i : \mathbb{R}_{\delta_i}[x] \to \mathbb{R}^{m_i}$ is the isomorphism which associates to every payoff function $u_i \in \mathbb{R}_{\delta_i}[x]$ its coefficients in $\mathbb{R}^{m_i}$, that the restriction of $\varphi = \times_{i \in N} \varphi_i$ to $\mathcal{U}$ is also denoted $\varphi$, that $m = \sum_{i \in N} m_i$, and that each element $x_i \in X_i \subset \mathbb{R}^{k_i}$ is also denoted $x_i = (x_{i,1}, \dots, x_{i,k_i})$.

For every $i \in N$, we denote by $\tilde{\mathbb{R}}_{\delta_i}[x]$ the linear subspace of $\mathbb{R}_{\delta_i}[x]$ generated by all the monomials in $\mathbb{R}_{\delta_i}[x]$, except the ones in $\mathcal{A}_i$, i.e.

$$ \tilde{\mathbb{R}}_{\delta_i}[x] := \operatorname{span}(\{x^k : k \in \mathbb{N}^\Lambda, \deg(k) \le \delta_i\} - (\{x_{i,j} : j = 1, \dots, k_i\} \cup \{1\})). $$

By definition, $\mathbb{R}_{\delta_i}[x] = \tilde{\mathbb{R}}_{\delta_i}[x] \oplus \mathcal{A}_i$ and $\prod_{i \in N} \mathbb{R}_{\delta_i}[x] = \prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x] \oplus \mathcal{A}$, thus $\varphi_i(\mathbb{R}_{\delta_i}[x]) = \mathbb{R}^{m_i} = \varphi_i(\tilde{\mathbb{R}}_{\delta_i}[x]) \oplus \varphi_i(\mathcal{A}_i)$ and $\varphi(\prod_{i \in N} \mathbb{R}_{\delta_i}[x]) = \mathbb{R}^m = \varphi(\prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x]) \oplus \varphi(\mathcal{A})$.

Now, if we denote by $\hat{\pi}_{-\mathcal{A}}$ the linear projection from $\prod_{i \in N} \mathbb{R}_{\delta_i}[x] = \prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x] \oplus \mathcal{A}$ to $\prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x]$, then we can define the mapping $\pi_{-\mathcal{A}} = \varphi \circ \hat{\pi}_{-\mathcal{A}} \circ \varphi^{-1}$, which is simply the linear projection from the set $\mathbb{R}^m = \varphi(\prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x]) \oplus \varphi(\mathcal{A})$ to the set $\varphi(\prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x])$. Since $\mathcal{S} = \varphi(\mathcal{U})$ is semi-algebraic (from semi-algebraicity assumption in Definition 3.1) and since $\pi_{-\mathcal{A}}$ is a semi-algebraic mapping, from Tarski-Seidenberg's theorem (see Proposition 4.3 in Section 4.1), the set $\pi_{-\mathcal{A}}(\mathcal{S})$ is semi-algebraic. In particular, from the decomposition result for semi-algebraic sets (see Definition 4.3 in Section 4.1),

$$ \pi_{-\mathcal{A}}(\mathcal{S}) = \bigcup_{k=1}^{\kappa} T^k, $$

the union being disjoint, where $\kappa \in N$ and where for every $k \in \{1, \dots, \kappa\}$, $T^k \subset \pi_{-\mathcal{A}}(\mathcal{S}) \subset \varphi(\prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x])$ is semi-algebraic and homeomorphic to $(0, 1)^{d_k}$ (for some $d_k \in N$). In particular, for every $k \in \{1, \dots, \kappa\}$, the set

$$ \mathcal{U}^k := \varphi^{-1}(T^k) $$

is homeomorphic to $(0, 1)^{d_k}$.

For every $k \in \{1, \dots, \kappa\}$, we now consider the set

$$ \mathcal{V}^k := \mathcal{U}^k + \mathcal{A}, $$

and we define $\mathcal{S}^k := \varphi(\mathcal{V}^k) = T^k + \varphi(\mathcal{A})$. We can notice that for every $k \in \{1, \dots, \kappa\}$:

$$ 1. \mathcal{V}^k + \mathcal{A} = (\mathcal{U}^k + \mathcal{A}) + \mathcal{A} = \mathcal{U}^k + \mathcal{A} = \mathcal{V}^k. $$

$$ 2. \mathcal{V}^k \text{ satisfies semi-algebraicity assumption (in Definition 3.1), because } \varphi(\mathcal{V}^k) = \mathcal{S}^k = T^k + \varphi(\mathcal{A}) \text{ is a semi-algebraic set, since } T^k \text{ and } \varphi(\mathcal{A}) \text{ are both semi-algebraic sets.}^{13} $$

$$ 3. \mathcal{V}^k \text{ is included in } \mathcal{F}. \text{ Indeed, first, since } \mathcal{U} + \mathcal{A} = \mathcal{U} \text{ (by assumption), we obtain that } \hat{\pi}_{-\mathcal{A}}(\mathcal{U}) \subset \mathcal{U} \text{ (because if } y \in \hat{\pi}_{-\mathcal{A}}(\mathcal{U}), \text{ then there exists } x = x_1+x_2 \in \mathcal{U}, \text{ where } x_1 \in \prod_{i \in N} \tilde{\mathbb{R}}_{\delta_i}[x] \text{ and } x_2 \in \mathcal{A}, \text{ such that } y = \hat{\pi}_{-\mathcal{A}}(x) = x_1, \text{ thus } y = x - x_2 \in \mathcal{U} + \mathcal{A} = \mathcal{U}. \text{ Second, since } T^k \subset \pi_{-\mathcal{A}}(\mathcal{S}) = \pi_{-\mathcal{A}}(\varphi(\mathcal{U})), \text{ we obtain that } \varphi^{-1}(T^k) \subset (\varphi^{-1} \circ \pi_{-\mathcal{A}} \circ \varphi)(\mathcal{U}) = \hat{\pi}_{-\mathcal{A}}(\mathcal{U}). \text{ This finally implies } \varphi^{-1}(T^k) \subset \mathcal{U}, \text{ and that} $$

$$ \mathcal{V}^k = \varphi^{-1}(T^k) + \mathcal{A} \subset \mathcal{U} + \mathcal{A} = \mathcal{U} \subset \mathcal{F}, $$

the last inclusion being true by assumption.

$$ 4. \mathcal{V}^k \text{ is homeomorphic}^{14} \text{ to } \varphi^{-1}(T^k) \times \mathcal{A}, \text{ thus homeomorphic to } (0, 1)^{e_k} \text{ (for some } e_k \in \mathbb{N}). \text{ In particular, } \mathcal{V}^k \text{ is homeomorphic to some Euclidean space.} $$

<footnote n="13">¹³The sum of two semi-algebraic subsets $S_1$ and $S_2$ of some Euclidean space is a semi-algebraic set: indeed, $S_1 + S_2 = f(S_1 \times S_2)$, where $f: (x, y) \mapsto x + y$ is a polynomial function and where $S_1 \times S_2$ is a semi-algebraic set. Moreover, $\varphi(\mathcal{A})$ is a subspace of $\mathbb{R}^m$, thus is semi-algebraic.</footnote>

<footnote n="14">¹⁴Indeed, the mapping $f: \varphi^{-1}(T^k) \times \mathcal{A} \to \varphi^{-1}(T^k) + \mathcal{A}, (x, y) \mapsto x + y$ is such a homeomorphism, since the linear subspace of $\prod_{i \in N} \mathbb{R}_{\delta_i}[x]$ generated by $\varphi^{-1}(T^k)$ and the linear subspace $\mathcal{A}$ of $\prod_{i \in N} \mathbb{R}_{\delta_i}[x]$ are in direct sum.</footnote>
5. Moreover, the family $(S^k)_{k=1}^\kappa$ forms a covering of $S = \varphi(\mathcal{U})$. Indeed,

$$ 
\begin{align*}
\bigcup_{k=1}^{\kappa} S^k &= \bigcup_{k=1}^{\kappa} T^k + \varphi(\mathcal{A}) = \pi_{-\mathcal{A}}(S) + \varphi(\mathcal{A}) \\
&= (\varphi \circ \hat{\pi}_{-\mathcal{A}} \circ \varphi^{-1})(S) + \varphi(\mathcal{A}) = \varphi((\hat{\pi}_{-\mathcal{A}}(\varphi^{-1}(S)) + \mathcal{A}) = \varphi((\hat{\pi}_{-\mathcal{A}}(\mathcal{U}) + \mathcal{A}) \\
&= \varphi(\mathcal{U}) \text{ (from } \mathcal{U} + \mathcal{A} = \mathcal{U}, \text{ we get } \hat{\pi}_{-\mathcal{A}}(\mathcal{U}) + \mathcal{A} = \mathcal{U})
\end{align*}
$$

From now on and until Step 9, we fix some element $k \in \{1, \dots, \kappa\}$.

**Step 2.** The set $\mathcal{M}^k := \{(\varphi(u), x) \in S^k \times X : (u, x) \in \mathcal{N}_{\mathcal{V}^k}\}$ is semi-algebraic and the mapping $\eta^k : \mathcal{M}^k \to S^k$, $(s, x) \mapsto (\varphi \circ \eta_{|_{\mathcal{N}_{\mathcal{V}^k}}})(\varphi^{-1}(s), x)$ is a semi-algebraic homeomorphism. In particular, $\dim(\mathcal{M}^k) = \dim(S^k)$, and both $\mathcal{M}^k$ and $S^k$ are oriented connected topological manifolds of the same dimension.

The following diagram summarizes the situation:

<figure><img src="image_3.png" /></figure>

where $\pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ and $\eta_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ are the restrictions of $\pi$ and $\eta$ to $\mathcal{N}_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ and where $\pi^k$ and $\eta^k$ are the “transportations” of $\pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ and $\eta_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ from $\mathcal{M}^k$ to $S^k$ by the homeomorphisms $\varphi$ and $\tilde{\varphi} : \mathcal{N}_{\mathcal{V}^k} \to \mathcal{M}^k$, $(u, x) \mapsto (\varphi(u), x)$. With this notation, $\pi^k = \varphi \circ \pi_{|_{\mathcal{N}_{\mathcal{V}^k}}} \circ \tilde{\varphi}^{-1}$ (which is the usual projection from $\mathcal{M}^k$ to $S^k$) and $\eta^k = \varphi \circ \eta_{|_{\mathcal{N}_{\mathcal{V}^k}}} \circ \tilde{\varphi}^{-1}$.

First, we show that $\mathcal{M}^k$ is semi-algebraic. From the concavity assumption of payoff functions in $\mathcal{U}$ and from the first order necessary (and sufficient) condition at a maximum for a concave function, the condition $(s, x) \in \mathcal{M}^k$, that is the condition “$x$ is a Nash equilibrium of $\varphi^{-1}(s)$”, is equivalent to the following condition: for every $i \in N$, for every $y_i \in X_i$,

$$ \langle \nabla_{x_i} u_i^s(\cdot, x_{-i}), y_i - x_i \rangle \le 0, $$

where $u^s := (u_i^s)_{i \in N} = \varphi^{-1}(s)$. This condition involves semi-algebraic mappings and involves quantifiers defined on semi-algebraic sets, thus we get that $\mathcal{M}^k$ is semi-algebraic (see Proposition 4.2).

Second, we show that the mapping $\eta^k$ is semi-algebraic, which is equivalent to say that for every $i \in N$,

$$ (s, x) \mapsto \varphi_i(y \mapsto u_i^s(y) + \langle \nabla_{x_i} u_i^s(\cdot, x_{-i}) - \nabla_{x_i} u_i^s(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle) $$

is a semi-algebraic mapping (where, as in the definition of $\eta$, $x^0 = (x_1^0, \dots, x_n^0) \in X$ is a fixed strategy profile). We can see directly that this is the case, since each coefficient of the polynomial function

$$ y \mapsto u_i^s(y) + \langle \nabla_{x_i} u_i^s(\cdot, x_{-i}) - \nabla_{x_i} u_i^s(\cdot, x_{-i}^0), y_i - x_i \rangle + \langle x_i, y_i \rangle $$

is a polynomial function of $(s, x)$.

We can remark that $\eta^k$ is a semi-algebraic homeomorphism from $\mathcal{M}^k$ to $S^k$, since both $\eta_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ and $\tilde{\varphi}$ are homeomorphisms. This implies (see [4], Theorem 2.8.8.) that $\dim(\mathcal{M}^k) = \dim(S^k)$. Finally, since $\mathcal{V}^k$ is homeomorphic to some Euclidean space (from Step 1), we obtain that both $\mathcal{M}^k$ and $S^k$ are oriented connected topological manifolds of the same dimension.

**Step 3.** $\pi^k$ and $\eta^k$ are properly homotopic.
We recall that from Corollary 2.1, there exists some proper homotopy $H_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ between $\pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ and $\eta_{|_{\mathcal{N}_{\mathcal{V}^k}}}$.
Using this homotopy, we can deduce an homotopy between $\pi^k$ and $\eta^k$. Indeed, the mapping

$$ \left\{ \begin{array}{rcl} H^k : [0,1] \times \mathcal{M}^k & \to & \mathcal{S}^k \\ (t, (s, x)) & \mapsto & (\varphi \circ H_{|_{\mathcal{N}_{\mathcal{V}^k}}}) (t, \tilde{\varphi}^{-1}(s, x)) \end{array} \right. $$

is continuous (by composition) and we obtain that

$$ H^k(0, (s, x)) = (\varphi \circ H_{|_{\mathcal{N}_{\mathcal{V}^k}}}) (0, \tilde{\varphi}^{-1}(s, x)) = (\varphi \circ \eta_{|_{\mathcal{N}_{\mathcal{V}^k}}}) \circ \tilde{\varphi}^{-1}(s, x) = \eta^k(s, x) $$

by definition of $\eta^k$, and similarly that

$$ H^k(1, (s, x)) = (\varphi \circ H_{|_{\mathcal{N}_{\mathcal{V}^k}}}) (0, \tilde{\varphi}^{-1}(s, x)) = (\varphi \circ \pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}) \circ \tilde{\varphi}^{-1}(s, x) = \pi^k(s, x) $$

by definition of $\pi^k$, for every $(s, x) \in \mathcal{M}^k$. We can notice that, as $H_{|_{\mathcal{N}_{\mathcal{V}^k}}}$ is a proper map, $H^k$ is also proper.

**Step 4.** The degree of $\pi^k$ is equal to $-1$ or $1$. In particular, $\pi^k$ is surjective.

From Step 2, we know that $\mathcal{M}^k$ and $\mathcal{S}^k$ are oriented connected topological manifolds of the same dimension, and in particular, we can apply topological degree. Since $\eta^k$ is a proper homeomorphism from $\mathcal{M}^k$ to $\mathcal{S}^k$, we get $\deg(\eta^k) \in \{-1, +1\}$ (see Appendix 4.2, Property (iii)). From Step 3, we know that $\pi^k$ and $\eta^k$ are properly homotopic, thus from homotopy invariance of topological degree (see Appendix 4.2, Property (i)), we get $\deg(\pi^k) = \deg(\eta^k)$, thus finally $\deg(\pi^k) \in \{-1, +1\}$, which implies that $\pi^k$ is a surjective mapping (see Appendix 4.2, Property (ii)).

**Step 5.** There exists a generic semi-algebraic subset $G^k$ of $\mathcal{S}^k$ such that for every $s \in G^k$, $(\pi^k)^{-1}(s)$ is nonempty and finite.

Indeed, $\pi^k : \mathcal{M}^k \to \mathcal{S}^k$ is a surjective semi-algebraic continuous mapping (from Step 4) and $\dim(\mathcal{M}) = \dim(\mathcal{S}^k)$ (from Step 1). Thus, from Theorem 4.1 (see Section 4.1), we obtain the existence of a generic semi-algebraic subset $G^k$ (now fixed) of $\mathcal{S}^k$ such that for every $s \in G^k$, $(\pi^k)^{-1}(s)$ is nonempty and finite.

**Step 6.** For every $s \in G^k$, the set of Nash equilibria of $u^s = \varphi^{-1}(s)$ is nonempty and finite (its cardinal is denoted $K_s$).

Indeed, from Step 5, we know that for every $s \in G^k$, $(\pi^k)^{-1}(s)$ is nonempty and finite. However, since $\tilde{\varphi}$ is a homeomorphism, we obtain that $\tilde{\varphi}^{-1}((\pi^k)^{-1}(s)) = \pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}^{-1}(\varphi^{-1}(s)) = \pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}^{-1}(u^s)$ is also nonempty and finite (with the same cardinal as $(\pi^k)^{-1}(s)$). By definition,

$$ \pi_{|_{\mathcal{N}_{\mathcal{V}^k}}}^{-1}(u^s) = \{(u^s, x) : x \text{ is a Nash equilibrium of } u^s\}. $$

**Step 7.** For every $s \in G^k$, there exists an open subset $V_s$ of $\mathcal{S}^k$ containing $s$ such that $(\pi^k)^{-1}(V_s)$ is a union of pairwise disjoint open sets $(V_s^l)_{l \in K}$ (where $K$ is a finite set of cardinal $K_s$) and such that for every $l \in K$, $\pi_{|_{V_s^l}}^k$ is a homeomorphism between $V_s^l$ and $V_s$.

Let $s \in G^k$, and let $C_s$ be the connected component of $G^k$ containing $s$. From Step 6, we know that $(\pi^k)^{-1}(s)$ is nonempty and finite of cardinal $K_s$. Moreover, from Theorem 4.1 (see Section 4.1), there exists an open neighborhood $V_s$ of $s$ such that $(\pi^k)^{-1}(V_s)$ is a union of pairwise disjoint open sets $(V_s^l)_{l \in K}$ (where $K$ is a finite set) such that for every $l \in K$, $\pi_{|_{V_s^l}}^k$ is a homeomorphism between $V_s^l$ and $V_s$.
Step 8. For every $s \in G^k$, there is an odd number of Nash equilibria of the game $u^s = \varphi^{-1}(s)$.

We want to prove that for every $s \in G^k$, the integer $K_s$ (introduced in Step 6) is odd. From Step 5 and Step 7, since $(\pi^k)^{-1}(s)$ is a finite subset of $\bigcup_{l \in K} V_s^l$ (with cardinal equal to $K_s = \text{card}(K)$) and since for every $l \in K$, $\pi_{|V_s^l}^k$ is a homeomorphism between $V_s^l$ and $V_s$, we obtain that

$$ (\pi^k)^{-1}(s) = \{y_s^l : l \in K\} $$

for some $y_s^l \in V_s^l$, $l \in K$. Also, from Property (v) of local degree (see Appendix 4.2), we obtain that $\text{deg}(\pi_{|V_s^l}^k)$ is equal to 1 or $-1$ for every $l \in K$. Now, from additivity of the topological degree with respect to local degrees (see Appendix 4.2, Property (vi)) and from Step 4, we obtain (modulo 2) that

$$ \text{deg}(\pi^k) = 1 = \sum_{l \in K} \text{deg}(\pi_{|V_s^l}^k) = \sum_{l \in K} 1 = \text{card}(K) = K_s [2], $$

i.e. that $K_s$ is odd.

Step 9. There exists a generic subset $U^*$ of $U$ such that for every $u \in U^*$, $u$ has an odd number of Nash equilibria.

Applying Step 2 to Step 8 to the sets $Vk$ built in Step 1, we obtain that for every $k \in \{1, \dots, \kappa\}$, there exists a generic semi-algebraic subset $G^k$ of $S^k = \varphi(V^k) = T^k + \varphi(A)$ such that for every $s \in G^k$, the society $u^s = \varphi^{-1}(s)$ has an odd number of Nash equilibria. This implies that for every $s$ in

$$ G := \bigcup_{\substack{k \in \{1, \dots, \kappa\} \\ T^k \text{ is open in } \pi_{-A}(S)}} G^k, $$

the society $u^s = \varphi^{-1}(s)$ has an odd number of Nash equilibria.

To finish, we prove that $G$ is generic in $S$. First, from Step 1, we get that the complement of $G$ in $S$ is included in

$$ \bigcup_{k=1}^{\kappa} (S^k - G^k) \cup \tilde{S}, $$

where

$$ \tilde{S} := \bigcup_{\substack{k \in \{1, \dots, \kappa\} \\ T^k \text{ is not open in } \pi_{-A}(S)}} S^k. $$

Indeed, suppose that $s \in S$ and $s \notin G$. From Step 1, the family $(S^k)_{k=1}^\kappa$ forms a covering of $S$, and as $s \in S$, there exists $l \in \{1, \dots, \kappa\}$ such that $s \in S^l$. As $s \notin G$, (1) either $T^l$ is open in $\pi_{-A}(S)$, and we get $s \notin G^l$, thus $s \in S^l - G^l \subset \bigcup_{k=1}^\kappa (S^k - G^k)$, (2) or $T^l$ is not open in $\pi_{-A}(S)$, and we get $s \in \tilde{S}$, which finally proves the inclusion.

Second, the dimension of $\bigcup_{k=1}^\kappa (S^k - G^k)$ is strictly less than $\dim(S)$, because for every $k \in \{1, \dots, \kappa\}$, $\dim(S^k - G^k) < \dim(S^k) \le \dim(S)$ (the first strict inequality being a consequence of $G^k$ generic in $S^k$). Also, the dimension of $\tilde{S}$ is strictly less than $\dim(S)$, because for every $k \in \{1, \dots, \kappa\}$ such that $T^k$ is not open in $\pi_{-A}(S)$, we get $\dim(T^k) < \dim(\pi_{-A}(S))$ (see the reminders about semi-algebraic sets and
in particular Definition 4.3). This implies that

$$
\begin{align*}
\dim(S^k) &= \dim(T^k + \varphi(\mathcal{A})) \\
&= \dim(T^k) + \dim(\varphi(\mathcal{A})) \quad (\text{since } \operatorname{span}(T^k) \text{ and } \varphi(\mathcal{A}) \text{ are in direct sum}) \\
&< \dim(\pi_{-\mathcal{A}}(S)) + \dim(\varphi(\mathcal{A})) \\
&= \dim(\pi_{-\mathcal{A}}(S) + \varphi(\mathcal{A})) \quad (\text{since } \operatorname{span}(\pi_{-\mathcal{A}}(S)) \text{ and } \varphi(\mathcal{A}) \text{ are in direct sum}) \\
&= \dim(\varphi(\hat{\pi}_{-\mathcal{A}}(\mathcal{U})) + \varphi(\mathcal{A})) \\
&= \dim(\varphi(\hat{\pi}_{-\mathcal{A}}(\mathcal{U}) + \mathcal{A})) \\
&= \dim(\varphi(\mathcal{U})) \quad (\text{since from } \mathcal{U} + \mathcal{A} = \mathcal{U} \text{ we get } \hat{\pi}_{-\mathcal{A}}(\mathcal{U}) + \mathcal{A} = \mathcal{U}) \\
&= \dim(S)
\end{align*}
$$

Finally, this proves that dimension of the complement of G in S is strictly less than the dimension of S.

Third, G is open in S, since for every $k \in \{1, \dots, \kappa\}$ such that $T^k$ is open in $\pi_{-A}(S)$, $G^k$ is open in $S$ (indeed, $G^k$ is open in $S^k$, from $G^k$ generic in $S^k$, and $S^k$ is open<fnref n="15" /> in $S$).

Finally, by definition, the set $\mathcal{U}^* := \varphi^{-1}(G)$ is generic in $\mathcal{U}$ and for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria, which ends Step I.

Now, in Step II below, we prove Theorem 3.1 when $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}[x] \cap \mathcal{F}$ instead of $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x] \cap \mathcal{F}$, and when stability assumption is replaced by the assumption that $\dim(\varphi(\mathcal{U} + \mathcal{A})) = \dim(\varphi(\mathcal{U}))$.

Step II. Consider $\mathcal{U} \subset \prod_{i \in N} \mathbb{R}_{\delta_i}[x] \cap \mathcal{F}$ which satisfies semi-algebraicity assumption, and such that $\dim(\varphi(\mathcal{U} + \mathcal{A})) = \dim(\varphi(\mathcal{U}))$. Then, there exists a generic subset $\mathcal{U}^*$ of $\mathcal{U}$ such that for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria.

The idea is to apply Step I to the set $\mathcal{U} + \mathcal{A}$. To do that, we first have to prove that $\mathcal{U} + \mathcal{A}$ satisfies semi-algebraicity assumption, which is true because $\varphi(\mathcal{U} + \mathcal{A}) = \varphi(\mathcal{U}) + \varphi(\mathcal{A})$ and both $\varphi(\mathcal{U})$ and $\varphi(\mathcal{A})$ are semi-algebraic. We also have to prove that $(\mathcal{U} + \mathcal{A}) + \mathcal{A} = \mathcal{U} + \mathcal{A}$ which is a consequence of $\mathcal{A} + \mathcal{A} = \mathcal{A}$. From Step I, there exists a generic subset $\mathcal{G}$ of $\mathcal{U} + \mathcal{A}$ (which means that $\dim(\varphi(\mathcal{U} + \mathcal{A}) - \varphi(\mathcal{G})) < \dim(\varphi(\mathcal{U} + \mathcal{A}))$, and that $\varphi(\mathcal{G})$ is open in $\varphi(\mathcal{U} + \mathcal{A})$ such that for every $u \in \mathcal{G}$, the game $u$ has an odd number of Nash equilibria. Now, let $\mathcal{U}^* = \mathcal{U} \cap \mathcal{G}$. In particular, for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria.

Finally, remark that the set $\mathcal{U}^*$ is generic in $\mathcal{U}$. Indeed,

$$ \varphi(\mathcal{U}) - \varphi(\mathcal{U}^*) = \varphi(\mathcal{U}) - \varphi(\mathcal{U} \cap \mathcal{G}) \subset \varphi(\mathcal{U} + \mathcal{A}) - \varphi(\mathcal{G}), $$

so that $\dim(\varphi(\mathcal{U}) - \varphi(\mathcal{U}^*)) \le \dim(\varphi(\mathcal{U} + \mathcal{A}) - \varphi(\mathcal{G}))$. Now, since $\dim(\varphi(\mathcal{U} + \mathcal{A}) - \varphi(\mathcal{G})) < \dim(\varphi(\mathcal{U} + \mathcal{A}))$ (from genericity of $\mathcal{G}$ in $\mathcal{U} + \mathcal{A}$) and since $\dim(\varphi(\mathcal{U} + \mathcal{A})) = \dim(\varphi(\mathcal{U}))$ (by assumption), we get that $\dim(\varphi(\mathcal{U}) - \varphi(\mathcal{U}^*)) < \dim(\varphi(\mathcal{U}))$. Moreover, $\varphi(\mathcal{U}^*)$ is open in $\varphi(\mathcal{U})$: indeed, $\mathcal{U}^* = \mathcal{U} \cap \mathcal{G}$, thus $\varphi(\mathcal{U}^*) = \varphi(\mathcal{U}) \cap \varphi(\mathcal{G})$. But $\varphi(\mathcal{G})$ is open in $\varphi(\mathcal{U} + \mathcal{A})$ (from genericity of $\mathcal{G}$ in $\mathcal{U} + \mathcal{A}$) and $\varphi(\mathcal{U}) \subset \varphi(\mathcal{U} + \mathcal{A})$, which implies that $\varphi(\mathcal{U}) \cap \varphi(\mathcal{G})$ is open in $\varphi(\mathcal{U})$. This ends the proof of Step II.

Now, we can prove our general oddness theorem (in particular, in Step III, $\mathcal{U} \subset \mathcal{F} \cap \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x]$). The idea is to apply Step II to the set $\mathcal{U} + \mathcal{C}^n$, where $\mathcal{C}^n$ denotes the set of constant profiles of payoff functions.

Step III. Oddness theorem: for every regular subset $\mathcal{U}$ of $\mathcal{F}$, there exists a generic subset $\mathcal{U}^*$ of $\mathcal{U}$ such that for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria.

<footnote n="15">¹⁵Since $\varphi$ is a homeomorphism, to prove that $S^k = \varphi(\mathcal{V}^k)$ is open in $S = \varphi(\mathcal{U})$, we only have to prove that $\mathcal{V}^k = \varphi^{-1}(T^k) + \mathcal{A}$ is open in $\mathcal{U}$. To prove that, remark that for every $k \in \{1, \dots, \kappa\}$ such that $T^k$ is open in $\pi_{-\mathcal{A}}(S)$, and since $\varphi$ is a homeomorphism, we get that $\varphi^{-1}(T^k)$ is open in $\varphi^{-1}(\pi_{-\mathcal{A}}(S))$. Thus, as $\varphi^{-1} \circ \pi_{-\mathcal{A}} = \hat{\pi}_{-\mathcal{A}} \circ \varphi^{-1}$, we obtain that $\varphi^{-1}(T^k)$ is open in $\hat{\pi}_{-\mathcal{A}}(\varphi^{-1}(S)) = \hat{\pi}_{-\mathcal{A}}(\mathcal{U})$. This finally implies that $\varphi^{-1}(T^k) + \mathcal{A}$ is open in $\hat{\pi}_{-\mathcal{A}}(\mathcal{U}) + \mathcal{A}$, which is equal to $\mathcal{U}$ (from $\mathcal{U} + \mathcal{A} = \mathcal{U}$).</footnote>
By definition, $\mathbb{R}_{\delta_i}^0[x]$ is the linear subspace of $\mathbb{R}_{\delta_i}[x]$ generated by all the monomials in $\mathbb{R}_{\delta_i}[x]$, except the one in $\mathcal{C}$, i.e.

$$ \mathbb{R}_{\delta_i}^0[x] = \operatorname{span}(\{x^k : k \in \mathbb{N}^\Lambda, \deg(k) \le \delta_i\} - \{1\}). $$

Remark that $\mathbb{R}_{\delta_i}[x] = \mathbb{R}_{\delta_i}^0[x] \oplus \mathcal{C}$ and $\prod_{i \in N} \mathbb{R}_{\delta_i}[x] = \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x] \oplus \mathcal{C}^n$, thus $\varphi_i(\mathbb{R}_{\delta_i}[x]) = \mathbb{R}^{m_i} = \varphi_i(\mathbb{R}_{\delta_i}^0[x]) \oplus \varphi_i(\mathcal{C})$ and $\varphi(\prod_{i \in N} \mathbb{R}_{\delta_i}[x]) = \mathbb{R}^m = \varphi(\prod_{i \in N} \mathbb{R}_{\delta_i}^0[x]) \oplus \varphi(\mathcal{C}^n)$. Moreover, denote $\hat{\pi}_{-\mathcal{C}^n}$ the linear projection from $\prod_{i \in N} \mathbb{R}_{\delta_i}[x] = \prod_{i \in N} \mathbb{R}_{\delta_i}^0[x] \oplus \mathcal{C}^n$ to $\prod_{i \in N} \mathbb{R}_{\delta_i}^0[x]$ and $\pi_{-\mathcal{C}^n}$ the linear projection from $\prod_{i \in N} \varphi(\mathbb{R}_{\delta_i}[x]) = \prod_{i \in N} \varphi(\mathbb{R}_{\delta_i}^0[x]) \oplus \varphi(\mathcal{C}^n)$ to $\prod_{i \in N} \varphi(\mathbb{R}_{\delta_i}^0[x])$ (in particular, $\varphi \circ \hat{\pi}_{-\mathcal{C}^n} = \pi_{-\mathcal{C}^n} \circ \varphi$). Now, notice that the set $\mathcal{U} + \mathcal{C}^n$ satisfies semi-algebraicity assumption, and is such that:

$$ \begin{aligned} \dim(\varphi[(\mathcal{U} + \mathcal{C}^n) + \mathcal{A}]) &= \dim(\varphi[(\mathcal{U} + \mathcal{C}^n) + (\mathcal{L} + \mathcal{C}^n)]) & (\text{as } \mathcal{A} = \mathcal{L} + \mathcal{C}^n) \\ &= \dim(\varphi[(\mathcal{U} + \mathcal{L}) + \mathcal{C}^n]) \\ &= \dim(\varphi(\mathcal{U} + \mathcal{L}) + \varphi(\mathcal{C}^n)) \\ &= \dim(\varphi(\mathcal{U} + \mathcal{L})) + \dim(\varphi(\mathcal{C}^n)) & (\text{since } \mathcal{U} + \mathcal{L} \subset \mathbb{R}_{\delta_i}^0[x]) \\ &= \dim(\varphi(\mathcal{U})) + \dim(\varphi(\mathcal{C}^n)) & (\text{since by assumption, } \dim(\varphi(\mathcal{U} + \mathcal{L})) = \dim(\varphi(\mathcal{U}))) \\ &= \dim(\varphi(\mathcal{U}) + \varphi(\mathcal{C}^n)) & (\text{since } \mathcal{U} \subset \mathbb{R}_{\delta_i}^0[x]) \\ &= \dim(\varphi(\mathcal{U} + \mathcal{C}^n)). \end{aligned} $$

Thus, from Step II, there exists a generic subset $\mathcal{G}$ of $\mathcal{U} + \mathcal{C}^n$ (which means that $\varphi(\mathcal{G})$ is generic in $\varphi(\mathcal{U} + \mathcal{C}^n)$) such that for every $u \in \mathcal{G}$, the game $u$ has an odd number of Nash equilibria.

To finish, we simply define $\mathcal{U}^* := \hat{\pi}_{-\mathcal{C}^n}(\mathcal{G})$. In particular, for every $u \in \mathcal{U}^*$, the game $u$ has an odd number of Nash equilibria (indeed, for every game $u = (u_1, \dots, u_n)$ and every $c = (c_1, \dots, c_n) \in \mathcal{C}^n$, the set $\mathcal{N}(u)$ of Nash equilibria of $u$ and the set $\mathcal{N}(u+c)$ of Nash equilibria of $u+c$ are the same). Thus, we only have to prove that $\mathcal{U}^*$ is a generic subset of $\mathcal{U}$, or equivalently (by definition) that $\varphi(\mathcal{U}^*) = \varphi(\hat{\pi}_{-\mathcal{C}^n}(\mathcal{G})) = \pi_{-\mathcal{C}^n}(\varphi(\mathcal{G}))$ is a generic subset of $\varphi(\mathcal{U})$. To prove that, first notice that $\hat{\pi}_{-\mathcal{C}^n}(\mathcal{G}) \subset \mathcal{U}$, since $\mathcal{U} \subset \mathbb{R}_{\delta_i}^0[x]$. Second, we know that $\varphi(\mathcal{G})$ is generic in $\varphi(\mathcal{U} + \mathcal{C}^n) = \varphi(\mathcal{U}) + \varphi(\mathcal{C}^n)$. Thus to finish the proof, we can simply apply the following lemma to $E = \varphi(\prod_{i \in N} \mathbb{R}_{\delta_i}^0[x])$, $F = C = \varphi(\mathcal{C}^n)$, $B = \varphi(\mathcal{U})$, and $A = \varphi(\mathcal{G})$.

**Lemma 4.1.** Let E and F be two finite-dimensional vector subspaces of $\mathbb{R}^p$ such that $E \cap F = \{0\}$. If A is a semi-algebraic set generic in $B+C$, where B is a semi-algebraic subset of E and C is a semi-algebraic subset of F, then $\pi_E(A)$ is generic in B.

**Proof.** Consider on E and F the topology induced by the restrictions of the Euclidean norm on $\mathbb{R}^p$.

First, $\pi_E(A)$ is semi-algebraic from Tarski-Seidenberg.

Second, let us prove that $\pi_E(A)$ is open in B. If $b \in \pi_E(A)$, then there exists $a \in A$ such that $b = \pi_E(a)$, and from the definition of A, there exists $c \in C$ such that $a = b + c$. Since A is open in $B+C$ (because it is generic in $B+C$), there exists a neighborhood $V_a \subset A$ of a in $B+C$. Consider the mapping $\psi : (e, f) \in E \times F \mapsto e + f \in \mathbb{R}^p$. Since it is continuous at $(b, c)$, for every neighborhood $V_a$ of $a = \psi(b, c)$ (and in particular for $V_a$ fixed before), there exists a neighborhood $V$ of $(b, c)$ such that $\psi(V) \subset V_a$. Since the sets of all $V_e \times V_f$ (where $V_e$ is any neighborhood of any $e \in E$ and $V_f$ any neighborhood of any $f \in F$) are a neighborhood basis of the product topology on $E \times F$, there exists $V_b$ and $V_c$ some neighborhoods of b and c such that $V_b \times V_c \subset V$, so that we have $\psi(V_b \times V_c) \subset V_a$, that is to say $V_b + V_c \subset V_a$. In particular, $V_b$ is a neighborhood of b included in $\pi_E(A)$ (because for every $b' \in V_b$, $a' := b' + c \in V_b + V_c \subset V_a \subset A$, thus $\pi_E(a') = b'$, which implies that $b' \in \pi_E(A)$).

Third, let us prove that $\dim(B - \pi_E(A)) < \dim(B)$. Otherwise, from property 4. in Proposition 4.4, there would exist $b \in B - \pi_E(A)$ and $\varepsilon > 0$ such that $B(b, \varepsilon) \subset B - \pi_E(A)$, where $B(b, \varepsilon)$ is an open ball in B centered at b and such that $\dim(B(b, \varepsilon)) = \dim(B)$. This would imply that $B(b, \varepsilon) + C \subset (B+C) - A$ (indeed, by contradiction, if there exists $b' \in B(b, \varepsilon)$ and $c \in C$ such that $a' := b' + c \in A$, then by definition we have $\pi_E(a') = b'$, that is $b' \in \pi_E(A)$, a contradiction with $b' \in B(b, \varepsilon) \subset B - \pi_E(A)$). In particular $\dim((B+C) - A) = \dim(B+C)$ (indeed, $\dim((B+C) - A) \ge \dim(B+C)$ because $B(b, \varepsilon) + C$ is a subset of $(B+C) - A$ whose dimension is equal to $\dim(B(b, \varepsilon) + C) = \dim(B(b, \varepsilon)) + \dim(C) = \dim(B) + \dim(C) = \dim(B+C)$), which is a contradiction with A generic in $B+C$.
REFERENCES

[1] Dold Albrecht. *Lectures on algebraic topology*. Die Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin New York Heidelberg, 1972.

[2] Philippe Bich and Julien Fixary. Structure and oddness theorems for pairwise stable networks. *halshs-03287524*, July 2021.

[3] Lawrence E. Blume and William R. Zame. The algebraic geometry of perfect and sequential equilibrium. *Econometrica*, 62(4):783–794, 1994.

[4] J. Bochnak, M. Coste, and M-F. Roy. *Real Algebraic Geometry*. Springer, 1998.

[5] Antoni Calvó-Armengol, Eleonora Patacchini, and Yves Zenou. Peer effects and social networks in education. *The Review of Economic Studies*, 76(4):1239–1267, 2009.

[6] Srihari Govindan and Andrew McLennan. On the generic finiteness of equilibrium outcome distributions in game forms. *Minnesota - Center for Economic Research, Papers*, 69, 01 1997.

[7] Srihari Govindan and Robert Wilson. Direct Proofs of Generic Finiteness of Nash Equilibrium Outcomes. *Econometrica*, 69(3):765–769, May 2001.

[8] John Harsanyi. Oddness of the number of equilibrium points: A new proof. *International Journal of Game Theory*, 2:235–250, 1973.

[9] Robert W. Helsley and Yves Zenou. Social networks and interactions in cities. *Journal of Economic Theory*, 150(C):426–466, 2014.

[10] P.J.J. Herings and R.J.A.P. Peeters. A differentiable homotopy to compute nash equilibria of n-person games. Research Memorandum 033, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR), January 2000.

[11] Matthew O. Jackson and Yves Zenou. Games on networks. In *Handbook of Game Theory with Economic Applications*, volume 4, chapter 3, pages 95–163. Elsevier, 2015.

[12] Elon Kohlberg and Jean-François Mertens. On the strategic stability of equilibria. *Econometrica*, 54(5):1003–1037, 1986.

[13] Michael D. König, Xiaodong Liu, and Yves Zenou. R&D Networks: Theory, Empirics, and Policy Implications. *The Review of Economics and Statistics*, 101(3):476–491, July 2019.

[14] Andreu Mas-Colell. Generic finiteness of equilibrium payoffs for bimatrix games. *Journal of Mathematical Economics*, 46:382–383, 07 2008.

[15] Eleonora Patacchini and Yves Zenou. Juvenile delinquency and conformism. *Journal of Law, Economics, and Organization*, 28(1):1–31, 2012.

[16] Carlos Pimienta. Generic Determinacy of Nash Equilibrium in Network Formation Games. Discussion Papers 2007-31, School of Economics, The University of New South Wales, October 2007.

[17] A. Predtetchinski. A general structure theorem for the nash equilibrium correspondence. Research Memorandum 023, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR), January 2004.

[18] Arkadi Predtetchinski. A general structure theorem for the nash equilibrium correspondence. *Games and Economic Behavior*, 66(2):950–958, 2009. Special Section In Honor of David Gale.

[19] R. Wilson. Computing equilibria of n-person games. *Siam Journal on Applied Mathematics*, 21:80–87, 1971.