| Version 14 |
Version 13 |
| The Minimax inequality was first proved by John von Neumann. It is the starting point to discuss two-players zero-sum static games theory. |
The Minimax inequality was first proved by John von Neumann. It is the starting point to discuss two-players zero-sum static games theory. |
|
|
| \smallskip |
\smallskip |
|
|
| ${\bf Theorem ~1:}~~\underline{\rm Minimax~Inequality,~Simple~Strategies}$ |
${\bf Theorem ~1:}~~\underline{\rm Minimax~Inequality,~Simple~Strategies}$ |
|
|
| For any $m\times n$ matrix $A_{i,j}$, we have |
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 |
(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} }$ |
\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} = |
(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}} |
\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})$ |
\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 {\sl value} of the game. |
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 {\sl 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 }~~$. |
${\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 |
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 |
$~~\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} }$ |
\min_{1\leq j\leq n}\max_{1\leq i\leq m}A_{i,j} }$ |
|
|
| \smallskip |
\smallskip |
|
|
| ${\bf Theorem ~2:}~~\underline{\rm Minimax~Inequality,~Mixed~Strategies}$ |
${\bf Theorem ~2:}~~\underline{\rm Minimax~Inequality,~Mixed~Strategies}$ |
|
|
| Let $\displaystyle{S_m=\{x\in {\mathbb R}^m~\vert~x_i\geq 0~\forall i~,~\sum_{i=1}^mx_i=1\}\subseteq {\mathbb R}^{m} }$. |
Let $\displaystyle{S_m=\{x\in {\mathbb R}^m~\vert~x_i\geq 0~\forall i~,~\sum_{i=1}^mx_i=1\}\subseteq {\mathbb R}^{m} }$. |
| For any $m\times n$ matrix $A_{i,j}$, we have |
For any $m\times n$ matrix $A_{i,j}$, we have |
|
|
| (1)$~~\displaystyle{ \max_{x\in S_m} \min_{y\in S_n}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j \leq |
(1)$~~\displaystyle{ \max_{x\in S_m} \min_{y\in S_n}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j \leq |
| \min_{y\in S_n}\max_{x\in S_m}\sum_{i=}^m\sum_{j=1}^nA_{i,j}x_iy_j }$ |
\min_{y\in S_n}\max_{x\in S_m}\sum_{i=}^m\sum_{j=1}^nA_{i,j}x_iy_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}^nA_{i,j}x_iy_j\leq\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_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}^nA_{i,j}x_iy_j\leq\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_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}^nA_{i,j}x_iy_j\leq \max_{s\in S_m}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_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}^nA_{i,j}x_iy_j\leq \max_{s\in S_m}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j}$ |
|
|
| Taking minimum for $y\in S_n$ on both sides, we have $\displaystyle{\max_{x\in S_m}\min_{y\in S_n}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j\leq \min_{y\in S_n}\max_{x\in S_m}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j }$ |
Taking minimum for $y\in S_n$ on both sides, we have $\displaystyle{\max_{x\in S_m}\min_{y\in S_n}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j\leq \min_{y\in S_n}\max_{x\in S_m}\sum_{i=1}^m\sum_{j=1}^nA_{i,j}x_iy_j }$ |
|
|
| \smallskip |
\smallskip |
|
|
|
An entire theory on minimax has already been developed and is one of the major research area in optimization theory. The following reference contains some good sources for further reference:
|
An entire theory on minimax has already been developed and is one of the major research area in optimization. The following reference contains some good sources for further reference:
|
|
|
|
[1] {\sl Introduction to Minimax}, {\sl by V.F.Demyanov and V.N.Malozemov}, {\sl Keter Publishing House Jerusalem Ltd 1974}
|
[1] Introduction to Minimax, by V.F.Demyanov $\&$ V.N.Malozemov, Keter Publishing House Jerusalem Ltf 1974
|
