The Secretary Problem with Predictions

• 成果类型: Article
• 署名作者: Fujii, Kaito; Yoshida, Yuichi
• 署名单位: Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• 发表日期: 2024
• 页码: 1241-1262
• 关键词: NASH SOCIAL-WELFARE; APPROXIMATE COMPETITIVE-EQUILIBRIUM; Envy-freeness; scale

摘要

The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be higher than some constant < 1=e, which is the best possible competitive ratio when we ignore predictions, if the algorithm performs nearly optimally when the predictions are accurate. Additionally, for the multiple-choice secretary problem, we propose an algorithm with a similar theoretical guarantee. We empirically illustrate that if the predictions are accurate, the proposed algorithms perform well; meanwhile, if the predictions are inaccurate, performance is comparable to existing algorithms that do not use predictions.