2 edited body

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 A 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?

1

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

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 A 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?