Threshold for prophet inequality

Question

The prophet inequality is related to the following scenario:

Suppose there are $n$ independent positive random variables $X_1,\dots,X_n$. They might not be identically distributed. We reveal them one at a time. When we see $X_i$, we have a choice between stopping with the value $X_i$, or continuing to search. If we reject all variables we get $0$.

How well can we do compared to a prophet who gets to see all variables before choosing a maximum? The prophet inequality says that there is a threshold $k$ such that the strategy where we stop whenever the value is at least $k$ gives expected value at least half of the expected value for the prophet.

Let $X$ be the random variable denoting the maximum of the $n$ values drawn. It is known that the threshold $k$ can be chosen in at least two ways:

1. Choose $k_1$ so that $P(X>k_1)=\frac{1}{2}$, and
2. Let $k_2=\frac12E[X]$.

These can be pretty different values. Are there other values of $k$ that work? For example, does any value of $k$ between $k_1$ and $k_2$ work?

Answer 1

In section D.2 of the appendix of Chawla et al. (2010), it is proven that you can take as your threshold any value $c$ in $[a,b]$, where $a= E[X]/2$ (following your notation) and $b$ is the unique solution of $$b=\sum_{i=1}^n E(X_i -b) ^+$$ with $x^+ = \max(x,0)$.

Actually, they reference the result to Samuel-Cahn, but they extend it to the setting where you can pick more than one value.