Recruitment Strategies That Take a Chance

Gregory Kehne, Ariel D. Procaccia, Jingyan WangNeurIPS 2022 · OpenReview

Academic hiring committees—whether for faculty positions or PhD admissions—perpetually face a "Goldilocks" problem: how do you make enough offers to fill your open positions without accidentally hiring so many people that you run out of office space and funding?

Presented at NeurIPS 2022, Recruitment Strategies That Take a Chance tackles this exact dilemma. The authors move away from traditional "hard budget" hiring models to a "soft constraint" framework that penalizes deviating from a target number of hires. By doing so, they provide new algorithms that help committees balance the pursuit of "star" candidates with the need for "safe bets" to ensure a stable yield.

The Challenge of Academic Recruitment

In recruitment settings, committees face a fundamental uncertainty: they do not know if a candidate will actually accept an offer.

Traditional algorithmic models often assume sequential hiring (making one offer at a time) with a hard budget (a strict cap of $k$ hires). The authors argue this modeling choice is inconsistent with actual academic recruitment. In practice:

  1. Offers are made in batches: Committees send out a group of offers simultaneously to avoid losing candidates to competing institutions.
  2. Targets are soft: Hiring six people when you only wanted five is a headache (over-enrollment), but hiring zero is a disaster (a failed search). Both outcomes carry costs, but they are not rigid walls.

The core challenge is that the "best" candidates (those with high value, $x_i$) are often the least likely to accept (low probability, $p_i$). A strategy that only targets stars risks a yield of zero, while a strategy that only targets safe bets leaves top-tier talent on the table.

Formalizing the Soft Constraint Model

To address these realities, the authors formalize the problem as selecting a single batch of candidates, $S$, to maximize an objective function:

$$U(S) = \text{Expected Reward} - \lambda \cdot \text{Expected Penalty}$$

Here, the reward is the sum of the values of candidates who accept. The penalty is a function of how much the actual number of hires deviates from a target $M$, scaled by a weight $\lambda$. The paper analyzes two primary penalty types:

  • $L_2$ Loss (Two-sided squared error): Penalizes both overshooting and undershooting the target.
  • $L_1^+$ Loss (One-sided linear): Specifically penalizes overshooting the target (i.e., hiring too many).

While the objective function is submodular (meaning there are diminishing returns to adding more candidates), the fact that it can take negative values makes it significantly harder to solve than standard submodular maximization problems.

Algorithmic Solutions

The researchers explore several approaches to optimize this objective:

  • Greedy Heuristics: The authors test simple strategies, such as sorting by candidate value ($x_i$) or expected value ($p_i x_i$). They prove that while these are intuitive, they can perform arbitrarily poorly in certain edge cases.
  • FPTAS for $L_2$: For the squared error penalty, they develop a Fully Polynomial-Time Approximation Scheme (FPTAS) by reducing the problem to an unconstrained binary quadratic program with constant rank.
  • ONESIDEDL1+: For the overshooting penalty, they introduce a novel algorithm that partitions candidates into three groups based on their value relative to the penalty weight $\lambda$. It uses a mix of brute force for small subsets and rounded dynamic programming for larger ones to achieve a constant-factor approximation.

Experimental Insights

The paper relies on synthetically generated data using Beta distributions to evaluate the algorithms across three scenarios: positive correlation (easy candidates are the most valuable), no correlation, and negative correlation.

Key findings from the empirical evaluation include:

  • Negative Correlation is "Hard Mode": The most realistic academic scenario is one where the highest-value candidates are the hardest to recruit. Experiments with $n=50$ candidates show that simple greedy heuristics struggle the most here. This is exactly where the sophisticated ONESIDEDL1+ algorithm demonstrates its strength.
  • Quantifying the Yield-Quality Tradeoff: The model explicitly shows that an optimal batch of offers must include a calculated mix of high-risk/high-reward stars and high-probability/lower-reward anchors.
  • Adaptability: The proposed algorithms better adapt to different "penalty regimes" (varying values of $\lambda$) compared to greedy methods, which tend to either over-hire or under-hire when the penalty for overshooting becomes steep.

Limitations and Future Directions

While the theoretical guarantees and empirical results are strong, the framework has practical limitations. First, the model assumes committees can accurately estimate a candidate's value ($x_i$) and their probability of acceptance ($p_i$). In reality, these are often subjective or grouped into rough categories (e.g., "high yield"). Second, the reliance on synthetic data means the model has not yet been stress-tested on actual, proprietary university admissions cycles. Finally, while the paper provides tools for different penalty functions, it leaves it up to individual departments to decide which penalty function ($L_1$ vs $L_2$) or weight ($\lambda$) truly represents their institutional constraints.

Despite these limitations, this research offers a highly practical, mathematically rigorous step forward for institutions looking to optimize their batch hiring processes under uncertainty.

Summary updated

Abstract

In academic recruitment settings, including faculty hiring and PhD admissions, committees aim to maximize the overall quality of recruited candidates, but there is uncertainty about whether a candidate would accept an offer if given one. Previous work has considered algorithms that make offers sequentially and are subject to a hard budget constraint. We argue that these modeling choices may be inconsistent with the practice of academic recruitment. Instead, we restrict ourselves to a single batch of offers, and we treat the target number of positions as a soft constraint, so we risk overshooting or undershooting the target. Specifically, our objective is to select a subset of candidates that maximizes the overall expected value associated with candidates who accept, minus an expected penalty for deviating from the target. We first analyze the guarantees provided by natural greedy heuristics, showing their desirable properties despite the simplicity. Depending on the structure of the penalty function, we further develop algorithms that provide fully polynomial-time approximation schemes and constant-factor approximations to this objective. Empirical evaluation of our algorithms corroborates these theoretical results.
BibTeX
@inproceedings{kehne2022recruitment,
  author = {Gregory Kehne and Ariel D. Procaccia and Jingyan Wang},
  title = {{Recruitment Strategies That Take a Chance}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=h9XrDreuAH},
}
Figure