# Are the min max is equivalent to max min?

1. Jun 1, 2012

### S_David

Hello,

Is

$$\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}$$?

Thanks

2. Jun 1, 2012

### micromass

No. Take

$$x_{i,n}=\left\{\begin{array}{l} 0 ~\text{if}~i+n~\text{even}\\ 1 ~\text{if}~i+n~\text{odd}\end{array}\right.$$

3. Jun 1, 2012

Yeah, right.

4. Jun 1, 2012

### theorem4.5.9

In general you do not have equality between min-max and max-min, however I couldn't resist mentioning a very neat inequality I learned a bit ago.

Given a real valued function $P(x,y): X \times Y \rightarrow \mathbb{R}$ one has

$$\inf_{x\in X} \sup_{y\in Y} P(x,y) \geq \sup_{y\in Y} \inf_{x\in X} P(x,y)$$

If you aren't familiar with sup (supremum - least upper bound) and inf (infimum - greatest lower bound) you can think of sup as max and inf as min.

I learned this from Robert McCann, it's in the following article. Skip to 2.2 Game Theory for an intuitive 'proof'.
http://www.math.toronto.edu/mccann/papers/FiveLectures.pdf

5. Jun 2, 2012

### S_David

Is this inequality true in general?

6. Jun 2, 2012

### dcpo

Yes. To see this pick $x'\in X$ and $y'\in Y$. Clearly $\sup_Y P(x',y)\geq \inf_X P(x,y')$, and since this is true for all $y'\in Y$ we have $\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)$, by definition of the supremum. Similarly, since this is true for all $x'\in X$ we have $\inf_X\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)$ by definition of the infimum.

Last edited: Jun 2, 2012
7. Jun 2, 2012

### S_David

OK, what abou max max or min min, are they interchangeable?

8. Jun 2, 2012

### dcpo

Yes. Consider $\sup_X\sup_Y P(x,y)$. By definition we have $\sup_X\sup_Y P(x,y)\geq P(x',y')$ for all $x'\in X,y'\in Y$, so $\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)$ by definition of $\sup$. Conversely, if $\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)$ then there is $x'\in X$ with $\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)$, and thus there is $y'\in Y$ with $\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)$, which would be a contradiction. So $\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)$ and a symmetry argument gives $\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)$.

Edit: We require that the suprema and infima are defined, I forgot to mention that in my original response.

9. Jun 2, 2012

### S_David

Yes, of course they are defined.

Thanks