Are the min max is equivalent to max min?

  • Thread starter EngWiPy
  • Start date
  • #1
1,367
61
Hello,

Is

[tex]\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}[/tex]?

Thanks
 

Answers and Replies

  • #2
22,129
3,297
No. Take

[tex]x_{i,n}=\left\{\begin{array}{l} 0 ~\text{if}~i+n~\text{even}\\
1 ~\text{if}~i+n~\text{odd}\end{array}\right.[/tex]
 
  • #3
1,367
61
No. Take

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

Yeah, right.
 
  • #4
103
0
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
1,367
61
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?
 
  • #6
95
3
Is this inequality true in general?
Yes. To see this pick [itex]x'\in X[/itex] and [itex]y'\in Y[/itex]. Clearly [itex]\sup_Y P(x',y)\geq \inf_X P(x,y')[/itex], and since this is true for all [itex]y'\in Y[/itex] we have [itex]\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)[/itex], by definition of the supremum. Similarly, since this is true for all [itex]x'\in X[/itex] we have [itex]\inf_X\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)[/itex] by definition of the infimum.
 
Last edited:
  • #7
1,367
61
Yes. To see this pick [itex]x'\in X[/itex] and [itex]y'\in Y[/itex]. Clearly [itex]\sup_Y P(x',y)\geq \inf_X P(x,y')[/itex], and since this is true for all [itex]y'\in Y[/itex] we have [itex]\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)[/itex], by definition of the supremum. Similarly, since this is true for all [itex]x'\in X[/itex] we have [itex]\inf_Y\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)[/itex] by definition of the infimum.

OK, what abou max max or min min, are they interchangeable?
 
  • #8
95
3
OK, what abou max max or min min, are they interchangeable?
Yes. Consider [itex]\sup_X\sup_Y P(x,y)[/itex]. By definition we have [itex]\sup_X\sup_Y P(x,y)\geq P(x',y')[/itex] for all [itex]x'\in X,y'\in Y[/itex], so [itex]\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)[/itex] by definition of [itex]\sup[/itex]. Conversely, if [itex]\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)[/itex] then there is [itex]x'\in X[/itex] with [itex]\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)[/itex], and thus there is [itex]y'\in Y[/itex] with [itex]\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)[/itex], which would be a contradiction. So [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)[/itex] and a symmetry argument gives [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)[/itex].

Edit: We require that the suprema and infima are defined, I forgot to mention that in my original response.
 
  • #9
1,367
61
Yes. Consider [itex]\sup_X\sup_Y P(x,y)[/itex]. By definition we have [itex]\sup_X\sup_Y P(x,y)\geq P(x',y')[/itex] for all [itex]x'\in X,y'\in Y[/itex], so [itex]\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)[/itex] by definition of [itex]\sup[/itex]. Conversely, if [itex]\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)[/itex] then there is [itex]x'\in X[/itex] with [itex]\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)[/itex], and thus there is [itex]y'\in Y[/itex] with [itex]\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)[/itex], which would be a contradiction. So [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)[/itex] and a symmetry argument gives [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)[/itex].

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
 

Related Threads on Are the min max is equivalent to max min?

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
8
Views
9K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
5
Views
2K
Replies
4
Views
4K
Replies
7
Views
13K
Replies
3
Views
3K
Top