Are the min max is equivalent to max min?

[EngWiPy]

Hello,

Is

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

Thanks

 

[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.$$

 

[EngWiPy]

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.$$

Yeah, right.

 

[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

 

[EngWiPy]

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

Is this inequality true in general?

 

[dcpo]

Is this inequality true in general?

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.

 

[EngWiPy]

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_Y\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)$ by definition of the infimum.

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

 

[dcpo]

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

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.

 

[EngWiPy]

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.

Yes, of course they are defined.

Thanks