  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-\ell\cdot
e^{-\Theta\left(\frac{\left(k-\ell\right)^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-8\ell}{2+2\ln \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 seller's
capacity, then allocate to the agents with the highest values among the
selected agents.
