Abstract

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.