Choosing either the best or the second best when the number of applicants is random
type: Item
instance of: scholarly article
title: Choosing either the best or the second best when the number of applicants is random
zbMATH Open document ID: 1052.60007
DOI: 10.1016/S0898-1221(03)90120-9
author: Sumit K. Garg
publication date: 2004-08-06T00:00:00Z
review text: The paper investigates a generalized variant of the secretary problem [\textit{S. M. Gusein-Zade}, Theory Probab. Appl. 11, 472--476 (1966); translation fromTeor. Veroyatn. Primen. 11, 534--537 (1966; Zbl 0203.20405)], which is announced as follows: A set of \(N\) applicants (1 being the best and \(N\) being the worst) appear before use one at a time in random order, with all \(N!\) permutations equally likely. The rank of each applicant relative to the preceding ones is noticed, and (based on the observed rank) decided to choose the best (or the second best) or to pass over to the next (if any). No recall of the previous applicants is allowed, and the choice is considered to be successful if the chosen applicant is either the best or the second best among all. While in the secretary problem \(N\) is a known natural number, the present paper considers \(N\) to be a random variable whose distribution is known. The optimality equations are derived for any given distribution on \(N\), but the authors concentrate on the case when \(N\) is uniformly distributed on the interval of integers \([1, m]\). For this situation, the authors prove that the optimal policy has the form similar to the solution of the more particular secretary problem. Namely, to pass the (\(s_1-1)\) applicants, then to choose the relatively best applicant thereafter (if any), but beginning with the \(s_2\)th stage \((s_2 \geq s_1)\) to choose also the relatively second best applicant (if any). A certain asymptotic result concerning the critical numbers \(s_1\) and \(s_2\), and the success probability when \(m\) tends to infinity is also provided.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 62L15
Mathematics Subject Classification ID: 60G40
Mathematics Subject Classification ID: 62L10
zbMATH DE Number: 2082663
zbMATH Keywords: optimal stopping
zbMATH Keywords: best-choice secretary problem
zbMATH Keywords: unknown number of applicants
zbMATH Keywords: relative ranks
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
cites work: The Best Choice Problem for a Random Number of Objects
cites work: On the best choice problem with random population size
cites work: On the best-choice problem when the number of observations is random
cites work: The best-choice secretary problem with random freeze on jobs
cites work: On an optimal stopping problem of Gusein-Zade
full work available at URL: s0898-1221(03)90120-9
OpenAlex ID: W2008619552
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 2082663