1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Giskard
    Oct 12, 2023 at 13:20
  • $\begingroup$ 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. $\endgroup$
    – Paul Huang
    Oct 13, 2023 at 0:49

1 Answer 1

3
$\begingroup$

An nice little proof is contained in Brown and von Neumann (1950), see also the (slightly more general) third proof in Hofbauer (2000). 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.

$\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.