Fair Secretaries with Unfair Predictions

  • 2025-01-21 02:52:42
  • Eric Balkanski, Will Ma, Andreas Maggiori
  • 0

Abstract

Algorithms with predictions is a recent framework for decision-making underuncertainty that leverages the power of machine-learned predictions withoutmaking any assumption about their quality. The goal in this framework is foralgorithms to achieve an improved performance when the predictions are accuratewhile maintaining acceptable guarantees when the predictions are erroneous. Aserious concern with algorithms that use predictions is that these predictionscan be biased and, as a result, cause the algorithm to make decisions that aredeemed unfair. We show that this concern manifests itself in the classicalsecretary problem in the learning-augmented setting -- the state-of-the-artalgorithm can have zero probability of accepting the best candidate, which wedeem unfair, despite promising to accept a candidate whose expected value is atleast $\max\{\Omega (1) , 1 - O(\epsilon)\}$ times the optimal value, where$\epsilon$ is the prediction error. We show how to preserve this promise whilealso guaranteeing to accept the best candidate with probability $\Omega(1)$.Our algorithm and analysis are based on a new "pegging" idea that diverges fromexisting works and simplifies/unifies some of their results. Finally, we extendto the $k$-secretary problem and complement our theoretical analysis withexperiments.

 

Quick Read (beta)

loading the full paper ...