Prophet Inequalities with Cancellation Costs

Abstract

Most of the literature on online algorithms and sequential decision-making in revenue management focuses on settings with irrevocable decisions. Motivated by modern applications such as cloud spot markets, selling banner ads, and online hotel booking, we study "prophet inequalities with cancellations" under linear cancellation costs (the buyback model). A sequence of independent random variables $X_1,X_2,\dots$ with known distributions is revealed one by one. After accepting $X_j$, a decision-maker may later discard it and accept another variable at a cost of $f\times X_j$, where $f\ge 0$. The goal is to maximize the expected net reward: the value of the final accepted variable minus the total cancellation cost. We compare online policies with an omniscient optimal offline "prophet" benchmark. Our first main result is an optimal prophet inequality for all parameters $f\ge 0$. We fully characterize the worst-case competitive ratio of the optimal online policy against the optimal offline benchmark via a differential equation, for which we provide a constructive solution. Our second main result is a simple polynomial-time randomized adaptive policy that achieves this optimal competitive ratio. Our policy is order-agnostic (in the sense of Samuel-Cahn (1984)): it only needs to know the set of distributions and not their arrival order. These results follow from reductions to a continuous "generalized flow problem," viewed as the dual to a factor-revealing LP for the worst-case competitive ratio. Our techniques include a geometric interpretation of its solution via a differential equation and the embedding of random variables into specific Poisson point processes. We also use these building blocks to construct lower-bound instances and to design and analyze our

arXiv commentThe first conference version of this paper has appeared in the ACM Symposium on Theory of Computing (STOC 2024), and the second conference version has appeared in the ACM Economics and Computations (EC 2026)