# Maximum of minimum is less than or equal than minimum of maximum

Let $$C \subset \mathbb{R}^n$$, $$D \subset \mathbb{R}^m$$ be compact sets, and let $$\phi : \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$$ be continuous. Define the functions $$g : \mathbb{R}^n \rightarrow \mathbb{R}$$ and $$h : \mathbb{R}^m \rightarrow \mathbb{R}$$ by

$$g(x) := \max\{\phi(x, y) \mid y \in D\}, \quad h(y) := \min\{\phi(x, y) \mid x \in C\}$$

Show that $$\max\{\min\{\phi(x, y) \mid x \in C\} \mid y \in D\} = \max\{h(y) \mid y \in D\} \leq \min\{g(x) \mid x \in C\}$$.

I have already proved this. Now I tried it with an example:

$$\phi(x,y)=xy+y^2,C=D=[-1,1]$$

Then $$g(x)=\max\{x+1,1-x\}$$ because the maximum is attained at $$y=\pm1$$ and $$h(y)=\min\{y+y^2,-y+y^2\}$$ because the minimum is attained at $$x=\pm1$$.

But then the minimum of $$g$$ in $$x$$ is $$0$$ and the maximum of $$h$$ in $$y$$ is $$2$$. I must have made some error! Could you tell me where?

No contradiction: $$\max_{y\in[-1,1]} h(y)=0$$ Please see the graph of $$h(y)$$:
Let $$y^*(x)$$ be such that $$g(x)=\phi(x,y^*(x))=\max_y\phi(x,y)$$, a point where the maximum is achieved. Then, for a given $$x$$, $$\phi(x,y)\le \phi(x,y^*(x))=g(x)\quad\text{for all }y.$$ Taking the minimum over $$x$$, $$\min_x \phi(x,y) \le \min_x g(x)\quad\text{for all }y.$$ Note that the RHS does not depend on $$y$$, hence $$\max_y(\min_x \phi(x,y)) \le \min_x g(x).$$