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}\\<br /> 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}\\<br /> 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&#039;\in X and y&#039;\in Y. Clearly \sup_Y P(x&#039;,y)\geq \inf_X P(x,y&#039;), and since this is true for all y&#039;\in Y we have \sup_Y P(x&#039;,y)\geq \sup_Y \inf_X P(x,y), by definition of the supremum. Similarly, since this is true for all x&#039;\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&#039;\in X and y&#039;\in Y. Clearly \sup_Y P(x&#039;,y)\geq \inf_X P(x,y&#039;), and since this is true for all y&#039;\in Y we have \sup_Y P(x&#039;,y)\geq \sup_Y \inf_X P(x,y), by definition of the supremum. Similarly, since this is true for all x&#039;\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&#039;,y&#039;) for all x&#039;\in X,y&#039;\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&#039;\in X with \sup_Y P(x&#039;,y)\not\leq \sup_{X\times Y} P(x,y), and thus there is y&#039;\in Y with \sup_Y P(x&#039;,y&#039;)\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&#039;,y&#039;) for all x&#039;\in X,y&#039;\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&#039;\in X with \sup_Y P(x&#039;,y)\not\leq \sup_{X\times Y} P(x,y), and thus there is y&#039;\in Y with \sup_Y P(x&#039;,y&#039;)\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