On Hiring Secretaries with Stochastic Departures

We study a generalization of the secretary problem, where decisions do not have to be made immediately upon applicants' arrivals. After arriving, each applicant stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this applicant or not. The arrival and waiting times are drawn from known distributions, and the decision maker's goal is to maximize the probabil-ity of selecting the best applicant overall. Our first main result is a characterization of the opti-mal policy for this setting. We show that when deciding whether to select an applicant, it suffices to know only the time and the number of applicants that have arrived so far. Further-more, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Our second main result is that when the number of applicants is large, a single threshold policy is almost optimal.