2025/11/10 by Hsiau, Shoou-Ren, Lin, Yi-Shen
Computer Science · #Optimization and Search Problems #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance
paper · doi:10.48550/arxiv.2511.07201
We consider a double secretary problem which contains 2n applicants of n different qualities, two of each quality. As in the classical secretary problem (CSP), the applicants are interviewed sequentially in a random order by a manager and the manager wants to find an optimal stopping rule that maximizes the probability of selecting one of the two best applicants. We prove that the problem leads to a monotone structure and so the corresponding one-stage look-ahead rule (which is of threshold type) is optimal. The limiting behavior of the rule and of the maximum probability are studied and compared with that of the CSP.