Optimal selection of the k-th best candidate

Publication date 30 December 2016

Abstract: In the subject of optimal stopping, the classical secretary problem is concerned with optimally selecting the best of

n

candidates when their relative ranks are observed sequentially. This problem has been extended to optimally selecting the

k

-th best candidate for

k g e 2

. While the optimal stopping rule for

k = 1, 2

(and all

n g e 2

) is known to be of threshold type (involving one threshold), we solve the case

k = 3

(and all

n g e 3

) by deriving an explicit optimal stopping rule that involves two thresholds. We also prove several inequalities for

p (k, n)

, the maximum probability of selecting the

k

-th best of

n

candidates. It is shown that (i)

p (1, n) = p (n, n) > p (k, n)

for

1 < k < n

, (ii)

p (k, n) g e p (k, n + 1)

, (iii)

p (k, n) g e p (k + 1, n + 1)

, and (iv)

p (k, i n f t y) := l i m_{n o i n f t y} p (k, n)

is decreasing in

k

.

This page was built for publication: Optimal selection of the $k$-th best candidate