Fair Secretaries with Unfair Predictions
This addresses fairness concerns in algorithms with predictions for sequential decision-making, which is incremental as it builds on prior work in the learning-augmented framework.
The paper tackles the problem of unfair decision-making in learning-augmented algorithms for the secretary problem, where biased predictions can lead to zero probability of selecting the best candidate. It proposes a new algorithm that guarantees to accept the best candidate with probability Ω(1) while maintaining competitive performance, with experiments extending to the k-secretary problem.
Algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about their quality. The goal in this framework is for algorithms to achieve an improved performance when the predictions are accurate while maintaining acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions is that these predictions can be biased and, as a result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem in the learning-augmented setting -- the state-of-the-art algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $\max\{Ω(1) , 1 - O(ε)\}$ times the optimal value, where $ε$ is the prediction error. We show how to preserve this promise while also guaranteeing to accept the best candidate with probability $Ω(1)$. Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results. Finally, we extend to the $k$-secretary problem and complement our theoretical analysis with experiments.