Ky Fan minimax inequality

Remarks

It suffices to prove the second form, applied to $f - c$ with $c = \sup_y f(y, y)$ when $c$ is finite; the first form is trivial when $c = +\infty$. For each $y$ the set $S(y) = \set{x \in C : f(x, y) \le 0}$ is closed by clause 1. If a point $x$ of the convex hull of $y_1, \dots, y_k$ lay outside every $S(y_i)$, clause 2 would give $f(x, x) \ge \min_i f(x, y_i) > 0$, which is impossible. So the sets $S(y)$ satisfy the hypothesis of the Knaster–Kuratowski–Mazurkiewicz lemma in Fan's form, and by compactness of $C$ they have a common point $\bar x$.

Example: let $\Delta_k$ be the set of probability vectors in $\R^k$, and let $A$ be a real $m \times n$ matrix. The payoff of the matrix game is $g(p, q) = p^T A q$ for $p \in \Delta_m$ and $q \in \Delta_n$, as in von Neumann's minimax theorem. Let $C = \Delta_m \times \Delta_n$, and for $z = (p, q)$ and $w = (p', q')$ in $C$ let $f(z, w) = g(p', q) - g(p, q')$. This $f$ is continuous, affine in $w$, and $f(z, z) = 0$. The point $\bar z = (\bar p, \bar q)$ given by the theorem satisfies $g(p', \bar q) \le g(\bar p, q')$ for all $p', q'$, so $(\bar p, \bar q)$ is a pair of optimal strategies.

Compactness cannot be dropped: on $C = [0, \infty) \subseteq \R$, the function $f(x, y) = y - x$ satisfies both clauses and $f(y, y) = 0$, but for every $x$ there is $y > x$ with $f(x, y) > 0$.

Going deeper

For a student

Ky Fan proved the inequality in 1972 as a common source of minimax theorems, fixed-point theorems and existence theorems for equilibria. From it one derives the minimax theorems of von Neumann and Sion, Nash equilibria of games with convex strategy sets, and solutions of variational inequalities on compact convex sets. Its proof rests on the KKM lemma, which is equivalent to the Brouwer fixed-point theorem.