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

${\bf Theorem~{}1:}~{}~{}\underline{\rm minimax~{}inequality,~{}simple~{}strategies}$

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

(1)$~{}~{}\displaystyle{\max_{1\leq i\leq m}\min_{1\leq j\leq n}A_{i,j}\leq\min_{1% \leq j\leq n}\max_{1\leq i\leq m}A_{i,j}}$

(2)$~{}~{}\displaystyle{\max_{1\leq i\leq m}\min_{1\leq j\leq n}A_{i,j}=\min_{1% \leq j\leq n}\max_{1\leq i\leq m}A_{i,j}}$ if and only if $A_{i,{\tilde{j}}}\leq A_{{\tilde{i}},{\tilde{j}}}\leq A_{{\tilde{i}},j}~{}~{}~% {}~{}\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.

${\bf Proof}$ Since $\displaystyle{\min_{1\leq j\leq n}A_{i,j}\leq\max_{1\leq i\leq m}A_{i,j}~{}~{}% ~{}~{}\forall i,j}~{}~{}$. The LHS is independent of $j$ while the RHS is independent of $i$, therefore we obtain $~{}~{}\displaystyle{\max_{1\leq i\leq m}\min_{1\leq j\leq n}A_{i,j}\leq\min_{1% \leq j\leq n}\max_{1\leq i\leq m}A_{i,j}}$

${\bf Theorem~{}2:}~{}~{}\underline{\rm minimax~{}inequality,~{}mixed~{}strategies}$

Let $\displaystyle{S_{m}=\{x\in{\mathbb{R}}^{m}~{}|~{}x_{i}\geq 0~{}\forall i~{},~{% }\sum_{i=1}^{m}x_{i}=1\}\subseteq{\mathbb{R}}^{m}}$. For any $m\times n$ matrix $A_{i,j}$, we have

$~{}~{}~{}~{}\displaystyle{\max_{x\in S_{m}}\min_{y\in S_{n}}\sum_{i=1}^{m}\sum% _{j=1}^{n}A_{i,j}x_{i}y_{j}=\min_{y\in S_{n}}\max_{x\in S_{m}}\sum_{i=}^{m}% \sum_{j=1}^{n}A_{i,j}x_{i}y_{j}}$

Here $0\leq x_{i}\leq 1$ is interpreted as the probability that Player 1 will choose strategy $i$ while $0\leq y_{j}\leq 1$ is the probability that Player 2 will choose strategy $j$.

${\bf Proof}$ For any $x\in S_{m}$ and any $y\in S_{n}$ we have $\displaystyle{\max_{x\in S_{m}}\min_{y\in S_{n}}\sum_{i=1}^{m}\sum_{j=1}^{n}A_% {i,j}x_{i}y_{j}\leq\sum_{i=1}^{m}\sum_{j=1}^{n}A_{i,j}x_{i}y_{j}}$

Taking maximum for $x\in S_{m}$ on both sides, we have $\displaystyle{\max_{x\in S_{m}}\min_{x\in S_{n}}\sum_{i=1}^{m}\sum_{j=1}^{n}A_% {i,j}x_{i}y_{j}\leq\max_{s\in S_{m}}\sum_{i=1}^{m}\sum_{j=1}^{n}A_{i,j}x_{i}y_% {j}}$

Taking minimum for $y\in S_{n}$ on both sides, we have $\displaystyle{v_{1}=\max_{x\in S_{m}}\min_{y\in S_{n}}\sum_{i=1}^{m}\sum_{j=1}% ^{n}A_{i,j}x_{i}y_{j}\leq v_{2}=\min_{y\in S_{n}}\max_{x\in S_{m}}\sum_{i=1}^{% m}\sum_{j=1}^{n}A_{i,j}x_{i}y_{j}}$

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

Step 1$~{}~{}$Suppose there is a $y\in S_{n}$ such that $\displaystyle{\sum_{j=1}^{n}A_{i,j}y_{j}\leq 0}$ $~{}~{}\Rightarrow~{}~{}$There is some ${\tilde{x}}\in S_{m}$ such that $\displaystyle{\sum_{i=1}^{m}\left\lgroup\sum_{j=1}^{n}A_{i,j}y_{j}\right% \rgroup{\tilde{x}}_{i}\leq 0}$

$\Rightarrow~{}~{}\displaystyle{\underset{x\in S_{n}}{\rm max}\sum_{i=1}^{m}% \sum_{j=1}^{n}A_{i,j}x_{i}y_{j}\leq 0}$ $~{}~{}\Rightarrow~{}~{}\displaystyle{v_{2}=\underset{y\in S_{n}}{\rm min}% \underset{x\in S_{m}}{\rm max}\sum_{i=1}^{m}\sum_{j=1}^{n}A_{i,j}x_{i}y_{j}% \leq 0}~{}~{}~{}~{}(*1)$

Step 2$~{}~{}$Suppose 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\lgroup\sum_{i=1}^{m}A_{i,j}x_{i}\right% \rgroup{\tilde{y}}_{j}\geq 0}$

$\Rightarrow~{}~{}\displaystyle{\underset{y\in S_{n}}{\rm min}\sum_{i=1}^{m}% \sum_{j=1}^{n}A_{i,j}x_{i}y_{j}\geq 0}$ $~{}~{}\Rightarrow~{}~{}\displaystyle{v_{1}=\underset{x\in S_{m}}{\rm max}% \underset{y\in S_{n}}{\rm min}\sum_{i=1}^{m}\sum_{j=1}^{n}A_{i,j}x_{i}y_{j}% \geq 0}~{}~{}~{}~{}(*2)$

Combining (*1) and (*2) we see that either $0\leq v_{1}$ or $v_{2}\leq 0$ is the case and $v_{1}<0 cannot be valid. Repeat the same procedure to the matrix ${\tilde{A}}_{i,j}=A_{i,j}-\lambda$ and we see that $v_{1}-\lambda<0 is invalid, i.e. $v_{1}<\lambda is not valid for any $\lambda$. Since $\lambda$ is arbitrary, we conclude that $v_{2}\leq 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:

## References

• 1 V.F.Demyanov and V.N.Malozemov, Introduction to Minimax, Keter Publishing House Jerusalem Ltd, 1974.
Title minimax inequality MinimaxInequality 2013-03-22 16:57:16 2013-03-22 16:57:16 bchui (10427) bchui (10427) 32 bchui (10427) Theorem msc 91A99 msc 91A05