  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 2-approximation algorithm
for the setting where offers must be made in sequence, an 8-approximation when
offers may be made in parallel, and a 10-approximation for the more general
stochastic knapsack setting with finite probes.
