Theorem. Polly's algorithm is a $0.5$-approximation to the prophet's, i.e. the optimal dynamic policy expects to achieve at least half of the largest $X_i$.

Proof. First, we notice that each $X_i$ is at most $b_i + V_{i+1}$. (With equality if $X_i$ exceeds $V_{i+1}$.) Next, we have $V_{i+1} = \mathbb{E} \sum_{j \gt i} b_j \leq DynAlg$. Putting these together: \begin{align} \mathbb{E} \max_i X_i &\leq \mathbb{E} \max_i \left(b_i + V_{i+1}\right) \\ &= \mathbb{E} \max_i \left(b_i + \mathbb{E}\sum_{j \gt i} b_j\right) \\ &\leq \mathbb{E} \max_i \left(b_i + DynAlg\right) \\ &= \mathbb{E} \left(\max_i b_i\right) + DynAlg \\ &\leq \mathbb{E} \left(\sum_i b_i\right) + DynAlg \\ &= 2\mathbb{E} DynAlg . \end{align}

Theorem. No algorithm can guarantee an approximation ratio strictly greater than $0.5$.

Proof. We give a family of instances, each getting larger and larger, where the approximation factor of any algorithm shrinks to $0.5$.

There are just two variables. $X_1 = 1$ with probability $1$. Meanwhile, $X_2 = 0$ with probability $1-p$, $X_2 = 1/p$ with probability $p$. Polly gets expected value $1$ no matter what: if she accepts $X_1$ then she gets $X_1 = 1$, and if she rejects it, she will keep $X_2$ which has expected value $1$. But the prophet gets to pick the max, which is $1/p$ with probability $p$ and $1$ otherwise. So the prophet gets $\mathbb{E}\max\{1,X_2\} = p(1/p) + (1-p)(1) = 2-p$.

By taking $p$ arbitrarily small, we get that Polly cannot guarantee any factor better than $0.5$.

(If you are not familiar with approximation algorithms, let me point out a subtlety. On the above instances, an algorithm achieves $\frac{1}{2-p}$ which is always greater than $0.5$. So it's not formally correct to say we proved no algorithm can beat $0.5$-fraction of the max. What we proved is there is no constant $c \gt 0.5$ such that the algorithm guarantees a $c$-fraction of the max.)

Lemma 1. The expected value achieved by the threshold algorithm (for a fixed $V$) is

\[ Alg \geq P V + (1-P)\mathbb{E} \sum_i b_i .\]

Proof. Notice that we get the bonus of every variable up until we stop. It is zero for all the variables but the last one, of course, because they didn't exceed the threshold. So the probability we get $b_i$ is exactly the probability we rejected $X_1,\dots,X_{i-1}$. Meanwhile, in addition to these bonuses, we get $V$ itself as long as we take some variable. This happens with probability $P$. So

\begin{align} Alg = P V + \mathbb{E} \sum_i \Pr[\text{rejected all $j \lt i$}] b_i \end{align}

Now, we have $\Pr[\text{rejected all $j \lt i$}] \leq 1-P$, which is the probability we rejected all variables. So

\[ Alg \geq P V + (1-P)\mathbb{E} \sum_i b_i \] (We used independence of the variables by assuming that the distribution of $b_i$ doesn't change when conditioning on rejecting $X_1,\dots,X_{i-1}$.)

Lemma 2. For any fixed threshold $V$, the prophet's performance satisfies

\begin{align} \mathbb{E} \max_i X_i &\leq V + \mathbb{E} \sum_i b_i . \end{align}

Proof. Each $X_i \leq b_i + V$. (We have equality if $X_i$ exceeds the threshold.) So

\begin{align} \mathbb{E} \max_i X_i &\leq \mathbb{E} \max_i \left(b_i + V\right) \\ &= \mathbb{E} \left(\max_i b_i\right) + V \\ &\leq \mathbb{E} \sum_i b_i + V . \end{align}

Theorem (Samuel-Cahn 1984). By picking threshold $V = $ the median of the random variable $\max_i X_i$, the threshold policy guarantees at least half of the prophet's value.

We are setting $V$ such that the probability that the maximum is weakly above $V$ is $0.5$. So $P = 0.5$ by definition, and $1-P = 0.5$. So by Lemma 1, \begin{align} Alg &\geq 0.5\left(V + \mathbb{E} \sum_i b_i\right) \\ &\geq 0.5 \mathbb{E} \max_i X_i \end{align} by Lemma 2.

Now, this proof is wrong if distributions have point masses. In that case, a median might cause $P \gt 0.5$. Exercise: Fix the algorithm and proof to deal with this case!

Theorem (Kleinberg, Weinberg 2012). By picking threshold $V = 0.5 \mathbb{E} \max_i X_i$, the threshold policy guarantees at least half of the prophet's value.

By Lemma 2,

\begin{align} \mathbb{E} \sum_i b_i &\geq \mathbb{E} \max_i X_i - V \\ &= 0.5\mathbb{E} \max_i X_i . \end{align}

Let us use this along with the definition of $V$ in Lemma 1:

\begin{align} Alg &\geq P V + (1-P) \mathbb{E} \sum_i b_i \\ &= 0.5 P \mathbb{E} \max_i X_i ~ + ~ (1-P) \mathbb{E} \sum_i b_i \\ &\geq 0.5 P \mathbb{E} \max_i X_i ~ + ~ 0.5 (1-P) \mathbb{E} \max_i X_i \\ &= 0.5 \mathbb{E} \max_i X_i \end{align}

Theorem. If $V$ satisfies $0.5 \mathbb{E} \max_i X_i \leq V \leq \mathbb{E} \sum_i (X_i - V)^+$, then setting a threshold $V$ guarantees half of the maximum value in expectation.

(Exercise: check that this is always feasible. Hint: just check that $V = 0.5\mathbb{E} \max_i X_i$ satisfies both inequalities.)

Proof. Fixing $V$, recall our definitions of $b_i$, so we have the assumption $0.5\mathbb{E}\max_i X_i \leq V \leq \mathbb{E} \sum_i b_i$. For any such $V$, we have by Lemma 1 (recall $P = \Pr[\max_i X_i \geq V]$) \begin{align*} Alg &\geq P V + (1-P) \mathbb{E} \sum_i b_i \\ &\geq P V + (1-P) V \\ &= V \\ &\geq 0.5 \mathbb{E} \max_i X_i \end{align*} where the inequalities used our assumptions on $V$.

Theorem. Let $m$ be the largest median of the maximum distribution, i.e. $m = \sup \{c : \Pr[\max_i X_i \geq c] \geq 0.5\}$. If $V$ satisfies $V \geq \mathbb{E} \sum_i (X_i - V)^+$ and $V \leq m$, then the $V$-threshold policy guarantees a half approximation.

Proof. By $V \leq m$, we get $P \geq 0.5$. We also have $V \geq \mathbb{E} \sum_i b_i$. So if we take Lemma 1: \begin{align} Alg &\geq P V + (1-P) \mathbb{E} \sum_i b_i \end{align} and shift some "weight" from the first term to the second, i.e. decrease $P$ to $0.5$ and increase $1-P$ to $0.5$, this only decreases the sum. \begin{align} Alg &\geq 0.5 V + 0.5 \mathbb{E} \sum_i b_i \\ &\geq 0.5 \mathbb{E} \max_i X_i \end{align} by Lemma 2.

Theorem. Let $m$ be the smallest median of the maximum distribution, i.e. $m = \inf \{c : \Pr[\max_i X_i \geq c] \geq 0.5\}$. If $V$ satisfies $V \leq \mathbb{E} \sum_i (X_i - V)^+$ and $V \geq m$, then the strict $V$-threshold policy guarantees a half approximation.

Proof. The strict threshold policy is to take the first variable strictly exceeding $V$. Strictness gives that $P \leq 0.5$, and now $V$ is the smaller of the two terms, so we have the same proof as above but shifting weight the other way:

\begin{align} Alg &\geq P V + (1-P) \mathbb{E} \sum_i b_i \\ &\geq 0.5 V + 0.5 \mathbb{E} \sum_i b_i \\ &\geq 0.5 \mathbb{E} \max_i X_i \end{align}

Corollary. Let

1. $V^*$ satisfy $V^* = \mathbb{E} \sum_i (X_i - V^*)^+$
2. $\mu = \mathbb{E} \max_i X_i$
3. $m,M$ be the lower and upper median of the random variable $\max_i X_i$.

If a threshold policy sets \[ V \in \left[ \min\{m, 0.5\mu\} ~,~ \max\{V^*,M\} \right] \] then it guarantees at least half of $\mathbb{E} \max_i X_i$. If $V \lt 0.5\mu$ it must be a strict threshold policy.