Prophet Secretary Through Blind Strategies 2: No Stopping Strategy Can Guarantee More Than √3 − 1 of the Prophet's Expected Maximum in Random OrderResearch Paper
In a prophet inequality a gambler sees the realizations of independent nonnegative random variables one at a time and must decide irrevocably, at each step, whether to stop and keep the current value. Her performance is compared with that of a prophet who sees everything in advance and takes the maximum. The ratio between the two is the standard benchmark…