Markovian Search with Socially Aware Constraints

Mohammad Reza Aminian, Vahideh Manshadi and Rad Niazadeh

Papers from arXiv.org

Abstract: We study a general class of sequential search problems for selecting multiple candidates from different societal groups under "ex-ante constraints" aimed at producing socially desirable outcomes, such as demographic parity, diversity quotas, or subsidies for disadvantaged groups. Starting with the canonical Pandora's box model [Weitzman, 1978] under a single affine constraint on selection and inspection probabilities, we show that the optimal constrained policy retains an index-based structure similar to the unconstrained case, but may randomize between two dual-based adjustments that are both easy to compute and economically interpretable. We then extend our results to handle multiple affine constraints by reducing the problem to a variant of the exact Carath\'eodory problem and providing a novel polynomial-time algorithm to generate an optimal randomized dual-adjusted index-based policy that satisfies all constraints simultaneously. Building on these insights, we consider richer search processes (e.g., search with rejection and multistage search) modeled by joint Markov scheduling (JMS) [Dumitriu et al., 2003; Gittins, 1979]. By imposing general affine and convex ex-ante constraints, we develop a primal-dual algorithm that randomizes over a polynomial number of dual-based adjustments to the unconstrained JMS Gittins indices, yielding a near-feasible, near-optimal policy. Our approach relies 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. Using a numerical study, we investigate the implications of imposing various constraints, in particular the utilitarian loss (price of fairness), and whether these constraints induce their intended societally desirable outcomes.

Date: 2025-01
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 ().