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

Mohammad Reza Aminian, Vahideh Manshadi and Rad Niazadeh

Papers from arXiv.org

Abstract: 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.

Date: 2025-01, Revised 2025-10
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2501.13346 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2501.13346

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().