<![CDATA[Nash Equilibria]]>As you know if you’ve been reading this blog lately, I’m teaching game theory. I could use some help.

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

\displaystyle{ 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

\displaystyle{ 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 mixed strategy q'.)

Some history

The history behind my question is sort of amusing, so let me tell you about that—though I probably don’t know it all.

Nash won the Nobel Prize for a one-page proof of a more general theorem for n-person games, 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 the one I’m interested in, but only in the special case where B = -A: the so-called minimax theorem. 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? If I don’t find one, I’ll have to work through Colman’s proof and then generalize it. But I feel sure someone must have done this already.

]]>