A generalized secretary problem. Issue 2 (2nd April 2016)

• Record Type: Journal Article
• Authors: Krieger, Abba; Samuel-Cahn, Ester
• Is Part Of: Sequential analysis. Volume 35:Issue 2(2016)
• Page Start: 145
• Page End: 157
• Publication Date: 2016-04-02
• Subjects: Optimal stopping rule -- relative rank -- secretary problem -- time-dependent win probability; 62L99 -- 62F07 -- 62L15; Sequential analysis -- Periodicals; 519.54
• DOI: 10.1080/07474946.2016.1165521
• Languages: English
• ISSNs: 0747-4946

Abstract

ABSTRACT: A new secretary problem is considered, where for fixed k and m one wins if at some time i = m ( j − 1) +1 up to jm one selects one of the j best items among the first jm items, j = 1, …, k . Selection is based on relative ranks only. Interest lies in small k values, such as k = 2 or 3. This is compared with a classical problem, where one wins if one of the k best among the n = km items is chosen. We prove that the win probability in the new formulation is always larger than in the classical one. We also show, for k = 2 and 3, that one stops sooner in the new formulation. Numerical comparisons are included.