Trying to understand the intuition behind Yao's Minimax Principle

Question

$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$The question that I am wondering in this post is if there is any intuition to get from Yao's Minimax Principle. Because right now I can prove that the statement is true with algebra and the definition of expectation but I don't really understand why this is the case. So initially I will just present the principle with the syntax my book on Randomized Algorithms by Motwani and Raghavan is using, then explain the concepts to the best of my ability, and then question why it implicates what it does:

For probability distributions $p$ over $\I$ and $q$ over $\A$, let $I_{p}$ denote a random input chosen according to $p$ and $A_{q}$ denote a random algorithm chosen according to $q$ then we have the following principle.

Yao's Minimax Principle: For all distributions $p$ over $\I$ and $q$ over $A$. $$ \min\limits_{A\in \A} \E[C(I_{p},A)] \leq \max\limits_{I \in \I} \E[C(I, A_{q})] $$

So for intuitions sake let us try to consider the following table of the finite class of deterministic algorithms $\A$ that solves some problem and the finite class of instances $\I$ for this problem. The entries are the actual cost of running the corresponding $A \in \A$ on input $I \in \I$.

	$A_{1}$	$A_{2}$	$A_{3}$	$A_{4}$	$\ldots$	$A_{|\A|}$
$I_{1}$	$\C{1}{1}$	$\C{1}{2}$	$\C{1}{3}$	$\C{1}{4}$		$\C{1}{|\A|}$
$I_{2}$	$\C{2}{1}$	$\C{2}{2}$	$\C{2}{3}$	$\C{2}{4}$		$\C{2}{|\A|}$
$I_{3}$	$\C{3}{1}$	$\C{3}{2}$	$\C{3}{3}$	$\C{3}{4}$		$\C{3}{|\A|}$
$I_{4}$	$\C{4}{1}$	$\C{4}{2}$	$\C{4}{3}$	$\C{4}{4}$		$\C{4}{|\A|}$
$I_{5}$	$\C{5}{1}$	$\C{5}{2}$	$\C{5}{3}$	$\C{5}{4}$		$\C{5}{|\A|}$
$I_{6}$	$\C{6}{1}$	$\C{6}{2}$	$\C{6}{3}$	$\C{6}{4}$		$\C{6}{|\A|}$
$\ldots$
$I_{|\I|}$	$\C{|\I|}{1}$	$\C{|\I|}{2}$	$\C{|\I|}{3}$	$\C{|\I|}{4}$		$\C{|\I|}{|\A|}$

So let me try to clarify what I think $$ \min\limits_{A\in \A} \E[C(I_{p},A)] $$ means, we fix an $A$ and calculate the expected cost of that $A$ and the random variable $I_{p}$ which can take on all of the values of $I \in \I$. When we have done this for all $A \in \A$ we pick the minimum expectation. This is equivalent to calculating the expected running time of the best deterministic algorithm against the worst distribution of inputs. And we hope to show that this is a lower bound to how well a randomized algorithm can hope to perform.

Now to try and explain: $$ \max\limits_{I \in \I} \E[C(I, A_{q})] $$ Our definition of a randomized algorithm is a random variable $A_{q}$ which takes on values $A \in \A$ with the distribution $q$ which we can then run on an input $I$. We want to find the worst case expectation for our randomized algorithm, so we fix all $I \in \I$ and calculate the expectation with regards to that and we then pick the one that had the $I$ which gave our randomized algorithm the worst expectation.

Now the way that I explain this, I don't see immediately why this is true

$$ \min\limits_{A\in \A} \E[C(I_{p},A)] \leq \max\limits_{I \in \I} \E[C(I, A_{q})] $$ although in multiple texts they say that this is a trivial observation. Is there any trick to understand the intuition behind why this is true?

Answer 1

$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\sigma$-field ${\mathcal F}$, and let $p$ be a probability measure on $({\mathcal I}, {\mathcal F }).$ Similarly, Let $ {\mathcal A } $ be the collection of possible algorithms, endowed with some $\sigma$-field ${\mathcal G}$, and Let $q$ be a probability measure on $({\mathcal A}, {\mathcal G }).$ Denote by ${\mathcal H }$ the product $\sigma$-field on ${\mathcal I } \times {\mathcal A }$. We are given a cost function $C: {\mathcal I } \times {\mathcal A } \to {\mathbb R } $ which is ${\mathcal H}$ measurable, and either non-negative, or $p \times q$ integrable. Write $\E_p$ for the expectation when we just average over $I_p \in \I$ and Write $\E_q$ for the expectation when we just average over $A_q \in \A$. Then $$ \inf\limits_{A\in \A} \E_p[C(I_{p},A)] \leq \E_q\bigl[\E_p[C(I_{p},A_q)]\bigr]= \E_p\bigl[\E_q[C(I_{p},A_q)]\bigr] \le\sup\limits_{I \in \I} \E[C(I, A_{q})] \,. $$ Here the inequalities are just the statements $\inf f \le \E(f) \le \sup f$ and the equality is the Fubini-Tonelli Theorem [1]. As Neal-Young wrote in the comments this is the easy direction of the minimax theorem, which is still very useful. For the other direction, which requires some conditions, see von-Neumann's minimax Theorem [2] (when $\I$ and $\A$ are finite) and Sion's minimax Theorem [3] for a more general setting.

[1] https://en.wikipedia.org/wiki/Fubini%27s_theorem

[2] https://en.wikipedia.org/wiki/Minimax_theorem

[3] https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem

Answer 2

It seems worth it to write up the "game" answer.

You are playing a game where you choose an algorithm $A$ and your opponent chooses an input $I$. You want to minimize $C(I,A)$.

First suppose you know what your opponent is doing. They are playing randomly according to $p$. Then you are going to be very smart and choose $A$ to get $\min_A \mathbb{E} C(I_p,A)$.

Next suppose you are using some distribution $q$ and your opponent knows exactly what you are doing. They cleverly choose the input to solve $\max_I \mathbb{E} C(I,A_q)$.

Which scenario will you do better in? Certainly the first one, where you get to see what the opponent is doing before you choose your strategy. That is, certainly $$ \min_A \mathbb{E} C(I_p, A) \leq \max_I \mathbb{E} C(I,A_q) . $$ In fact, one thing you can do in the first scenario (roughly) is not even look at what the opponent is doing, and just play $A_q$. Then even if the opponent was very lucky in choosing $I$, you will do at least as well as $\max_I \mathbb{E} C(I,A_q)$. If you choose $A$ wisely, you may be able to push $C(I,A)$ even smaller. This is the idea of Yuval Peres' proof.