<![CDATA[Game Theory (Part 17)]]>Last time we saw the official definition of maximin strategy. Now we’ll prove something really important. In a Nash equilibrium for a zero-sum 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!

Nash equilibria give maximin strategies

We start with a cool-looking inequality:

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'}

Proof. Since a function is always greater than or equal to its minimum value, for any mixed strategies p and q we have

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

If one function is \ge another, its maximum value is \ge the other function’s maximum value. So, the above inequality gives

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

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:

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

Next, we’ll show this cool-looking 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 zero-sum 2-player normal form game for which a Nash equilibrium exists,

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

Proof. Suppose a Nash equilibrium (p,q) exists. Then for any mixed strategy p' for player A, we have

\displaystyle{ p \cdot A q \ge p' \cdot A q}

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

\displaystyle{ p \cdot A q' \ge p \cdot A q}

Combining these two inequalities, we get

\displaystyle{ p \cdot A q' \ge p' \cdot A q}

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':

\displaystyle{ \min_{q'} p \cdot A q' \ge p' \cdot A 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':

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

It follows that

\begin{array}{ccl} \displaystyle{ \max_{p'} \min_{q'} p' \cdot A q'} &\ge& \displaystyle{ \min_{q'} p \cdot A q'} \\ \\ &\ge& \displaystyle{ \max_{p'} p' \cdot A q } \\ \\ &\ge& \displaystyle{ \min_{q'} \max_{p'} p' \cdot A q' } \end{array}

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:

\textrm{for all } x, \; \displaystyle{ \max_{x'} f(x') \ge f(x) }

so

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

And the last inequality comes from the fact that the values of a function are always greater than or equal to its minimum value:

\textrm{for all } x, \; \displaystyle{ f(x) \ge \max_{x'} f(x') }

so

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

Putting all these inequalities together, we get

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

On the other hand, Theorem 1 gives an inequality pointing the other way:

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

So, the two sides must be equal:

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

which is what we were trying to show!   █

What’s the point of this cool-looking 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 zero-sum game, both players must be using a maximin strategy!

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.

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

\begin{array}{ccl} \displaystyle{ \max_{p'} \min_{q'} p' \cdot A q'} &\ge& \displaystyle{ \min_{q'} p \cdot A q'} \\ \\ &\ge& \displaystyle{ \max_{p'} p' \cdot A q } \\ \\ &\ge& \displaystyle{ \min_{q'} \max_{p'} p' \cdot A q' } \end{array}

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,

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

Last time we saw this means that p is a maximin strategy for player A. Also,

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

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.

]]>