# Trying to understand the intuition behind Yao's Minimax Principle


## 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?

• – D.W.
Jun 15 at 19:07
• Note that in your presentation your expressions are leaving out some quantifiers (e.g. for $p$ and $q$ in your last expression). The principle is that if you want to show a lower-bound of $\lambda$ on worst-case complexity of all randomized algorithms, it suffices to show that there is an input distribution $p$ such that, for a random input $I_p$ drawn from $p$, any deterministic algorithm has complexity at least $\lambda$. That is, $$\min_q \max_{I\in \mathcal I} E[C(I, A_q)] \ge \max_p \min_A E[C(I_p, A)].$$ Jun 15 at 20:13
• As for an answer, Yao's principle is the same as the "easy" direction of the von Neumann min-max principle, applied in a particular context. Maybe you would find that easier to get the intuition for, and it really is the same intuition. But the basic idea is that, if you consider the game where each player chooses a mixed strategy, (i) it cannot hurt to play second (knowing the other player's choice), and (ii) if you know the other player's mixed strategy, there is always an optimal deterministic response. Jun 15 at 20:16
• Related (intuition for strong duality): cstheory.stackexchange.com/questions/16206/… Jun 16 at 16:16
• @NealYoung so in your version, where you said that I left out some quantifiers, you want to also iterate over all of the possible distributions for inputs and algorithms? Jun 21 at 23:14


• Note that the proper syntax for LaTeX font commands is \mathcal{TEXT}. For a single-letter text, this can be simplified to \mathcal T, but it's pointless to put the whole expression in braces {\mathcal T}, they do not do anything (and, of course, multi-letter {\mathcal TEXT} fails completely). This is in contrast to old-style font switching commands that stay in effect until further change, where {\cal TEXT} is correct. Jun 18 at 7:29
• Thank you for explaining this. Jun 18 at 23:11
• @YuvalPeres this was actually a really great answer, first it looked a little scary, but with your explanation and using the facts that: The weighted average of a sequence is always upper-bounded by its maximum value. The weighted average of a sequence is always lower-bounded by its minimum value. I think that it actually makes sense intuitively to me now. Jun 22 at 1:49
• I am glad this was helpful. You might want to look at an exposition of the classical von Neumann minimax theorem, e.g. in Chapter 2 of the book yuvalperes.com/game-theory-alive (There is a link to a PDF of the book there). Jun 22 at 1:56

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.