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 and are matrices of real numbers. Say a mixed strategy for player A is a vector with
and a mixed strategy for player B is a vector with
A Nash equilibrium is a pair consisting of a mixed strategy for A and a mixed strategy for B such that:
1) For every mixed strategy for A,
2) For every mixed strategy for B,
(The idea is that is the expected payoff to player A when A chooses mixed strategy and B chooses Condition 1 says A can’t improve their payoff by unilaterally switching to some mixed strategy Similarly, condition 2 says B can’t improve their expected payoff by unilaterally switching to some mixed strategy )
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 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
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.