Selection and Ordering Policies for Hiring Pipelines via Linear Programming

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions are interviewed or sent offers. There is a finite time budget for interviewing/sending offers, and every interview/offer is followed by a stochastic realization of discovering the applicant's quality or acceptance decision, leading to computationally challenging problems. In the first problem, we study sequential interviewing and show that a computationally tractable, nonadaptive policy that must make offers immediately after interviewing is near optimal, assuming offers are always accepted. We further show how to use this policy as a subroutine for obtaining a polynomial -time approximation scheme. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous, and is near optimal relative to a policy that can make the same total number of offers one by one. In the third problem, we introduce a parsimonious model of overbooking where all offers are sent simultaneously, and a linear penalty is incurred for each acceptance beyond the number of positions; we provide nearly tight bounds on the performance of practically motivated value -ordered policies. All in all, our paper takes a unified approach to three different hiring problems based on linear programming. Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1 -1/e approximate to 63:2%. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight into when a firm should favor each one.