We’re talking about zero-sum 2-player normal form games. Last time we saw that in a Nash equilibrium for a game like this, both players must use a maximin strategy. Now let’s try to prove the converse!
In other words: let’s try to prove that if both players use a maximin strategy, the result is a Nash equilibrium.
Today we’ll only prove this is true if a certain equation holds. It’s the cool-looking equation we saw last time:
Last time we showed this cool-looking equation is true whenever our game has a Nash equilibrium. In fact, this equation is always true. In other words: it’s true for any zero-sum two-player normal form game. The reason is that any such game has a Nash equilibrium. But we haven’t showed that yet.
So, let’s do what we can easily do.
Maximin strategies give Nash equilibria… sometimes
We’re studying a zero-sum 2-player normal form game. Player A’s payoff matrix is , and player B’s payoff matrix is
We saw that a pair of mixed strategies one for player A and one for player B, is a Nash equilibrium if and only if
1) for all
2) for all
We saw that is a maximin strategy for player A if and only if:
We also saw that is a maximin strategy for player B if and only if:
With these in hand, we can easily prove our big result for the day. We’ll call it Theorem 4, continuing with the theorem numbers we started last time:
Theorem 4. Suppose we have a zero-sum 2-player normal form game for which
holds. If is a maximin strategy for player A and is a maximin strategy for player B, then is a Nash equilibrium.
Proof. Suppose that is a maximin strategy for player A and is a maximin strategy for player B. Thus:
But since ★ holds, the right sides of these two equations are equal. So, the left sides are equal too:
Now, since a function is always less than or equal to its maximum value, and greater than or equal to its minimum value, we have
But ★★ says the quantity at far left here equals the quantity at far right! So, the quantity in the middle must equal both of them:
By the definition of minimum value, the first equation in ★★★:
for all This is condition 2) in the definition of Nash equilibrium. Similarly, by the definition of maximum value, the second equation in ★★★:
for all This is condition 1) in the definition of Nash equilibrium. So, the pair is a Nash equilibrium. █