EXPRESS: Optimal Online Strategies for the Secretary Problem with Two-Tier Decision-Making

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 ( SP-TT ), 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 make an irrevocable decision without knowing future candidates' scores, except that all scores are bounded within the known interval [ m , M ]. 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 r * and propose a randomized threshold-based strategy RTS achieving this bound. Our main contribution is introducing a new non-linear programming technique for obtaining and analyzing strategy RTS for SP-TT and its extended variants. We establish a one-to-one correspondence between strategy RTS for SP-TT and the optimal solution to the non-linear program ( NLP ). The contribution of the extension section lies in enhancing 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.