# Hiring Under Uncertainty

arXiv: https://arxiv.org/abs/1905.02709 · HTML: https://mlsanity.com/paper/1905.02709/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2019.

## Built on by (most cited first, 4 of 4)

- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [A Computational Approach to Improving Fairness in K-means Clustering](https://mlsanity.com/paper/2505.22984/) (2025)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)

## Abstract (arXiv)

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.