# A constructive and elementary proof of Reny's theorem

Philippe Bich

► To cite this version:

Philippe Bich. A constructive and elementary proof of Reny's theorem. 2006. halshs-00082760

HAL Id: halshs-00082760

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

Submitted on 28 Jun 2006

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
<figure><img src="image_2.png" /></figure>

Cahiers de la MSE

A constructive and elementary proof
of Reny's theorem

Philippe BICH

2006.01

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

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

Maison des Sciences Économiques, 106-112 boulevard de L'Hôpital, 75647 Paris Cedex 13
http://mse.univ-paris1.fr/Publicat.htm

ISSN : 1624-0340
# A constructive and elementary proof of Reny's Theorem *

Bich philippe †

## Abstract

In a recent but well known paper (see [2]), Reny proved the existence of Nash equilibria for better-reply-secure games, with possibly discontinuous payoff functions. Reny's proof is purely existential, and is similar to a contradiction proof: it gives no hint of a method to compute a Nash equilibrium in the class of games considered.

In this paper, we adapt the arguments of Reny in order to obtain, for better-reply-secure games:

1) An elementary proof of Nash equilibria existence, which is a consequence of Kakutani's theorem.

2) A "constructive" proof, in the sense that we obtain Nash equilibria as limits of fixed-point of well chosen correspondences.

To obtain a "constructive" proof, one has to add a new assumption on the strategy sets: one will suppose that they are Lindeloff spaces, a property which is very general (for example, it is true in the case of separable metric spaces).

This property seems important to obtain a constructive proof: notice that a slight adaptation of our proof provides an elementary (but purely existential) proof of Reny's result in the case where the strategy sets are not Lindeloff spaces.

<footnote>*Je remercie Jean-Marc Bonnisseau, Pascal Gourdel et Hakim Hammami pour les discussions et remarques concernant soit cet article, soit l'article de Reny.</footnote>

<footnote>†CERMSEM, France. E-mail : bich@ceremade.dauphine.fr.</footnote>
# 1 Introduction

In a recent but well known paper (see [2]), Reny proved the existence of Nash equilibria for better-reply-secure games, with possibly discontinuous payoff functions. Reny's proof is purely existential, and is similar to a contradiction proof: it gives no hint of a method to compute a Nash equilibrium in the class of games considered.

More precisely, Reny shows that finding a Nash equilibrium is equivalent to finding some element of an infinite intersection of closed subsets $E(x)$ (where $x \in X$) of a compact set $\Gamma$ (see [2], p. 1037, line 6).

Then, from the compactness assumption, he remarks that proving the existence of an element in $\cap_{x \in X} E(x)$ is equivalent to proving that for every finite subset $I$ of $X$, one has $\cap_{x \in I} E(x) \neq \emptyset$.

Finally he constructs, for every finite subset $I$ of $X$, an element $s_I$ in $\cap_{x \in I} E(x)$, as limits of fixed points of well-chosen correspondances. But it is not sure, if $X$ is not countable, that there exists some sequences $I^n \subset X$ such that $s_{I^n}$ converges to an elements of $\cap_{x \in X} E(x) \neq \emptyset$: thus Reny's proof assures that $\cap_{x \in X} E(x)$ is not empty, but it does not say how to compute an element in $\cap_{x \in X} E(x)$ (and so a Nash equilibrium).

In this paper, we adapt the arguments of Reny in order to obtain, for better-reply-secure games:

1) An elementary proof of Nash equilibria existence, which is a consequence of Kakutani's theorem, and does not rest (as Reny's proof) on the existence of Nash equilibria for some well chosen continuous.

2) A "constructive" proof, in the sense that we obtain Nash equilibria as limits of fixed-points of well chosen correspondences.

To obtain a "constructive" proof, one has to add a new assumption on the strategy sets: one will suppose that they are Lindeloff spaces, a property which is very general (for example, it is true in the case of separable metric spaces).

This property seems important to obtain a constructive proof: notice that a slight adaptation of our proof provides an elementary (but purely existential) proof of Reny's result in the case where the strategy sets are not Lindeloff spaces.
## 2 Better reply secure games

Let consider $N$ players. Each player $i$ has a pure strategy set $X_i$, a non empty and compact subset of a metric space, and a bounded payoff function

$$u_i: X = \prod_{i=1}^{N} X_i \to \mathbb{R}.$$

The symbol $-i$ denotes "all the players but $i$", i.e. for every $x \in X$, one will denote

$$x_{-i} = (x_j)_{j \neq i},$$

and

$$X_{-i} = \prod_{j \neq i} X_j.$$

Let suppose that for every $i = 1, ..., N$ and every $x_{-i} \in X_{-i}$, the mapping $u_i(., x_{-i})$ is quasiconcave.

In the following, a game satisfying these assumptions will be called a compact and quasiconcave game.

Let $u = (u_1, ..., u_N)$ and let

$$\Gamma = \overline{\{(x, u(x)), x \in X\}},$$

which is clearly a compact subset of $X \times \mathbb{R}^N$ from the assumptions above.

As in Reny [2], one defines the following notion

**Definition 2.1** Player $i$ can secure a payoff $u_i \in \mathbb{R}$ at $x = (x_i, x_{-i}) \in X$ if there exists $x'_i \in X_i$ and $V_{x_{-i}}$, an open neighborhood of $x_{-i}$, such that

$$\forall x'_{-i} \in V_{x_{-i}}, u_i(x'_i, x'_{-i}) \geq u_i.$$

A game $G$ is said to be better reply secure if for every $(x^*, u^*) \in \Gamma$ such that $x^*$ is not a Nash equilibrium, some player $i$ can secure a payoff strictly above $u_i^*$.

It is easy to see that a game is better reply secure if for every $(x^*, u^*) \in \Gamma$ such that $x^*$ is not a Nash equilibrium, there exists a player $i$ such that

$$\sup_{x_i \in X_i} \lim_{x_{-i} \to x_{-i}^*} \inf u_i(x_i, x_{-i}) > u_i^*.$$
In the following,

$$ \underline{u}_i(x_i, x_{-i}) = \liminf_{x'_{-i} \to x_{-i}} u_i(x_i, x'_{-i}). $$

One of the key result of the proof is the following lemma, which will allow to restrict oneself, in some sense, to countable strategies sets.

**Lemma 2.2** There exists a countable set $\prod_{i=1}^N X'_i \subset X$ such that for every $(x^*, u^*) \in \Gamma$ such that $x^*$ is not a Nash equilibrium, there exists $i \in \{1, ..., N\}$ such that

$$ \sup_{x_i \in X'_i} \underline{u}_i(x_i, x_{-i}^*) > u_i^*. $$

The proof of this lemma rests on Lindeloff theorem, which we now recall.

**Theorem 2.3 (Lindeloff Theorem)** Let $X$ be a separable metric space (which means that there exists $C$, a countable and dense subset of $X$). Then $X$ is a Lindeloff space, i.e. every open cover of $X$ has a countable subcover

**Proof of Lemma 1.2.** Let $\Gamma^{equ} = \{(x^*, u^*) \in \Gamma, x^*$ is an equilibrium\}$ and $\Gamma^{nequ} = \{(x^*, u^*) \in \Gamma, x^*$ is not an equilibrium\} =^c \Gamma_{equ}$.

For every $(x^*, u^*) \in \Gamma^{nequ}$, from the better reply secure assumption, for some player $i$ and for some strategy $a \in X_i$, one has

$$ u_i^* < \underline{u}_i(a, x_{-i}^*). $$

Since $\underline{u}_i$ is l.s.c. with respect to $x_{-i}$ (from its definition), this last condition remains true for every $(x, u) \in V_{x^*,u^*}(a)$, an open neighborhood of $(x^*, u^*)$ in $\Gamma^{nequ}$ well chosen.

Since $\Gamma$ is a compact subset of a metric space, it is separable. Thus $\Gamma^{nequ}$, as a subset of a separable metric space, is separable. Thus, it is a Lindeloff space, i.e. every open cover of $\Gamma^{nequ}$ has a countable subcover. Thus, there exists a countable covering $\mathcal{O}$ of $\Gamma^{nequ}$ by some open neighborhoods $V_{x^*(j),u^*(j)}(a(j))$ (where $(x^*(j), u^*(j)) \in \Gamma$ and $a(j) \in \cup_{i=1}^N X_i$ for every $j \in \mathbb{N}$), which allows to define

$$ X'_i = \{a(j), j \in \mathbb{N}\} \cap X_i $$

if it is nonempty, and $X'_i$ be any point of $X_i$ otherwise. It clearly satisfies what we want.
### 3 A constructive proof of Reny's theorem

The aim of this paper is to give a constructive and elementary proof of the following theorem, proved by Reny [2]:

**Theorem 3.1** If G is a compact, quasiconcave and better reply secure game, then it admits a pure strategy Nash equilibrium.

**Proof.** First, let $X' = \prod_{i=1}^{N} X'_{i}$, where $X'_{i}$ is defined in Lemma 1.2. Since $X'$ is countable, one can consider an increasing sequence of finite subsets

$$X^n = \prod_{i=1}^{N} X_i^n$$

of X such that

$$\cup_n X^n = X'$$

Now, one recalls that for each $i = 1, ..., N$, and since $u_i(x_i, x_{-i})$ is a l.s.c. mapping (with respect to $x_{-i}$), for every $x_i \in X_i$ and every $i = 1, ..., N$, there exists a sequence $u_i^n(x_i, \cdot)$ continuous (upon $\cdot$) with:

$$u_i^n(x_i, x_{-i}) \le u_i(x_i, x_{-i}) \quad (1)$$

and such that if $x_{-i}^n$ converges to $x_{-i}$ then

$$\liminf_n u_i^n(x_i, x_{-i}^n) \ge u_i(x_i, x_{-i}) \quad (2)$$

(See Reny [2] for a proof of the existence of such sequence).

Let us now consider the correspondance $\Phi^n$ from $\text{co}X^n$ to $\text{co}X^n$, defined by

$$\Phi^n(x) = \text{co}\{x' \in X^n, \forall a \in X^n, \forall i = 1, \dots, N, u_i^n(x'_i, x_{-i}^n) \ge u_i^n(a_i, x_{-i}^n)\}. \quad (3)$$

The correspondance $\Phi^n$ easily satisfies the assumptions of Kakutani's theorem:

1) It has convex values (from its definition).

2) It has nonempty values: indeed, for every $i = 1, ..., N$ and every $x \in X$, and since the set $X^n$ is finite, there exists $\bar{x}_i \in X_i^n$ such that

$$u_i^n(\bar{x}_i, x_{-i}) = \text{Argmax}_{a_i \in X_i^n} u_i^n(a_i, x_{-i})$$
and one has $\bar{x} = (\bar{x}_1, ..., \bar{x}_N) \in \Phi^n(x)$.

3) It has a closed graph, which is an easy consequence of the continuity of $u_i^n$ with respect to the second variable, and the fact that $X^n$ is finite.

Thus, from Kakutani's Theorem, there exists $x^n \in \text{co}(X^n)$ which is a fixed point of $\Phi^n$. It means that there exists $x'(1), ...x'(K)$ in $X^n$ such that for every $k = 1, ..., K$,

$$ \forall a \in X^n, \forall i = 1, \dots, N, u_i^n(x'_i(k), x^n_{-i}) \geq u_i^n(a_i, x^n_{-i}) \quad (4) $$

and such that

$$ x^n \in \text{co}\{x'(1), ..., x'(K)\} \quad (5) $$

From Equations (1) and from $\underline{u_i} \leq u_i$, one obtains

$$ \forall a \in X^n, \forall i = 1, \dots, N, u_i(x'_i(k), x^n_{-i}) \geq u_i^n(a_i, x^n_{-i}) \quad (6) $$

Now, from the quasi-concavity of $u_i$ with respect to the first variable and from Equation (5), one obtains

$$ \forall a \in X^n, \forall i = 1, \dots, N, u_i(x^n_i, x^n_{-i}) \geq u_i^n(a_i, x^n_{-i}) \quad (7) $$

One can suppose (extracting a subsequence if necessary) that $(x^n, u(x^n))$, which is a sequence of the compact set $\Gamma$, converges to $(x^*, u^*) \in \Gamma$. Taking the lower limit in Equation (8) and from Equation (2), one obtains

$$ \forall a \in \cup_n X^n = X', \forall i = 1, \dots, N, u_i^* \geq \underline{u}_i(a_i, x^n_{-i}) \quad (8) $$

which proves, from the choice of $X'$, that $(x^*, u^*) \in \Gamma^{\text{equ}}$, i.e. that $x^*$ is a Nash-equilibrium.

# 4 Extension to non-metric spaces

The framework adopted in this article is slightly less general than Reny's framework, since we suppose that the strategy sets are metric spaces. But this plays no real role in the proof: the only important point is that each strategy set needs to be a lindeloff space, which is a restriction that Reny
does not impose. Imposing this very general condition allows us to obtain a constructive proof.

Anyway, one could easily adapt the proof above in order to obtain a simple (non constructive) proof of Reny's Theorem, without imposing that the strategy sets are Lindeloff spaces. Indeed, suppose that there does not exist a Nash equilibrium under the assumptions of Reny's Theorem. Then the set $\Gamma^{nequ} = \Gamma$ is compact. Thus, without using Lindeloff Theorem, one obtain the following new version of Lemma 1.2.:

**Lemma 4.1** If there does not exist a Nash equilibrium, then there exists a finite set $\prod_{i=1}^{N} X'_{i} \subset X$ such that for every $(x^{*}, u^{*}) \in \Gamma$, there exists $i \in \{1, ..., N\}$ such that

$$ \sup_{x_i \in X'_i} u_i(x_i, x_{-i}^{*}) > u_i^{*}. $$

This allows to finish the proof as above (taking $X^n = X'$ in the proof). The main difference with section 3. is that in that case, Equation (8) allows only to yield a contradiction with the assumption that there does not exist a Nash equilibrium, but $x^*$ in Equation (8) may not be a Nash equilibrium.

## References

[1] Bonnisseau, J.M., Gourdel, P., Hammami, H., "Existence d'un équilibre de Nash dans un jeu discontinu", working paper.

[2] Reny, Philip J. "On the Existence of Pure and Mixed Strategy Nash Equilibria in Discontinuous Games." Econometrica, 1999, 67(5), 1029-56.