让预测算法在公平性与性能间平衡，确保最优候选人被录用概率不为零。
Fair Secretaries with Unfair Predictions
- 引入'钉住'机制，重构学习增强型秘书问题的决策逻辑。
- 在预测误差ε下，仍保证以Ω(1)概率录用最佳候选人。
- 适用于需兼顾公平与性能的在线决策场景，如招聘、推荐系统。
基于预测的算法是应对不确定性的新框架，利用机器学习预测提升性能，同时不假设预测质量。其目标是在预测准确时表现更优，预测错误时仍保持可接受的保障。然而，预测偏差可能导致算法做出不公平决策。我们发现，在经典秘书问题中，现有最优算法可能对最佳候选人的录用概率为零，这被视为不公平，尽管其承诺的期望值可达最优值的Ω(1)（或1−O(ε)）倍，其中ε为预测误差。本文提出一种新方法——“钉住”策略，既维持该期望值承诺，又确保以Ω(1)概率录用最佳候选人。该方法突破现有范式，简化并统一了部分已有结果。进一步将该方法拓展至k-秘书问题，并通过实验验证理论分析的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。