Optimal Guarantees for Online Selection Over Time

Abstract

Prophet inequalities are a cornerstone in optimal stopping and online decision-making. Traditionally, they involve the sequential observation of $n$ non-negative independent random variables and face irrevocable accept-or-reject choices. The goal is to provide policies that provide a good competitive ratio against the optimal offline solution that can access all the values upfront---the so-called prophet value. In the \emph{prophet inequality over time problem} (POT), the decision-maker can commit to an accepted value for $\tau$ units of time, during which no new values can be accepted. This creates a trade-off between the duration of commitment and the opportunity to capture potentially higher future values. In this work, we provide best possible worst-case competitive ratios in the IID setting of POT for single-threshold algorithms and the optimal dynamic programming policy. We show a single-threshold algorithm that achieves a competitive ratio of $(1+e^{-2})/2\approx 0.567$, and we prove that no single-threshold algorithm can surpass this guarantee. With our techniques, we can analyze simple algorithms using $k$ thresholds and show that with $k=3$ it is possible to get a competitive ratio larger than $\approx 0.602$. Then, for each $n$, we prove it is possible to compute the tight worst-case competitive ratio of the optimal dynamic programming policy for instances with $n$ values by solving a convex optimization program. A limit analysis of the first-order optimality conditions yields a nonlinear differential equation showing that the optimal policy's asymptotic worst-case competitive ratio is $\approx 0.609$.