Prophet Inequalities with Delayed and Uncertain Acceptance.

Abstract : We introduce the prophet inequality with delayed and uncertain acceptance, a variant of the classical prophet inequality in which a decision maker sequentially evaluates options whose selection may fail and whose outcome is revealed only after a fixed delay. At each time step, the decision maker observes the realized value of an arriving option and must irrevocably decide whether to attempt to select it or to continue searching. If an option is selected, the process is suspended for a fixed delay period during which no other options can be considered. Once the delay expires, the selection succeeds with a known probability, in which case the decision maker receives the realized value and the process terminates; otherwise, the search resumes. We show that the decision maker can always guarantee a constant fraction of the utility achieved by the Prophet, an omniscient benchmark that knows all future realizations in advance. In the limiting case where acceptance outcomes are revealed immediately, our guarantee recovers the classical 1/2 bound. This setting also gives rise to a second natural benchmark: the value-aware decision maker, who knows all future value realizations in advance but not the acceptance outcomes. We characterize the worst-case competitive ratios among all three agents and show that they all coincide with 1/2. Finally, we provide sufficient conditions under which the value-aware decision maker surpasses the 1/2 barrier against the more informed Prophet, namely when all acceptance probabilities are strictly positive, by establishing a reduction to a classical prophet inequality instance over scaled Bernoulli random variables.

Joint work with Umberto GRANDI and Emile MARTINEZ