Minimax Principle
The purpose of the applet below is to illustrate a mathematical fact that plays an important role in the Game Theory, Economics, and general optimization problems. I postpone the statement until later. See if, with the help of the applet, you can arrive at the right formulation yourself.
Given a rectangular array of numbers. In every column, select the maximum value and write it under the column. Similarly, in every row, select the minimum value and write it to the right of the column. In the applet, these computed values appear in blue. In this fashion, our original array of numbers is augmented with one (blue) row and one (blue) column. In the blue row select the minimum element and write it (in red) to the right of the row. Similarly, in the blue column select the maximum number and right it under that column. Compare the two (red) numbers. Is there any regularity? Most of the time the numbers will be different. Sometimes they will coincide. On such occasions, the applet will provide an additional clue. Try to grasp its significance.
To get a different configuration, press the Reset button. With larger matrix dimensions, it may become tiresome to keep pressing the Reset, just in order to get a matrix with a saddle point. However, each of the numbers in the matrix can be changed individualy. Click or drag the mouse off the vertical center line of each entry. The number will go down or up, depending on whether the cursor is to the left or right of the central line.
What if applet does not run? |
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander BogomolnyLet's first of all formalize the procedure. We start with an array
In a similar manner, let
Statement
- MinMax ≥ MaxMin
- The equality is achieved iff there exists an element
A_{i0,k0} that is simultaneously maximal in its column and minimal in its row.
Proof
Writing subscripts in HTML (this is the language of the Web) is somewhat awkward. Let's just agree that Max is taken over index i, whereas Min is always taken over index k.
Assume MinMax = A_{i0 ,k0} for some indices i_{0} and k_{0}.
A_{i,k0} ≥ Min(A_{i, k}) = B_{i}
Combining that with
A_{i0, k0} = Max(A_{i, k0}) ≥ A_{i, k0}
(which is just a different way of describing our selection of indices) we get
A_{i0,k0} ≥ Min(A_{i,k}) = B_{i}
The left hand side in the latter does not depend on the index i, and the inequality holds for any value of i (any row in the table.) Therefore, maximizing the right hand side will preserve the inequality:
(1) | MinMax = A_{i0,k0} ≥ Max(B_{i}) = MaxMin |
which proves the first part of the statement.
To prove the second part, first assume that MinMax = MaxMin. Introduce
MinMax = Min(C_{k}) = C_{k0} and
MaxMin = Max(B_{i}) = B_{i0},
and consider A_{i0,k0}. By definition,
MaxMin = B_{i0} ≤ A_{i0,k0} ≤ C_{k0} = MinMax.
By the assumption MinMax = MaxMin,
MinMax = A_{i0,k0} = MaxMin.
Conversely, assume there exists an element A_{i0,k0} such that
C_{k0} = Max(A_{i, k0}) = A_{i0, k0} = Min(A_{i0, k}) = B_{i0}
Then, by definition,
MaxMin = Max(B_{i}) ≥ B_{i0} = C_{k0} ≥ Min(C_{k}) = MinMax
However, as we have shown in the first part of the proof, MinMax ≥ MaxMin always, which gives
The point (i_{0}, k_{0}) such that MinMax = A_{i0,k0} = MaxMin is called a saddle point for a given table A. Saddle points may exist for functions of continuous arguments as well. Graphs of such functions in a vicinity of a saddle point in fact resemble the shape of a saddle.
The saddle points have interesting properties that you may observe with the applet and also try proving:
- If there are more than one saddle point, then all corresponding matrix entries coincide.
- If there are two saddle points at
(i_{1}, j_{1}) and(i_{2}, j_{2}), such that i_{1} differs from i_{2} and j_{1} differs from j_{2}, then(i_{1}, j_{2}) and(i_{2}, j_{1}) are also saddle points.
Peter Bajorski rewrote the above replacing matrices with a more general functional setting. His writeup is available as a pdf file.
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny70372781