# Nash equilibrium existence for some discontinuous games

Philippe Bich

► To cite this version:

Philippe Bich. Nash equilibrium existence for some discontinuous games. 2007. halshs-00188764

HAL Id: halshs-00188764

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

Submitted on 19 Nov 2007

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>

UNIVERSITÉ PARIS 1
- PANTHÉON - SORBONNE -

Documents de Travail du
Centre d'Economie de la Sorbonne

CES Working Papers

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

Nash equilibrium existence for
some discontinuous games

Philippe BICH

2007.69

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

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

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

ISSN : 1955-611X
# Nash equilibrium existence for some discontinuous games

by Philippe Bich<fnref n="1" />

Centre d'Economie de la Sorbonne - C.N.R.S., Université Paris I Panthéon Sorbonne

## Abstract

Answering to an open question of Herings et al. (see [3]), one extends their fixed point theorem to mappings defined on convex compact subset of $\mathbf{R}^n$, and not only polytopes. Such extension is important in non-cooperative game theory, where typical strategy sets are convex and compact. An application in game theory is given.

# 1 Introduction

In [2], Herings et al. prove the following new fixed point theorem for possibly discontinuous mappings:

**Theorem 1.1** Let $P$ a non empty polytope, i.e. the convex hull of a finite subset of $\mathbf{R}^n$; let $f : P \to P$ which is "locally gross direction preserving" in the following sense: for every $x \in P$ such that $f(x) \neq x$, there exists $V_x$, an open neighborhood of $x$ in $P$ such that for every $u$ and $v$ in $V_x$, $\langle f(u) - u, f(v) - v \rangle \geq 0$.

Then $f$ admits a fixed-point, i.e. there exists $\bar{x} \in P$ such that $f(\bar{x}) = \bar{x}$.

Here, and throughout this paper, for every $x \in \mathbf{R}^n$ and $y \in \mathbf{R}^n$, $\langle x, y \rangle$ denotes the eulidean scalar product of $x$ and $y$.

This theorem is a generalization of Brouwer fixed point theorem (see [1]) which says that every continuous mapping from the unit closed ball of $\mathbf{R}^n$ to itself admits a fixed point.

<footnote n="1">¹Centre d'Economie de la Sorbonne, 106/112 Boulevard de l'Hôpital, 75013 Paris.
Email: bich@univ-paris1.fr.</footnote>
The authors provide an application to the existence of equilibria for games with possibly discontinuous payoffs. There is a huge literature on discontinuous games (see, for example, [4]); a usual issue in such games is that classical fixed point theorems as Brouwer’s one cannot be directly applied to yield Nash equilibria existence. Thus, Theorem 1.1 could be a answer to this problem for some classes of discontinuous games.

Yet, there is a restriction in Theorem 1.1: the set $P$ must be a polytope.
But typical strategy sets in game theory are rather compact and convex sets.
Thus, an important question in practice is to know if Theorem 1.1 holds
true for such subset of $\mathbf{R}^n$. In [3], one can read: "whether locally gross
direction preserving is sufficient to guarantee the existence of a fixed point
on an arbitrary non empty convex and compact set is still an open question".

The aim of this paper is to answer to this question. A first natural idea to extend Theorem 1.1 to the case where $P$ is any compact and convex subset of $\mathbf{R}^n$ is the following: first, approximate $P$ by a sequence of polyhedra $P_n \subset P$; then, Theorem 1.1 applied to the mappings $\text{proj}_{P_n} \circ f|_{P_n}$ provides a sequence of fixed points $x_n$ of these mappings; finally, one could hope that the sequence $(x_n)$ converges (up to an extraction) to a fixed point of $f$. But, as the authors say: "... the discontinuities of $f$ on the boundary of $P$ prevent us from taking the limit of the sequence of polyhedra. So to resolve this problem, a different approach is needed". In this paper, we provide such a different approach.

As a matter of fact, our approach drives us to generalize strictly the
"locally gross direction preserving" property. Thus, we extend Herings et
al. in two ways: we replace polytopes by any non empty and convex subset
of $\mathbf{R}^n$, and extend their continuity assumption. Finally, we prove that our
fixed point theorem can be applied to yield the existence of Nash equilibria
in possibly discontinuous games.

**2 The main theorem**

The following theorem extend Herings et al. result to compact and convex
subsets of $\mathbf{R}^n$.

**Theorem 2.1** Let $C$ be a non empty convex and compact subset of $\mathbf{R}^n$, and let $f: C \to C$. Assume that $f$ is "locally gross direction preserving" in the following sense: for every $x \in C$ such that $f(x) \neq x$, there exists $V_x$, an open neighborhood of $x$ in $C$ such that for every $u$ and $v$ in $V_x$, $\langle f(u) - u, f(v) - v \rangle \ge 0$. Then, there exists $x \in C$ such that $f(x) = x$.
**Proof.** Throughout this paper, for every $x \in \mathbb{R}^n$ and $r \in \mathbb{R}_+$, $B(x, r)$ denotes the open ball centered at $x$ of radius $r$, for the euclidean norm of $\mathbb{R}^n$.

• Step 1: one proves that any locally gross direction preserving mapping satisfy the following property that we call half-continuity:

**Definition 2.2** A mapping $f : C \to C$ is said to be half-continuous if:

$\forall x \in C, x \neq f(x) \Rightarrow \exists p \in \mathbb{R}^n, \exists \epsilon > 0$ such that: $\forall x' \in B(x, \epsilon) \cap C, x' \neq f(x') \Rightarrow \langle p, f(x') - x' \rangle > 0$.

To prove Step 1, suppose that $f : C \to C$ is locally gross direction preserving, and prove that it is half-continuous. Let $x \in C$ such that $f(x) \neq x$, and let $V_x$ be an open neighborhood of $x$ such that for every $u$ and $v$ in $V_x$, $\langle f(u) - u, f(v) - v \rangle \ge 0$.

Let $\{f(x_1)-x_1, ..., f(x_k)-x_k\}$ be a basis of the vector space $F := \operatorname{span}\{f(y)-y, y \in V_x\}$, where $k \in \mathbb{N}^*$, and $x_1, ..., x_k$ are in $V_x$. Then define

$$p = \sum_{i=1}^{k} (f(x_i) - x_i).$$

Let $x' \in V_x$ such that $f(x') \neq x'$. One clearly have

$$\langle p, f(x') - x' \rangle \ge 0 \qquad (1)$$

from "locally gross direction preserving" property and from the definition of $p$.

Besides, since one has $\langle f(x_i) - x_i, f(x') - x' \rangle \ge 0$ for every $i = 1, ..., k$, Inequation 1 is an equality if and only if one has

$$\forall i = 1, ..., k, \langle f(x') - x', f(x_i) - x_i \rangle = 0.$$

This last property would imply $f(x') - x' \in F^{\perp} \cap F = \{0\}$, a contradiction with the assumption that $f(x') \neq x'$. Thus, Inequality 1 is strict, and Step 1 if proved.

• Step 2: supposing that $f : C \to C$ has no fixed point and is half-continuous, one builds a continuous mapping $p : C \to \mathbb{R}^n$ such that
for every $x \in C$, $\langle p(x), f(x) - x \rangle > 0$.

Suppose that $f$ admits no fixed point and is half-continuous. For every $x \in C$, and from half-continuity, there exists $p_x \in \mathbf{R}^n$ and $\epsilon_x > 0$ such that

for all $x' \in B(x, \epsilon_x) \cap C$, $\langle p_x, f(x') - x' \rangle > 0$.

One has $C \subset \cup_{x \in C} B(x, \epsilon)$. Since $C$ is compact, there exists $x_1, \dots, x_n$ in $C$ such that

$$C \subset \cup_{i=1}^{n} B(x_i, \epsilon_{x_i}).$$

Consider $\lambda_1, \dots, \lambda_n$ a partition of unity subordinate to this open covering. That means that each $\lambda_i$ is a continuous mapping from $C$ to $[0, 1]$ such that

$$\forall x \in C, \sum_{i=1}^{n} \lambda_i(x) = 1$$

and such that

$$\forall i = 1, \dots, n, \forall x' \in C, x' \notin B(x_i, \epsilon_{x_i}) \Rightarrow \lambda_i(x') = 0.$$

Define the mapping $p: C \to \mathbf{R}^n$ by

$$\forall x \in C, p(x) = \sum_{i=1}^{n} \lambda_i(x) p_{x_i}.$$

Clearly, from the properties of the $\lambda_i$, one has

$$\forall x \in C, \langle p(x), f(x) - x \rangle > 0$$

and Step 2 is proved.

### Step 3: Proof of Theorem 2.1

Suppose that $f: C \to C$, a locally gross direction preserving mapping, has no fixed point. From Step one, $f$ is half-continuous. From Step two, there exists a continuous mapping $p: C \to \mathbf{R}^n$ such that for every $x \in C$, $\langle p(x), f(x) - x \rangle > 0$.

Now, define $g: C \to C$ by

$$\forall x \in C, g(x) = \text{proj}_{C}(x + p(x)),$$
where for every $y \in \mathbb{R}^n$, $\text{proj}_C(y)$ denotes the orthogonal projection of $y$ on the convex set $C$. Clearly, $g$ is a continuous mapping. Thus, from Brouwer fixed point theorem, there exists $\bar{x} \in C$ such that $g(\bar{x}) = \bar{x}$, or equivalently $\text{proj}_C(\bar{x} + p(\bar{x})) = \bar{x}$.

Besides, from a standard characterization of projection of $y \in \mathbb{R}^n$ on a convex set $C$, one has

$$ \forall c \in C, \langle y - \text{proj}_C(y), c - \text{proj}_C(y) \rangle \le 0 $$

Applying this inequality to $y = \bar{x} + p(\bar{x})$ and $c = f(\bar{x})$, one obtains

$$ \langle \bar{x} + p(\bar{x}) - \text{proj}_C(\bar{x} + p(\bar{x})), f(\bar{x}) - \text{proj}_C(\bar{x} + p(\bar{x})) \rangle \le 0, $$

or equivalently, since $\text{proj}_C(\bar{x} + p(\bar{x})) = \bar{x}$,

$$ \langle p(\bar{x}), f(\bar{x}) - \bar{x} \rangle \le 0. $$

a contradiction with the definition of $p$. This ends the proof of the Theorem 2.1.

### 3 Extension of Theorem 2.1

In the proof given above, one can notice that one only needs that the mapping $f$ is half-continuous. Thus, from Step two and three of the previous proof, one obtains the following result:

**Theorem 3.1** Let $C$ a non empty convex compact subset of $\mathbb{R}^n$, let $f: C \to C$ half-continuous, which means: $\forall x \in C, x \ne f(x) \Rightarrow \exists p \in \mathbb{R}^n, \exists \epsilon > 0$ such that: $\forall x' \in B(x, \epsilon) \cap C, x' \ne f(x') \Rightarrow \langle p, f(x') - x' \rangle > 0$. Then $f$ admits a fixed point.

In fact, half-continuity is strictly weaker than locally gross direction preserving assumption. Indeed, geometrically, Herings et al. assumption requires that for every $x \in C$ which is not a fixed point, then $f(y) - y$ and $f(z) - z$ make a sharp angle or are orthogonal for $y$ and $z$ on some neighborhood of $x$. Our half-continuity assumption requires that for every $x \in C$ which is not a fixed point, then all the vectors $f(y) - y$ are in a same strict
half-space for $y$ on some neighborhood of $x$. This is clearly a weaker assumption. In the following example, one exhibits a large class of half-continuous mappings that may be not locally gross direction preserving:

**Example** Let $C$ a closed subset of $\mathbb{R}^n$ and $F$ a multivalued mapping from $C$ to $\mathbb{R}^n$. Suppose that $F$ has a closed graph, non empty convex values and that $F(C)$ is bounded. Suppose that for every $x \in C$ one has $x \notin F(x)$, i.e. $F$ has no fixed point. Then we assert that any selection $f$ of $F$ (i.e. for every $x \in C$, $f(x) \in F(x)$) is half-continuous. To prove this result, let $\bar{x} \in C$. Since $F(\bar{x})$ is convex and compact (because $F$ has a closed graph and $F(C)$ is bounded) and since, by assumption, $\bar{x} \notin F(\bar{x})$, a separation theorem implies that there exists $p \in \mathbb{R}^n$ such that

$$ \forall y \in F(\bar{x}), \langle p, y - \bar{x} \rangle > 0. \qquad (2) $$

and in particular, since $f$ is a selection of $F$,

$$ \langle p, f(\bar{x}) - \bar{x} \rangle > 0. \qquad (3) $$

Now, if $f$ is not half-continuous at $\bar{x}$, then from Equation 3, there exists a sequence $(x_n)_{n \in \mathbb{N}}$ of $C$ converging to $\bar{x} \in C$, and such that

$$ \forall n \in \mathbb{N}, \langle p, f(x_n) - x_n \rangle \le 0. \qquad (4) $$

Let us define, for every integer $n \in \mathbb{N}$, $y_n = f(x_n)$. Since $f$ is a selection of $F$, one has $y_n \in F(x_n)$ for every integer $n$. Since $F(C)$ is bounded, and since $F$ has a closed graph, the sequence $(y_n)_{n \in \mathbb{N}}$ converges (up to an extraction) to $\bar{y} \in F(\bar{x})$.

Passing to the limit in Equation 4, one obtains

$$ \langle p, \bar{y} - \bar{x} \rangle \le 0 \qquad (5) $$

which contradicts Equation 2, because $\bar{y} \in F(\bar{x})$.

Now, one constructs a multivalued mapping satisfying the assumptions of Example above, and a particular selection $f$ of $F$ which is not locally gross direction preserving. Let $C$ be the closed unit ball of $\mathbb{R}^2$, and define $f: C \to \mathbb{R}^2$ by $f(x, y) = (x, y) + (1, 0)$ if $x \le 0$ and $f(x, y) = (x, y) + (-1, 1)$ if $x > 0$. Define a multivalued mapping $F$ from $C$ to $\mathbb{R}^2$ by

$$ \forall (x, y) \in C, x \ne 0 \Rightarrow F(x) = \{f(x)\} $$
and

$$ \forall (0, y) \in C, F(0, y) = \{(0, y) + (-1 + 2t, 1 - t), t \in [0, 1]\}. $$

Clearly, $f$ is a selection of $F$, $F$ has non empty, convex values, and $F(C)$ is compact. We let the reader prove that $F$ has a closed graph, and clearly $F$ has no fixed points. So, $f$, which is a selection of $F$, is half-continuous (which can be checked directly).

Now, $f$ is not locally gross direction preserving at every $(0, \bar{y})$ for $\bar{y} \in [-1, 1]$. Indeed, one has $\langle f(x, y) - (x, y), f(x', y') - (x', y') \rangle = -1$ for $x \le 0$ and $x' > 0$. Thus one can not have $\langle f(x, y) - (x, y), f(x', y') - (x', y') \rangle \ge 0$ for $(x, y)$ and $(x', y')$ in a neighborhood of $(0, \bar{y})$, and so $f$ is not locally gross direction preserving at $(0, \bar{y})$.

# 4 An extension of Nash equilibrium existence theorem

In this subsection, we apply our main fixed point theorem to Game theory. Consider $n$ players, and for every $i = 1, ..., n$, let $X_i$ be the strategy space of player $i$. Suppose each $X_i$ is included in $\mathbb{R}^N$ where $N \in \mathbb{N}^*$ is fixed. For every $i = 1, ..., n$, let $b_i : \Pi_{j=1}^n X_j \to X_i$ be a best reply function of player $i$ and $b = (b_1, ..., b_n)$. For every $x = (x_1, ..., x_n) \in \Pi_{j=1}^n X_j$, $b_i(x)$ is a best strategy of player $i$, given the strategy $x_j$ of all the others players ($j \ne i$). A game $G$ is defined by the couple $G = ((X_i)_{i=1}^n, (b_i)_{i=1}^n)$.

A Nash equilibrium of $G$ is $x = (x_1, ..., x_n) \in \Pi_{j=1}^n X_j$ such that for every $i = 1, ..., n$, $b_i(x) = x_i$.

We now define half-continuous games:

**Definition 4.1** A game $G = ((X_i)_{i=1}^n, (b_i)_{i=1}^n)$ is said to be half-continuous if for every $x \in \Pi_{i=1}^n X_i$ which is not a Nash equilibrium, there exists $p \in (\mathbb{R}^N)^n$ and a neighborhood $V_x$ of $x$ in $(\mathbb{R}^N)^n$ such that for every $x' \in V_x$ which is not a Nash equilibrium, one has $\langle p, b(x') - x' \rangle > 0$.

A possible interpretation of this definition is the following: suppose there are $N$ goods, and suppose a strategy $x_i$ of each player $i = 1, ..., n$ is to specify the quantity $x_i(j)$ he wants to buy for every good $j = 1, ..., N$. Suppose that the players do not know the real prices of the $N$ goods, but each player $i = 1, ..., N$ is ready to pay $p_i$ for having one unit of each good. Consider a strategy profile $x = (x_1, ..., x_n)$. For every $i = 1, ..., n$, $p_i(b_i(x) - x_i)$ would
be the best profit that player *i* can do if he replaces his strategy $x_i$ by $b_i(x)$, given the strategy of the others. Call this the best profit of player *i* reachable from *x*.

Then, a game $G$ is half-continuous if each time $x$ is not a Nash equilibrium, then there exists a profile of prices $p = (p_1, ..., p_n)$ such that the sum of best profits of all payers reachable from $x' \in \Pi_{i=1}^n X_i$ is strictly positive, for every non Nash equilibrium $x'$ in a neighborhood of $x$.

In the following, a game $G = ((X_i)_{i=1}^n, (b_i)_{i=1}^n)$ is compact (resp. convex) if all the $X_i$ are compact (resp. convex):

**Theorem 4.2** Every compact, convex and half-continuous game

$G = ((X_i)_{i=1}^n, (b_i)_{i=1}^n)$ admits a Nash-equilibrium.

**Proof.** Let $X = \Pi_{i=1}^n X_i$. Clearly, since $G$ is half-continuous, the mapping $b: X \to X$ is half-continuous. From Theorem 3.1, $b$ admits a fixed point which is a Nash equilibrium.

References

[1] L. Brouwer, Über Abbildung von Mannigfaltigkeiten, Math. Ann. 71, 1912, 97-115.

[2] J.J. Herings, G. van der Laan, D. Talman, Z. Yang, A fixed point theorem for discontinuous functions, Operations Research Letters, to appear, 2007.

[3] J.J. Herings, G. van der Laan, D. Talman, Z. Yang, A fixed point theorem for discontinuous functions, Tinbergen Institute discussion paper, 2005-004/1.

[4] P.J. Reny, On the existence of pure and mixed strategy Nash equilibria in discontinuous games, Econometrica vol. 67, issue 5, 1999, 1029-1056.