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 must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is approximately optimal, assuming offerees always accept their offers. 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 approximately optimal relative to a policy that can make the same amount of offers not in parallel. In the third problem, we introduce a model where the hiring firm is tightly time constrained and must send all offers simultaneously in a single time step, with the possibility of hiring over capacity at a cost; we provide nearly-tight bounds for 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 guarantees from Purohit et al. (2019) that were between 1/8 and 1/2 to new guarantees that are at least 1-1/e. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight on when a firm should favor each one.