|
|
|
Viewing Version
19
of
'minimax inequality'
|
[ view 'minimax inequality'
|
back to history
]
| Title of object: |
minimax inequality |
| Canonical Name: |
MinimaxInequality |
| Type: |
Theorem |
| Created on: |
2007-04-20 02:32:57 |
| Modified on: |
2007-04-23 22:53:42 |
| Classification: |
msc:91A05, msc:91A99 |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
|
Content:
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
${\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 {\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 }~~$.
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} }$
\smallskip
${\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} }$.
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
\min_{y\in S_n}\max_{x\in S_m}\sum_{i=}^m\sum_{j=1}^nA_{i,j}x_iy_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}^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 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
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:
\begin{thebibliography}{9}
\bibitem{xyz} V.F.Demyanov~and~V.N.Malozemov, \emph{title of book}, Keter Publishing House Jerusalem Ltd, 1974.
\end{thebibliography}Introduction~to~Minimax
|
|
|
|
|
|
