用预测值控制面试顺序,提升选最优候选人的成功率。
The Secretary Problem with Predictions and a Chosen Order
- 根据预测值自定义候选人到来顺序,动态调整决策策略。
- 预测准确时性能逼近最优,最差情况仍保证0.262的竞争力。
- 适合有预测数据且可安排顺序的在线决策场景。
我们研究了由Fujii和Yoshida(2023)提出的秘书问题学习增强变体,其中决策者可获取候选人价值的机器学习预测。核心挑战是平衡一致性与鲁棒性:预测准确时应接近最优选择,预测不准时仍需保证有界竞争力。考虑经典随机顺序秘书问题(ROSP)及更自然的模型——决策者可基于预测值选择到来顺序的选任顺序秘书问题(COSP),该模型适用于提前设定面试日程等场景。本文提出一种适用于ROSP和COSP的新随机算法。当检测到较大预测偏差时,算法从完全信任预测切换为阈值规则。设ε∈[0,1]为最大乘法预测误差,则在ROSP下,竞争力为max{0.221, (1−ε)/(1+ε)},优于之前max{0.215, (1−ε)/(1+ε)};在COSP下,竞争力达max{0.262, (1−ε)/(1+ε)},超越先前方法0.25的最坏情况,更接近经典基准1/e≈0.368。结果表明,结合预测与顺序控制能显著提升在线决策性能。
原文摘要 · Abstract (English)
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023), in which the decision-maker has access to machine-learned predictions of candidate values. The central challenge is to balance consistency and robustness: when predictions are accurate, the algorithm should select a near-optimal secretary, while under inaccurate predictions it should still guarantee a bounded competitive ratio. We consider both the classical Random Order Secretary Problem (ROSP), where candidates arrive in a uniformly random order, and a more natural learning-augmented model in which the decision-maker may choose the arrival order based on predicted values. We call this model the Chosen Order Secretary Problem (COSP), capturing scenarios such as interview schedules set in advance. We propose a new randomized algorithm applicable to both ROSP and COSP. Our method switches from fully trusting predictions to a threshold-based rule once a large prediction deviation is detected. Let $ε\in [0,1]$ denote the maximum multiplicative prediction error. For ROSP, our algorithm achieves a competitive ratio of $\max\{0.221, (1-ε)/(1+ε)\}$, improving upon the prior bound of $\max\{0.215, (1-ε)/(1+ε)\}$. For COSP, we achieve $\max\{0.262, (1-ε)/(1+ε)\}$, surpassing the $0.25$ worst-case bound for prior approaches and moving closer to the classical secretary benchmark of $1/e \approx 0.368$. These results highlight the benefit of combining predictions with arrival-order control in online decision-making.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。