1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Are the min max is equivalent to max min?

  1. Jun 1, 2012 #1



  2. jcsd
  3. Jun 1, 2012 #2
    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]
  4. Jun 1, 2012 #3
    Yeah, right.
  5. Jun 1, 2012 #4
    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'.
  6. Jun 2, 2012 #5
    Is this inequality true in general?
  7. Jun 2, 2012 #6
    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: Jun 2, 2012
  8. Jun 2, 2012 #7
    OK, what abou max max or min min, are they interchangeable?
  9. Jun 2, 2012 #8
    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.
  10. Jun 2, 2012 #9
    Yes, of course they are defined.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook