Fairness and Bias in Online Selection

There is growing awareness and concern about fairness in machine learning and algorithm design. This is particularly true in online selection problems, where decisions are often biased: for example, when assessing credit risks or hiring staff. We address the issues of fairness and bias in online selection by studying multicolor versions of the classic secretary and prophet problems. In the multicolor secretary problem, we consider that each candidate has a color, and we can only compare candidates of the same color. In addition, we are given probabilities with which the best candidate of a given color is the best candidate overall. These probabilities but not the outcome of the random coin flip are known to both the online and offline algorithms. We characterize the optimal online algorithm and show that unlike the optimal offline algorithm, it enjoys very desirable fairness properties. In the multicolor prophet problem that we study, candidates can again be partitioned into groups of different colors. To counteract imbalanced selection, each color is associated with a target selection probability. We design fair online algorithms that conditional on stopping, select from the different colors with the given target probabilities and achieve optimal approximation guarantees against the fair offline optimum. We also study data-driven (sampling-based) variants of both the multicolor secretary problem and the multicolor prophet problem, and we provide an empirical evaluation of our algorithms.

Funding: J. Correa and A. Cristi were partially funded by the Centro de Modelamiento Matemático, Facultad de Ciencias Físicas y Matemáticas [Grant ANID FB210005]; the Millennium Institute for Research in Market Imperfections and Public Policy [Grant ICS13002]; the Instituto de Sistemas Complejos de Ingeniería [Grant AFB230002]; the Fondo Nacional de Desarrollo Científico y Tecnológico [Grant FONDECYT 1220054]; and Programa Formación de Capital Humano Avanzado (PFCHA) [Grant 2018-21180347].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2021.0662.