秘书问题的一种实用策略

A practical strategy for secretary problem

"截止阀法则"是秘书问题中最常使用的一种决策方式,但在目前的应用中普遍不涉及标杆策略变化的情况,更缺乏对阀值和标杆关系的定量分析.有鉴于此,推导了由阀值和标杆到期望排名的计算公式,指出在秘书问题中"比决策时机更重要的是决策的参照标准",进而提出一种以苏格拉底"三分决策法"为基础的、可应用于实际的简化策略:当选项总量低于100时,以总量的1/3为样本,并以1 3号标杆为参照选取目标.对比分析表明,该策略可操作性强,性能优越,其有效性可达到理论最优期望的95%以上.

Cut-off rule is the most common approach for solving the secretary problem （SP）. Most previous work assumes fixed benchmark used in an application and does not give quantitative analysis of the relationship between the threshold and the benchmark. In this paper we show the impacts of the threshold and benchmark on the expected ranking of the obtained results, pointing out that the frame of reference in solving the SP is more important than the decision-making time. We propose a practical solution based on socrates＇ trichotomy for the SP with less than 100 candidates. This solution takes the first one-third of the candidates as the sample set and applies flexible benchmark -- from the first to the third one when examining the rest of the candidates. The method is simple and practical. And simulation shows that the average performance of our solution is very close （95%） to the best theoretical solution.