The discussion confirms that the min-max and max-min operations are not equivalent in general. Specifically, the inequality inf_{x∈X} sup_{y∈Y} P(x,y) ≥ sup_{y∈Y} inf_{x∈X} P(x,y) holds true, as established by Robert McCann in his paper on Game Theory. The participants clarify that while min-max and max-min are not interchangeable, the operations max-max and min-min are indeed equivalent. The requirement for the definitions of supremum and infimum to be established is also emphasized.
Mathematicians, students of optimization theory, and researchers in Game Theory will benefit from this discussion, particularly those interested in the properties of min-max and max-min operations.
micromass said: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.
theorem4.5.9 said: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
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.S_David said:Is this inequality true in general?
dcpo said: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.
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).S_David said:OK, what abou max max or min min, are they interchangeable?
dcpo said: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.