This is a question about this formulation of von Neumann's Minimax theorem:
Let $X \subseteq \mathbb R^n$ and $Y \subseteq \mathbb R^m$ be compact and convex. Let $f: X \times Y \longrightarrow \mathbb R$ be continuous and such that
- $f(\cdot, y)$ is convex for all $y \in Y$, and
- $f(x, \cdot)$ is concave for all $x \in X$.
Then: $$ \max_{x \in X} \min_{y \in Y} f(x,y) = \min_{y \in Y} \max_{x \in X} f(x,y)$$
My question is: why is condition (2) needed? I cannot think of a case where $f$ satisfies all the conditions but (2) and the equality above does not hold.
Looking around I've found some minimax theorems that seem stronger than von Neumann's, but basically all of them impose conditions on the second argument of $f$. Yet it seems to me (though I cannot quite get a proof to work, so that should tell me something) that with something like the following construction you could get $\hat f: X \times Z \longrightarrow \mathbb R$ with $Z$ compact and convex such that $\hat f$ is convex-concave and where both
$$ \max_{x \in X} \min_{y \in Y} f(x,y) = \max_{x \in X} \min_{z \in Z} \hat f(x,z)$$
and
$$ \min_{y \in Y} \max_{x \in X} f(x,y) = \min_{z \in Z} \max_{x \in X} \hat f(x,z).$$
The construction I have in mind is this: fix $f$ meeting all conditions of the theorem but (2); let $\kappa = | Y |$ and fix a bijection $\phi: \kappa \longrightarrow Y$; finally, let $Z_0$ be the set of function from $\kappa$ to $[0,1]$ that are 0 in all but finitely many points and whose values add up to $1$, and let $Z = \overline{Z_0}$. (Essentially, $Z_0$ is the set of probability functions defined over $Y$ with finite support.) Define now $\hat f: X \times Z \longrightarrow \mathbb R$ as follows
$$ \hat f(x,z) = \sum_{\alpha < \kappa} z(\alpha) \cdot f(x, \phi(\alpha)).$$
Now, I have more or less hand wavy arguments for each of the following claims:
- $\hat f$ is concave-convex.
- $Z$ is compact and convex.
- For each $x \in X$,
$$ \min_{y \in Y} f(x,y) = \min_{z \in Z} \hat f(x,z).$$
So we can apply von Neumann's theorem to get that
$$ \max_{x \in X} \min_{y \in Y} f(x,y) = \max_{x \in X} \min_{z \in Z} \hat f(x,z) = \min_{z \in Z} \max_{x \in X} \hat f(x,z) = \min_{y \in Y} \max_{x \in X} f(x,y).$$
(Now that I'm writing this down I see that maybe that last identity is not obvious even if we assume all my conjectures are correct, so perhaps that's where things break down?)
Best Answer
I am not sure if this is what you are looking for:
Take $X=Y=[-1,1]$, $f(x,y) = (x-y)^2$.
$\max_x \min_y (x-y)^2 = \max_x 0 = 0 $, $\min_y \max_x (x-y)^2 = \min_y (1+|y|)^2 = 1$.