OPTIMAL SELECTION of the k-TH BEST CANDIDATE

Yi Shen Lin, Shoou Ren Hsiau, Yi Ching Yao

Research output: Contribution to journalArticle

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 kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 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) ≥ p(k, n + 1), (iii) p(k, n) ≥ p(k + 1, n + 1) and (iv) p(k, ): = lim n→ p(k, n) is decreasing in k.

Original languageEnglish
Pages (from-to)327-347
Number of pages21
JournalProbability in the Engineering and Informational Sciences
Volume33
Issue number3
DOIs
Publication statusPublished - 2019 Jul 1

Fingerprint

Optimal Stopping Rule
Secretary Problem
Optimal Stopping
Optimal stopping
Stopping rule
Secretary problem

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this

@article{84be8282e6c84b12b36718a9780025a9,
title = "OPTIMAL SELECTION of the k-TH BEST CANDIDATE",
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 kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 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",
author = "Lin, {Yi Shen} and Hsiau, {Shoou Ren} and Yao, {Yi Ching}",
year = "2019",
month = "7",
day = "1",
doi = "10.1017/S0269964818000256",
language = "English",
volume = "33",
pages = "327--347",
journal = "Probability in the Engineering and Informational Sciences",
issn = "0269-9648",
publisher = "Cambridge University Press",
number = "3",

}

OPTIMAL SELECTION of the k-TH BEST CANDIDATE. / Lin, Yi Shen; Hsiau, Shoou Ren; Yao, Yi Ching.

In: Probability in the Engineering and Informational Sciences, Vol. 33, No. 3, 01.07.2019, p. 327-347.

Research output: Contribution to journalArticle

TY - JOUR

T1 - OPTIMAL SELECTION of the k-TH BEST CANDIDATE

AU - Lin, Yi Shen

AU - Hsiau, Shoou Ren

AU - Yao, Yi Ching

PY - 2019/7/1

Y1 - 2019/7/1

N2 - 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 kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 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

AB - 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 kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 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

UR - http://www.scopus.com/inward/record.url?scp=85065082652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065082652&partnerID=8YFLogxK

U2 - 10.1017/S0269964818000256

DO - 10.1017/S0269964818000256

M3 - Article

AN - SCOPUS:85065082652

VL - 33

SP - 327

EP - 347

JO - Probability in the Engineering and Informational Sciences

JF - Probability in the Engineering and Informational Sciences

SN - 0269-9648

IS - 3

ER -