Competitive Analysis of Stock-based Thresholds via Prophet Inequalities in Continuous Time

Abstract

We study a continuous-time $K$-unit online resource allocation problem with nonhomogeneous Poisson arrivals and time-varying valuation distributions. While the optimal dynamic policy generally depends on both the remaining inventory and the time left in the horizon, we focus on a simpler and practically appealing class of stock-based threshold policies, whose limited number of thresholds depend only on the number of units remaining. We evaluate these policies against the multi-unit prophet benchmark, which selects the best $K$ realized values in hindsight. Our main contribution is a new competitive-analysis framework for stock-based thresholds in continuous time. We first reformulate the problem through a type-covering dual. The central challenge for analyzing the dual is that the dual is both infinite-dimensional and non-convex: the adversary can choose time-varying arrival and valuation processes, while the policy performance depends nonlinearly on the stochastic inventory trajectory. We overcome these challenges by reducing the continuous-time adversarial problem to a Poisson optimization $PoisOPTRe_K$, and then proving sharp structural properties of its worst-case solutions. In particular, adversarial arrivals admit cutoff and late-filling structures, which yield an exact four-parameter formulation for two thresholds and a finite nested-interval representation for general thresholds. These reductions make the guarantees directly computable. For example, for two thresholds, we obtain a competitive ratio $0.6269$ for $K=2$; with three thresholds, we obtain the ratio $0.6816$ for $K=3$. In this way, we show that simple stock-based thresholds achieve strong prophet-inequality guarantees despite ignoring calendar time.