<p>An nice little proof is contained in <a href="https://apps.dtic.mil/sti/pdfs/AD0603877.pdf" rel="nofollow noreferrer">Brown and von Neumann (1950)</a>, see also the (slightly more general) third proof in <a href="https://homepage.univie.ac.at/josef.hofbauer/00sel.pdf" rel="nofollow noreferrer">Hofbauer (2000)</a>. This is the idea:</p>
<p>For a mixed strategy <span class="math-container">$x$</span> (a column vector in the <span class="math-container">$I$</span>-simplex) define a pure strategy <span class="math-container">$i$</span>'s <em>excess payoff</em> against <span class="math-container">$x$</span> as <span class="math-container">$k_i(x)=\max\{(Ax)_i,\,0\}$</span>. Let <span class="math-container">$\bar k(x)=\sum_{j\in I} k_j(x)$</span> be the sum of excess payoffs.</p>
<p>Now consider the system of differential equations known as the <em>Brown-von Neumann-Nash dynamics</em> (BNN dynamics), <span class="math-container">$\dot x_i=k_i(x)-x_i\bar k(x)$</span>.</p>
<p>Then it is fairly straightforward to show: The function <span class="math-container">$V(x)=\sum_{j\in I} k_j(x)^2$</span> is a global Ljapunov function for the BNN dynamics and therefore all solutions converge to the set where <span class="math-container">$V(x)=0$</span>. This set is the set of Nash equilibria, which is therefore nonempty.</p>

CC BY-SA 4.0
2023-10-12T14:49:15.697Z
2023-10-13T07:55:59.713Z
2023-10-13T07:55:59.713Z
VARulle
<p>I am trying to prove the existence of mixed-strategy NE for 2-player zero-sum symmetric game, under the condition that given they have <span class="math-container">$I$</span> pure strategies and for the pay-off matrix <span class="math-container">$A$</span>, <span class="math-container">$\exists x\in R_+^I$</span> such that <span class="math-container">$xA\ge0$</span>. I know that I can use Nash's theorem directly, but I want to prove it explicitly.</p>
<p>So far what I have done is that I proved the payoff must be 0 since <span class="math-container">$A=-A^T$</span>. And if <span class="math-container">$xA$</span> always has negative element(s), the best response of each players must be some pure strategy (by decomposing <span class="math-container">$xAy$</span>). But it seems that all these are irrelevant to a direct proof the existence of NE. Please share with me if you have any idea!</p>

CC BY-SA 4.0
2023-10-12T13:20:47.473Z
You stipulate "$\exists x\in R_+^I$ such that $xA\ge0$" but then go on to write "if $xA$ always has negative element(s)". Don't these two contradict?
Giskard
CC BY-SA 4.0
2023-10-13T00:49:29.153Z
Sorry for the confusion. I just mean that I happened to prove the "If NOT $xA\ge 0$ then NO mixed strategy NE" case, but just don't know how to deal with prove the original statement.
Paul Huang
<game-theory><nash-equilibrium>
Proving the existence of mixed-strategy NE for 2-player zero-sum symmetric game
Paul Huang
# Proving the existence of mixed-strategy NE for 2-player zero-sum symmetric game

(Asked by: username_0 on 2023-10-12)

I am trying to prove the existence of mixed-strategy NE for 2-player zero-sum symmetric game, under the condition that given they have $I$ pure strategies and for the pay-off matrix $A$, $\exists x\in R\_+^I$ such that $xA\ge0$. I know that I can use Nash's theorem directly, but I want to prove it explicitly.

So far what I have done is that I proved the payoff must be 0 since $A=-A^T$. And if $xA$ always has negative element(s), the best response of each players must be some pure strategy (by decomposing $xAy$). But it seems that all these are irrelevant to a direct proof the existence of NE. Please share with me if you have any idea!

**Tags:** game-theory, nash-equilibrium

> **Comments:**
> **username_1**: You stipulate "$\exists x\in R_+^I$ such that $xA\ge0$" but then go on to write "if $xA$ always has negative element(s)". Don't these two contradict?  
> **username_0**: Sorry for the confusion. I just mean that I happened to prove the "If NOT $xA\ge 0$ then NO mixed strategy NE" case, but just don't know how to deal with prove the original statement.  

---

## 1 answers

### Answer by username_2 on 2023-10-12. Score: 3

An nice little proof is contained in [Brown and von Neumann (1950)](https://apps.dtic.mil/sti/pdfs/AD0603877.pdf), see also the (slightly more general) third proof in [Hofbauer (2000)](https://homepage.univie.ac.at/josef.hofbauer/00sel.pdf). This is the idea:

For a mixed strategy $x$ (a column vector in the $I$-simplex) define a pure strategy $i$'s *excess payoff* against $x$ as $k\_i(x)=\max\{(Ax)\_i,\,0\}$. Let $\bar k(x)=\sum\_{j\in I} k\_j(x)$ be the sum of excess payoffs.

Now consider the system of differential equations known as the *Brown-von Neumann-Nash dynamics* (BNN dynamics), $\dot x\_i=k\_i(x)-x\_i\bar k(x)$.

Then it is fairly straightforward to show: The function $V(x)=\sum\_{j\in I} k\_j(x)^2$ is a global Ljapunov function for the BNN dynamics and therefore all solutions converge to the set where $V(x)=0$. This set is the set of Nash equilibria, which is therefore nonempty.


---

