<p><span class="math-container">$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$</span>Let <span class="math-container">$ {\mathcal I } $</span> be the collection of possible inputs, endowed with a <span class="math-container">$\sigma$</span>-field <span class="math-container">${\mathcal F}$</span>, and let <span class="math-container">$p$</span> be  a   probability measure on <span class="math-container">$({\mathcal I}, {\mathcal F }).$</span>  Similarly,
Let <span class="math-container">$ {\mathcal A } $</span> be the collection of possible algorithms, endowed with some <span class="math-container">$\sigma$</span>-field <span class="math-container">${\mathcal G}$</span>, and  Let <span class="math-container">$q$</span> be  a   probability measure on <span class="math-container">$({\mathcal A}, {\mathcal G }).$</span> Denote by <span class="math-container">${\mathcal H }$</span> the product <span class="math-container">$\sigma$</span>-field on <span class="math-container">${\mathcal I } \times {\mathcal A }$</span>. We are given a cost function <span class="math-container">$C: {\mathcal I } \times {\mathcal A } \to {\mathbb R } $</span> which is <span class="math-container">${\mathcal H}$</span> measurable, and either non-negative, or <span class="math-container">$p \times q$</span> integrable. Write <span class="math-container">$\E_p$</span> for the expectation when we just average over <span class="math-container">$I_p \in \I$</span> and  Write <span class="math-container">$\E_q$</span> for the expectation when we just average over <span class="math-container">$A_q \in \A$</span>. Then
<span class="math-container">$$
\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})] \,.
$$</span>
Here the inequalities are just the statements <span class="math-container">$\inf f \le \E(f) \le \sup f$</span> 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 <span class="math-container">$\I$</span> and <span class="math-container">$\A$</span> are finite) and Sion's minimax Theorem [3] for a more general setting.</p>
<p>[1] <a href="https://en.wikipedia.org/wiki/Fubini%27s_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Fubini%27s_theorem</a></p>
<p>[2] <a href="https://en.wikipedia.org/wiki/Minimax_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Minimax_theorem</a></p>
<p>[3] <a href="https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Sion%27s_minimax_theorem</a></p>

CC BY-SA 4.0
2022-06-18T07:29:32.133Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-06-18T23:11:48.550Z
Thank you for explaining this.
Yuval Peres
CC BY-SA 4.0
2022-06-22T01:49:57.627Z
@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.
DenLilleMand
CC BY-SA 4.0
2022-06-22T01:56:29.563Z
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 https://yuvalperes.com/game-theory-alive/  (There is a link to a PDF of the book there).
Yuval Peres
CC BY-SA 4.0
2022-06-17T20:47:28.250Z
2022-06-19T17:46:59.273Z
2022-06-19T17:46:59.273Z
Yuval Peres
<p>It seems worth it to write up the &quot;game&quot; answer.</p>
<p>You are playing a game where you choose an algorithm <span class="math-container">$A$</span> and your opponent chooses an input <span class="math-container">$I$</span>. You want to minimize <span class="math-container">$C(I,A)$</span>.</p>
<p>First suppose you know what your opponent is doing. They are playing randomly according to <span class="math-container">$p$</span>. Then you are going to be very smart and choose <span class="math-container">$A$</span> to get <span class="math-container">$\min_A \mathbb{E} C(I_p,A)$</span>.</p>
<p>Next suppose you are using some distribution <span class="math-container">$q$</span> and your opponent knows exactly what you are doing. They cleverly choose the input to solve <span class="math-container">$\max_I \mathbb{E} C(I,A_q)$</span>.</p>
<p>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
<span class="math-container">$$ \min_A \mathbb{E} C(I_p, A) \leq \max_I \mathbb{E} C(I,A_q) . $$</span>
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 <span class="math-container">$A_q$</span>. Then even if the opponent was very lucky in choosing <span class="math-container">$I$</span>, you will do at least as well as <span class="math-container">$\max_I \mathbb{E} C(I,A_q)$</span>. If you choose <span class="math-container">$A$</span> wisely, you may be able to push <span class="math-container">$C(I,A)$</span> even smaller. This is the idea of Yuval Peres' proof.</p>

CC BY-SA 4.0
2022-06-22T19:08:02.877Z
2022-06-27T03:19:11.607Z
2022-06-27T03:19:11.607Z
usul
<p><span class="math-container">$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$</span>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:</p>
<h2>For probability distributions <span class="math-container">$p$</span> over <span class="math-container">$\I$</span> and <span class="math-container">$q$</span> over <span class="math-container">$\A$</span>, let <span class="math-container">$I_{p}$</span> denote a random input chosen according to <span class="math-container">$p$</span> and <span class="math-container">$A_{q}$</span> denote a random algorithm chosen according to <span class="math-container">$q$</span> then we have the following principle.</h2>
<p><strong>Yao's Minimax Principle</strong>: For all distributions <span class="math-container">$p$</span> over <span class="math-container">$\I$</span> and <span class="math-container">$q$</span> over <span class="math-container">$A$</span>.
<span class="math-container">$$
\min\limits_{A\in \A} \E[C(I_{p},A)] \leq \max\limits_{I \in \I} \E[C(I, A_{q})]
$$</span></p>
<p>So for intuitions sake let us try to consider the following table of the finite class of deterministic algorithms <span class="math-container">$\A$</span> that solves some problem and the finite class of instances <span class="math-container">$\I$</span> for this problem. The entries are the actual cost of running the corresponding <span class="math-container">$A \in \A$</span> on input <span class="math-container">$I \in \I$</span>.</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th style="text-align: center;"></th>
<th style="text-align: center;"><span class="math-container">$A_{1}$</span></th>
<th style="text-align: center;"><span class="math-container">$A_{2}$</span></th>
<th style="text-align: center;"><span class="math-container">$A_{3}$</span></th>
<th style="text-align: center;"><span class="math-container">$A_{4}$</span></th>
<th style="text-align: center;"><span class="math-container">$\ldots$</span></th>
<th style="text-align: center;"><span class="math-container">$A_{|\A|}$</span></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{1}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{1}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{1}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{1}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{1}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{2}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{2}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{2}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{2}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{2}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{3}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{3}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{3}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{3}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{3}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{4}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{4}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{4}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{4}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{4}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{4}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{5}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{5}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{5}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{5}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{5}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{5}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{6}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{6}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{6}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{6}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{6}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{6}{|\A|}$</span></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$\ldots$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"></td>
</tr>
<tr>
<td style="text-align: center;"><span class="math-container">$I_{|\I|}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{|\I|}{1}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{|\I|}{2}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{|\I|}{3}$</span></td>
<td style="text-align: center;"><span class="math-container">$\C{|\I|}{4}$</span></td>
<td style="text-align: center;"></td>
<td style="text-align: center;"><span class="math-container">$\C{|\I|}{|\A|}$</span></td>
</tr>
</tbody>
</table>
</div>
<p>So let me try to clarify what I think
<span class="math-container">$$
\min\limits_{A\in \A} \E[C(I_{p},A)]
$$</span>
means, we fix an <span class="math-container">$A$</span> and calculate the expected cost of that <span class="math-container">$A$</span> and the random variable <span class="math-container">$I_{p}$</span> which can take on all of the values of <span class="math-container">$I \in \I$</span>.
When we have done this for all <span class="math-container">$A \in \A$</span> 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.</p>
<p>Now to try and explain:
<span class="math-container">$$
\max\limits_{I \in \I} \E[C(I, A_{q})]
$$</span>
Our definition of a randomized algorithm is a random variable <span class="math-container">$A_{q}$</span> which takes on values <span class="math-container">$A \in \A$</span> with the distribution <span class="math-container">$q$</span> which we can then run on an input <span class="math-container">$I$</span>.
We want to find the worst case expectation for our randomized algorithm, so we fix all <span class="math-container">$I \in \I$</span> and calculate the expectation with regards to that and we then pick the one that had the <span class="math-container">$I$</span> which gave our randomized algorithm the worst expectation.</p>
<p>Now the way that I explain this, I don't see immediately why this is true</p>
<p><span class="math-container">$$
\min\limits_{A\in \A} \E[C(I_{p},A)] \leq \max\limits_{I \in \I} \E[C(I, A_{q})]
$$</span>
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?</p>

CC BY-SA 4.0
2022-06-15T19:07:45.427Z
Cross-posted: https://cs.stackexchange.com/q/152381/755, https://cstheory.stackexchange.com/q/51591/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2022-06-15T20:13:37.043Z
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)].$$
Neal Young
CC BY-SA 4.0
2022-06-15T20:16:42.313Z
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.
Neal Young
CC BY-SA 4.0
2022-06-16T16:16:48.543Z
Related (intuition for strong duality): https://cstheory.stackexchange.com/questions/16206/an-intuitive-informal-proof-for-lp-duality/16207
Neal Young
CC BY-SA 4.0
2022-06-21T23:14:20.777Z
@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?
DenLilleMand
CC BY-SA 4.0
2022-06-22T01:32:19.113Z
@NealYoung I guess there is nothing wrong with the way I have written it though? Because I have just picked some distribution and the theorem says that this holds for any distribution.
DenLilleMand
CC BY-SA 4.0
2022-06-22T13:11:45.027Z
True: for this statement, instead of $\min_q$ and $\max_p$, it is equivalent to use $\forall p, q$.
Neal Young
<lower-bounds><randomized-algorithms><gt.game-theory>
Trying to understand the intuition behind Yao's Minimax Principle
DenLilleMand
# Trying to understand the intuition behind Yao's Minimax Principle

(Asked by: username_0 on 2022-06-15)

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

**Tags:** lower-bounds, randomized-algorithms, gt.game-theory

> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/152381/755, https://cstheory.stackexchange.com/q/51591/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_2**: 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)].$$  
> **username_2**: 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.  
> **username_2**: Related (intuition for strong duality): https://cstheory.stackexchange.com/questions/16206/an-intuitive-informal-proof-for-lp-duality/16207  
> **username_0**: @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?  
> **username_0**: @NealYoung I guess there is nothing wrong with the way I have written it though? Because I have just picked some distribution and the theorem says that this holds for any distribution.  
> **username_2**: True: for this statement, instead of $\min_q$ and $\max_p$, it is equivalent to use $\forall p, q$.  

---

## 2 answers

### Answer by username_3 on 2022-06-17. Score: 6 | Accepted answer

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

> **Comments:**
> **username_4**: 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.  
> **username_3**: Thank you for explaining this.  
> **username_0**: @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.  
> **username_3**: 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 https://yuvalperes.com/game-theory-alive/  (There is a link to a PDF of the book there).  

---

### Answer by username_5 on 2022-06-22. Score: 4

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 username_3' proof.


---

