16
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$
    – John Baez
    Feb 12, 2013 at 1:13
  • $\begingroup$ 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/… $\endgroup$ Feb 12, 2013 at 7:50
  • $\begingroup$ @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. $\endgroup$ Feb 14, 2013 at 4:49
  • $\begingroup$ @Michael Greinecker the game in that blog site is not a finite game. $\endgroup$ Feb 14, 2013 at 4:51
  • 1
    $\begingroup$ @John Baes the computational complexity relationship between 2NASH and finding a fixed point has recently been establishment in the literature on PPAD complexity classes. Google PPAD 2-Nash $\endgroup$ Mar 9, 2013 at 2:07
1
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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