minimax vs. maximin
Comments(0)
An elementary, nice lemma relating to the optimization of multivariable functions says that the smallest “big thing” is still bigger than the biggest “small thing”, in other words,
\(\min_x \max_y f(x,y) \ge \max_y \min_x f(x,y)\).
The proof is almost trivial. Let \((x^*, y^*)\) optimize the left hand side and let \((x_*, y_*)\) optimize the right hand side. Now note two facts: for any given \(x\), \(f(x, \arg\max_y f(x,y)) \ge f(x,y) \forall y\); for any given \(y\), \(f(x, y) \ge f(\arg\min_x f(x,y), y) \forall x\).
So in particular, \(f(x^*, y^*) \ge f(x^*, y_*)\) and \(f(x^*, y_*) \ge f(x_*, y_*)\). So putting everything together, \(f(x^*, y^*) \ge f(x_*,y_*)\).
