2
$\begingroup$

$\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?

$\endgroup$
7
  • 3
  • 3
    $\begingroup$ 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)].$$ $\endgroup$
    – Neal Young
    Jun 15 at 20:13
  • 4
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jun 15 at 20:16
  • $\begingroup$ Related (intuition for strong duality): cstheory.stackexchange.com/questions/16206/… $\endgroup$
    – Neal Young
    Jun 16 at 16:16
  • $\begingroup$ @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? $\endgroup$ Jun 21 at 23:14

2 Answers 2

6
$\begingroup$

$\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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 18 at 7:29
  • 1
    $\begingroup$ Thank you for explaining this. $\endgroup$ Jun 18 at 23:11
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 22 at 1:49
  • 1
    $\begingroup$ 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). $\endgroup$ Jun 22 at 1:56
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.