Max-Min Inequality

The max-min inequality states that \[ \sup_{y}\inf_{x}f(x,y)\leq\inf_{x}\sup_{y}f(x,y). \] At first glance, it is not clear why swapping the order of \(\sup\) and \(\inf\) will make any difference. Here is an example taken from a math exchange page which will make it clear. Suppose \(f(x,y)=\sin(x+y)\). Then \(\inf_{x}\sin(x+y)=-1\) and \(\sup_{y}\sin(x+y)=1\). Clearly, \[ \sup_{y}-1\leq\inf_{x}1 \] holds.

The proof for general case relies on the following inequality: \[ \inf_{x'}f(x',y)\leq\sup_{y'}f(x,y') \] for all \(x,y\). This is certainly true because any setting of \(y\) will not yield a value larger than \(y'\) such that \(f\) achieves its maximum. Likewise any setting of \(x\) will not give a value smaller than \(x'\) such that \(f\) achieves its minimum. Since the inequality holds for any \(x\) and \(y\), it must hold for \(x\) such that the right hand side achieves its minimum and for \(y\) such that the left hand side achieves its maximum. Hence, \[ \sup_{y}\inf_{x'}f(x',y)\leq\inf_{x}\sup_{y'}f(x,y'). \]