3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Please add a reference for the third proof. $\endgroup$ Nov 27, 2022 at 11:14
  • $\begingroup$ Nash, J. F. (1950): Non-cooperative Games. Dissertation, Princeton University, Department of Mathematics. $\endgroup$
    – VARulle
    Nov 27, 2022 at 23:44
  • $\begingroup$ @VARulle I took a look; Nash used a slightly different construction in his thesis. $\endgroup$ Nov 28, 2022 at 14:03
  • 1
    $\begingroup$ @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 homepage.univie.ac.at/josef.hofbauer/00sel.pdf $\endgroup$
    – VARulle
    Nov 29, 2022 at 8:55
  • $\begingroup$ @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. $\endgroup$ Nov 29, 2022 at 8:57

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.