Hiring Under Uncertainty

Manish Purohit, Sreenivas Gollapudi, Manish Raghavan
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5181-5189, 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 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 this Paper

BibTeX
@InProceedings{pmlr-v97-purohit19a, title = {Hiring Under Uncertainty}, author = {Purohit, Manish and Gollapudi, Sreenivas and Raghavan, Manish}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {5181--5189}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/purohit19a/purohit19a.pdf}, url = {https://proceedings.mlr.press/v97/purohit19a.html}, 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.} }
Endnote
%0 Conference Paper %T Hiring Under Uncertainty %A Manish Purohit %A Sreenivas Gollapudi %A Manish Raghavan %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-purohit19a %I PMLR %P 5181--5189 %U https://proceedings.mlr.press/v97/purohit19a.html %V 97 %X 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.
APA
Purohit, M., Gollapudi, S. & Raghavan, M.. (2019). Hiring Under Uncertainty. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5181-5189 Available from https://proceedings.mlr.press/v97/purohit19a.html.

Related Material