## Game Theory (Part 18)

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:

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

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

Let’s start by remembering some facts we saw in Part 16 and Part 17.

We’re studying a zero-sum 2-player normal form game. Player A’s payoff matrix is $A$, and player B’s payoff matrix is $-A.$

We saw that a pair of mixed strategies $(p,q),$ one for player A and one for player B, is a Nash equilibrium if and only if

1) $p \cdot A q \ge p' \cdot A q$ for all $p'$

and

2) $p \cdot A q \ge p \cdot A q'$ for all $q'.$

We saw that $p$ is a maximin strategy for player A if and only if:

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

We also saw that $q$ is a maximin strategy for player B if and only if:

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

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

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

holds. If $p$ is a maximin strategy for player A and $q$ is a maximin strategy for player B, then $(p,q)$ is a Nash equilibrium.

Proof. Suppose that $p$ is a maximin strategy for player A and $q$ is a maximin strategy for player B. Thus:

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

and

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

But since ★ holds, the right sides of these two equations are equal. So, the left sides are equal too:

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

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

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

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:

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

By the definition of minimum value, the first equation in ★★★:

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

says that

$\displaystyle{ p \cdot A q \le p \cdot A q' }$

for all $q'.$ This is condition 2) in the definition of Nash equilibrium. Similarly, by the definition of maximum value, the second equation in ★★★:

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

says that

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

for all $p'.$ This is condition 1) in the definition of Nash equilibrium. So, the pair $(p,q)$ is a Nash equilibrium. █

### One Response to Game Theory (Part 18)

1. […] Let’s remember what we’ve proved in Part 16 and Part 18: […]