A Principled Approach to Randomized Selection under Uncertainty
Alexander Goldberg, Giulia Fanti, Nihar Shah
Many decision-making processes involve evaluating and then selecting items; examples include scientific peer review, job hiring, school admissions, and financial investment. Selection typically involves applying rules to evaluations and then deterministically choosing the best candidates. These domains often feature error-prone evaluations and uncertainty about future outcomes, which undermine the reliability of deterministic selection. As a result, selection mechanisms that incorporate uncertainty by involving explicit randomization are beginning to gain traction. However, current randomization methods are ad hoc. In this paper, we propose a principled framework for randomized decision-making based on interval estimates of the quality of each item. We introduce MERIT (Maximin Efficient Randomized Interval Top-k), an optimization-based method that maximizes the worst-case expected number of top candidates selected under "Knightian" uncertainty represented by overlapping intervals. We develop a polynomial-time algorithm to solve the optimization problem and demonstrate empirically that the method scales to over 10,000 items. Further, we prove that our approach can satisfy desirable axiomatic properties not guaranteed by existing approaches to randomization.