Is there a nice elementary proof of the existence of Nash equilibria for 2-person games?
Here's the theorem I have in mind. Suppose $A$ and $B$ are $m \times n$ matrices of real numbers. Say a mixed strategy for player A is a vector $p \in \mathbb{R}^m$ with
$$ p_i \ge 0 , \quad \sum_i p_i = 1 $$
and a mixed strategy for player B is a vector $q \in \mathbb{R}^n$ with
$$ q_i \ge 0 , \quad \sum_j q_j = 1 $$
A Nash equilibrium is a pair consisting of a mixed strategy $p$ for A and a mixed strategy $q$ for B such that:
-
For every mixed strategy $p'$ for A, $p' \cdot A q \le p \cdot A q$.
-
For every mixed strategy $q'$ for B, $p \cdot B q' \le p \cdot B q$.
(The idea is that $p \cdot A q$ is the expected payoff to player A when A chooses mixed strategy $p$ and B chooses $q$. Condition 1 says A can't improve their payoff by unilaterally switching to some mixed strategy $p'$. Similarly, condition 2 says B can't improve their expected payoff by unilaterally switching to some $q'$.)
Nash won the Nobel prize for a one-page proof of a more general theorem for $n$-person games here, but his proof uses Kakutani's fixed-point theorem, which seems like overkill, at least for the 2-person case. There is also a proof using Brouwer's fixed-point theorem; see here for the $n$-person case and here for the 2-person case. But again, this seems like overkill.
Earlier, von Neumann had proved a result which implies this one in the special case where $B = -A$: the so-called minimax theorem for 2-player zero-sum games. Von Neumann wrote:
As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved.
I believe von Neumann used Brouwer's fixed point theorem, and I get the impression Kakutani proved his fixed point theorem in order to give a different proof of this result! Apparently when Nash explained his generalization to von Neumann, the latter said:
That's trivial, you know. That's just a fixed point theorem.
But you don't need a fixed point theorem to prove von Neumann's minimax theorem! There's a more elementary proof in an appendix to Andrew Colman's 1982 book Game Theory and its Applications in the Social and Biological Sciences. He writes:
In common with many people, I first encountered game theory in non-mathematical books, and I soon became intrigued by the minimax theorem but frustrated by the way the books tiptoed around it without proving it. It seems reasonable to suppose that I am not the only person who has encountered this problem, but I have not found any source to which mathematically unsophisticated readers can turn for a proper understanding of the theorem, so I have attempted in the pages that follow to provide a simple, self-contained proof with each step spelt out as clearly as possible both in symbols and words.
This proof is indeed very elementary. The deepest fact used is merely that a continuous function assumes a maximum on a compact set – and actually just a very special case of this. So, this is very nice.
Unfortunately, the proof is spelt out in such enormous elementary detail that I keep falling asleep halfway through! And worse, it only covers the case $B = -A$.
Is there a good references to an elementary but terse proof of the existence of Nash equilibria for 2-person games?
Best Answer
Any proof of the existence of a Nash equilibrium for two person finite games games is a proof of Kakutani's fixed point theorem. This (by A. McLennan and me) is the simplest proof that I know of, though I can conceive of simpler proofs.