Applications of minmax theorem(s)

Question

Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions, $$ \inf_Y \sup_X f = \sup_X \inf_Y f$$.

This theorem is full of applications in a lot of different fiels of mathematics, applied mathematics, statistics, economy, ...

Question: what is the application of this theorem you prefer? (the deepest, the most tricky ...) what is the interpretation of minmax duality that strikes you the most ?

Companion document: 11 different formulations of minimax theorem (with different assumptions, context ...) can be found in http://www.math.ucsb.edu/~simons/preprints/Eoo.pdf and we should refer to these formulations in answers to be more rigorous.

inspirations: Some references on the web to start with

• Monge-Kantorovitch duality (transportation theory) http://en.wikipedia.org/wiki/Transportation_theory#Monge_and_Kantorovich_formulations
• Decision Theory http://en.wikipedia.org/wiki/Minimax
• I don't have it anymore but I remenber the book of Simons was so interesting http://www.amazon.com/Minimax-Monotonicity-Lecture-Notes-Mathematics/dp/3540647554 (I can't remember the proof of Banach Alaoglu Theorem that was given there using 3 lines and Min max theorem)

Answer 1

One minimax theorem not described in the linked file is Yao's application of the Von Neumann result to lower bounds for algorithms. The elegant idea is that in order to prove a lower bound on the behavior of a randomized algorithm over worst-case inputs, it is sufficient to instead analyze the behavior of a fixed algorithm over a carefully chosen distribution of inputs. Thinking of algorithms as columns and inputs as rows, the connection becomes a bit clearer.

Answer 2

Application in Statistical hypothesis testing (due to LeCam).

Let $\mathcal{P}_1$ and $\mathcal{P}_0$ be to set of probability measures on the same space $(X,\mathcal{A})$, dominated by a sigma finite measure $\lambda$. Then, if $\Psi$ is the set of $[0,1]$ valued measurable functions from $X$, minimax theorem implies:

$$ \inf_{\psi \in \Psi} \sup_{P_1\in \mathcal{P}_1, P_0\in \mathcal{P}_0} \int\psi dP_0 +\int1-\psi dp_1= 1-\frac{1}{2} \sup_{P_1\in conv(\mathcal{P}_1), P_0\in conv(\mathcal{P}_0)} |P_1-P_0|_1$$

where $conv(\mathcal{P}_1)$ is the set of convex combinations of elements in $\mathcal{P}_1$ and $|P_1-P_0|_1=\int|dP_1-dP_0|$ ($L_1$ distance).

The left side of the above equation is the minimal worst case sum of type I and type II error, and it is directly connected to $L_1$ distance between the sets of distributions (null and alternative hypothesis).

Additionally, if the suppremum on the right is obtained for $P_0^*$ and $P_1^*$ then the problem of finding a minimax test between $\mathcal{P}_1$ and $\mathcal{P}_0$ reduces to the problem of finding a test between $P_1^*$ and $P_0^*$. This last simple testing problem is easely solved using Neyman-Pearson lemma.