Simple proof of the existence of Nash equilibria for 2-person games?

Question

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:

1. For every mixed strategy $p'$ for A, $p' \cdot A q \le p \cdot A q$.

2. 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?

Answer 1

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.

Answer 2

I, too, have been curious about a short proof of von Neumann's Minimax theorem for matrix games which might be explained to undergraduates. Without introducing any concepts from linear programming and without using hyperplane arrangements or fixed point theorems, I sat down and hammered out a proof (which is uses similar ideas as other proofs of the theorem). It is posted at

http://www.calpoly.edu/~aamendes/Minimax.pdf

This is not a proof of Nash's more general theorem as referenced in the question.

The heaviest machinery used (besides an overall level of mathematical sophisitcation usually not seen in undergraduates) is the fact that if $C$ is compact, then a continous function $f : C \rightarrow \mathbb{R}$ attains its minimum.