## 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.

### Nash equilibria give maximin strategies

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 \min_{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.

### 5 Responses to Game Theory (Part 17)

1. Last time we saw that in a Nash equilibrium for a game like this, both players must use a maximin strategy. […]

2. Jennifer Avila says:

I believe there is typo in the proof for theorem 2. It states “And the last inequality comes from the fact that the values of a function are always greater than or equal to its minimum value”. But in the inequality directly under this statement you put max instead of min.

• John Baez says:

Thanks for noticing that! I’ll fix it now.

3. Javier Salazar says:

For Theorem 1, does min_q’max_p’ represent all that is above or equal to the security level for A? Also, Does Theorem 2 mean that there must be an intersection of strategies for a Nash Equilibrium to exist?

• John Baez says:

To understand $\displaystyle{\min_{q'} \max_{p'} \; p' \cdot A q'}$, it’s probably best to review Theorem 1 from Part 16. The proof of this theorem says that $\displaystyle{- \min_{q'} \max_{p'} \; p' \cdot A q'}$

is the security value for player B when that player is using a maximin strategy! (The minus sign here shows up because we’re dealing with a zero-sum game.)

I don’t know what an “intersection strategies” is. By the time we get to Theorem 5, we’ll see that a Nash equilibrium always exists for the kind of game we’re talking about. But maybe this will answer your question: the equation $\displaystyle{\min_{q'} \max_{p'} \; p' \cdot A q' = \max_{p'} \min_{q'} \; p' \cdot A q'}$

says that the security level for player B when they are playing a maximin strategy is minus the security level for player A when they are playing a maximin strategy!

This site uses Akismet to reduce spam. Learn how your comment data is processed.