Optimal online strategies for the secretary problem with two-tier decision-making

• 成果类型: Article; Early Access
• 署名作者: Zhang, Wenming; Zhang, Xiangyue; Shu, Na; Cheng, Yongxi
• 署名单位: Northwest University Xi'an; Xi'an Jiaotong University
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1177/10591478261472999
• 发表日期: 2026
• 关键词: COMPETITIVE ALGORITHMS; optimal search

摘要

In the classic secretary problem, the decision-maker is faced with an online sequence of candidates with values. Upon seeing a candidate, they have to make an irrevocable take-it-or-leave-it decision. We generalize this framework to the secretary problem with two-tier decision-making (), modeling online selection with hierarchical screening. The problem becomes even more complicated under two-tier decision-making, which captures pervasive real-world scenarios. The first-tier decision-maker (DM1) filters candidates for the second-tier decision-maker (DM2), who must decide irrevocably without knowing future candidates' scores, except that all scores are bounded within the interval . The aim is to find a collaborative online strategy between DM1 and DM2 that maximizes the expected return. We prove that no strategy surpasses a competitive ratio of and propose a randomized threshold-based strategy () achieving this bound. Our main contribution is introducing a new non-linear programming technique for obtaining and analyzing strategy for and its extended variants. We establish a one-to-one correspondence between strategy for and the optimal solution to the non-linear program. The extension section enhances the real-world applicability of the framework. Introducing a family of problem variants, including those based on different performance evaluations, data-driven dynamic thresholds considering prior information, inaccuracy scores, and interview costs, we rigorously derive the optimal deterministic and randomized online strategies for each variant. Through simulation experiments, we demonstrate the superior performance of the proposed strategies, particularly compared with the strategy derived from the classic single-stage secretary model, and provide practical recommendations for firm recruitment.