Fair Markovian Search

We study the problem of optimal search (with costly information acquisition) for the best alternative among a pool of candidates that belong to different societal groups. Due to baked-in biases in the prior data, group-unaware comparisons of candidates may lead to unfair treatment of certain groups. As such, a socially-aware decision-maker aims to achieve fairness by imposing constraints on ex-ante outcomes in various stages of the search. We start with the classic Pandora's box model of Weitzman (1979) under demographic parity constraints. Candidates belong to two demographic groups and we constrain the policy to equalize the probability of selection or the expected number of opportunities (inspected candidates) across these groups. For each case, we show that optimal fair policy retains the index-based structure of the optimal unfair policy, but potentially randomizes between two policies that are dual-based adjustments of the unfair problem — thus they are easy to compute and economically interpretable. Building on these constructs, we consider richer search processes, such as search with rejection and multi-stage search, that can be modeled by joint Markov scheduling (JMS). Imposing general affine and convex ex-ante fairness constraints — that encompass various notions such as the 4/5 rule or minimum guaranteed welfare — across an arbitrary number of groups or even individuals, we give a primal-dual algorithm to find the almost fair and optimal policy. This algorithm, too, randomizes over index-based policies; this time, over a polynomial number of policies whose indices are dual-based adjustments to the Gittins indices of the unfair JMS. Our algorithmic developments, while involving many intricacies, rely on a simple yet powerful observation: there exists a relaxation to the Lagrange dual function of these constrained optimization problems that admit index-based policies akin to the original unconstrained ones