Categories
Ask Mathematics

$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$

Let $f(x,y)$ be a real function of the variables $x,y$ (which can be real vectors). Under what conditions do we have the following equality:

$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$

For example, this equality is true if $f(x,y) = xy$ and $x,y$ are real scalars.

Note that this is not the same as Von Neumann’s minimax theorem (https://en.wikipedia.org/wiki/Minimax_theorem), because here the role of the variables is exchanged (e.g., $x$ is minimized on the left-hand side, but it is maximized on the right-hand side).

Though I do not know if convexity/concavity of $f(x,y)$ with respect to either arguments plays a role here (like it does for Von Neumann’s minimax), I am using the convex-related tags here since that’s the context where I’ve seen related questions. Similarly I am tagging game-theory, though I’m not sure it’s directly applicable.

I also expect that the a condition for this equality to be true is that the saddle-points of both sides of the equation be attained at points where the gradient of $f$ vanishes (see my answer below).

Leave an answer

Your email address will not be published. Required fields are marked *