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

We study and develop an algorithmic framework for incorporating “ex ante” constraints—constraints on outcomes that hold only on average—into stateful sequential search problems with costly inspection. Our framework encompasses the classical Weitzman’s Pandora’s box and its extensions to joint Markovian scheduling, which model richer processes such as multistage search with multiple layers of inspection. Ex ante constraints are particularly motivated by social considerations in algorithmic hiring, where they can adjust outcome distributions to promote equity and access. Although most work in the algorithmic fairness literature in computer science and economics has focused on incorporating such constraints into machine learning tasks like classification and regression, far less attention has been devoted to operational problems such as sequential search, with their unique intricacies. Our work aims to bridge this gap. Building on the optimality of index-based policies in the unconstrained versions of these 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 multiple affine constraints by reducing the problem to a variant of the exact Carathéodory problem and providing a polynomial-time algorithm that constructs an optimal randomized dual-adjusted index-based policy satisfying 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. 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 imposing socially aware ex ante constraints and their socially desirable outcomes.

This paper was accepted by Vivek Farias, data science.

Funding: R. Niazadeh’s research was partially supported by the Asness Junior Faculty Fellowship at The University of Chicago Booth School of Business.

Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.04079.