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

We develop an algorithmic framework to incorporate "ex-ante" constraints on outcomes (that hold only on average) into stateful sequential search with costly inspection. Our framework encompasses the classical Weitzman's Pandora's box Weitzman, 1979 as well as its extensions to joint Markovian scheduling Dumitriu et al., 2003; Gittins, 1979, modeling richer processes such as multistage search with multiple layers of inspection. Ex-ante constraints in search are particularly motivated by social considerations in algorithmic hiring, where they adjust outcome distributions to promote equity and access. Building on the optimality of index-based policies in the unconstrained problems, we show that optimal policies under a single ex-ante constraint (e.g., demographic parity) retain an index-based structure but require (i) dual-based adjustments of the indices and (ii) randomization between two such adjustments via a "tie-breaking rule," both easy to compute and economically interpretable. We then extend our results to handle multiple affine constraints by reduction to a variant of the exact Carathéodory problem and providing a polynomial-time algorithm to construct an optimal randomized dual-adjusted index-based policy that satisfies all constraints simultaneously. For general affine and convex constraints, we develop a primal-dual algorithm that randomizes over a polynomial number of dual-based adjustments, yielding a near-feasible, near-optimal policy. All these results rely on the key observation that a suitable relaxation of the Lagrange dual function for these constrained problems admits index-based policies akin to those in the unconstrained setting. Finally, through a numerical study, we investigate the implications of various socially aware ex-ante constraints on the utilitarian loss (price of fairness), and examine whether they achieve their intended socially desirable outcomes.