Technical Note—On Hiring Secretaries with Stochastic Departures
研究了秘书问题的推广，其中决策者不必在应聘者到达时立即做决定，而是可以在其随机停留期间选择，目标是最大化选中最优者的概率，并刻画了最优策略的单调性。
The paper studies 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 probability of selecting the best applicant overall. The paper characterizes the optimal policy for this setting, showing 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. Furthermore, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Furthermore, when the number of applicants is large, a single threshold policy is almost optimal.