For any matrix , we have
(2) if and only if is valid for some
Since . The LHS is independent of while the RHS is independent of , therefore we obtain
Let . For any matrix , we have
Here is interpreted as the probability that Player 1 will choose strategy while is the probability that Player 2 will choose strategy .
For any and any we have
Taking maximum for on both sides, we have
Taking minimum for on both sides, we have
The prove of other half of the inequality takes two steps:
Step 1Suppose there is a such that There is some such that
Step 2Suppose there is a such that There is some such that
Combining (*1) and (*2) we see that either or is the case and cannot be valid. Repeat the same procedure to the matrix and we see that is invalid, i.e. is not valid for any . Since is arbitrary, we conclude that .
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:
- 1 V.F.Demyanov and V.N.Malozemov, Introduction to Minimax, Keter Publishing House Jerusalem Ltd, 1974.
|Date of creation||2013-03-22 16:57:16|
|Last modified on||2013-03-22 16:57:16|
|Last modified by||bchui (10427)|