Min-Max = Max-Min

EC487_Advanced_Microeconomics

Proposition The following are equivalent in any finite two player zero-sum game:

• ${\min }_{s^{-j}\in S^{-j}}{\max }_{s^j\in S^j}{v}^j(s^j,s^{-j})={\max }_{s^j\in S^j}{\min }_{s^{-j}\in S^{-j}}{v}^j(s^j,s^{-j})\forall j\in \{1,2\}$
• There exists a Nash Equilibrium $s^{\ast }\in S$.

Recall that this proposition is only suitable for the two player Zero Sum Game, (also recall the Simultaneous Move Game)

Proof

We first prove the $(<=)$ direction.

Assume that there exists a Nash Equilibrium $s^{\ast }\in S$. We would definitely have

$$\underset{s^j}{\max }{v}^j(s^j,s^{-j})\ge \underset{s^j}{\max }\underset{s^{-j}}{\min }{v}^j(s^j,s^{-j})\text{for all}{s}^{-j}$$

It’s obvious that you can’t be worse than the worst.

Since it is in the Nash Equilibrium, by definition, all $j$ would have no incentive to deviate from $s^{\ast }$. Thus we have:

$$\underset{s^{-j}}{\min }\underset{s^j}{\max }{v}^j(s^j,s^{-j})\le \underset{s^j}{\max }{v}^j(s^j,s^{\ast -j})\text{for all}{s}^j$$

Otherwise $-j$ would like to deviate from $s^{\ast -j}$.

Also, notice that

$$\underset{s^j}{\max }{v}^j(s^j,s^{\ast -j})=v^j(s^{\ast j},s^{\ast -j})=\underset{s^{-j}}{\min }{v}^j(s^{\ast j},s^{-j})$$

Combining these three inequalities, we have:

$$\underset{s^{-j}}{\min }\underset{s^j}{\max }{v}^j(s^j,s^{-j})\le \underset{s^j}{\max }\underset{s^{-j}}{\min }{v}^j(s^j,s^{-j})$$

The other direction $(=>)$ is a bit more complicated.

Suppose

${\min }_{s^{-j}\in S^{-j}}{\max }_{s^j\in S^j}{v}^j(s^j,s^{-j})={\max }_{s^j\in S^j}{\min }_{s^{-j}\in S^{-j}}{v}^j(s^j,s^{-j})\forall j\in \{1,2\}$ holds.

And assume that in Nash Equilibrium, we have $s^{\ast }=(s^{\ast 1},s^{\ast 2})$.

And for player $1$, we have:

$$s^{\ast 1}\in \arg \underset{s^1\in S^1}{\max }\underset{s^2\in S^2}{\min }{v}^1(s^1,s^2)$$

Also,

$$v^1(s^{\ast 1},s^2)\ge \underset{s^2\in S^2}{\min }{v}^1(s^{\ast 1},s^2)=\underset{s^1\in S^1}{\max }\underset{s^2\in S^2}{\min }{v}^1(s^1,s^2)=\underset{s^2\in S^2}{\min }\underset{s^1\in S^1}{\max }{v}^1(s^1,s^2)\forall s^2\in S^2$$

And notice that

$$\underset{s^2\in S^2}{\min }\underset{s^1\in S^1}{\max }{v}^1(s^1,s^2)=\underset{s^1\in S^1}{\max }{v}^1(s^1,s^{\ast 2})$$

Thus we have:

$$v^1(s^{\ast 1},s^2)\ge \underset{s^1\in S^1}{\max }{v}^1(s^1,s^{\ast 2})\forall s^2\in S^2$$

Similarly, we can also prove that for player $2$:

$$v^2(s^1,s^{\ast 2})\ge \underset{s^2\in S^2}{\max }{v}^2(s^{\ast 1},s^2)\forall s^1\in S^1$$

Thus, no player would like to deviate from $s^{\ast }$, and $s^{\ast }$ is a Nash Equilibrium.

---

Connection With Nash Equilibrium

This theorem provides proof that the relationship between Nash Equilibrium and the Min Max = Max Min