Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution: Without Samples, No Stopping Rule Guarantees More Than 1/e of the Expected MaximumResearch Paper
A prophet inequality compares the value obtained by an online decision maker with the largest value in a sequence that could be chosen by someone who sees the entire sequence. The online decision maker observes values one at a time and must decide whether to accept the current value before seeing future values. When the common distribution of the values is…