Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality

We take a unifying approach to single selection optimal stopping problems with random arrival order and independent sampling of items. In the problem we consider, a decision maker (DM) initially gets to sample each of N items independently with probability p, and can observe the relative rankings of these sampled items. Then, the DM faces the remaining items in an online fashion, observing the relative rankings of all revealed items. While scanning the sequence the DM makes irrevocable stop/continue decisions and her reward for stopping the sequence facing the item with rank i is Yi. The goal of the DM is to maximize her reward. We start by studying the case in which the values Yi are known to the DM, and then move to the case in which these values are adversarial. For the former case we are able to recover several classic results in the area, thus giving a unifying framework for single selection optimal stopping. For the latter, we pin down the optimal algorithm, obtaining the optimal competitive ratios for all values of p.

Automated summary

This paper presents a unified approach to single selection optimal stopping problems with random arrival order and independent sampling. The decision maker initially samples N items independently with probability p, and observes the relative rankings of these sampled items. The goal is to maximize the reward by making irrevocable stop/continue decisions while facing the remaining items and observing their rankings. The paper covers the cases where the reward values are known and adversarial, recovering classic results and determining the optimal algorithm and competitive ratios.