Prophet Secretary Against the Online Optimal

We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing a value at each step, the decision maker has to either select it and stop or irrevocably discard it. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one. In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark: the online optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. Our main result is a polynomial-time approximation scheme for this problem. The approximation scheme builds on careful discretization and bundling arguments, in combination with a novel “front-loading” technique that helps reduce the number of decisions the algorithm has to make.