# Structure and oddness theorems for pairwise stable networks

Philippe Bich, Julien Fixary

► To cite this version:

Philippe Bich, Julien Fixary. Structure and oddness theorems for pairwise stable networks. 2021. halshs-03287524

HAL Id: halshs-03287524

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

Submitted on 15 Jul 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CES

Centre d'Économie de la Sorbonne
UMR 8174

Structure and Oddness Theorems
for Pairwise Stable Networks

Philippe BICH, Julien FIXARY

2021.16
STRUCTURE AND ODDNESS THEOREMS
FOR PAIRWISE STABLE NETWORKS

PHILIPPE BICH* AND JULIEN FIXARY†

7th June 2021

Abstract

We determine the topological structure of the graph of pairwise stable weighted networks.
As an application, we obtain that for large classes of polynomial payoff functions, there exists
generically an odd number of pairwise stable networks. This improves the results in Bich
and Morhaim ([5]) or in Herings and Zhan ([14]), and can be applied to many existing
models, as for example to the public good provision model of Bramoullé and Kranton ([8]),
the information transmission model of Calvó-Armengol ([9]), the two-way flow model of
Bala and Goyal ([2]), or Zenou-Ballester's key-player model ([3]).

KEYWORDS: Weighted Networks, Pairwise Stable Networks Correspondence, Generic Oddness.

JEL CLASSIFICATION: 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

Pairwise stability concept, proposed in Jackson and Wolinsky ([16]), plays a central role in strategic network formation models. First introduced for unweighted networks, it was then extended for weighted networks (i.e. networks for which relationships are measured by real numbers between 0 and 1), and recently, it was proved that a pairwise stable weighted network exists for large classes of payoff functions (see Bich and Morhaim [4, 5]).

Roughly, a network is pairwise stable if “no two agents could gain from linking and no single agent could gain by severing one of his or her link” (see [16]). A frequently mentioned issue in network formation literature is the too large number of pairwise stable networks, which can be a problem because it prevents the use of comparative statics analysis. Thus, it seems quite important to study the question of the number of pairwise stable networks.

In game theory, this question has been intensively studied for Nash equilibria: for example, several papers have proved generic finiteness and oddness of the set of mixed Nash equilibria of finite games (e.g. [6, 11, 12, 18, 10, 19, 15, 21]).

The aim of this paper is twofold:

1. First, we characterize the topological structure of the graph of pairwise stable networks $\mathcal{P}$, formally the set of all pairs $(v, g)$, where $v = (v_1, ..., v_n)$ is a profile of payoffs functions of $n$ agents involved in the network, and $g$ is a pairwise stable network associated to $v$. Under mild assumptions, we prove that $\mathcal{P}$ is homeomorphic to the set of profiles of payoff functions. This result is similar to Kohlberg-Mertens theorem ([17]), but for pairwise stable networks, instead of Nash equilibria.<fnref n="1" />

2. Second, we prove that for large classes of polynomial payoff functions, there exists generically an odd number of pairwise stable networks.<fnref n="2" /> There exist some analogous results for Nash equilibria ([11, 21, 12, 6, 18, 10]), but, to our knowledge, they apply only to affine payoff functions.

To get an idea of our two main results, first consider the following example, introduced in Bich-Morhaim ([5]): three researchers are labeled in $N = \{1, 2, 3\}$. For every $i \in N$ and every $j \neq i$, researchers $i$ and $j$ write a paper together, and we call $x_{ij} \in [0, 1]$ the (normalized) amount of time spent together by $i$ and $j$ on their common project. Assume $u_1(x_{12}, x_{13}, x_{23}) = x_{12} + x_{13} - c_{12}x_{12}^2 - c_{13}x_{13}^2$: the linear term captures that

<footnote n="1">¹Kohlberg-Mertens theorem states that the graph of the mixed Nash equilibrium correspondence, if defined on the space of finite games, is homeomorphic to the space of finite games. Predtetchinsky ([20]) generalizes this result for more general payoff functions than those involved in mixed extensions of finite games.</footnote>

<footnote n="2">²A recent work of Herings and Zhan ([14]) provides the same result for affine payoff functions, using homotopy methods.</footnote>
$u_1$ is increasing with respect to the total amount of work of 1, and the quadratic term measures the cost of working on the different projects. The payoff functions are assumed to be similar for researchers 2 and 3: $u_2(x_{12}, x_{13}, x_{23}) = x_{12} + x_{23} - c_{21}x_{12}^2 - c_{23}x_{23}^2$ and $u_3(x_{12}, x_{13}, x_{23}) = x_{13} + x_{23} - c_{31}x_{13}^2 - c_{32}x_{23}^2$. The optimal amounts of time for $i$ are $\bar{x}_{ij} = \min\{\frac{1}{2c_{ij}}, 1\}$ for all $j \neq i$, and it is easy to see that the unique pairwise stable weighted network is $\bar{x}_{ij}(c) = \min\{1, \frac{1}{2\max\{c_{ij}, c_{ji}\}}\}$, where $c = (c_{12}, c_{13}, c_{23}) \in (0, +\infty)^3$ and $ij$ is equal to $\{1, 2\}$, $\{1, 3\}$ or $\{2, 3\}$.

Each profile of payoff functions can be represented by $c \in (0, +\infty)^3$, thus, denoting $\bar{g}(c)$ the pairwise stable network associated to $c$, the graph of pairwise stable networks can be written

$$ \mathcal{P} = \{(c, \bar{g}(c)) : c \in (0, +\infty)^3\}, $$

and it is clearly homeomorphic to the set $(0, +\infty)^3$ of profile of payoff functions, the homeomorphism being the projection on the first factor. Our first main result (Structure Theorem 2.1) is a generalization of this example.

To illustrate our second main result, suppose now that the payoffs of the three researchers are equal to $u(x_{12}, x_{13}, x_{23}) = -x_{12}x_{13}x_{23} - c(x_{12} + x_{13} + x_{23})$, for some parameter $c \ge 0$. For every $c > 0$, $(0, 0, 0)$ is the unique pairwise stable network. But for $c = 0$, there is an infinite number of pairwise stable networks (since any network for which two links have weights equal to zero is pairwise stable). Thus, there is a finite number of pairwise stable networks for all parameters $c \ge 0$ except for $c = 0$. Our second result (Oddness Theorem 3.3) is a generalization of this example: we prove that for large classes of profiles of payoff functions, there is generically an odd number of pairwise stable networks (which means intuitively that the situations for which the number of pairwise stable networks is even or infinite are exceptional).

We describe several standard models in network formation literature to which our Oddness Theorem can be applied: the public good provision model of Bramoullé and Kranton ([8]), the information transmission model of Calvó-Armengol ([9]), the two-way flow model of Bala and Goyal ([2]), or Zenou-Ballester's key-player model ([3]).

Our paper is organized as follows: in Section 2, we first recall notations and basic facts about pairwise stability (Subsection 2.1), we define the graph of pairwise stable networks (Subsection 2.2) and we state our first main structure theorem (Subsection 2.3). In Section 3, after some reminders about real algebraic geometry and algebraic topology (Subsection 3.1), we state generic finiteness and oddness of the set of pairwise stable networks (Subsection 3.2). Then, several examples are given (Subsection 3.3).
# 2 STRUCTURE OF THE GRAPH OF PAIRWISE STABLE NETWORKS

## 2.1 REMINDERS ABOUT PAIRWISE STABILITY

Throughout this paper,<fnref n="3" /> we fix some integer $n \ge 2$, and we define $N = \llbracket 1, n \rrbracket$, called the set of agents. The set $L = \{\{i, j\} : (i, j) \in N^2, i \neq j\}$ denotes the set of links on $N$ and $G = [0, 1]^L$ the set of (weighted) networks on $N$. We now define a society, which is a $n$-tuple of payoff functions (one for each agent) defined on the set of all possible networks on $N$.

**Definition 2.1.** A society is an element $v = (v_1, \dots, v_n) \in \mathcal{F}(G, \mathbb{R})^n$, where each mapping $v_i$ is called the payoff function of agent $i \in N$.

**Notations.** Every link $\{i, j\} \in L$ is denoted $ij$. For every network $g$ and every $ij \in L$, the element $g_{\{i,j\}}$ is simply denoted $g_{ij}$. For every $ij \in L$, we denote $L_{-ij} = L - ij$ (i.e $L_{-ij} = \{kl \in L : kl \neq ij\}$) and $G_{-ij} = [0, 1]^{L_{-ij}}$. For every $ij \in L$, every network $g_{-ij} \in G_{-ij}$ and every $w \in [0, 1]$, $g' = (w, g_{-ij}) \in G$ is the network defined by $g'_{kl} = g_{kl}$ for every $kl \neq ij$ and $g'_{ij} = w$. For every network $g \in G$ and every $ij \in L$, $g_{-ij} \in G_{-ij}$ is defined as $g_{-ij} = (g_{kl})_{kl \neq ij}$.

We now recall the seminal concept of pairwise stability, introduced by Jackson and Wolinsky ([16]) for unweighted societies,<fnref n="4" /> and extended by Bich and Morhaim for weighted societies (see [4], [5]).

**Definition 2.2.** A network $g \in G$ is pairwise stable with respect to a society $v = (v_1, \dots, v_n)$ if for every $ij \in L$, the two following conditions hold:

1. For every $w \in [0, g_{ij})$, $v_i(w, g_{-ij}) \le v_i(g)$ and $v_j(w, g_{-ij}) \le v_j(g)$.

2. For every $w \in (g_{ij}, 1]$, $v_i(w, g_{-ij}) \le v_i(g)$ or $v_j(w, g_{-ij}) \le v_j(g)$.

The set of pairwise stable networks of the society $v$ is denoted $P(v)$.

<footnote n="3">³Let us recall some mathematical definitions or notations used in this paper: for every sets $X$ and $Y$, $\mathcal{F}(X, Y)$ denotes the set of functions from $X$ to $Y$. For every finite set $X$, $\text{card}(X)$ (or sometimes $|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$. For every $g \in G$, the Euclidean norm $\|g\|$ of $g$ is defined by $\|g\| = \sqrt{\sum_{ij \in L} g_{ij}^2}$. 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 space $X$ and $Y$, a homotopy from a continuous function $f: X \to Y$ to another continuous function $g: X \to Y$ is a continuous function $H: [0, 1] \times X \to Y$ such that $H(0, \cdot) = f(\cdot)$ and $H(1, \cdot) = g(\cdot)$. We say that: (1) $f$ and $g$ are homotopic if there exists a homotopy $H$ 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$. A function $f: G \to \mathbb{R}$ is said to be polynomial if $f$ is a polynomial function of the weights $g_{ij}$ of $g$.</footnote>

<footnote n="4">⁴By definition, the set of unweighted networks is $G_u = \{0, 1\}^L$ and an unweighted society is a $n$-tuple $v = (v_1, \dots, v_n) \in \mathcal{F}(G_u, \mathbb{R})^n$.</footnote>
## 2.2 GRAPH OF PAIRWISE STABLE NETWORKS

The payoff functions considered in this paper satisfy some concavity assumption: more precisely, for every $i \in N$, let

$$ \mathcal{F}_i = \{v_i \in \mathcal{C}^0(\mathbb{G}, \mathbb{R}) : \forall j \neq i, \forall g_{-ij} \in \mathbb{G}_{-ij}, g_{ij} \mapsto v_i(g_{ij}, g_{-ij}) \text{ is concave and } \mathcal{C}^1 \text{ on } [0, 1]\} $$

and $\mathcal{F} = \prod_{i \in N} \mathcal{F}_i$. Here, a function $f : [0, 1] \to \mathbb{R}$ is said to be $\mathcal{C}^1$ if it is continuous on $[0, 1]$, $\mathcal{C}^1$ on $]0, 1[$, $f^{-}(0)$ and $f^{+}(1)$ (the left and right derivative of $f$ at 0 and 1) exist, and if $\lim_{x \to 0} f'(x) = f^{-}(0)$ and $\lim_{x \to 1} f'(x) = f^{+}(1)$.

For every $i \in N$, the set $\mathcal{F}_i$ is endowed with the norm<fnref n="5" />

$$ \|v_i\|_i = \max\{\max\{\|v_i\|_{\infty}, \|\partial_{ij}v_i\|_{\infty}\} : j \neq i\} $$

and $\mathcal{F}$ with the product norm. Here, $\partial_{ij}v_i$ denotes the function from $\mathbb{G}$ to $\mathbb{R}$ defined by

$$ \forall g = (g_{ij}, g_{-ij}) \in \mathbb{G}, \quad \partial_{ij}v_i(g) = \frac{\partial v_i}{\partial g_{ij}}(g_{ij}, g_{-ij}). $$

**Definition 2.3.** The pairwise stable networks correspondence (or PSN correspondence) is the correspondence

$$ \left\{ \begin{array}{rcl} P: & \mathcal{F} & \to \mathbb{G} \\ & v & \mapsto P(v) \end{array} \right. $$

and the graph of the PSN correspondence (sometimes called simply the *graph of pairwise stable networks*) is defined by

$$ \mathcal{P} := \mathrm{Gr}(P) = \{(v, g) \in \mathcal{F} \times \mathbb{G} : g \in P(v)\}. $$

We endow $\mathcal{P}$ with the following product norm

$$ \|(v, g)\| = \max\{\max\{\|v_i\|_i : i = 1, \dots, n\}, \|g\|\} $$

where $\|g\|$ denotes the Euclidean norm of $g$. We denote the projection from $\mathcal{P}$ to $\mathcal{F}$ by $\pi$, i.e. $\pi(v, g) = v$ for every $(v, g) \in \mathcal{F} \times \mathbb{G}$.

## 2.3 THE STRUCTURE THEOREM

In this section, we determine the topological structure of $\mathcal{P}$, the graph of pairwise stable networks:

<footnote n="5">⁵This norm is defined on the vector space $\{v_i \in \mathcal{C}^0(\mathbb{G}, \mathbb{R}) : \forall j \neq i, \forall g_{-ij} \in \mathbb{G}_{-ij}, v_i(\cdot, g_{-ij}) \text{ is } \mathcal{C}^1 \text{ on } [0, 1]\}$.</footnote>
**Theorem 2.1.** (Structure Theorem)

The projection mapping $\pi : \mathcal{P} \to \mathcal{F}$ is properly homotopic to some homeomorphism
$\eta : \mathcal{P} \to \mathcal{F}$.

The proof is given in Appendix 4.1. For a similar result applied to mixed Nash equilibria of games, see Kohlberg-Mertens’ structure theorem ([17]), and also a recent generalization due to Predtetchinsky ([20]).

Actually, Corollary 2.1 proves 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 N$, let

$$
\mathcal{A}_i = \{ g \in \mathbb{G} \mapsto \sum_{j \neq i} \alpha_{ij} g_{ij} + c : (\alpha_{ij})_{j \neq i} \in \mathbb{R}^{n-1}, c \in \mathbb{R} \},
$$

that is to say, $v_i \in \mathcal{A}_i$ if $v_i$ is affine and does not depend on $g_{-ij}$, for every $j \neq i$. In
particular, $\mathcal{A}_i \subset \mathcal{F}_i$. For every subset $\mathcal{U}$ of $\mathcal{F}$, we define

$$
\mathcal{P}_U := \{(v, g) \in \mathcal{P} : v \in \mathcal{U}\}
$$

and we consider $\pi|_{\mathcal{P}_U}$ the restriction of $\pi$ to $\mathcal{P}_U$, that is to say

$$
\forall (v, g) \in \mathcal{P}_U, \pi|_{\mathcal{P}_U}(v, g) = v.
$$

Similarly, $\eta|_{\mathcal{P}_U}$ denotes the restriction of $\eta$ (the mapping defined in the above theorem)
to $\mathcal{P}_U$.

**Corollary 2.1.** For every $i \in N$, consider $\mathcal{U}_i \subset \mathcal{F}_i$ such that for every $v_i \in \mathcal{U}_i$ and every $A_i \in \mathcal{A}_i$, $v_i + A_i \in \mathcal{U}_i$, and let $\mathcal{U} = \prod_{i \in N} \mathcal{U}_i$. Then, $\eta|_{\mathcal{P}_U} : \mathcal{P}_U \to \mathcal{U}$ is a homeomorphism which is properly homotopic to $\pi|_{\mathcal{P}_U} : \mathcal{P}_U \to \mathcal{U}$.

The proof is given in Appendix 4.3.

3 GENERIC FINITENESS AND ODDNESS OF THE GRAPH OF
PAIRWISE STABLE NETWORKS

3.1 REMINDERS ABOUT REAL ALGEBRAIC GEOMETRY AND
ALGEBRAIC TOPOLOGY

Let us first recall the definition of a semi-algebraic subset of $\mathbb{R}^m$ and of a semi-algebraic
mapping (see Bochnak [7]).
**Definition 3.1.** 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$.

Thus, by definition, semi-algebraic sets are closed under finite unions and finite intersections. Actually, these sets are also closed under projections, a consequence of Tarski-Seidenberg principle:

**Proposition 3.1.** 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$.

From this result, we can also define semi-algebraic sets using quantified variables (or $m$-tuples of variables) which range in $\mathbb{R}$, $\mathbb{R}^m$ or more generally in a semi-algebraic set (for example, see Bochnak [7], p. 28).

**Definition 3.2.** 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 3.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 3.3.** 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$.

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 [7], Theorem 2.3.6. p. 33 and Corollary 2.8.9., p. 53).

**Definition 3.4.** 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$).

Then, we have the following properties:

**Proposition 3.3.** 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)$.

**Definition 3.5.** 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 3.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 [7], p. 224):

**Theorem 3.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$^6$ over each semi-algebraically connected component$^7$ of $T_0$.

<footnote>$^6$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>$^7$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 [7], Theorem 2.4.5., p. 35).</footnote>
Now, 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 $\mathcal{K}$. In particular, $C_0 \times \mathcal{K}$ and $f^{-1}(C_0)$ are semi-algebrically homeomorphic, thus we obtain that

$$ \dim(C_0 \times \mathcal{K}) = \dim(C_0) + \dim(\mathcal{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 $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 $\mathcal{K}$ (indeed, $\mathcal{K}$ is semi-algebraically homeomorphic to $\{t_0\} \times \mathcal{K}$ and $\theta_{\{t_0\} \times \mathcal{K}}$ is a semi-algebraic homeomorphism from $\{t_0\} \times \mathcal{K}$ to $f^{-1}(t_0)$). In particular, $\dim(f^{-1}(t_0)) = \dim(\mathcal{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 [7], Theorem 2.3.6.) with the same cardinal as $\mathcal{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 \mathcal{K}$, we easily get that:

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

2. For every $k \in \mathcal{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. $\square$

## 3.2 THE ODDNESS THEOREM

In this section, we prove that for some large classes of polynomial payoff functions (which we call regular), we obtain the generic oddness of the set of pairwise stable networks. From now, we denote by $\mathbb{R}[g]$ the set of polynomial functions from $\mathbb{G}$ to $\mathbb{R}$, and we denote by $\mathbb{R}_{\delta}[g]$ the vector space of polynomial functions whose degree is less or equal to $\delta \in \mathbb{N}$. We consider on $\mathbb{R}_{\delta}[g]$ the topology induced by the norm defined in Section 2.2 (actually, from the equivalence of norms in finite dimensional spaces, any norm would give the same topology).

For every agent $i \in N$, we consider $U_i$ a subset of $\mathbb{R}_{\delta_i}[g]$ for some fixed integer $\delta_i \in \mathbb{N}$. In particular, any element $v_i \in U_i$ can be expressed as

$$ v_i(g) = \sum_{k \in \mathbb{N}^L} \alpha_k^i g^k $$
where $g \in \mathbb{G}$, $k = (k_{ij})_{ij \in L} \in \mathbb{N}^L$ is a multi-index (with $\alpha_k^i = 0$ if $\deg(k) := \sum_{ij \in L} k_{ij} > \delta_i$) and where $g^k := \prod_{ij \in L} g_{ij}^{k_{ij}}$ is called a monomial. We also recall that for every monomial $g^k \neq 0$, the degree of $g^k$ is by definition equal to $\deg(k)$, and that the degree of $v_i$ is equal to $\max\{\deg(k) : \alpha_k^i \neq 0\}$ (which is equal, by convention, to $-\infty$ when $v_i = 0$).

For example, if we consider three agents and if $v_1(g_{12}, g_{13}, g_{23}) = -g_{12}^2 g_{23} + 3g_{12}g_{13}g_{23}^5 - g_{13}^2 g_{23}$, then we can write $v_1(g) = \alpha_{k_1}^1 g^{k_1} + \alpha_{k_2}^1 g^{k_2} + \alpha_{k_3}^1 g^{k_3}$ with $k_1 = (2, 0, 3)$, $k_2 = (1, 5, 4)$ and $k_3 = (0, 2, 1)$ and with $\alpha_{k_1}^1 = -1$, $\alpha_{k_2}^1 = 3$ and $\alpha_{k_3}^1 = -1$ (in particular, $\deg(v_i) = 10$).

The mapping which associates to every payoff function $v_i \in \mathbb{R}_{\delta_i}[g]$ its coefficients (with respect to some predefined order of the monomials in $\mathbb{R}[g]$) is an isomorphism from $\mathbb{R}_{\delta_i}[g]$ to $\mathbb{R}^{m_i}$ for some integer $m_i$. Let us consider its restriction $\varphi_i : \mathcal{U}_i \to \mathbb{R}^{m_i}$. In particular, for every $i \in N$, $\varphi_i$ is a homeomorphism from $\mathcal{U}_i$ to $\varphi_i(\mathcal{U}_i)$.

In the following, we note $m = \prod_{i \in N} m_i$, $S_i := \varphi_i(\mathcal{U}_i)$, $S = \prod_{i \in N} S_i$ and $\varphi := \times_{i \in N} \varphi_i : \mathcal{U} \to \mathbb{R}^m$. Moreover, for every agent $i \in N$, we consider the subset $A_i$ of $\mathbb{R}[g]$ of affine functions in $(g_{ij})_{j \neq i}$, that is the set of functions $A_i \in A_i$ of the following form

$$A_i(g) = \sum_{j \neq i} \alpha_{ij} g_{ij} + c$$

for every $g \in \mathbb{G}$, where $c \in \mathbb{R}$ and $\alpha_{ij} \in \mathbb{R}$ for every $j \neq i$.

**Definition 3.6.** The set $\mathcal{U} := \prod_{i \in N} \mathcal{U}_i$ is said to be regular if for every $i \in N$, the two following conditions are fulfilled:

1. (Stability assumption) For every $v_i \in \mathcal{U}_i$ and every $A_i \in A_i$, $v_i + A_i \in \mathcal{U}_i$.

2. (Semi-algebraicity assumption) $S_i = \varphi_i(\mathcal{U}_i)$ (the set of coefficients of polynomials in $\mathcal{U}_i$) is a semi-algebraic set.

In the following theorem, proved in Appendix 4.4, for every $x \in S$, we denote by $v^x := \varphi^{-1}(x)$ the family of polynomials in $\mathcal{U}$ associated to $x$.

**Theorem 3.3. (Oddness Theorem)**

For every regular subset $\mathcal{U} \subset \mathcal{F}$, there exists a generic semi-algebraic subset $G$ of $S$ such that for every $x \in G$, the society $v^x$ has an odd number of pairwise stable networks.

## 3.3 SOME APPLICATIONS OF THEOREM 3.3

### 3.3.1 Polynomial payoff functions concave with respect to agents' weights

For every $i \in N$, let us consider the set $\mathcal{U}_i$ of polynomial functions with a degree less or equal to some fixed integer $\delta_i$ and which are concave in $g_{ij}$ for each $j \neq i$. The following corollary states that societies with payoff functions in $\mathcal{U}_i$ have generically an odd number of pairwise stable networks.
**Corollary 3.1.** There exists a generic semi-algebraic subset $G$ of $S$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.

*Proof.* We show that $\mathcal{U} = \prod_{i \in N} \mathcal{U}_i$ is a regular set:

1. Stability assumption is satisfied, since the sum of a concave function and an affine function is a concave function.

2. Semi-algebraicity assumption is satisfied: indeed, for every $i \in N$ and every $g \in G$, any payoff function in $\mathcal{U}_i$ can be written $v_i(g) = \sum_{k \in \mathbb{N}^L} \alpha_k^i g^k$. Then we can define the polynomial function $P_i : (\alpha^i := (\alpha_k^i)_{k \in \mathbb{N}^L}, g) \mapsto \sum_{k \in \mathbb{N}^L} \alpha_k^i g^k$, and finally

$$ \mathcal{S}_i = \{ \alpha^i : \forall g \in G, \forall j \neq i, \frac{\partial^2 P_i(\alpha^i, g_{ij}, g_{-ij})}{\partial g_{ij}^2} \leq 0 \} $$

which is a semi-algebraic set, from $G$ being semi-algebraic and from Proposition 3.2 (see Section 3.1).

Finally, from Theorem 3.3, we obtain Corollary 3.1. □

### 3.3.2 Linear costs of link formation

For every $i \in N$, let $\bar{v}_i$ be a polynomial function in $\mathcal{F}_i$ (i.e. concave in $g_{ij}$ for each $j \neq i$), and let $L' = \{(i, j) : (i, j) \in N^2, i \neq j\}$ denotes the set of directed links on $N$. Let $x \in \mathbb{R}^{L'}$, denoted $x = (x_{i,j})_{(i,j) \in L'}$, and consider the society parameterized by $x$, $v^x(\cdot) = (v_i^x(\cdot))_{i \in N}$ where for every $i \in N$, $v_i^x(g) := \bar{v}_i(g) - \sum_{j \neq i} x_{i,j} g_{ij}$ for every $g \in G$. Here, $x_{i,j} \in \mathbb{R}$ can be interpreted as a marginal cost of maintaining the weight $g_{ij}$ of link $ij$ (at least when $x_{i,j} \ge 0$). The following corollary states that societies with such payoff functions have generically an odd number of pairwise stable networks.

**Corollary 3.2.** There exists a generic semi-algebraic subset $G$ of $\mathbb{R}^{L'}$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.

*Proof.* Define $\mathcal{U}_i = \{g \mapsto \bar{v}_i(g) - \sum_{j \neq i} x_{i,j} g_{ij} : \forall j \neq i, x_{i,j} \in \mathbb{R}\}$. We can easily show that $\mathcal{U} = \prod_{i \in N} \mathcal{U}_i$ is a regular set: stability assumption is obviously satisfied, and for every $i \in N$, the set $\mathcal{S}_i$ is a finite product of singletons (corresponding to coefficients of $\bar{v}$) and of copies of $\mathbb{R}$, thus is a semi-algebraic set (i.e. semi-algebraicity assumption is satisfied). Finally, from Theorem 3.3, there exists a generic semi-algebraic subset $G'$ of $\mathcal{S} = \prod_{i \in N} \varphi_i(\mathcal{U}_i)$ such that for every $x' \in G'$, $\varphi^{-1}(x')$ has an odd number of pairwise stable networks. Now, since the mapping $f: x \in \mathbb{R}^{L'} \mapsto \varphi(v^x)$ is a semi-algebraic homeomorphism from $\mathbb{R}^{L'}$ to $\mathcal{S}$, we get that for every $x \in G = f^{-1}(G')$, $v^x$ has an odd number of pairwise stable networks, and $G$ is a generic subset of $\mathbb{R}^{L'}$. □

<figure><img src="image_2.png" /></figure>
### 3.3.3 Quadratic costs of link formation

Consider the same example as above, but where the payoff functions are parameterized by $x = (x_{i,j})_{(i,j)\in L'} \in (0, +\infty)^{L'}$, where $L' = \{(i,j) : (i,j) \in \mathbb{N}^2, i \neq j\}$ denotes the set of directed links on $N$, and $y = (y_{i,j})_{(i,j)\in L'} \in \mathbb{R}^{L'}$ as follows: $v_i^{x,y}(g) := \bar{v}_i(g) - \sum_{j \neq i} x_{i,j} g_{ij}^2 - \sum_{j \neq i} y_{i,j} g_{ij}$ for every $g \in \mathbb{G}$. Here, the cost of maintaining the weight $g_{ij}$ of link $ij$ is assumed to be quadratic. Again, we get that societies with such payoff functions have generically an odd number of pairwise stable networks:

**Corollary 3.3.** *There exists a generic semi-algebraic subset $G$ of $(0, +\infty)^{L'} \times \mathbb{R}^{L'}$ such that for every $(x, y) \in G$, $v^{x,y}$ has an odd number of pairwise stable networks.*

*Proof.* It is easy to check that $\mathcal{U} = \prod_{i \in N} \mathcal{U}_i$ is a regular set, where $\mathcal{U}_i = \{g \mapsto \bar{v}_i(g) - \sum_{j \neq i} x_{i,j} g_{ij}^2 - \sum_{j \neq i} y_{i,j} g_{ij} : \forall j \neq i, x_{i,j} \in (0, +\infty), y_{i,j} \in \mathbb{R}\}$. $\square$

### 3.3.4 A public good provision model

Consider the following modification of a model introduced by Bramoullé and Kranton ([8]): consider $n$ agents, each of them being characterized by some level of effort $e_i \in [0, +\infty)$ (it could be the amount of time a consumer spends researching a new product). The marginal cost of effort of each individual is $z \in \mathbb{R}$. Agents interact in some network $g$, and $g_{ij}$ measures the benefit for agent $i$ (resp. $j$) of agent's $i$ (resp. agent's $j$) efforts. For every $x = (x_{i,j})_{(i,j)\in L'} \in \mathbb{R}^{L'}$, consider a society $v^x(\cdot) = (v_i^x(\cdot))_{i \in N}$ parameterized by $x$, and defined by: for every $i \in N$, $v_i^x(g) := b(e_i + \sum_{j \neq i} g_{ij}e_j) - ze_i - \sum_{j \neq i} x_{i,j}g_{ij}$, where $b: \mathbb{R} \to \mathbb{R}$ is a concave polynomial benefit function and for every $j \neq i$, $x_{i,j} \in \mathbb{R}$ is the marginal cost of maintaining the weight $g_{ij}$ of the link $ij$.

In their paper, Bramoullé and Kranton are interested by the optimal levels of efforts $e_i$ ($i = 1, \dots, n$), which are here exogenous, and they consider exogenous values of the weights $g_{ij} \in \{0, 1\}$, which are here endogenous, and belong to $[0, 1]$.

**Corollary 3.4.** *There exists a generic semi-algebraic subset $G$ of $\mathbb{R}^{L'}$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.*

*Proof.* The proof is similar to the linear cost example, remarking that $b(e_i + \sum_{j \neq i} g_{ij}e_j) - ze_i$ is a polynomial function in $\mathcal{F}_i$ (i.e. concave in $g_{ij}$ for each $j \neq i$). $\square$

### 3.3.5 Information transmission

We now apply Theorem 3.3 to a weighted version of an information transmission model due to Calvó-Armengol [9] (see also [5]). We consider $n$ agents: if agent $i$ and agent $j$ are in a full relationship ($g_{ij} = 1$), some information can be transmitted from one agent to another agent with some probability $p_{ij}$. We assume that if the relationship is weighted
$(g_{ij} \in [0, 1])$, the probability of transmission is $p_{ij}g_{ij}$. The payoff of agent $i \in N$ is defined by

$$v_i^x(g) = 1 - \prod_{j \in N - \{i\}} (1 - p_{ij}g_{ij}) - \sum_{j \in N - \{i\}} x_{i,j}g_{ij},$$

for every $x = (x_{i,j})_{(i,j) \in L'} \in \mathbb{R}^{L'}$, and where $g$ is a weighted network on $N$. The first term corresponds to the probability that the message is transmitted to agent $i$, and the second term to the cost of maintaining his links (i.e. $x_{i,j} \in \mathbb{R}$ is the marginal cost of maintaining the weight $g_{ij}$ of the link $ij$ between agent $i$ and agent $j$). Denoting $v^x(\cdot) = (v_i^x(\cdot))_{i \in N}$, another application of the linear cost example treated above is the following corollary:

**Corollary 3.5.** There exists a generic semi-algebraic subset $G$ of $\mathbb{R}^{L'}$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.

### 3.3.6 A two-way flow model

We now adapt a model of Bala and Goyal [2] to weighted networks: we consider $n$ agents, and for every agent $i$ and agent $j \neq i$, a path from $i$ to $j$ is a finite sequence $x_0 = i, x_1, \dots, x_k = j$ of distinct elements of $N$. Let $\mathcal{P}_j$ be the (finite) set of all paths from $i$ to $j$, and $n_i(g)$ be the sum on all paths in $\mathcal{P}_j$ ($j \neq i$) of the product of weights along these paths. We can interpret $n_i(g)$ as the benefit that agent $i$ receives from his links.

For every agent $i$, define $v^x(\cdot) = (v_i^x(\cdot))_{i \in N}$ and

$$v_i^x(g) = n_i(g) - \sum_{j \in N - \{i\}} x_{i,j}g_{ij},$$

where $g \in \mathbb{G}$ and where $x_{i,j} \in \mathbb{R}$ is the marginal cost of maintaining the weight $g_{ij}$ of the link $ij$ between agent $i$ and agent $j$ (at least when $x_{i,j} > 0$). Denoting $x = (x_{i,j})_{(i,j) \in L'} \in \mathbb{R}^{L'}$, we get from the linear cost example above:

**Corollary 3.6.** There exists a generic semi-algebraic subset $G$ of $\mathbb{R}^{L'}$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.

### 3.3.7 Zenou-Ballester's model

We consider the following modification of a model introduced by Zenou and Ballester ([3]): $n$ agents interact in some (endogenous) network $g$. Each agent $i$ has chosen a (exogenous) level of effort $e_i \in [0, +\infty)$. The (strictly concave) payoff function of each agent $i$ has the following form

$$v_i^x(g) = \alpha_i e_i + \frac{1}{2}\sigma_{ii}e_i^2 + \sum_{j \neq i} g_{ij}(x_{i,j} + e_i e_j),$$

where $((\alpha_i)_{i \in N}, (\sigma_{ii})_{i \in N}) \in \mathbb{R}^n \times (-\infty, 0)^n$ are fixed parameters, and where $x = (x_{ij})_{(i,j) \in L'} \in \mathbb{R}^{L'}$. As in the previous corollaries, denoting $v^x(\cdot) = (v_i^x(\cdot))_{i \in N}$, we get:

**Corollary 3.7.** There exists a generic semi-algebraic subset $G$ of $\mathbb{R}^{L'}$ such that for every $x \in G$, $v^x$ has an odd number of pairwise stable networks.
# 4 APPENDIX

## 4.1 PROOF OF THEOREM 2.1

We first construct the homeomorphism $\eta$ from $\mathcal{P}$ to $\mathcal{F}$ (see Step 1-4 below), and we prove that $\eta$ is properly homotopic to $\pi$ in Step 5. Let us fix some element $g^0 \in \mathbb{G}$, and consider

$$ \left\{ \begin{array}{l} \eta: \mathcal{P} \to \mathcal{F} \\ (v, g) \mapsto v^g \end{array} \right. $$

where for every $i \in N$ and every $\gamma \in \mathbb{G}$,

$$ v_i^g(\gamma) = v_i(\gamma) + \sum_{j \neq i} \left( \partial_{ij} v_i(g_{ij}, g_{-ij}) - \partial_{ij} v_i(g_{ij}, g_{-ij}^0) \right) (\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij} \gamma_{ij}, \quad (1) $$

that is $v_i^g$ and $v_i$ are equal up to an affine mapping. Moreover, to define the inverse of $\eta$, we consider

$$ \left\{ \begin{array}{l} \rho: \mathcal{F} \to \mathcal{F} \times \mathbb{G} \\ v \mapsto (\tilde{v}, g^v) \end{array} \right. $$

where for every $i \in N$,

$$ \tilde{v}_i(\gamma) = v_i(\gamma) - \sum_{j \neq i} \left( \partial_{ij} v_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij} v_i(g_{ij}^v, g_{-ij}^0) \right) (\gamma_{ij} - g_{ij}^v) - \sum_{j \neq i} g_{ij}^v \gamma_{ij} \quad (2) $$

and where for every link $ij \in L$, $g_{ij}^v = \min\{w_{i,j}^v, w_{j,i}^v\}$, with $w_{i,j}^v \in [0, 1]$ be the unique solution of the strictly concave maximization problem

$$ \max_{w \in [0,1]} v_i(w, g_{-ij}^0) - \frac{w^2}{2} $$

and $w_{j,i}^v \in [0, 1]$ be the unique solution of the strictly concave maximization problem

$$ \max_{w \in [0,1]} v_j(w, g_{-ij}^0) - \frac{w^2}{2}. $$

In the proof, we will use the following first order necessary and sufficient condition for a maximum:

**Lemma 4.1.** A $\mathcal{C}^1$ concave function $f: [0, 1] \to \mathbb{R}$ has a maximum at $x \in [0, 1]$ if and only if one of the three following conditions is true:

1. $f'(x) = 0$ and $x \in (0, 1)$.
2. $f'(x) \ge 0$ and $x = 1$.

3. $f'(x) \le 0$ and $x = 0$.

Step 1: we show that $\rho(\mathcal{F}) \subset \mathcal{P}$.

Let $v \in \mathcal{F}$ and $\rho(v) = (\tilde{v}, g^v)$. We have to prove that the network $g^v$ is pairwise stable with respect to $\tilde{v}$. For that, we fix a link $ij \in L$. Since $g_{ij}^v = \min\{w_{i,j}^v, w_{j,i}^v\}$, we can assume, without any loss of generality (permuting $w_{i,j}^v$ and $w_{j,i}^v$ if necessary), that $g_{ij}^v = w_{i,j}^v$, which corresponds to the case where $w_{i,j}^v \le w_{j,i}^v$.

First, we prove that $g_{ij}^v = w_{i,j}^v$ maximizes the payoff function $\tilde{v}_i(., g_{-ij}^v)$ of agent $i$: from Lemma 4.1, we have to prove that $\tilde{v}_i(., g_{-ij}^v)$ satisfies one of the three conditions of the lemma at $g_{ij}^v = w_{i,j}^v$. But an easy computation gives at every $w \in [0, 1]$:

$$ \partial_{ij} \tilde{v}_i(w, g_{-ij}^v) = \partial_{ij} v_i(w, g_{-ij}^v) - (\partial_{ij} v_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij} v_i(g_{ij}^v, g_{-ij}^0)) - g_{ij}^v $$

and in particular

$$ \partial_{ij} \tilde{v}_i(g_{ij}^v, g_{-ij}^v) = \partial_{ij} v_i(g_{ij}^v, g_{-ij}^0) - g_{ij}^v. \quad (3) $$

But this last quantity is also the derivative with respect to $w$ of the concave function $v_i(w, g_{-ij}^0) - \frac{w^2}{2}$ at $g_{ij}^v = w_{i,j}^v$. By definition, $g_{ij}^v = w_{i,j}^v$ is the maximum of $v_i(w, g_{-ij}^0) - \frac{w^2}{2}$ on $[0, 1]$, and writing the first order and necessary condition given by Lemma 4.1 applied to this function, we also get (still from Lemma 4.1) that $g_{ij}^v = w_{i,j}^v$ maximizes $\tilde{v}_i(., g_{-ij}^v)$.

In particular, this implies that Condition 1. of pairwise stability is fulfilled for agent $i$ at $g_{ij}^v$, and that Condition 2. of pairwise stability is also fulfilled. It remains to show that Condition 1. of pairwise stability is satisfied for agent $j$ at $g_{ij}^v$. It is clearly the case if $g_{ij}^v = 0$, thus we can assume $g_{ij}^v > 0$, and finally the proof of Step 1 will be finished if we prove that $\tilde{v}_j(., g_{-ij}^v)$ is nondecreasing on $[0, g_{ij}^v)$. Because $\tilde{v}_j(., g_{-ij}^v)$ is concave, this is equivalent to $\partial_{ij} \tilde{v}_j(g_{ij}^v, g_{-ij}^v) \ge 0$, or, after a computation similar to this in Equation (3), it is equivalent to $\partial_{ij} v_j(g_{ij}^v, g_{-ij}^0) - g_{ij}^v \ge 0$. But by definition, the concave function $w \mapsto v_j(w, g_{-ij}^0) - \frac{w^2}{2}$ reaches its maximum at $w_{j,i}$: hence, from Lemma 4.1 and concavity, its derivative at $g_{ij}^v \le w_{j,i}$, which is precisely $\partial_{ij} v_j(g_{ij}^v, g_{-ij}^0) - g_{ij}^v$, has to be nonnegative. This ends the proof that $g^v$ is pairwise stable with respect to $\tilde{v}$. Finally, we have proved that $\rho(\mathcal{F}) \subset \mathcal{P}$, and we now consider, by abuse of notation, that $\rho$ is a mapping from $\mathcal{F}$ to $\mathcal{P}$.

Step 2: we show that $\eta \circ \rho = \text{id}_{\mathcal{F}}$.

For every $v \in \mathcal{F}$, let us define $\tilde{v} := (\eta \circ \rho)(v) = \eta(\tilde{v}, g^v)$. We have to prove that $\tilde{v} = v$. By definition of $\eta$, we have, for every $i \in N$:

$$ \tilde{v}_i(\gamma) = \tilde{v}_i(\gamma) + \sum_{j \neq i} (\partial_{ij} \tilde{v}_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij} \tilde{v}_i(g_{ij}^v, g_{-ij}^0)(\gamma_{ij} - g_{ij}^v)) + \sum_{j \neq i} g_{ij}^v \gamma_{ij} \quad (4) $$

and summing Equation (4) and Equation (2), we get
$$
\begin{align*}
\tilde{v}_i(\gamma) - v_i(\gamma) &= \sum_{j \neq i} (\partial_{ij} \tilde{v}_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij} \tilde{v}_i(g_{ij}^v, g_{-ij}^0)(\gamma_{ij} - g_{ij}^v)) \\
&\quad - \sum_{j \neq i} (\partial_{ij} v_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij} v_i(g_{ij}^v, g_{-ij}^0)(\gamma_{ij} - g_{ij}^v)) \\
&= \sum_{j \neq i} (\partial_{ij}(\tilde{v}_i - v_i)(g_{ij}^v, g_{-ij}^v) - \partial_{ij}(\tilde{v}_i - v_i)(g_{ij}^v, g_{-ij}^0))(\gamma_{ij} - g_{ij}^v).
\end{align*}
$$

But $(\tilde{v}_i - v_i)(\gamma)$ is an affine mapping of $\gamma$, and in particular, for each $j \neq i$, $\partial_{ij}(\tilde{v}_i - v_i)(g_{ij}, g_{-ij})$ does not depend on $g_{-ij}$, thus the last term is nul, which finishes Step 2.

Step 3: we show that $\rho \circ \eta = \text{id}_P$.

For every $(v, g) \in \mathcal{P}$, we have $(\rho \circ \eta)(v, g) = \rho(v^g) = (\tilde{v}^g, g')$, where $g' = g^{v^g}$, that is for every $ij \in L$, $g'_{ij} = \min\{w'_{i,j}, w'_{j,i}\}$, with $w'_{i,j} \in [0, 1]$ be the unique solution of the strictly concave maximization problem

$$
\max_{w \in [0,1]} v_i^g(w, g_{-ij}^0) - \frac{w^2}{2},
$$

and $w'_{j,i} \in [0, 1]$ be the unique solution of the strictly concave maximization problem

$$
\max_{w \in [0,1]} v_j^g(w, g_{-ij}^0) - \frac{w^2}{2}.
$$

We have to show that $\tilde{v}^g = v$ and that $g = g'$.

**First, we show that** $g = g'$.

Let us consider an arbitrary link $ij \in L$. Recall that since $(v,g) \in \mathcal{P}$, $g$ is pairwise stable with respect to $v$. The following lemma (cf. Bich and Morhaim [4], [5]) establishes the relationship between a weight of a link between agents $i$ and $j$ at some pairwise stable network and the optimal weights for agent $i$ and agent $j$:

**Lemma 4.2.** Let $g = (g_{ij})_{ij \in L}$ be some pairwise stable network with respect to a society $v = (v_i)_{i \in N}$. Moreover, for every $ij \in L$, let $I_i = [a_i, b_i] = \arg\max_{w \in [0,1]} v_i(w, g_{-ij})$ and $I_j = [a_j, b_j] = \arg\max_{w \in [0,1]} v_j(w, g_{-ij})$.<fnref n="8" /> Then we have:

$$
g_{ij} \in [\min\{a_i, a_j\}, \min\{b_i, b_j\}].
$$

<footnote n="8">⁸These sets are closed nonempty intervals, since the functions maximized are concave and continuous on a compact set.</footnote>
To prove that $g_{ij} = g'_{ij}$, without any loss of generality (up to a permutation of $i$ and $j$ if necessary), we can assume $a_i \le a_j$. In particular, from the above lemma, we get $g_{ij} \in [a_i, b_i]$ in all cases. Thus, $g_{ij} \in I_i$, and as a maximizer of $v_i(., g_{-ij})$, it has to satisfy the necessary (and sufficient) condition of Lemma 4.1 for this function. Now, the derivative of the function $q_i : w \mapsto q_i(w) := v_i^g(w, g_{-ij}^0) - \frac{w^2}{2}$ at $g_{ij}$ is $\partial_{ij}v_i^g(g_{ij}, g_{-ij}^0) - g_{ij}$, which is also equal to $\partial_{ij}v_i(g_{ij}, g_{-ij})$ (computing $\partial_{ij}v_i^g(g_{ij}, g_{-ij}^0)$ thanks to Equation (1)). Thus, $q_i$ has also to verify the necessary (and sufficient) condition of Lemma 4.1 at $w = g_{ij}$, and by strict concavity of $q_i$, $g_{ij}$ has to be the unique maximum of this function, i.e. $g_{ij} = w'_{i,j}$. To finish, we only have to prove that $g'_{ij} = w'_{i,j}$, or equivalently that $w'_{i,j} \le w'_{j,i}$. Since this inequality is true when $w'_{i,j} = 0$ or when $w'_{j,i} = 1$, we can now assume $w'_{i,j} > 0$ and $w'_{j,i} < 1$. The same computation as above gives that the derivative of $q_j : w \mapsto q_j(w) := v_j^g(w, g_{-ij}^0) - \frac{w^2}{2}$ at $g_{ij}$ is $\partial_{ij}v_j(g_{ij}, g_{-ij})$. Thus, since $w'_{j,i} < 1$ is the unique maximizer of $q_j$, we get

$$q'_{j}(w'_{j,i}) \le 0$$

from Lemma 4.1. Also, since $v_j(., g_{-ij})$ is concave and since $w'_{i,j} = g_{ij} \le b_j$ (because $g_{ij} \le \min\{b_i, b_j\}$), we get that $\partial_{ij}v_j(w'_{i,j}, g_{-ij}) \ge 0$, and in particular,

$$q'_{j}(w'_{i,j}) \ge 0.$$

Finally, $q'_{j}(w'_{j,i}) \le q'_{j}(w'_{i,j})$, thus in particular $w'_{i,j} \le w'_{j,i}$ because $q'_{j}$ is strictly decreasing from strict concavity of $q_j$. This proves that $g = g'$.

**Second, we show that $\tilde{v}^g = v$.**

The proof is very similar to the proof of Step 2 (i.e. the proof that $\eta \circ \rho = \text{id}_F$): for every $i \in N$, by definition of $\rho$, since $\rho(v^g) = (\tilde{v}^g, g') = (\tilde{v}^g, g)$, we have:

$$\tilde{v}_i^g(\gamma) = v_i^g(\gamma) - \sum_{j \neq i} (\partial_{ij}v_i^g(g_{ij}, g_{-ij}) - \partial_{ij}v_i^g(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) - \sum_{j \neq i} g_{ij}\gamma_{ij} \quad (5)$$

and by definition of $\eta$

$$v_i^g(\gamma) = v_i(\gamma) + \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij}. \quad (6)$$

Summing the two above equations, we get

$$\tilde{v}_i^g(\gamma) - v_i(\gamma) = \sum_{j \neq i} (\partial_{ij}(v_i - v_i^g)(g_{ij}, g_{-ij}) - \partial_{ij}(v_i - v_i^g)(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}).$$

But $(v_i - v_i^g)(\gamma)$ is an affine mapping of $\gamma$, and in particular, for each $j \neq i$, $\partial_{ij}(v_i - v_i^g)(g_{ij}, g_{-ij})$ does not depend on $g_{-ij}$, thus the last term is nul, which finishes the proof that $\tilde{v}^g = v$ and the proof of Step 3.
Step 4: we show that $\eta$ and $\rho$ are continuous mappings.

Recall that for every $(v, g) \in \mathcal{P}$, $\eta(v, g) = v^g$, where for every $i \in N$ and every $\gamma \in \mathbb{G}$,

$$v_i^g(\gamma) = v_i(\gamma) + \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij}.$$

To prove the continuity of $\eta$, notice that:

1. The mapping $(v, g) \in \mathcal{P} \to v_i \in \mathcal{F}_i$ is continuous, as a projection, since $\mathcal{F}$ is endowed with the product norm (see Section 2.2).

2. The mapping $(v, g) \in \mathcal{P} \mapsto (\gamma \mapsto \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}))$ (from $\mathcal{P}$ to $\mathcal{F}_i$) is continuous: first, to prove the continuity of the mapping

$$F_{ij} : (v, g) \in \mathcal{P} \mapsto (F_{ij}(v, g) : \gamma \mapsto \partial_{ij}v_i(g_{ij}, g_{-ij})\gamma_{ij}),$$

consider $(\bar{v}, \bar{g}) \in \mathcal{P}$ and for every $(v, g) \in \mathcal{P}$, compute

$$\|F_{ij}(v, g) - F_{ij}(\bar{v}, \bar{g})\|_i = \max\{\max\{\|F_{ij}(v, g) - F_{ij}(\bar{v}, \bar{g})\|_{\infty}, \|\partial_{ik}F_{ij}(v, g) - \partial_{ik}F_{ij}(\bar{v}, \bar{g})\|_{\infty}\} : k \neq i\}$$

Now, for every $\gamma \in \mathbb{G}$,

$$F_{ij}(v, g)(\gamma) - F_{ij}(\bar{v}, \bar{g})(\gamma) = \partial_{ij}v_i(g_{ij}, g_{-ij})\gamma_{ij} - \partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij})\gamma_{ij} \\ = \partial_{ij}(v_i - \bar{v}_i)(g_{ij}, g_{-ij})\gamma_{ij} - (\partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij}) - \partial_{ij}\bar{v}_i(g_{ij}, g_{-ij}))\gamma_{ij},$$

which implies that

$$\|F_{ij}(v, g) - F_{ij}(\bar{v}, \bar{g})\|_{\infty} \leq |\partial_{ij}(v_i - \bar{v}_i)(g_{ij}, g_{-ij})| + |(\partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij}) - \partial_{ij}\bar{v}_i(g_{ij}, g_{-ij}))| \\ \leq \|v_i - \bar{v}_i\|_i + |(\partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij}) - \partial_{ij}\bar{v}_i(g_{ij}, g_{-ij}))|,$$

which proves that

$$\lim_{(v,g) \to (\bar{v}, \bar{g})} \|F_{ij}(v, g) - F_{ij}(\bar{v}, \bar{g})\|_{\infty} = 0.$$

Moreover,

$$\partial_{ij}F_{ij}(v, g)(\gamma) - \partial_{ij}F_{ij}(\bar{v}, \bar{g})(\gamma) = \partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij})$$

which gives by a same argument as above

$$\|\partial_{ij}F_{ij}(v, g)(\gamma) - \partial_{ij}F_{ij}(\bar{v}, \bar{g})(\gamma)\|_{\infty} \leq \|v_i - \bar{v}_i\|_i + |(\partial_{ij}\bar{v}_i(\bar{g}_{ij}, \bar{g}_{-ij}) - \partial_{ij}\bar{v}_i(g_{ij}, g_{-ij}))|,$$

which proves that

$$\lim_{(v,g) \to (\bar{v}, \bar{g})} \|\partial_{ij}F_{ij}(v, g)(\gamma) - \partial_{ij}F_{ij}(\bar{v}, \bar{g})(\gamma)\|_{\infty} = 0.$$

This proves finally the continuity of $F_{ij}$. We prove similarly the continuity of the mappings $(v, g) \in \mathcal{P} \mapsto (\gamma \mapsto (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))g_{ij})$ and of the mappings $(v, g) \in \mathcal{P} \mapsto (\gamma \mapsto g_{ij}\gamma_{ij})$ for every $j \neq i$. Summing all these mappings, we finally get the continuity of $\eta$.
Now, to prove the continuity of $\rho$, we recall that for every $v \in \mathcal{F}$, $\rho(v) = (\tilde{v}, g^v)$ where for every $i \in N$ and for every $\gamma \in \mathbb{G}$,

$$ \tilde{v}_i(\gamma) = v_i(\gamma) - \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}^v, g_{-ij}^v) - \partial_{ij}v_i(g_{ij}^v, g_{-ij}^{0}))(\gamma_{ij} - g_{ij}^v) - \sum_{j \neq i} g_{ij}^v \gamma_{ij} \quad (7) $$

and where for every $ij \in L$, $g_{ij}^v = \min\{w_{i,j}^v, w_{j,i}^v\}$, with $w_{i,j}^v$ be the unique maximum of the strictly concave function $q_i(w) := v_i(w, g_{-ij}^0) - \frac{w^2}{2}$ on $[0, 1]$ and $w_{j,i}^v$ be the unique maximum of the strictly concave function $q_j(w) := v_j(w, g_{-ij}^0) - \frac{w^2}{2}$ on $[0, 1]$. Actually, the continuity of $\rho$ can be proved similar as the continuity of $\eta$. The only additional point to be proved is that the mapping $v \mapsto g^v$ is continuous, which is a consequence of the continuity of the mappings $v \mapsto w_{i,j}^v$ and $v \mapsto w_{j,i}^v$ (from Berge theorem).$^9$

Step 5: the mapping $H : [0, 1] \times \mathcal{P} \to \mathcal{F}$, $(t, (v, g)) \mapsto H(t, (v, g)) = (1-t)\pi(v, g) + t\eta(v, g)$ is a proper homotopy between $\pi$ and $\eta$.

For every $i \in N$, let us define the following mapping $G_i : [0, 1] \times \mathcal{F} \times \mathbb{G} \to \mathcal{F}_i$ by

$$ G_i(t, (v, g))(\gamma) = v_i(\gamma) + t \left( \sum_{j \neq i} \left( \partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0) \right) (\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij} \gamma_{ij} \right) \quad (8) $$

for every $(t, (v, g)) \in [0, 1] \times \mathcal{F} \times \mathbb{G}$ and for every $\gamma \in \mathbb{G}$, and let $G : [0, 1] \times \mathcal{F} \times \mathbb{G} \to \mathcal{F}$ defined by $G = (G_i)_{i \in N}$. It is easy to see that the restriction of $G$ to $[0, 1] \times \mathcal{P}$ is equal to $H$. Let us define $\psi : [0, 1] \times \mathcal{F} \times \mathbb{G} \to [0, 1] \times \mathcal{F} \times \mathbb{G}$ by

$$ \psi(t, (v, g)) = (t, G(t, (v, g))), g) $$

for every $(t, (v, g)) \in [0, 1] \times \mathcal{F} \times \mathbb{G}$. The mapping $\psi$ is invertible: for every $t \in [0, 1]$, $\psi^{-1}(t, (v, g)) = (t, \tilde{G}(t, (v, g))), g)$ where $\tilde{G} = (\tilde{G}_i)_{i \in N}$ and where for every $i \in N$, $\tilde{G}_i : [0, 1] \times \mathcal{F} \times \mathbb{G} \to \mathcal{F}_i$ is defined by

$$ \tilde{G}_i(t, (v, g))(\gamma) = v_i(\gamma) - t \left( \sum_{j \neq i} \left( \partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0) \right) (\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij} \gamma_{ij} \right) $$

(similar to Step 2 and Step 3). Moreover, $\psi$ and $\psi^{-1}$ are continuous (similar to Step 4). Thus, for every compact subset $K$ of $\mathcal{F}$,

$$ \begin{aligned} H^{-1}(K) &= \{(t, (v, g)) \in [0, 1] \times \mathcal{P} : H(t, (v, g)) \in K\} \\ &= \{(t, (v, g)) \in [0, 1] \times \mathcal{P} : \psi(t, (v, g)) \in [0, 1] \times K \times \mathbb{G}\} \\ &= \psi^{-1}([0, 1] \times K \times \mathbb{G}) \cap ([0, 1] \times \mathcal{P}). \end{aligned} $$

<footnote>$^9$Indeed, Berge Theorem states that if we consider a continuous correspondence $\Phi : X \to Y$ with nonempty compact values and if we consider a continuous mapping $f : X \times Y \to \mathbb{R}$, then the argmax correspondence of the maximization problem $\max_{y \in \Phi(x)} f(x, y)$ has a closed graph and nonempty values. In particular, if we take $Y = [0, 1]$, $X = \mathcal{F}$, $\Phi(x) = [0, 1]$ for every $x \in X$ and finally $f : (v, w) \in \mathcal{F} \times [0, 1] \mapsto f(v, w) = v_i(w, g_{-ij}^0) - w^2/2$ (which is continuous), then we get that the (single-valued) correspondence $v \mapsto w_{i,j}^v$ has a closed graph, or equivalently that the mapping $v \to w_{i,j}^v$ is continuous.</footnote>
But $\psi^{-1}$ is a continuous mapping and $[0, 1] \times K \times \mathbb{G}$ is a compact subset of $[0, 1] \times \mathcal{F} \times \mathbb{G}$, thus $\psi^{-1}([0, 1] \times K \times \mathbb{G})$ is compact in $[0, 1] \times \mathcal{F} \times \mathbb{G}$. Moreover, $[0, 1] \times \mathcal{P}$ is closed in $[0, 1] \times \mathcal{F} \times \mathbb{G}$ (see lemma below). Thus, finally $H^{-1}(K) = \psi^{-1}([0, 1] \times K \times \mathbb{G}) \cap ([0, 1] \times \mathcal{P})$ is compact as a closed subset of a compact set, which proves that $H$ is a proper mapping.

**Lemma 4.3.** The set $\mathcal{P}$ is a closed subset of $\mathcal{F} \times \mathbb{G}$.

*Proof.* Consider a sequence $(v^k, g^k)$ in $\mathcal{P}$ which converges to $(v, g) \in \mathcal{F} \times \mathbb{G}$. To prove that $(v, g) \in \mathcal{P}$, suppose by contradiction that $(v, g) \notin \mathcal{P}$:

1. Suppose first that there exists some $ij \in L$ and some $w < g_{ij}$ such that $v_i(w, g_{-ij}) > v_i(g)$. Since $v_i$ is continuous, this implies that there exists $k \ge 0$ such that $v_i^k(w, g_{-ij}^k) > v_i^k(g^k)$ (indeed, from the topology defined on $\mathcal{F}$, $v_i^k(g^k)$ converges to $v_i(g)$ since $|v_i^k(g^k) - v_i(g)| \le |v_i^k(g^k) - v_i(g^k)| + |v_i(g^k) - v_i(g)| \le \|v_i^k - v_i\|_\infty + |v_i(g^k) - v_i(g)| \le \|v_i^k - v_i\|_i + |v_i(g^k) - v_i(g)|$, and similarly $v_i^k(w, g_{-ij}^k)$ converges to $v_i(w, g_{-ij})$). But this contradicts that $g^k$ is pairwise stable with respect to $v^k$.

2. Now, suppose that there exists some $ij \in L$ and some $w > g_{ij}$ such that $v_i(w, g_{-ij}) > v_i(g)$ and $v_j(w, g_{-ij}) > v_j(g)$. Since $v_i$ and $v_j$ are continuous, this implies that there exists $k \ge 0$ such that $v_i^k(w, g_{-ij}^k) > v_i(g^k)$ and $v_j^k(w, g_{-ij}^k) > v_j(g^k)$ (same proof as above), which again contradicts that $g^k$ is pairwise stable with respect to $v^k$.

□

## 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. To every continuous mapping $f : \mathbb{S}^m \to \mathbb{S}^m$, one can associate an integer $\deg(f) \in \mathbb{Z}$, called the degree of $f$ (or topological degree, or Brouwer degree) which satisfies the following properties:

(i) **(Degree of identity).** $\deg(\mathrm{id}_{\mathbb{S}^m}) = 1$ (see Dold [1], Proposition 4.2., (i), p. 62).

(ii) **(Homotopy invariance).** If $f : \mathbb{S}^m \to \mathbb{S}^m$ and $g : \mathbb{S}^m \to \mathbb{S}^m$ are homotopic, then $\deg(f) = \deg(g)$ (see Dold [1], Proposition 4.2., (iii), p. 62 or Hatcher [13], p. 134).

(iii) **(Surjectivity).** For every continuous function $f : \mathbb{S}^m \to \mathbb{S}^m$ such that $\deg(f) \ne 0$, $f$ is surjective (see Hatcher [13], p. 134).

(iv) **(Homeomorphism).** If $f : \mathbb{S}^m \to \mathbb{S}^m$ is a homeomorphism, then $\deg(f) \in \{-1, 1\}$ (see Hatcher [13], p. 135, in the proof of Proposition 2.29).

To every continuous mapping $f : \mathbb{S}^m \to \mathbb{S}^m$ and every $y \in \mathbb{S}^m$, one can also associate an integer $\deg(f)|_y \in \mathbb{Z}$ called the local degree of $f$ at $y$ which satisfies the following properties:
(v) **(Local homeomorphism)**. If $f$ is a homeomorphism from some neighborhood of $y$ to some neighborhood of $f(y)$, then $\deg(f)|_y \in \{-1, 1\}$ (see Hatcher [13], p. 135-136 or Dold [1], Example 5.4., p. 67).

(vi) **(Additivity of degree modulo 2)**. For every $f : \mathbb{S}^m \to \mathbb{S}^m$ continuous and for every $z \in \mathbb{S}^m$, if $f^{-1}(z) = \{y_1, \dots, y_m\}$, then

$$ \deg(f) = \sum_{k=1}^{m} \deg(f)|_{y_k} [2]. $$

(see Hatcher [13], Proposition 2.30., p. 135-136 or Dold [1], Proposition 5.8., p. 68). In particular, from the formula above, if for every $k = 1, \dots, m$, $f$ is a homeomorphism from some neighborhood of $y_k$ to some neighborhood of $f(y_k)$ and if $\deg(f) = 1$, then $m$ is odd.

## 4.3 PROOF OF COROLLARY 2.1

The idea is to follow the proof of Theorem 2.1 by restricting $\eta$ to $\mathcal{P}_U$: the only important point is to remark that $\eta(\mathcal{P}_U) \subset \mathcal{U}$, which is true because for every $i \in N$,

$$ (\eta_{|\mathcal{P}_U})_i(v, g)(\gamma) = v_i(\gamma) + \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij} $$

where $\eta_{|\mathcal{P}_U} = ((\eta_{|\mathcal{P}_U})_i)_{i \in N}$, and because the mapping

$$ \gamma \mapsto \sum_{j \neq i} (\partial_{ij}v_i(g_{ij}, g_{-ij}) - \partial_{ij}v_i(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij} $$

belongs to $\mathcal{A}_i$. Thus, we can use the stability assumption in Corollary 2.1.

## 4.4 PROOF OF THEOREM 3.3

Consider a regular set $\mathcal{U} = \prod_{i \in N} \mathcal{U}_i$ of profiles of payoff functions such that for every $i \in N$, $\mathcal{U}_i \subset \mathcal{F}_i$ (equivalently, each $v_i \in \mathcal{U}_i$ is polynomial and concave in $g_{ij}$ for each $j \neq i$). From Theorem 2.1, there exists a homeomorphism $\eta$ (defined in Equation (1)) from $\mathcal{P}$, the graph of pairwise stable networks, to $\mathcal{F}$. Recall that $\pi: \mathcal{P} \to \mathcal{F}$ denotes the projection from $\mathcal{P}$ to $\mathcal{F}$, and that for every profile of polynomials payoff functions $v \in \mathcal{U}$, $\varphi(v)$ denotes the vector of its coefficients.

Since $\mathcal{U}$ is regular, Corollary 2.1 implies that $\eta_{|\mathcal{P}_U}$, the restriction of $\eta$ to $\mathcal{P}_U$ (the graph of pairwise stable networks restricted to $\mathcal{U}$) is a homeomorphism from $\mathcal{P}_U$ to $\mathcal{U}$.

In the first part of the proof (from Step 1 to Step 8), we assume that $\mathcal{S} = \varphi(\mathcal{U})$, the set of coefficients of profiles of polynomials in $\mathcal{U}$, is equal to $\mathbb{R}^m$. Actually, the proof below
is similar if we only assume that $\mathcal{S}$ is homeomorphic to $\mathbb{R}^p$, for some integer $p \le m$. The general case where $\mathcal{S}$ is simply semi-algebraic is considered at the end of the proof (see Step 9).

**Step 1: the set $\mathcal{M}$** := $\{(\varphi(v), g) \in \mathbb{R}^m \times \mathbb{G} : (v, g) \in \mathcal{P}_U\}$ is semi-algebraic and the mapping $\tilde{\eta} : \mathcal{M} \to \mathbb{R}^m, (x, g) \mapsto \varphi(\eta_{|_{\mathcal{P}_U}}(\varphi^{-1}(x), g))$ is a semi-algebraic homeomorphism. In particular, $\dim(\mathcal{M}) = m$.

First, we show that $\mathcal{M}$ is semi-algebraic. From the concavity assumption of payoff functions in $\mathcal{U}$, we can remark that the condition $(x, g) \in \mathcal{M}$, that is the condition “$g$ is a pairwise stable network of $\varphi^{-1}(x)$”, is equivalent to the following conditions (where we recall that $v^x = (v_i^x)_{i \in N} = \varphi^{-1}(x)$): for every $ij \in L$,

1. either $g_{ij} \in (0, 1)$, $\partial_{ij}v_i^x(g_{ij}, g_{-ij}) = 0$ and $\partial_{ij}v_j^x(g_{ij}, g_{-ij}) \ge 0$,

2. or $g_{ij} \in (0, 1)$, $\partial_{ij}v_j^x(g_{ij}, g_{-ij}) = 0$ and $\partial_{ij}v_i^x(g_{ij}, g_{-ij}) \ge 0$,

3. or $g_{ij} = 0$ and $[\partial_{ij}v_i^x(g_{ij}, g_{-ij}) \le 0 \text{ or } \partial_{ij}v_j^x(g_{ij}, g_{-ij}) \le 0]$,

4. or $g_{ij} = 1$ and $[\partial_{ij}v_i^x(g_{ij}, g_{-ij}) \ge 0 \text{ and } \partial_{ij}v_j^x(g_{ij}, g_{-ij}) \ge 0]$.

These conditions involve a finite number of equalities and of inequalities with semi-algebraic mappings, thus $\mathcal{M}$ is a semi-algebraic set, as announced.

Second, we show that the mapping $\tilde{\eta}$ is semi-algebraic. From its definition and the definition of $\eta$ (in Equation 1), this is equivalent to say that

$$ (x, g) \mapsto \varphi(\gamma \mapsto v_i^x(\gamma) + \sum_{j \neq i} (\partial_{ij}v_i^x(g_{ij}, g_{-ij}) - \partial_{ij}v_i^x(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij}) $$

is a semi-algebraic mapping. We can see directly that this is the case, since each coefficient of the polynomial function

$$ \gamma \mapsto v_i^x(\gamma) + \sum_{j \neq i} (\partial_{ij}v_i^x(g_{ij}, g_{-ij}) - \partial_{ij}v_i^x(g_{ij}, g_{-ij}^0))(\gamma_{ij} - g_{ij}) + \sum_{j \neq i} g_{ij}\gamma_{ij} $$

is a polynomial function of $(x, g)$. Now, the following diagram summarizes the situation:

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

where $\pi_{|_{\mathcal{P}_U}}$ and $\eta_{|_{\mathcal{P}_U}}$ are the restrictions of $\eta$ and $\pi$ to $\mathcal{P}_U$ and where $\tilde{\pi}$ and $\tilde{\eta}$ are the ‘transportations’ of $\pi_{|_{\mathcal{P}_U}}$ and $\eta_{|_{\mathcal{P}_U}}$ from $\mathcal{M}$ to $\mathbb{R}^m$ by the homeomorphisms $\varphi$ and $\tilde{\varphi} : \mathcal{P}_U \to \mathcal{M}, (v, g) \mapsto (\varphi(v), g)$. With this notation, $\tilde{\pi} = \varphi \circ \pi_{|_{\mathcal{P}_U}} \circ \tilde{\varphi}^{-1}$ (which is the usual projection from $\mathcal{M}$ to $\mathbb{R}^m$) and $\tilde{\eta} = \varphi \circ \eta_{|_{\mathcal{P}_U}} \circ \tilde{\varphi}^{-1}$. We can remark that $\tilde{\eta}$ is a semi-algebraic homeomorphism from $\mathcal{M}$ to $\mathbb{R}^m$, since both $\eta_{|_{\mathcal{P}_U}}$ and $\tilde{\varphi}$ are homeomorphisms. This implies (see [7], Theorem 2.8.8.) that the dimensions of $\mathcal{M}$ and of $\mathbb{R}^m$ coincide, thus that $\dim(\mathcal{M}) = m$. This ends the proof of Step 1.
Step 2: extensions of $\tilde{\pi}$ and $\tilde{\eta}$ to the compactifications of $\mathcal{M}$ and $\mathbb{R}^m$.

The network $g \in \mathbb{G}$ is pairwise stable in the society $v^x$ if and only if $(x, g) \in \tilde{\pi}^{-1}(x)$. Thus, to finish the proof of Theorem 3.3, we need informations on the cardinal of $\tilde{\pi}^{-1}(x)$, which can be done by using topological degree. The topological degree we use (see Section 4.2) is applied to functions defined on spheres (which avoids boundary issues). But $\tilde{\pi}$ is not defined on a sphere (but on $\mathcal{M}$): that is why we try to extend $\tilde{\pi}$ on the compactification of $\mathcal{M}$, which will be proved to be homeomorphic to some $m$-dimensional sphere. We recall that every noncompact locally compact Hausdorff space $(X, \tau_X)$ admits a (Alexandroff one-point) compactification $X^*$. Formally, $X^* = X \cup \{\infty\}$ (where $\infty$ is any element which does not belong to $X$) and $X^*$ is endowed with the following topology: $O \subset X^*$ is open in $X^*$ if (i) either $\infty \notin O$ and $O$ is open in $X$, (ii) or $\infty \in O$ and the complement of $O$ is compact for the topology $\tau_X$. Also, let us recall that if $X$ and $Y$ are noncompact locally compact Hausdorff space and $f: X \to Y$ is a continuous proper mapping, then it can be extended (uniquely) to a continuous mapping $f^*: X^* \to Y^*$ for which $f(\infty) = \infty$.

Since $\mathcal{M}$ is homeomorphic to $\mathbb{R}^m$ (the homeomorphism being $\tilde{\eta}$), $\mathcal{M}$ is a noncompact locally compact Hausdorff space and thus, it admits a compactification $\mathcal{M}^*$. From Corollary 2.1 and from stability assumption in Definition 3.6, $\pi_{|\mathcal{P}_U}$ and $\eta_{|\mathcal{P}_U}$ are proper mappings. In particular, since $\varphi$ and $\tilde{\varphi}$ are homeomorphisms, $\tilde{\pi}$ and $\tilde{\eta}$ are also proper mappings. Thus, these mappings admit (unique) continuous extensions $\tilde{\pi}^*: \mathcal{M}^* \to (\mathbb{R}^m)^*$ and $\tilde{\eta}^*: \mathcal{M}^* \to (\mathbb{R}^m)^*$ (we can notice that $\tilde{\eta}^*$ is a homeomorphism). Moreover, we recall that $(\mathbb{R}^m)^*$ is also homeomorphic to $\mathbb{S}^m$, the $m$-sphere (where the inverse of the stereographic projection, denoted $s: (\mathbb{R}^m)^* \to \mathbb{S}^m$, is such a homeomorphism).

The following diagram summarizes the situation:

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

where

$$ \hat{\pi} = s \circ \tilde{\pi}^* \circ (s \circ \tilde{\eta}^*)^{-1} = s \circ \tilde{\pi}^* \circ (\tilde{\eta}^*)^{-1} \circ s^{-1} \\ \hat{\eta} = s \circ \tilde{\eta}^* \circ (s \circ \tilde{\eta}^*)^{-1} = s \circ \mathrm{id}_{(\mathbb{R}^m)^*} \circ s^{-1} = \mathrm{id}_{\mathbb{S}^m} $$

and where $s \circ \tilde{\eta}^*$ is a homeomorphism from $\mathcal{M}^*$ to $\mathbb{S}^m$.

Step 3: $\tilde{\pi}^*$ (resp. $\hat{\pi}$) and $\tilde{\eta}^*$ (resp. $\hat{\eta}$) are homotopic.

We recall that from Corollary 2.1, there exists some proper homotopy $H_{|\mathcal{P}_U}$ between $\pi_{|\mathcal{P}_U}$ and $\eta_{|\mathcal{P}_U}$. Using this homotopy, we can deduce an homotopy between $\tilde{\pi}$ and $\tilde{\eta}$. Indeed, the map

$$ \left\{ \begin{array}{rcl} \tilde{H} : [0,1] \times \mathcal{M} & \to & \mathbb{R}^m \\ (t, (x,g)) & \mapsto & \varphi(H_{|\mathcal{P}_U}(t, (\tilde{\varphi}^{-1}(x,g)))) \end{array} \right. $$

is continuous (by composition) and we obtain that

$$ \tilde{H}(0, x, g) = \tilde{\varphi}(H_{|\mathcal{P}_U}(0, \tilde{\varphi}^{-1}(x, g))) = \tilde{\varphi}(\eta|_{\mathcal{P}_U}(\tilde{\varphi}^{-1}(x, g))) = \tilde{\eta}(x, g) $$
by definition of $\tilde{\eta}$, and similarly that

$$ \tilde{H}(1, x, g) = \tilde{\varphi}(H_{|\mathcal{P}_U}(1, \tilde{\varphi}^{-1}(x, g))) = \tilde{\varphi}(\pi|_{\mathcal{P}_U}(\tilde{\varphi}^{-1}(x, g))) = \tilde{\pi}(x, g) $$

by definition of $\tilde{\pi}$. We can notice that, as $H_{|\mathcal{P}_U}$ is a proper map, $\tilde{H}$ is also proper.

Now, let us define the following map:

$$ \left\{ \begin{array}{rcl} \tilde{H}^* : [0, 1] \times \mathcal{M}^* & \to & (\mathbb{R}^m)^* \\ (t, (x, g)) & \mapsto & \left\{ \begin{array}{ll} \tilde{H}(t, (x, g)) & \text{if } (x, g) \neq \infty \\ \infty & \text{otherwise} \end{array} \right. \end{array} \right. $$

and let us show that $\tilde{H}^*$ is an homotopy between $\tilde{\pi}^*$ and $\tilde{\eta}^*$.

First, we can remark that

$$ \tilde{H}^*(0, x, g) = \left\{ \begin{array}{ll} \tilde{H}(0, x, g) = \tilde{\eta}(x, g) = \tilde{\eta}^*(x, g) & \text{if } (x, g) \neq \infty \\ \infty = \tilde{\eta}^*(\infty) & \text{otherwise} \end{array} \right. $$

and similarly that

$$ \tilde{H}^*(1, x, g) = \left\{ \begin{array}{ll} \tilde{H}(1, x, g) = \tilde{\pi}(x, g) = \tilde{\pi}^*(x, g) & \text{if } (x, g) \neq \infty \\ \infty = \tilde{\pi}^*(\infty) & \text{otherwise} \end{array} \right. $$

This homotopy can be “transported”, using the homeomorphisms $s \circ \tilde{\eta}^*$ and $s$, to an
homotopy $\hat{H}$ between $\hat{\pi}$ and $\hat{\eta}$, which is defined in the following way:

$$ \left\{ \begin{array}{rcl} \hat{H} : [0, 1] \times \mathbb{S}^m & \to & \mathbb{S}^m \\ (t, x) & \mapsto & s(\tilde{H}^*(t, (s \circ \tilde{\eta}^*)^{-1}(x))). \end{array} \right. $$

Now, we only have to prove that $\tilde{H}^*$ is a continuous map: let $O \subset (\mathbb{R}^m)^*$ be an open subset in $(\mathbb{R}^m)^*$ and let us prove that $(\tilde{H}^*)^{-1}(O)$ is open in $[0, 1] \times \mathcal{M}^*$:

First, if $\infty \notin O$ and $O$ is open in $\mathbb{R}^m$, then $(\tilde{H}^*)^{-1}(O) = \tilde{H}^{-1}(O)$ is open in $[0, 1] \times \mathcal{M}$ (by continuity of $\tilde{H}$), thus open in $[0, 1] \times \mathcal{M}^*$.

Second, if $O = \{\infty\} \cup K^c$ (where $K$ is compact for the induced topology in $\mathbb{R}^m$), then

$$ (\tilde{H}^*)^{-1}(O) = ([0, 1] \times \{\infty\}) \cup \tilde{H}^{-1}(K)^c. $$

To prove that this set is open in $[0, 1] \times \mathcal{M}^*$, let us consider an element $(t, (x, g)) \in (\tilde{H}^*)^{-1}(O)$ and let us find an open neighborhood of $(t, (x, g))$ which is included in $(\tilde{H}^*)^{-1}(O)$. We will prove that there exists $\epsilon > 0$ such that

$$ V_{\epsilon} = ([t - \epsilon, t + \epsilon] \cap [0, 1]) \times (L_{\epsilon}^{c} \cup \{\infty\}) $$

is the neighborhood we are looking for, where

$$ \begin{aligned} L_{\epsilon} &:= \{(x', g') \in \mathcal{M} : \exists t' \in [0, 1] \cap [t - \epsilon, t + \epsilon] : (t', (x', g')) \in \tilde{H}^{-1}(K)\} \\ &= \{(x', g') \in \mathcal{M} : \exists t' \in [0, 1] \cap [t - \epsilon, t + \epsilon] : \tilde{H}(t', (x', g')) \in K\}. \end{aligned} $$
• First, $L_\epsilon$ is compact in $\mathcal{M}$: indeed, if $(x^k, g^k)$ is sequence in $L_\epsilon$, by definition, for every integer $k$, there exists $t^k \in [0, 1] \cap [t-\epsilon, t+\epsilon]$ such that $(t^k, (x^k, g^k)) \in \tilde{H}^{-1}(K)$ which is compact since $K$ is compact and $\tilde{H}$ is a proper. Thus, $(t^k, (x^k, g^k))$ admits some subsequence converging to some $(\bar{t}, (\bar{x}, \bar{g})) \in \tilde{H}^{-1}(K)$, and finally $(\bar{x}, \bar{g}) \in L_\epsilon$ since $\bar{t} \in [0, 1] \cap [t-\epsilon, t+\epsilon]$.

• Second, let us prove there exists $\epsilon > 0$ such that $V_\epsilon = ([t-\epsilon, t+\epsilon] \cap [0, 1]) \times (L_\epsilon^c \cup \{\infty\})$ contains $(t, x, g)$: this is always true if $(x, g) = \infty$. If this is false when $(x, g) \neq \infty$, then in particular (choosing $\epsilon = \frac{1}{k}$ for every integer $k \ge 1$), we get that $(x, g) \in L_{\frac{1}{k}}$ for every $k \ge 1$. This means that there exists a sequence $t^k$ converging to $t$ such that for every $k \ge 1$, $\tilde{H}(t^k, (x, g)) \in K$. Passing to the limit, from the continuity of $\tilde{H}$ and the compactness of $K$ (which is closed for the considered topology), we get that $\tilde{H}(t, (x, g)) \in K$, which contradicts that $(t, (x, g)) \in (\tilde{H}^*)^{-1}(O) = ([0, 1] \times \{\infty\}) \cup \tilde{H}^{-1}(K)^c$ (since this implies in particular $(t, (x, g)) \in \tilde{H}^{-1}(K)^c$, that is $\tilde{H}(t, (x, g)) \notin K$).

• Third, let us prove that $V_\epsilon \subset (\tilde{H}^*)^{-1}(O)$. If $(t', (x', g')) \in V_\epsilon$ and $(x', g') = \infty$, then we obtain directly that $(t', (x', g')) \in (\tilde{H}^*)^{-1}(O)$. Moreover, if $(x', g') \neq \infty$ and $(t', (x', g')) \in ([t-\epsilon, t+\epsilon] \cap [0, 1]) \times L_\epsilon^c$, then by definition of $L_\epsilon$, for every $t'' \in [0, 1] \cap [t-\epsilon, t+\epsilon]$ we have $(t'', (x', g')) \notin \tilde{H}^{-1}(K)$, and in particular, $\tilde{H}(t', (x', g')) \notin K$, which implies that $(t', (x', g')) \in (\tilde{H}^*)^{-1}(O)$ and ends the proof.

*Step 4: the degree of $\hat{\pi}$ is equal to 1, and $\tilde{\pi}$ is surjective (which implies that for every $v \in \mathcal{U}$, there exists a pairwise stable network).*

From the previous step, $\hat{\pi} : \mathbb{S}^m \to \mathbb{S}^m$ and $\hat{\eta} : \mathbb{S}^m \to \mathbb{S}^m$ are homotopic, thus from homotopy invariance of topological degree (see Appendix 4.2, Property (ii)), we have $\deg(\hat{\pi}) = \deg(\hat{\eta})$. But from Step 2, we know that $\hat{\eta} = \text{id}_{\mathbb{S}^m}$, thus $\deg(\hat{\eta}) = 1$ (see Appendix 4.2, Property (i)). In particular, $\deg(\hat{\pi}) = 1$, which implies that $\hat{\pi}$ is a surjective mapping (see Appendix 4.2, Property (iii)).

This also implies that $\tilde{\pi}$ is surjective: indeed, for every $x \in \mathbb{R}^m$, $s(x) \in \mathbb{S}^m$, thus there exists $y \in \mathbb{S}^m$ such that $\hat{\pi}(y) = s(x)$, which gives $x = (s^{-1} \circ \hat{\pi})(y)$, thus $x = \tilde{\pi} \circ (s \circ \tilde{\eta})^{-1}(y)$ (by definition of $\tilde{\pi}$). Remark that for every $v \in \mathcal{U}$, we also have that there exists $y \in \mathbb{S}^m$ such that $v = (\pi_{|_{\mathcal{P}_U}} \circ \tilde{\varphi}^{-1} \circ (s \circ \tilde{\eta})^{-1})(y)$, which proves that $\pi_{|_{\mathcal{P}_U}}$ is also surjective: equivalently, for every $v \in \mathcal{U}$, there exists a pairwise stable network.

In particular, we recover (but for a smaller class of payoff functions) the result of Bich and Morhaim [5], which proves the existence of a pairwise stable network for every continuous society $v = (v_1, \dots, v_n)$ such that $v_i$ is quasiconcave with respect to $g_{ij}$, for every link $ij$.

*Step 5: there exists a generic semi-algebraic subset $G$ of $\mathbb{R}^m$ such that for every $x \in G$, $\tilde{\pi}^{-1}(x)$ is nonempty and finite.*

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

**Step 6:** for every $x \in G$, the set of pairwise stable networks of $v^x = \varphi^{-1}(x)$ is nonempty and finite (we call $K_x$ its cardinal).

Indeed, from Step 5, we know that for every $x \in G$, $\tilde{\pi}^{-1}(x)$ is nonempty and finite. However, since $\tilde{\varphi}$ is a homeomorphism, we obtain that $\tilde{\varphi}^{-1}(\tilde{\pi}^{-1}(x)) = \pi_{|\mathcal{P}_U}^{-1}(\varphi^{-1}(x)) = \pi_{|\mathcal{P}_U}^{-1}(v^x)$ is also nonempty and finite (with the same cardinal as $\tilde{\pi}^{-1}(x)$). But $\pi_{|\mathcal{P}_U}^{-1}(v^x) = \{(v^x, g) : g \text{ is a pairwise stable network of } v^x\}$.

**Step 7:** for every $x \in G$, there exists $\hat{V}_x$ an open neighborhood (in $\mathbb{S}^m$) of $s(x)$ such that $\hat{\pi}^{-1}(\hat{V}_x)$ is a union of pairwise disjoint open sets $(\hat{V}_x^k)_{k \in \mathcal{K}}$ (where $\mathcal{K}$ is a finite set of cardinal $K_x$) and such that for every $k \in \mathcal{K}$, $\hat{\pi}_{|\hat{V}_x^k}$ is a homeomorphism between $\hat{V}_x^k$ and $\hat{V}_x$.

Let $x \in G$, and let $C_x$ be the connected component of $G$ containing $x$. From Step 6, we know that $\tilde{\pi}^{-1}(x)$ is nonempty and finite, so we obtain that $(\tilde{\pi}^*)^{-1}(x) = (\tilde{\pi})^{-1}(x)$ and $\hat{\pi}^{-1}(s(x))$ are also non empty and finite, with the same cardinal as $\tilde{\pi}^{-1}(x)$ (as $s$ is a homeomorphism), i.e. of cardinal $K_x$. Moreover, from Theorem 3.1 (see Section 3.1), there exists an open neighborhood $V_x$ of $x$ such that $\tilde{\pi}^{-1}(V_x)$ is a union of pairwise disjoint open sets $(V_x^k)_{k \in \mathcal{K}}$ (where $\mathcal{K}$ is a finite set) such that for every $k \in \mathcal{K}$, $\tilde{\pi}_{|V_x^k}$ is a homeomorphism between $V_x^k$ and $V_x$. Denote by $\hat{V}_x$ the image by the homeomorphism $s$ of $V_x$ and for every $k \in \mathcal{K}$, denote by $\hat{V}_x^k$ the image by the homeomorphism $s \circ \tilde{\eta}^*$ of $V_x^k$. Since $s$ is a homeomorphism, $\hat{V}_x$ is an open neighborhood of $s(x)$. Also, since $s \circ \tilde{\eta}^*$ is a homeomorphism, $\hat{\pi}^{-1}(\hat{V}_x) = \bigcup_{k \in \mathcal{K}} \hat{V}_x^k$, and $(\hat{V}_x^k)_{k \in \mathcal{K}}$ is a family of pairwise disjoint open sets such that for every $k \in \mathcal{K}$, $\hat{\pi}_{|\hat{V}_x^k}$ is a homeomorphism between $\hat{V}_x^k$ and $\hat{V}_x$.

**Step 8:** for every $x \in G$, there is an odd number of pairwise stable networks of the society $v^x = \varphi^{-1}(x)$.

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

$$ \hat{\pi}^{-1}(s(x)) = \{y_x^k : k \in \mathcal{K}\} $$

for some $y_x^k \in \hat{V}_x^k$, $k \in \mathcal{K}$. Also from Property (v) of local degree (see Appendix 4.2) we obtain that $\text{deg}(\hat{\pi})_{|y_x^k}$ is equal to 1 or -1 for every $k \in \mathcal{K}$. Now, from additivity of the topological degree with respect to local degrees (see Appendix 4.2, Property (vi)) we obtain (modulo 2) that

$$ 1 = \text{deg}(\hat{\pi}) = \sum_{k \in \mathcal{K}} \text{deg}(\hat{\pi})_{|y_x^k} = \sum_{k \in \mathcal{K}} 1 = \text{card}(\mathcal{K}) = K_x [2] $$

i.e. that $K_x$ is odd.
Step 9: the general case.

We now return to the general case. We recall that for every $i \in N$, $\varphi_i : \mathcal{U}_i \to \mathbb{R}^{m_i}$ is the topological embedding which associates to any polynomial function in $\mathcal{U}_i$ its coefficients in $\mathbb{R}^{m_i}$, $\mathbb{R}_{\delta_i}[g]$ is the vector space of polynomial functions with a degree less or equal to $\delta_i \in \mathbb{N}$, and $\varphi := \times_{i \in N} \varphi_i : \mathcal{U} \to \mathbb{R}^m$.

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

$$K_{-i} := \operatorname{span}(\{g^k : k \in \mathbb{N}^{|L|}, \operatorname{deg}(k) \le \delta_i\} - \{g_{ij} : j \ne i\}).$$

Then, denoting also (by abuse of notation) $\varphi_i$, the mapping from $\mathbb{R}_{\delta_i}[g]$ to $\mathbb{R}^{m_i}$ such that for every $P \in \mathbb{R}_{\delta_i}[g]$, $\varphi_i(P)$ is the $m_i$-tuple of coefficients of $P$, we can define

$$\pi_{-i} : \mathbb{R}^{m_i} \to \varphi_i(K_{-i})$$

to be the projection from the set $\mathbb{R}^{m_i}$ of coefficients of polynomial functions in $\mathbb{R}_{\delta_i}[g]$ to the set $\varphi_i(K_{-i})$ of coefficients of polynomial functions in $K_{-i}$. Since $\mathcal{S}_i = \varphi_i(\mathcal{U}_i)$ is semi-algebraic (from semi-algebraicity assumption in Definition 3.6), from Tarski-Seidenberg's theorem (see Section 3.1), each set $\pi_{-i}(\mathcal{S}_i)$ is semi-algebraic. In particular, from a well-known decomposition result for semi-algebraic sets (see Definition 3.4 in Section 3.1),

$$\pi_{-i}(\mathcal{S}_i) = \bigcup_{k=1}^{\kappa_i} T_k^i,$$

the union being disjoint, where $\kappa_i \in \mathbb{N}$ and where for every $k \in \{1, \dots, \kappa_i\}$, $T_k^i \subset \pi_{-i}(\mathcal{S}_i) \subset \varphi_i(K_{-i})$ is semi-algebraic and homeomorphic to $]0, 1^{[^i_k}$ (for some $t_k^i \in \mathbb{N}$). Thus,

$$\pi_{-1}(\mathcal{S}_1) \times \dots \times \pi_{-n}(\mathcal{S}_n) = \bigcup_{k=1}^{\kappa_1} T_k^1 \times \dots \times \bigcup_{k=1}^{\kappa_n} T_k^n = \bigcup_{(k_1, \dots, k_n) \in \Lambda} (T_{k_1}^1 \times \dots \times T_{k_n}^n) \quad (9)$$

where $\Lambda := \prod_{i \in N} \{1, \dots, \kappa_i\}$. In particular, for every $k = (k_1, \dots, k_n) \in \Lambda$, the set

$$\mathcal{U}^k := \varphi_1^{-1}(T_{k_1}^1) \times \dots \times \varphi_n^{-1}(T_{k_n}^n)$$

is homeomorphic to $]0, 1^{[^k}$, for some $t_k \in \mathbb{N}$. For every $k = (k_1, \dots, k_n) \in \Lambda$, we now consider the set

$$\mathcal{V}^k := \mathcal{U}^k + \prod_{i=1}^{n} \mathcal{A}_i = \prod_{i=1}^{n} (\varphi_i^{-1}(T_{k_i}^i) + \mathcal{A}_i)$$

and we define $\mathcal{V}_i^{k_i} := \varphi_i^{-1}(T_{k_i}^i) + \mathcal{A}_i$, for every $i \in N$. We can notice that for every $k = (k_1, \dots, k_n) \in \Lambda$ and every $i \in N$:

1. Stability assumption (in Definition 3.6) is satisfied for $\mathcal{V}_i^{k_i}$.
2. Semi-algebraicity assumption (in Definition 3.6) is satisfied for $\mathcal{V}_i^{k_i}$ because

$$ \varphi_i(\mathcal{V}_i^{k_i}) = T_{k_i}^i + \varphi_i(\mathcal{A}_i) $$

is a semi-algebraic set, since $T_{k_i}^i$ and $\varphi_i(\mathcal{A}_i)$ are both semi-algebraic sets.<fnref n="10" />

3. $\mathcal{V}_i^{k_i}$ is included in $\mathcal{F}_i$ because $T_{k_i}^i \subset \pi_{-i}(\mathcal{S}_i) = \pi_{-i}(\varphi_i(\mathcal{U}_i))$, which implies that $\varphi_i^{-1}(T_{k_i}^i) \subset (\varphi_i^{-1} \circ \pi_{-i} \circ \varphi_i)(\mathcal{U}_i) \subset \mathcal{U}_i$.

4. $\mathcal{V}_i^{k_i}$ is homeomorphic<fnref n="11" /> to $\varphi_i^{-1}(T_{k_i}^i) \times \mathcal{A}_i$, thus homeomorphic to $(0, 1)^{t_{k_i}^i}$, for some $t_{k_i}^i \in \mathbb{N}$.

Thus, from the previous steps, we know that for every $k = (k_1, \dots, k_n) \in \Lambda$, there exists a generic semi-algebraic subset $G^k$ of $\mathcal{S}^k := \varphi(\mathcal{V}^k)$ such that for every $x \in G^k$, the society $v^x = \varphi^{-1}(x)$ has an odd number of pairwise stable networks. This implies that for every $x \in G := \bigcup_{k \in \Lambda} G^k$, the society $v^x = \varphi^{-1}(x)$ has an odd number of pairwise stable networks.

To finish, we can notice that $G$ is generic in $\mathcal{S}$ because:

1. The $(\mathcal{S}^k)_{k \in \Lambda}$ forms a covering of $\mathcal{S} = \varphi(\mathcal{U})$; indeed,

$$
\begin{align*}
\bigcup_{k \in \Lambda} \mathcal{S}^k &= \bigcup_{k \in \Lambda} \varphi(\mathcal{V}^k) = \bigcup_{k \in \Lambda} \varphi\left(\prod_{i=1}^n (\varphi_i^{-1}(T_{k_i}^i) + \mathcal{A}_i)\right) = \bigcup_{k \in \Lambda} \prod_{i=1}^n (\varphi_i(\varphi_i^{-1}(T_{k_i}^i) + \mathcal{A}_i)) \\
&= \bigcup_{k \in \Lambda} \left(\prod_{i=1}^n (T_{k_i}^i + \varphi_i(\mathcal{A}_i))\right) = \bigcup_{k \in \Lambda} \left(\prod_{i=1}^n T_{k_i}^i\right) + \left(\prod_{i=1}^n \varphi_i(\mathcal{A}_i)\right) \\
&= \pi_{-1}(\mathcal{S}_1) \times \dots \times \pi_{-n}(\mathcal{S}_n) + \left(\prod_{i=1}^n \varphi_i(\mathcal{A}_i)\right) \text{ (from Equation (9))} \\
&= (\pi_{-1}(\mathcal{S}_1) + \varphi_1(\mathcal{A}_1)) \times \dots \times (\pi_{-n}(\mathcal{S}_n) + \varphi_n(\mathcal{A}_n)) \\
&= (\pi_{-1}(\varphi_1(\mathcal{U}_1)) + \varphi_1(\mathcal{A}_1)) \times \dots \times (\pi_{-n}(\varphi_n(\mathcal{U}_n)) + \varphi_n(\mathcal{A}_n)) \\
&= \varphi_1(\mathcal{U}_1) \times \dots \times \varphi_n(\mathcal{U}_n) = \varphi(\mathcal{U}).
\end{align*}
$$

2. From the previous step, the complement of $G$ in $\mathcal{S}$ is included in $\bigcup_{k \in \Lambda}(\mathcal{S}^k - G^k)$: indeed, if $x \in \mathcal{S}$ and $x \notin G$, then since $(\mathcal{S}^k)_{k \in \Lambda}$ forms a covering of $\mathcal{S}$, there exists $l \in \Lambda$ such that $x \in \mathcal{S}^l$. But $x \notin G^l$, thus finally

$$ x \in \mathcal{S}^l - G^l \subset \bigcup_{k \in \Lambda} (\mathcal{S}^k - G^k) $$

whose dimension is strictly less than $\dim(\mathcal{S})$, because $\dim(\mathcal{S}^k - G^k) < \dim(\mathcal{S}^k) \le \dim(\mathcal{S})$.

<footnote n="10">¹⁰The sum of two semi-algebraic subsets $S_1$ and $S_2$ of some Euclidean space is a semi-algebraic set: $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_i(\mathcal{A}_i)$ is a subspace of $\mathbb{R}^{m_i}$, thus is semi-algebraic.</footnote>

<footnote n="11">¹¹Indeed, the mapping $f: \varphi_i^{-1}(T_{k_i}^i) \times \mathcal{A}_i \to \varphi_i^{-1}(T_{k_i}^i) + \mathcal{A}_i$, $(x, y) \mapsto x + y$ is such a homeomorphism, since the vector subspace generated by $\varphi_i^{-1}(T_{k_i}^i)$ and the vector subspace $\mathcal{A}_i$ are in direct sum.</footnote>
REFERENCES

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

[2] Venkatesh Bala and Sanjeev Goyal. A noncooperative model of network formation. *Econometrica*, 68(5):1181–1229, 2000.

[3] Coralio Ballester, Antoni Calvó-Armengol, and Yves Zenou. Who's who in networks. wanted: The key player. *Econometrica*, 74(5):1403–1417, 2006.

[4] Philippe Bich and Lisa Morhaim. On the existence of Pairwise stable weighted networks. *halshs-01564591*, July 2017.

[5] Philippe Bich and Lisa Morhaim. On the existence of pairwise stable weighted networks. *Math. Oper. Res.*, 45(4):1393–1404, 2020.

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

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

[8] Yann Bramoullé and Rachel Kranton. Public goods in networks. *Journal of Economic Theory*, 135(1):478–494, 2007.

[9] Antoni Calvó-Armengol and Rahmi İlkılıç. Pairwise-stability and nash equilibria in network formation. *International Journal of Game Theory*, 38(1):51–79, 2009.

[10] 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.

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

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

[13] Allen Hatcher. *Algebraic topology*. Cambridge Univ. Press, Cambridge, 2000.

[14] P. Jean-Jacques Herings and Yang Zhan. The computation of pairwise stable networks. Research Memorandum 004, Maastricht University, Graduate School of Business and Economics (GSBE), January 2021.
[15] 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 (MET-EOR), January 2000.

[16] Matthew O. Jackson and Asher Wolinsky. A strategic model of social and economic networks. *Journal of Economic Theory*, 71(1):44–74, 1996.

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

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

[19] 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.

[20] 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.

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