Game Theory (Part 18)

John Baez

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

You can also read comments on Azimuth, and make your own comments or ask questions there!