# Fair Secretaries with Unfair Predictions

arXiv: https://arxiv.org/abs/2411.09854 · HTML: https://mlsanity.com/paper/2411.09854/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 56 references that are in the map.
- First posted on arXiv 15 Nov 2024.

## Builds on (most cited first, 24 of 24)

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Measuring Fairness in Ranked Outputs](https://mlsanity.com/paper/1610.08559/) (2016)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Efficient candidate screening under multiple tests and implications for fairness](https://mlsanity.com/paper/1905.11361/) (2019)
- [Group-level Fairness Maximization in Online Bipartite Matching](https://mlsanity.com/paper/2011.13908/) (2020)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Prophet Secretary](https://mlsanity.com/paper/1507.01155/) (2015)
- [Individual Fairness in Prophet Inequalities](https://mlsanity.com/paper/2205.10302/) (2022)
- [Prophet Secretary: Surpassing the 1-1/e Barrier](https://mlsanity.com/paper/1711.01834/) (2017)
- [The Secretary Problem with Predictions](https://mlsanity.com/paper/2306.08340/) (2023)
- [Prophet Secretary Through Blind Strategies](https://mlsanity.com/paper/1807.07483/) (2018)
- [The Secretary Problem with Independent Sampling](https://mlsanity.com/paper/2011.07869/) (2020)
- [A short note about the learning-augmented secretary problem](https://mlsanity.com/paper/2410.06583/) (2024)

## Built on by (most cited first, 4 of 4)

- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)
- [Fairness in the Multi-Secretary Problem](https://mlsanity.com/paper/2511.23097/) (2025)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)

## Abstract (arXiv)

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 maxOmega (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 Omega(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.