Min-Max is always greater than Max-Min:

\[min_y max_x f(x,y) \geq max_x min_y f(x,y)\]

Why?

Look at the following table, showing a simple function f(x,y) values for x,y=1,2,3. At the top you see the minimum of every column, which is the min-y, and on the right side the maximum of every row, that is max-x.

y \ min-y 2 1 1 max-x
3 5 1 1 5
2 8 1 3 8
1 2 6 4 6
x 1 2 3  

Let’s prove that every number in max_x column is greater than any number in min_y row. For simplicity, every time we write ‘greater’ we mean ‘greater or equal’.

Can it be that a number in max_x is less than some number in min_y?

Let’s say we want to reduce the number 6 in max_x to be less than the number 2 in min_y. That means we need to replace the whole row to be ones, so the number in max_x will be 1, but then the number 2 in min_y will also be 1, since min_y is taking the minimums.

In general, every row and column we look at, we have some number in the intersection. Let’s call this number a. The corresponding number in max_x will always be greater than a, by definition, and the corresponding number in min_y will always be lower than a, by definition. That’s why for any row and column we choose, the corresponding number in max_x will always be higher than the corresponding number in min_y.

And that means every number in the max_x column is greater (or equal) than all the numbers in the min_y row.

If it’s true in general for any two numbers in max_x and min_y, it must be true for the specific number \(min (max_x)\) and the number \(max (min_y)\), therefore:

\[min_y max_x f(x,y) \geq max_x min_y f(x,y) \hspace{1cm} \square\]