Abstract: In the classical prophet inequality problem, a decision-maker observes a sequence of independent nonnegative random variables revealed one by one and must decide, upon seeing each value, whether to accept it irrevocably. The goal is to design an online strategy that achieves a reward close to that of a “prophet” who knows all values in advance. A well-known result shows that even with this information disadvantage, the gambler can guarantee in expectation at least half the expected value of the maximum.
In this talk, I will present a new variant of this model, the Residual Prophet Inequality, which captures situations where the top k values in the sequence are removed before observation—reflecting competition or access restrictions commonly encountered in practice. This removal introduces nontrivial dependencies among the observed values and invalidates classical threshold-based strategies.
For this new model, I will describe a randomized algorithm that guarantees a reward of at least 1/(k+2) times the expected (k+1)-th highest value, and I will show that this bound is tight.