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

arXiv: https://arxiv.org/abs/2501.13346 · HTML: https://mlsanity.com/paper/2501.13346/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2025.

## Built on by (most cited first, 2 of 2)

- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

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'eodory 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.