Technical Note—On Hiring Secretaries with Stochastic Departures

Thomas Kesselheim (), Alexandros Psomas () and Shai Vardi ()
Additional contact information
Thomas Kesselheim: Institute of Computer Science, University of Bonn, 53115 Bonn, Germany
Alexandros Psomas: Department of Computer Science, Purdue University, West Lafayette, Indiana 47907
Shai Vardi: Krannert School of Management, Purdue University, West Lafayette, Indiana 47906

Operations Research, 2024, vol. 72, issue 5, 2076-2081

Abstract: 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 probability of selecting the best applicant overall. Our first main result is a characterization of the optimal 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. Furthermore, 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. Funding: A. Psomas is supported in part by the National Science Foundation [Grant CCF-2144208], a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2476 .

Keywords: Optimization; online algorithms; secretary problem; stopping problems (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2476 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:5:p:2076-2081

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().