Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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 is the simplest proof that I know of. Though I can conceive of simpler proofs.

http://cupid.economics.uq.edu.au/mclennan/Papers/kakutani60.pdf

share|improve this answer
    
Thanks! There's a lot of nice history in this paper. And I guess you wouldn't say any proof of the existence of a Nash equilibrium for two person finite zero sum games is a proof of Kakutani's fixed point theorem? The trick in this paper seems to involve taking $A$ arbitrary, $B = I$. –  John Baez Feb 12 '13 at 1:13
    
Here is what seems to amount to a simplified version of the argument that shows how one can prove the Brouwer fixed point theorem from the existence of Nash equilibria in two player games (modulo a limiting compactness argument): theoryclass.wordpress.com/2012/01/05/… –  Michael Greinecker Feb 12 '13 at 7:50
    
@John Baez existence of a Nash equilibrium for two person finite zero sum games is a linear programming problem. The existence of symmetric equilibrium for a two person finite game with symmetric payoff matrices that are symmetric is a quadratic programming problem. The general case is a general fixed point problem. Recently, two person Nash equilibrium has been shown to be PPAD complete in computational economics. That means you can reduce the problem in polynomial time to Sperner's lemma with $2^n$ many vertices as strategies. –  Rabee Tourky Feb 14 '13 at 4:49
    
@Michael Greinecker the game in that blog site is not a finite game. –  Rabee Tourky Feb 14 '13 at 4:51
    
@Rabee He explains how to prove the general result from existence for finite games using narrow convergence. That's not really practical for classroom use, but should convince mathematicians. –  Michael Greinecker Feb 19 '13 at 18:27
show 3 more comments

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 thoerems, 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.

share|improve this answer
    
Thanks! You might like to see my own proof here: johncarlosbaez.wordpress.com/2013/02/27/game-theory-part-17 johncarlosbaez.wordpress.com/2013/03/05/game-theory-part-18 johncarlosbaez.wordpress.com/2013/03/07/game-theory-part-19 johncarlosbaez.wordpress.com/2013/03/11/game-theory-part-20 It's not very efficient but it proves a few related results in the process and only uses some basic facts, like what you said about compact sets. –  John Baez Apr 18 '13 at 22:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.