Research map / Learning theory and algorithms / Prediction and decision losses
Fair Secretaries with Unfair Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Pegging algorithms for the learning-augmented secretary problem (single and k-choice) that keep the smoothness guarantee of prior work while accepting the best candidate with constant probability (1/16 for single secretary).
Problem
Secretary problem with (possibly biased) predictions: existing learning-augmented algorithms can accept the best candidate with zero probability, which is unfair, while guaranteeing near-optimal expected value under small prediction error.
Approach
A "pegging" rule: reject a currently-best-predicted candidate if a future candidate has high enough predicted value, so the algorithm stays smooth in prediction error while Dynkin-style acceptance after time 1/2 guarantees a constant probability of hiring the true best candidate.
Key results
- Additive-Pegging satisfies smoothness with C=4 and fairness F=1/16 for the single secretary problem.
- k-Pegging achieves smoothness with C=4k and fairness F_l = max{(1/3)^(k+5), (1-(l+13)/k)/256}; for k>=52 every top-k/2 candidate is accepted with probability at least 1/1024.
- In experiments with n=100 and 10000 instances per setting, the proposed algorithms are consistently best or close to best on competitive ratio and fairness; on Unfair instances they outperform all benchmarks on competitive ratio.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use pegging with additive prediction error | Secretary algorithm · Secretary problem with additive prediction error | fairness probability: 1/16 | Helped |
| use pegging with additive prediction error | Secretary algorithm · Secretary problem with additive prediction error | smoothness constant C: C=4 | Helped |
| use pegging with multiplicative prediction error | Secretary algorithm · Secretary problem with multiplicative prediction error | fairness probability: F=1/16 | Helped |
| use pegging with additive prediction error | k-Secretary algorithm · k-Secretary problem | smoothness constant C: C=4 k | Helped |
| use pegging with additive prediction error | k-Secretary algorithm · k-Secretary problem | fairness probability: F_l=max {(1/3)^{k+5}, (1 - (l+13)/k)/256} | Helped |
| use predictions to select the highest-prediction candidate without a fairness safeguard | Learned-Dynkin · Secretary problem, biased-prediction example | probability of accepting the best candidate: 0 | Hurt |
| use Additive-Pegging instead of benchmark algorithms | Secretary algorithms · Unfair instances | competitive ratio | Helped |
| use Additive-Pegging instead of benchmark algorithms | Secretary algorithms · Unfair instances | fairness | Helped |
| use Additive-Pegging instead of Learned-Dynkin | Secretary algorithms · Experiments across instance types and ε values | competitive ratio and fairness | Helped |
| use Highest-prediction instead of Additive-Pegging | Secretary algorithms · Uniform and Adversarial instances under most ε values | competitive ratio | Helped |
| use Highest-prediction instead of Additive-Pegging | Secretary algorithms · Almost-constant and Unfair instances | fairness | Hurt |
Surprising findings
- The Learned-Dynkin algorithm of prior work can have zero probability of accepting the best candidate, e.g., on a two-candidate instance.
- Any constant smoothness constant C implies fairness upper bounded by 1/3 + o(1), since 1-consistent algorithms cannot exceed this robustness.
Limitations
- Fairness is an individual notion; does not address group fairness or hiring from underprivileged populations.
- Assumes true value is fully revealed upon arrival, ignoring bias in evaluation such as interviews.
- Fairness constant 1/16 is not optimized; trade-off with smoothness remains open.
Experimental setup
Benchmarks: synthetic secretary instances (Almost-constant, Uniform, Adversarial, Unfair)
Metrics: competitive ratio fairness (probability of accepting best candidate)
Baselines: Learned-Dynkin Dynkin Highest-prediction Value-maximization secretary
Builds on: Dynkin's algorithm Learned-Dynkin (Fujii and Yoshida) algorithms with predictions
Closest papers by meaning
- The Secretary Problem with Predicted Additive Gap (NeurIPS 2024 · similarity 0.90)
- Ordinal Secretaries with Advice (AAAI 2026 · similarity 0.89)
- Secretary and Online Matching Problems with Machine Learned Advice (NeurIPS 2020 · similarity 0.88)
- Position: Scarce Resource Allocations That Rely On Machine Learning Should Be Randomized (ICML 2024 · similarity 0.84)
- Fairness Shields: Safeguarding against Biased Decision Makers (AAAI 2025 · similarity 0.83)
- Counterfactual Fairness by Combining Factual and Counterfactual Predictions (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.