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

min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'} \geq 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

p \cdot A q \geq min_{q^{'}} p \cdot A q^{'}

If one function is

\geq

another, its maximum value is

\geq

the other function's maximum value. So, the above inequality gives

max_{p^{'}} p^{'} \cdot A q \geq 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:

min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'} \geq 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,

min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'} = max_{p^{'}} min_{q^{'}} 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 \geq p \cdot B q^{'},

since B can't improve their payoff by switching their mixed strategy. But

B = - A,

so this says

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^{'} :

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

min_{q^{'}} p \cdot A q^{'} \geq max_{p^{'}} p^{'} \cdot A q

\begin{array}{ccl} max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'} & \geq & min_{q^{'}} p \cdot A q^{'} \\ \geq & max_{p^{'}} p^{'} \cdot A q \\ \geq & 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:

for all x, max_{x^{'}} f (x^{'}) \geq f (x)

max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'} \geq 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:

for all x, f (x) \geq min_{x^{'}} f (x^{'})

max_{p^{'}} p^{'} \cdot A q \geq min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'}

max_{p^{'}} min_{q^{'}} p \cdot A q^{'} \geq min_{q^{'}} max_{p^{'}} p^{'} \cdot A q

min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'} \geq max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'}

max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'} = min_{q^{'}} max_{p^{'}} p^{'} \cdot A q^{'}

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} max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'} & \geq & min_{q^{'}} p \cdot A q^{'} \\ \geq & max_{p^{'}} p^{'} \cdot A q \\ \geq & 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,

min_{q^{'}} p \cdot A q^{'} = max_{p^{'}} min_{q^{'}} p^{'} \cdot A q^{'}

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

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!

Game Theory (Part 17)

John Baez

Nash equilibria give maximin strategies