Prophet Inequalities with Cancellation Costs

Most of the literature on online algorithms and sequential decision-making in revenue management focuses on settings with irrevocable decisions, where once a decision is made upon the arrival of a new input, it cannot be canceled later. Motivated by modern revenue management applications-such as cloud spot markets, selling banner ads, or online hotel booking-we introduce and study "prophet inequalities with cancellations" under linear cancellation costs (known as the buyback model in the literature). In the classic prophet inequality problem, a sequence of independent random variables 𝑋 1 , 𝑋 2 , . . . with known distributions is revealed one by one, and a decision maker must decide when to stop and accept the current variable in order to maximize the expected value of their choice. In our model, after accepting 𝑋 𝑗 , one may later discard 𝑋 𝑗 and accept another 𝑋 𝑖 at a cost of 𝑓 × 𝑋 𝑗 , where 𝑓 ≥ 0 is a given parameter in this model. The goal is to maximize the expected net reward: the value of the final accepted variable minus the total cancellation cost. We aim to design online policies that are competitive against an omniscient optimal offline "prophet" benchmark.

Our first main result is an optimal prophet inequality for all parameters 𝑓 ≥ 0. We show this result by fully characterizing the worst-case competitive ratio of the optimal online policy against the optimal offline benchmark via the solution to a certain differential equation (for which we provide a constructive solution). Our second main result is to design and analyze a simple and polynomial-time randomized adaptive policy that achieves this optimal competitive ratio. Importantly, our policy is order-agnostic (à la Samuel-Cahn (1984)), meaning that it only needs to know the set of distributions and not the order in which the random variables arrive. These results are obtained by a sequence of reductions to a (continuous) "generalized flow problem," which can be viewed as the dual to a factor-revealing LP for characterizing the worst-case competitive ratio in the original problem. We develop several techniques to solve this reduced problem, including a geometric interpretation of its solution via a differential equation and the embedding of our random variables into specific Poisson point processes. We also leverage these building blocks in novel ways, both for constructing our lower bound instances and in designing (and analyzing) our order-agnostic policy.