minimax inequality

The minimax inequality was first proved by John von Neumann. It is the starting point to discuss two-players zero-sum static games theory.

$\mathrm{𝐓𝐡𝐞𝐨𝐫𝐞𝐦}\mathrm{𝟏}:\underset{¯}{\mathrm{minimax}\mathrm{inequality},\mathrm{simple}\mathrm{strategies}}$

For any $m\times n$ matrix $A_{i,j}$, we have

(1)$\underset{1\le i\le m}{\max }\underset{1\le j\le n}{\min }{A}_{i,j}\le \underset{1\le j\le n}{\min }\underset{1\le i\le m}{\max }{A}_{i,j}$

(2)$\underset{1\le i\le m}{\max }\underset{1\le j\le n}{\min }{A}_{i,j}=\underset{1\le j\le n}{\min }\underset{1\le i\le m}{\max }{A}_{i,j}$ if and only if $A_{i,\tilde{j}}\le A_{\tilde{i},\tilde{j}}\le A_{\tilde{i},j}\mathit{\hspace{1em}\hspace{0.25em}}\forall i,j$ is valid for some $(\tilde{i},\tilde{j})$

For a 2 players zero-sum game, the entries of $A_{i,j}$ is interpreted as the payoff when player 1 has chosen the $i^{th}$ strategy while player 2 has chosen the $j^{th}$ strategy. The value $A_{\tilde{i},\tilde{j}}$ is known as the value of the game.

$\mathrm{𝐏𝐫𝐨𝐨𝐟}$ Since $\underset{1\le j\le n}{\min }{A}_{i,j}\le \underset{1\le i\le m}{\max }{A}_{i,j}\mathit{\hspace{1em}\hspace{0.25em}}\forall i,j$. The LHS is independent of $j$ while the RHS is independent of $i$, therefore we obtain $\underset{1\le i\le m}{\max }\underset{1\le j\le n}{\min }{A}_{i,j}\le \underset{1\le j\le n}{\min }\underset{1\le i\le m}{\max }{A}_{i,j}$

$\mathrm{𝐓𝐡𝐞𝐨𝐫𝐞𝐦}\mathrm{𝟐}:\underset{¯}{\mathrm{minimax}\mathrm{inequality},\mathrm{mixed}\mathrm{strategies}}$

Let $S_m=\{x\in {ℝ}^m|x_i\ge 0\forall i,{\displaystyle \sum _{i=1}^m}{x}_i=1\}\subseteq {ℝ}^m$. For any $m\times n$ matrix $A_{i,j}$, we have

$\underset{x\in S_m}{\max }\underset{y\in S_n}{\min }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j=\underset{y\in S_n}{\min }\underset{x\in S_m}{\max }{\displaystyle \sum _{i=}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j$

Here $0\le x_i\le 1$ is interpreted as the probability that Player 1 will choose strategy $i$ while $0\le y_j\le 1$ is the probability that Player 2 will choose strategy $j$.

$\mathrm{𝐏𝐫𝐨𝐨𝐟}$ For any $x\in S_m$ and any $y\in S_n$ we have $\underset{x\in S_m}{\max }\underset{y\in S_n}{\min }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j\le {\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j$

Taking maximum for $x\in S_m$ on both sides, we have $\underset{x\in S_m}{\max }\underset{x\in S_n}{\min }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j\le \underset{s\in S_m}{\max }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j$

Taking minimum for $y\in S_n$ on both sides, we have $v_1=\underset{x\in S_m}{\max }\underset{y\in S_n}{\min }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j\le v_2=\underset{y\in S_n}{\min }\underset{x\in S_m}{\max }{\displaystyle \sum _{i=1}^m}{\displaystyle \sum _{j=1}^n}{A}_{i,j}{x}_i{y}_j$

The prove of other half of the inequality takes two steps:

Step 1Suppose there is a $y\in S_n$ such that ${\displaystyle \sum _{j=1}^n}{A}_{i,j}{y}_j\le 0$ $\Rightarrow$There is some $\tilde{x}\in S_m$ such that ${\displaystyle \sum _{i=1}^m}\left({\displaystyle \sum _{j=1}^n}{A}_{i,j}{y}_j\right){\tilde{x}}_i\le 0$

$\Rightarrow \underset{x\in S_n}{\max }{\displaystyle \sum _{\mathrm{i}=1}^{\mathrm{m}}}{\displaystyle \sum _{\mathrm{j}=1}^{\mathrm{n}}}{\mathrm{A}}_{\mathrm{i},\mathrm{j}}{\mathrm{x}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{j}}\le 0$ $\Rightarrow v_2=\underset{y\in S_n}{\min }\underset{\mathrm{x}\in {\mathrm{S}}_{\mathrm{m}}}{\max }{\displaystyle \sum _{\mathrm{i}=1}^{\mathrm{m}}}{\displaystyle \sum _{\mathrm{j}=1}^{\mathrm{n}}}{\mathrm{A}}_{\mathrm{i},\mathrm{j}}{\mathrm{x}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{j}}\le 0\mathit{\hspace{1em}\hspace{0.25em}}(*1)$

Step 2Suppose there is a $x\in S_m$ such that ${\displaystyle \sum _{i=1}^m}{A}_{i,j}{x}_i{y}_j>0$ $\Rightarrow$There is some $\tilde{y}\in S_n$ such that ${\displaystyle \sum _{j=1}^n}\left({\displaystyle \sum _{i=1}^m}{A}_{i,j}{x}_i\right){\tilde{y}}_j\ge 0$

$\Rightarrow \underset{y\in S_n}{\min }{\displaystyle \sum _{\mathrm{i}=1}^{\mathrm{m}}}{\displaystyle \sum _{\mathrm{j}=1}^{\mathrm{n}}}{\mathrm{A}}_{\mathrm{i},\mathrm{j}}{\mathrm{x}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{j}}\ge 0$ $\Rightarrow v_1=\underset{x\in S_m}{\max }\underset{\mathrm{y}\in {\mathrm{S}}_{\mathrm{n}}}{\min }{\displaystyle \sum _{\mathrm{i}=1}^{\mathrm{m}}}{\displaystyle \sum _{\mathrm{j}=1}^{\mathrm{n}}}{\mathrm{A}}_{\mathrm{i},\mathrm{j}}{\mathrm{x}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{j}}\ge 0\mathit{\hspace{1em}\hspace{0.25em}}(*2)$

Combining (*1) and (*2) we see that either $0\le v_1$ or $v_2\le 0$ is the case and cannot be valid. Repeat the same procedure to the matrix ${\tilde{A}}_{i,j}=A_{i,j}-\lambda$ and we see that is invalid, i.e. is not valid for any $\lambda$. Since $\lambda$ is arbitrary, we conclude that $v_2\le v_1$.

An entire theory on minimax has already been developed and is one of the major research area in optimization theory. The following contains some good sources for further reference:

Title	minimax inequality
Canonical name	MinimaxInequality
Date of creation	2013-03-22 16:57:16
Last modified on	2013-03-22 16:57:16
Owner	bchui (10427)
Last modified by	bchui (10427)
Numerical id	32
Author	bchui (10427)
Entry type	Theorem
Classification	msc 91A99
Classification	msc 91A05