Hiring Under Uncertainty
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 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.
Cite
Text
Purohit et al. "Hiring Under Uncertainty." International Conference on Machine Learning, 2019.Markdown
[Purohit et al. "Hiring Under Uncertainty." International Conference on Machine Learning, 2019.](https://mlanthology.org/icml/2019/purohit2019icml-hiring/)BibTeX
@inproceedings{purohit2019icml-hiring,
title = {{Hiring Under Uncertainty}},
author = {Purohit, Manish and Gollapudi, Sreenivas and Raghavan, Manish},
booktitle = {International Conference on Machine Learning},
year = {2019},
pages = {5181-5189},
volume = {97},
url = {https://mlanthology.org/icml/2019/purohit2019icml-hiring/}
}