# Why is max min less than min max?

I couldn’t find a simple proof of this supposedly simple fact after searching online for quite some time. It took me more time than I expected to finally convince myself, hence it seems worthwhile noting the proof.

Statement: Given a function $f(x,y)$

$f: R \times R \longmapsto R$

And given subsets $S_x$ and $S_y$ of R

$\displaystyle\max_{\substack{x \in S_x}} \min_{\substack{y \in S_y}} f(x,y) \leq \min_{\substack{y \in S_y}} \max_{\substack{x \in S_x}} f(x,y)$

Proof: Let

$\displaystyle g(x) = \min_{\substack{y \in S_y}} f(x,y)$

Thus, for any $x$, $g(x)$ is the minimum value of $f(x,y)$ over all values of $y \in S_y$. Also let $g_y(x)$ be the value of $y$ that is associated with that minimum value of $f(x,y)$. Note there can be multiple such values in which case we can pick any one of them, e.g., the smallest.

$\displaystyle g_y(x) = argmin_{\substack{y \in S_y}} f(x,y)$

This means

$\displaystyle \min_{\substack{y \in S_y}} f(x,y) = f(x, g_y(x))$

Similarly, define $h(x)$ and $h_x(y)$ to be the maximum value of $f(x,y)$ over all $x \in S_x$ and the value of $x$ that gives that maximum value.

$\displaystyle h(y) = \max_{\substack{x \in S_x}} f(x,y)$

$\displaystyle h_x(y) = argmax_{\substack{x \in S_x}} f(x,y)$

This means

$\displaystyle \max_{\substack{x \in S_x}} f(x,y) = f(h_x(y), y)$

Claim 1: $\forall y f(x, g_y(x)) \leq f(x,y)$

This follows from the fact that

$\displaystyle \min_{\substack{y \in S_y}} f(x,y) = f(x, g_y(x))$

Claim 2: $\forall x f(x, y) \leq f(h_x(y),y)$

Again, this follows from the fact that

$\displaystyle \max_{\substack{x \in S_x}} f(x,y) = f(h_x(y), y)$

Claim 3: $\forall x \forall y f(x, g_y(x)) \leq f(h_x(y),y)$

Given any x and y, by claim 1

$f(x, g_y(x)) \leq f(x,y)$

And by claim 2

$f(x, y) \leq f(h_x(y),y)$

Thus, by claim 3

$\displaystyle\max_{\substack{x \in S_x}} f(x, g_y(x)) \leq \min_{\substack{y \in S_y}} f(h_x(y),y)$

The picture below is purely for illustration and might help visualize the proof of claim 3.