The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $ell$ elements in the selected set. Equivalently, the decision makes can hold up to $ell$ elements at any given point in time, but can make up to $k-ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-ellcdot e^{-Thetaleft(frac{left(k-ellright)^2}{k}right)}$, which is asymptotically tight for $k-ell=Theta(ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-ell e^{-frac{k-8ell}{2+2ln ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the sellers capacity, then allocate to the agents with the highest values among the selected agents.
Download