2015/08/31 by Shan-Yuan Ho, Ho, Shan-Yuan, Abijith Krishnan +1
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Search Problems #Probability (math.PR) #cs.IT #math.CO #math.IT #math.PR
paper · pdf · doi:10.48550/arxiv.1508.07931
28 pages, 8 figures, 4 tables
arxiv created 2015/08/31 · openalex publication_date 2015/08/31 · arxiv updated 2015/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Sliding Window Secretary Problem allows a window of choices to the Classical Secretary Problem, in which there is the option to choose the previous K choices immediately prior to the current choice. We consider a case of this sequential choice problem in which the interviewer has a finite, known number of choices and can only discern the relative ranks of choices, and in which every permutation of ranks is equally likely. We examine three cases of the problem: (i) the interviewer has one choice to choose the best applicant; (ii) the interviewer has one choice to choose one of the top two applicants; and (iii) the interviewer has two choices to choose the best applicant. The form of the optimal strategy is shown, the probability of winning as a function of the window size is derived, and the limiting behavior is discussed for all three cases.