91社区

Vahideh Manshadi

Yale School of Management

Markovian Search with Socially Aware Constraints

Date: Friday, April 4, 2025
Time: 10:00 - 11:00 am
Location: Bronfman Building, Room 046

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鈥檚 box model [Weitzman,1978] under a single affine constraint on selection and inspection probabilities, we show that the optimal constrained policy retains an index鈥恇ased structure similar to the unconstrained case---but may randomize between two dual鈥恇ased 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茅odory 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.