<![CDATA[Game Theory (Part 19)]]>

<![CDATA[Game Theory (Part 19)]]>Okay, we’re almost done! We’ve been studying Nash equilibria for zero-sum 2-player normal form games. We proved a lot of things about them, but now we’ll wrap up the story by proving this:

Grand Theorem. For every zero-sum 2-player normal-form game, a Nash equilibrium exists. Moreover, a pair of mixed strategies $(p,q)$ for the two players is a Nash equilibrium if and only if each strategy is a maximin strategy.

Review

Let’s remember what we’ve proved in Part 16 and Part 18:

Theorem 1. For any zero-sum 2-player normal form game,

$\displaystyle{ \min_{q'} \max_{p'} p' \cdot A q' \ge \max_{p'} \min_{q'} \; p' \cdot A q'}$

Theorem 2. Given a zero-sum 2-player normal form game for which a Nash equilibrium exists, we have

$\displaystyle{\min_{q'} \max_{p'} \; p' \cdot A q' = \max_{p'} \min_{q'} \; p' \cdot A q'}$ ★

Theorem 3. If $(p,q)$ is a Nash equilibrium for a zero-sum 2-player normal-form game, then $p$ is a maximin strategy for player A and $q$ is a maximin strategy for player B.

Theorem 4. Suppose we have a zero-sum 2-player normal form game for which ★ holds. If $p$ is a maximin strategy for player A and $q$ is a maximin strategy for player B, then $(p,q)$ is a Nash equilibrium.

The plan

Today we’ll prove two more results. The first one is easy if you know some topology. The second one is the real heart of the whole subject:

Theorem 5. For every zero-sum 2-player normal-form game, a maximin strategy exists for each player.

Theorem 6. For every zero-sum 2-player normal-form game, ★ holds.

Putting all these results together, it’s easy to get our final result:

Proof. By Theorem 6 we know that ★ holds. By Theorem 5 we know that there exist maximin strategies for each player, say $p$ and $q.$ . Theorem 4 says that if $p$ and $q$ are maximin strategies and ★ holds, then $(p,q)$ is a Nash equilibrium. So, a Nash equilibrium exists.

Moreover, if $(p,q)$ is any Nash equilibrium, Theorem 3 says $p$ and $q$ are maximin strategies. Conversely, since ★ holds, Theorem 4 says that if $p$ and $q$ are maximin strategies, $(p,q)$ is a Nash equilibrium. █

Minimax strategies exist

Okay, let’s dive in and get to work:

Theorem 5. For every zero-sum 2-player normal-form game, a maximin strategy exists for each player.

Proof. We’ll prove this only for player A, since the proof for player B is similar. Remember that a maximin strategy for player A is a mixed strategy that maximizes A’s security level, which is a function

$\displaystyle{ f(p') = \min_{q'} p' \cdot A q' }$

So, we just need to show that this function $f$ really has a maximum. To do this, we note that

$f : \{ \textrm{A's mixed strategies} \} \to \mathbb{R}$

is a continuous function defined on a compact set. As mentioned at the start of Part 17, this guarantees that $f$ has a maximum. █

I apologize if this proof is hard to understand. All this stuff is standard if you know some topology, and a huge digression if you don’t, so I won’t go through the details. This is a nice example of how topology can be useful in other subjects!

The key theorem

Now we finally reach the heart of the whole subject: von Neumann’s minimax theorem. Our proof will be a condensed version of the one in Andrew Colman’s 1982 book Game Theory and its Applications in the Social and Biological Sciences.

Theorem 6. For every zero-sum 2-player normal-form game,

$\displaystyle{\min_{q'} \max_{p'} \; p' \cdot A q' = \max_{p'} \min_{q'} \; p' \cdot A q'}$ ★

holds.

Proof. Let’s write

$\displaystyle{ \max_{p'} \min_{q'} \; p' \cdot A q' = V}$

and

$\displaystyle{ \min_{q'} \max_{p'} \; p' \cdot A q' = W}$

Our goal is to prove ★, which says $V = W.$ By Theorem 1 we know

$V \le W$

So, we just need to prove

$V \ge W$

Here’s how we will do this. We will prove

$\textrm{if } W > 0 \textrm{ then } V \ge 0$

Since we’ll prove this for any game of the sort we’re studying, it’ll be true even if we add some real number $c$ to each entry of the payoff matrix $A_{ij}.$ Doing this adds $c$ to the expected payoff $p' \cdot A q',$ so it adds $c$ to $V$ and $W.$ So, it will follow that

$\textrm{if } V + c > 0 \textrm{ then } W + c\ge 0$

for any real number $c,$ and this implies

$V \ge W$

So, let’s get going.

Assume $W > 0.$ To prove that $V \ge 0$ , remember that

$\displaystyle{ V = \max_{p'} \min_{q'} \; p' \cdot A q'}$

To show this is greater than or equal to zero, we just need to find some mixed strategy $p$ for player A such that

$\displaystyle{ \min_{q'} \; p \cdot A q' \ge 0}$

In other words, we need to find $p$ such that

$\displaystyle{ p \cdot A q' \ge 0}$ ★★

for all mixed strategies $q'$ for player B.

How can we find $p$ for which this ★★ is true? The key is to consider the set

$C = \{ A q' : \; q' \textrm{ is a mixed strategy for B} \} \subseteq \mathbb{R}^m$

For example, if

$\displaystyle{ A = \left( \begin{array}{rrr} 2 & 10 & 4 \\-2 & 1 & 6 \end{array} \right) }$

then $C$ looks like this:

Since $W > 0$ , for any $Aq' \in C$ we have

$\displaystyle{ \max_{p'} \; p' \cdot A q' \ge \min_{q'} \max_{p'} \; p' \cdot A q' = W > 0}$

so there must exist $p'$ with

$\displaystyle{ p' \cdot A q' \ge W > 0}$

Since $p' = (p'_1, \dots, p'_m)$ is a mixed strategy, we have $p'_i \ge 0$ for all $1 \le i \le m.$ But since we’ve just seen

$\displaystyle{ \sum_{i=1}^m p'_i (Aq')_i = p' \cdot A q' \ge W > 0}$

at least one of the numbers $(Aq')_i$ must be positive. In other words, if we define a set $N$ by

$\displaystyle{ N = \{(x_1, \dots, x_m) : x_i \le 0 \textrm{ for all } i\} \subseteq \mathbb{R}^m }$

then $Aq'$ can’t be in this set:

$\displaystyle{ Aq' \notin N }$

So, we’ve seen that no point in $C$ can be in $N$ :

$C \cap N = \emptyset$

Here’s what it looks like in our example:

Now the trick is to:

• let $r$ be a point in $N$ that’s as close as possible to $C,$

and

• let $s$ be a point in $C$ that’s as close as possible to $r,$

We need to use a bit of topology to be sure these points exist, since it means finding the minima of certain functions (namely, distances). But let’s not worry about that now! We’ll complete the proof with two lemmas:

Lemma 1. $r \cdot (s-r) = 0,$ $s_i - r_i \ge 0$ for all $i,$ and $s_i - r_i > 0$ for at least one $i.$

Lemma 2. If $Aq'$ is any point in $C$ , then

$(s-r) \cdot Aq' \ge 0$

Here’s what the points $s$ and $r$ and the vector $s - r$ look like in our example:

Check to see that Lemmas 1 and 2 are true in this example! We’ll prove the lemmas later; right now let’s see how they get the job done.

First, by Lemma 1, the numbers $s_i - r_i$ are nonnegative and at least one is positive. So, we can define a mixed strategy $p$ for player A by defining

$\displaystyle{ p_i = \frac{1}{c} (s_i - r_i) }$

where $c > 0$ is a number chosen to make sure $\sum_i p_i = 1.$ (Remember, the probabilities $p_i$ must be $\ge 0$ and must sum to 1.) In other words,

$\displaystyle{ p = \frac{1}{c} (s - r) }$

Now, for any mixed strategy $q'$ for player B, we have $Aq' \in C$ and thus by Lemma 1

$(s-r) \cdot Aq' \ge 0$

Dividing by $c$ , we get

$p \cdot Aq' \ge 0$

for all $q'.$ But this is ★★, which is what we wanted to prove! So we are done! █

I will give the proofs of Lemmas 1 and 2 in the next part.

]]>