Online Selection with Uncertain Disruption

In numerous online selection problems, decision makers (DMs) must allocate on the fly limited resources to customers with uncertain values. The DM faces the tension between allocating resources to currently observed values and saving them for potentially better, unobserved values in the future. Addressing this tension becomes more demanding if an uncertain disruption occurs while serving customers. Without any disruption, the DM gets access to the capacity information to serve customers throughout the time horizon. However, with uncertain disruption, the DM must act more cautiously because of the risk of running out of capacity abruptly or misusing the resources. Motivated by this tension, we introduce the online selection with uncertain disruption (OS-UD) problem. In OS-UD, a DM sequentially observes n nonnegative values drawn from a common distribution and must commit to select or reject each value in real time without revisiting past values. The disruption is modeled as a Bernoulli random variable with probability p each time that the DM selects a value. We aim to design an online algorithm that maximizes the expected sum of selected values before a disruption occurs, if any. We evaluate online algorithms using the competitive ratio—the ratio between the expected value achieved by the algorithm and that of an optimal clairvoyant algorithm that knows all value realizations in advance but still faces uncertain disruption. Using a quantile-based approach, we devise a nonadaptive single-threshold algorithm that attains a competitive ratio of at least $1-1/e$ and an adaptive threshold algorithm characterized by a sequence of nonincreasing thresholds that attains an asymptotic competitive ratio of at least 0.745. Both of these results are worst-case optimal within their corresponding class of algorithms and continue to hold regardless of whether the last value is partially recoverable. Our results reveal an interesting connection between the OS-UD problem and the independent and identically distributed prophet inequality problems as the number of customers grows large. Finally, we also study the nonidentical setting and show a tight competitive ratio of $1/2$.