<p>The first step is showing that <span class="math-container">$BR^\epsilon$</span> is a continuous function from the compact convex set <span class="math-container">$\Sigma$</span> to itself, which amounts to showing <span class="math-container">$BR_n^\epsilon$</span> is a continuous function for each <span class="math-container">$n$</span>.</p>
<p>First, note that <span class="math-container">$G_n$</span> and is linear in <span class="math-container">$\Sigma_n$</span> and, therefore, concave. Since <span class="math-container">$h_n$</span> is strictly concave, the function <span class="math-container">$G_n^\epsilon$</span> is strictly concave as the sum of a concave function and a strictly concave function. Now, a strictly concave function can have at most one maximizer, otherwise, there would be a proper convex combination of two maximizers with a strictly higher value. Also, the function <span class="math-container">$G_n^\epsilon$</span> is continuous on <span class="math-container">$\Sigma$</span> and <span class="math-container">$\Sigma_n$</span>, a compact set, so a maximum exists. To show the unique maximizer is a continuous function of <span class="math-container">$\Sigma_{-n}$</span>, you can use that the best-reply correspondence is upper hemicontinuous by Berge's maximum theorem, which in the case of a function reduces to continuity; the problem als.</p>
<p>Second, to see that <span class="math-container">$\sigma^{\epsilon} \underset{\epsilon \to 0}{\to} \sigma$</span> implies that <span class="math-container">$\sigma$</span> is a Nash equilibrium, suppose it does not. Then there exists some <span class="math-container">$n$</span> and some <span class="math-container">$\tau_n\in\Sigma_n$</span> such that <span class="math-container">$$G_n(\tau_n,\sigma_{-n})-G_n(\sigma_n,\sigma_{-n})&gt;0.$$</span> The function <span class="math-container">$$\sigma'\mapsto G_n(\tau_n,\sigma_{-n}')-G_n(\sigma_n',\sigma_{-n}')$$</span> is continuous, so for some <span class="math-container">$\epsilon$</span> we must have <span class="math-container">$$G_n(\tau_n,\sigma_{-n}^\epsilon)-G_n(\sigma_n^\epsilon,\sigma_{-n}^\epsilon)&gt;0,$$</span> which gives us a contradiction.</p>

CC BY-SA 4.0
2022-11-27T12:14:00.800Z
2022-11-28T01:04:44.020Z
2022-11-28T01:04:44.020Z
Michael Greinecker
<p>I know there are two proofs of the existence of Nash equilibrium: One by using Kakutani's fixed point theorem in Nash (1950), and the other by using Brouwer's fixed point theorem in Nash (1951).</p>
<p>I saw a third proof but lack of details. Could anyone help me fill in the details and understand the proof? I really appreciate it!</p>
<p>The background information is the following:</p>
<p>Let G denote a game with n players. Let <span class="math-container">$S = \prod_n S_n$</span> where <span class="math-container">$S_n$</span> is player n's finite pure strategy set. Let <span class="math-container">$G_n: S \to \mathbb R$</span> denote the payoff function. Let <span class="math-container">$\Sigma_n$</span> be player n's set of mixed strategies:</p>
<p><span class="math-container">$$\Sigma_{n} = \{ \sigma_{n} \in \mathbb{R}^{S_{n}}_{+} \vert \sum_{s_n \in S_n} \sigma_{n,s_n} = 1 \}$$</span></p>
<p>Let <span class="math-container">$\Sigma = \prod_n \Sigma_n$</span>. Then <span class="math-container">$G_n(\sigma) = \sum_{s \in S} G_n(s)\sigma_{1,s_1} \dots \sigma_{n,s_n}$</span>.</p>
<p><span class="math-container">$\forall n$</span>, <span class="math-container">$\Sigma_{-n} = \prod_{m \neq n} \Sigma_m$</span>. Then, <span class="math-container">$G_n(\sigma) = \sum_{s_n \in S_n} G_n(s_n, \sigma_{-n})\sigma_{n,s_n}$</span></p>
<p>Definition: <span class="math-container">$\sigma^{\ast}$</span> is a Nash equilibrium of G if <span class="math-container">$\forall n$</span>, <span class="math-container">$\tau_n \in \Sigma_n$</span>,
<span class="math-container">$G_n(\sigma^{\ast}) \ge G_n(\tau_n, \sigma_{-n})$</span></p>
<p>Lemma: <span class="math-container">$\sigma^{\ast}$</span> is a Nash equilibrium if and only if <span class="math-container">$\forall n, s_n, G_n(\sigma^{\ast}) \ge G_n(s_n, \sigma_{-n})$</span></p>
<p>Now we have the existence theorem:</p>
<p><span class="math-container">$\mathbf {Theorem: \ G \ has \ a \ Nash \ equilibrium.}$</span></p>
<p>The third <span class="math-container">$\mathbf {proof}$</span> goes like this:</p>
<p><span class="math-container">$\forall n$</span>, let
<span class="math-container">$$h_n: \Sigma_n \to \mathbb R$$</span>
be a strictly concave continuous function.
<span class="math-container">$\forall \epsilon \gt 0$</span>, define
<span class="math-container">$$G^{\epsilon}_n:\Sigma \to \mathbb R$$</span>
by <span class="math-container">$G^{\epsilon}_n(\sigma) = G_n(\sigma)+\epsilon h_n(\sigma_n)$</span>
Then the best response function
<span class="math-container">$${BR}^{\epsilon}_n(\sigma) = \underset{\tau_n \in \Sigma_n}{ArgMax} \  G^{\epsilon}_n(\sigma_{-n}, \tau_n)$$</span>.</p>
<p>Also,
<span class="math-container">$${BR}^{\epsilon} = {BR}^{\epsilon}_1 \times \dots \times {BR}^{\epsilon}_n$$</span>
Apply Brouwer's fixed point theorem to get a fixed point <span class="math-container">$\sigma^{\epsilon}$</span> of <span class="math-container">${BR}^{\epsilon}$</span>.</p>
<p>Now, take a convergent sequence {<span class="math-container">$\sigma^{\epsilon}$</span>} such that
<span class="math-container">$$\sigma^{\epsilon} \underset{\epsilon \to 0}{\to} \sigma$$</span>
Then <span class="math-container">$\sigma$</span> is a Nash equilibrium of G.</p>
<p>Basically, I cannot see why Brouwer's fixed point theorem can be applied in that step. Also, in the last step, I cannot understand why is <span class="math-container">$\sigma$</span> is a Nash equilibrium of G.</p>

CC BY-SA 4.0
2022-11-27T11:14:11.553Z
Please add a reference for the third proof.
Michael Greinecker
CC BY-SA 4.0
2022-11-27T23:44:29.863Z
Nash, J. F. (1950): Non-cooperative Games. Dissertation, Princeton
University, Department of Mathematics.
VARulle
CC BY-SA 4.0
2022-11-28T14:03:43.367Z
@VARulle I took a look; Nash used a slightly different construction in his thesis.
Michael Greinecker
CC BY-SA 4.0
2022-11-29T08:55:12.130Z
@MichaelGreinecker, true. Tbh, I didn't even look it up, just had a look at where I remembered having seen it---the "second proof" chapter in https://homepage.univie.ac.at/josef.hofbauer/00sel.pdf
VARulle
CC BY-SA 4.0
2022-11-29T08:57:33.127Z
@VARulle That makes sense. It is also a nicer reference than the original thesis. Nash's handwriting, used for the formulas, makes me feel good about mine.
Michael Greinecker
<game-theory><nash-equilibrium>
Existence of Nash Equilibrium
Teacup
# Existence of Nash Equilibrium

(Asked by: username_0 on 2022-11-27)

I know there are two proofs of the existence of Nash equilibrium: One by using Kakutani's fixed point theorem in Nash (1950), and the other by using Brouwer's fixed point theorem in Nash (1951).

I saw a third proof but lack of details. Could anyone help me fill in the details and understand the proof? I really appreciate it!

The background information is the following:

Let G denote a game with n players. Let $S = \prod\_n S\_n$ where $S\_n$ is player n's finite pure strategy set. Let $G\_n: S \to \mathbb R$ denote the payoff function. Let $\Sigma\_n$ be player n's set of mixed strategies:

$$\Sigma\_{n} = \{ \sigma\_{n} \in \mathbb{R}^{S\_{n}}\_{+} \vert \sum\_{s\_n \in S\_n} \sigma\_{n,s\_n} = 1 \}$$

Let $\Sigma = \prod\_n \Sigma\_n$. Then $G\_n(\sigma) = \sum\_{s \in S} G\_n(s)\sigma\_{1,s\_1} \dots \sigma\_{n,s\_n}$.

$\forall n$, $\Sigma\_{-n} = \prod\_{m \neq n} \Sigma\_m$. Then, $G\_n(\sigma) = \sum\_{s\_n \in S\_n} G\_n(s\_n, \sigma\_{-n})\sigma\_{n,s\_n}$

Definition: $\sigma^{\ast}$ is a Nash equilibrium of G if $\forall n$, $\tau\_n \in \Sigma\_n$,
$G\_n(\sigma^{\ast}) \ge G\_n(\tau\_n, \sigma\_{-n})$

Lemma: $\sigma^{\ast}$ is a Nash equilibrium if and only if $\forall n, s\_n, G\_n(\sigma^{\ast}) \ge G\_n(s\_n, \sigma\_{-n})$

Now we have the existence theorem:

$\mathbf {Theorem: \ G \ has \ a \ Nash \ equilibrium.}$

The third $\mathbf {proof}$ goes like this:

$\forall n$, let
$$h\_n: \Sigma\_n \to \mathbb R$$
be a strictly concave continuous function.
$\forall \epsilon \gt 0$, define
$$G^{\epsilon}\_n:\Sigma \to \mathbb R$$
by $G^{\epsilon}\_n(\sigma) = G\_n(\sigma)+\epsilon h\_n(\sigma\_n)$
Then the best response function
$${BR}^{\epsilon}\_n(\sigma) = \underset{\tau\_n \in \Sigma\_n}{ArgMax} \ G^{\epsilon}\_n(\sigma\_{-n}, \tau\_n)$$.

Also,
$${BR}^{\epsilon} = {BR}^{\epsilon}\_1 \times \dots \times {BR}^{\epsilon}\_n$$
Apply Brouwer's fixed point theorem to get a fixed point $\sigma^{\epsilon}$ of ${BR}^{\epsilon}$.

Now, take a convergent sequence {$\sigma^{\epsilon}$} such that
$$\sigma^{\epsilon} \underset{\epsilon \to 0}{\to} \sigma$$
Then $\sigma$ is a Nash equilibrium of G.

Basically, I cannot see why Brouwer's fixed point theorem can be applied in that step. Also, in the last step, I cannot understand why is $\sigma$ is a Nash equilibrium of G.

**Tags:** game-theory, nash-equilibrium
> **Comments:**
> **username_1**: Please add a reference for the third proof.  
> **username_2**: Nash, J. F. (1950): Non-cooperative Games. Dissertation, Princeton University, Department of Mathematics.  
> **username_1**: @VARulle I took a look; Nash used a slightly different construction in his thesis.  
> **username_2**: @MichaelGreinecker, true. Tbh, I didn't even look it up, just had a look at where I remembered having seen it---the "second proof" chapter in https://homepage.univie.ac.at/josef.hofbauer/00sel.pdf  
> **username_1**: @VARulle That makes sense. It is also a nicer reference than the original thesis. Nash's handwriting, used for the formulas, makes me feel good about mine.  

---

## 1 answers

### Answer by username_1 on 2022-11-27. Score: 6

The first step is showing that $BR^\epsilon$ is a continuous function from the compact convex set $\Sigma$ to itself, which amounts to showing $BR\_n^\epsilon$ is a continuous function for each $n$.

First, note that $G\_n$ and is linear in $\Sigma\_n$ and, therefore, concave. Since $h\_n$ is strictly concave, the function $G\_n^\epsilon$ is strictly concave as the sum of a concave function and a strictly concave function. Now, a strictly concave function can have at most one maximizer, otherwise, there would be a proper convex combination of two maximizers with a strictly higher value. Also, the function $G\_n^\epsilon$ is continuous on $\Sigma$ and $\Sigma\_n$, a compact set, so a maximum exists. To show the unique maximizer is a continuous function of $\Sigma\_{-n}$, you can use that the best-reply correspondence is upper hemicontinuous by Berge's maximum theorem, which in the case of a function reduces to continuity; the problem als.

Second, to see that $\sigma^{\epsilon} \underset{\epsilon \to 0}{\to} \sigma$ implies that $\sigma$ is a Nash equilibrium, suppose it does not. Then there exists some $n$ and some $\tau\_n\in\Sigma\_n$ such that $$G\_n(\tau\_n,\sigma\_{-n})-G\_n(\sigma\_n,\sigma\_{-n})>0.$$ The function $$\sigma'\mapsto G\_n(\tau\_n,\sigma\_{-n}')-G\_n(\sigma\_n',\sigma\_{-n}')$$ is continuous, so for some $\epsilon$ we must have $$G\_n(\tau\_n,\sigma\_{-n}^\epsilon)-G\_n(\sigma\_n^\epsilon,\sigma\_{-n}^\epsilon)>0,$$ which gives us a contradiction.


---

