
Last time we saw the official definition of maximin strategy. Now we'll prove something really important. In a Nash equilibrium for a zerosum game, both players must be using a maximin strategy!
To prove this we will need to look at a lot of maxima and minima. We will always assume these maxima and minima exist. For what we're doing, this is true. This can be proved using an important result from topology: given a continuous real valued function \( f: X \to \mathbb{R}\) on a compact set \( X,\) it has a minimum and a maximum. If you haven't learned this yet... well, I hope you do by the time you get a degree in mathematics.
But now is not the time to talk about this. Let's dive in!
We start with a coollooking inequality:
Theorem 1. For any zerosum 2player normal form game,
Proof. Since a function is always greater than or equal to its minimum value, for any mixed strategies \( p\) and \( q\) we have
If one function is \( \ge\) another, its maximum value is \( \ge\) the other function's maximum value. So, the above inequality gives
The right side here is just a number; the left side is a function of \( q\). Since this function is always greater than or equal to the right side, so is its minimum:
Next, we'll show this coollooking inequality becomes an equation when a Nash equilibrium exists. In fact a Nash equilibrium always exists, but we haven't shown this yet. So:
Theorem 2. Given a zerosum 2player normal form game for which a Nash equilibrium exists,
since A can't improve their payoff by switching their mixed strategy. Similarly, for any mixed strategy \( q'\) for player B, \( p \cdot B q \ge p \cdot B q',\) since B can't improve their payoff by switching their mixed strategy. But \( B = A,\) so this says
Combining these two inequalities, we get
for all \( p', q'.\) The minimum of the left side over all \( q'\) must be greater than or equal to the right side, which doesn't depend on \( q':\)
Now the maximum of the right side over all \( p'\) must be less than or equal to the left side, which doesn't depend on \( p':\)
It follows that
The middle inequality here is the one we saw a moment ago. The first inequality comes from the fact that the maximum value of a function is greater than or equal to any of its values:
so
And the last inequality comes from the fact that the values of a function are always greater than or equal to its minimum value:
so
Putting all these inequalities together, we get
On the other hand, Theorem 1 gives an inequality pointing the other way:
So, the two sides must be equal:
which is what we were trying to show! █
What's the point of this coollooking equation? One point is it connects the terms 'minimax' and 'maximin'. There's a lot more to say about it. But right now, we need it for one big thing: it lets us prove that in a Nash equilibrium for a zerosum game, both players must be using a maximin strategy!
Theorem 3. If \( (p,q)\) is a Nash equilibrium for a zerosum 2player normalform game, then \( p\) is a maximin strategy for player A and \( q\) is a maximin strategy for player B.
Proof. Let's assume that \( (p,q)\) is a Nash equilibrium. We need to show that \( p\) is a maximin strategy for player A and \( q\) is a maximin strategy for player B.
First let's remember some things we saw in the proof of Theorem 2. We assumed that \( (p,q)\) is a Nash equilibrium, and we showed
If this looks confusing, go back to the proof of Theorem 2. But now look at the beginning and the end of this chain of inequalities. We saw in Theorem 2 that they're equal! So all the stuff in the middle has to be equal, too. In particular,
Last time we saw this means that \( p\) is a maximin strategy for player A. Also,
Last time we saw this means that that \( q\) is a maximin strategy for player B. █
Whew! That was quite a workout!
But we're on a mission here, and we're not done. We've shown that if \( (p,q)\) is a Nash equilibrium, \( p\) and \( q\) are maximin strategies. Next time we'll try to show the converse: if \( p\) and \( q\) are maximin strategies, then \( (p,q)\) is a Nash equilibrium.
You can also read comments on Azimuth, and make your own comments or ask questions there!
