Paper Markovian Search with Ex-Ante Constraints: Theory and Applications to Socially Aware Algorithmic Hiring

This study develops an algorithmic framework for incorporating fairness constraints into sequential search problems where inspecting each candidate is costly. The framework generalizes classical models of optimal search, including Weitzman's Pandora's Box and its extensions to multi-stage Markovian scheduling, which arise naturally in settings such as hiring, where decision-makers sequentially evaluate candidates across multiple rounds of assessment. The motivating application is algorithmic hiring, where so-called ex-ante constraints—requirements that hold on average across outcomes rather than for each individual decision—can be used to promote equity and access by adjusting the distribution of selected candidates. While the algorithmic fairness literature has devoted considerable attention to classification and regression tasks, sequential operational problems with their unique structural features have received comparatively little treatment. This work aims to bridge that gap. Building on the known optimality of index-based policies in unconstrained versions of these problems, the study shows that optimal policies under a single ex-ante constraint, such as demographic parity, retain an index-based structure, but require dual-based adjustments to the indices and randomization between two such policies via a tie-breaking rule. Both modifications are computationally tractable and admit natural economic interpretations. These results are extended to multiple simultaneous constraints by reducing the problem to a variant of the Carathéodory problem, yielding a polynomial-time algorithm. For general convex constraints, a primal-dual algorithm produces near-feasible, near-optimal policies. Numerical experiments illustrate the practical implications of imposing socially motivated constraints and characterize the resulting trade-offs.

Get the Paper