Hiring Under Uncertainty
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:51815189, 2019.
Abstract
In this paper we introduce the hiring under uncertainty problem to model the questions faced by hiring committees in large enterprises and universities alike. Given a set of $n$ eligible candidates, the decision maker needs to choose the sequence of candidates to make offers so as to hire the $k$ best candidates. However, candidates may choose to reject an offer (for instance, due to a competing offer) and the decision maker has a time limit by which all positions must be filled. Given an estimate of the probabilities of acceptance for each candidate, the hiring under uncertainty problem is to design a strategy of making offers so that the total expected value of all candidates hired by the time limit is maximized. We provide a 2approximation algorithm for the setting where offers must be made in sequence, an 8approximation when offers may be made in parallel, and a 10approximation for the more general stochastic knapsack setting with finite probes.
Related Material


