×
Bayón, L.; Fortuny, P.; Grau, J.; Oller-Marcén, A. M.; Ruiz, M. M.

The best-or-worst and the postdoc problems with random number of candidates. (English) Zbl 1461.90115

J. Comb. Optim. 38, No. 1, 86-110 (2019).
Summary: In this paper we consider two variants of the Secretary problem: The Best-or-Worst and the Postdoc problems. We extend previous work by considering that the number of objects is not known and follows either a discrete Uniform distribution \(\mathcal{U}[1,n]\) or a Poisson distribution \(\mathcal{P} (\lambda)\). We show that in any case the optimal strategy is a threshold strategy, we provide the optimal cutoff values and the asymptotic probabilities of success. We also put our results in relation with closely related work.

Cited in 3 Documents

MSC:

90C27 Combinatorial optimization
60G40 Stopping times; optimal stopping problems; gambling theory
62L15 Optimal stopping in statistics

Keywords:

secretary problem; best-or-worst problem; postdoc problem; combinatorial optimization
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Numerators of convergents to e.
Denominators of convergents to e.

References:

[1] Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms. ACM, New York, pp 434-443 · Zbl 1302.68133
[2] Bayón L, Fortuny Ayuso P, Grau JM, Oller-Marcén AM, Ruiz MM (2018) The Best-or-Worst and the Postdoc problems. J Comb Optim 35(3):703-723 · Zbl 1416.90039 · doi:10.1007/s10878-017-0203-4
[3] Bruss FT (1987) On an optimal selection problem of Cowan and Zabczyk. J Appl Probab 24(4):918-928 · Zbl 0596.60046 · doi:10.2307/3214216
[4] Bruss FT (2000) Sum the odds to one and stop. Ann Probab 28(3):1384-1391 · Zbl 1005.60055 · doi:10.1214/aop/1019160340
[5] Bruss FT (2003) A note on bounds for the odds theorem of optimal stopping. Ann Probab 31(4):1859-1861 · Zbl 1059.60056 · doi:10.1214/aop/1068646368
[6] Cowan R, Zabczyk J (1978) An optimal selection problem associated with the Poisson process. Teor Veroyatnost i Primenen 23(3):606-614 · Zbl 0396.62063
[7] Dendievel R (2013) New developments of the odds-theorem. Math Sci 38(2):111-123 · Zbl 1291.60082
[8] Dendievel R (2015) Weber’s optimal stopping problem and generalizations. Stat Probab Lett 97:176-184 · Zbl 1314.60088 · doi:10.1016/j.spl.2014.11.002
[9] Dynkin EB (1963) Optimal choice of the stopping moment of a Markov process. Dokl Akad Nauk SSSR 150:238-240 · Zbl 0242.60018
[10] Ferguson TS (1989) Who solved the secretary problem? Stat Sci 4(3):282-296 · Zbl 0788.90080 · doi:10.1214/ss/1177012493
[11] Ferguson, TS; Bruss, FT (ed.); Ferguson, TS (ed.); Samuels, S. (ed.), Best-choice problems with dependent criteria. Strategies for sequential search and selection in real time, No. 125, 135-151 (1992), Providence, RI · Zbl 0794.60039
[12] Ferguson, TS; Hardwick, JP; Tamaki, M.; Bruss, FT (ed.); Ferguson, TS (ed.); Samuels, S. (ed.), Maximizing the duration of owning a relatively best object. Strategies for sequential search and selection in real time, No. 125, 37-58 (1992), Providence, RI
[13] Freij R, Wastlund J (2010) Partially ordered secretaries. Electron. Commun. Probab. 15:504-507 · Zbl 1225.60019 · doi:10.1214/ECP.v15-1579
[14] Garrod B, Morris R (2013) The secretary problem on an unknown poset. Random Struct Algorithms 43(4):429-451 · Zbl 1278.90192 · doi:10.1002/rsa.20466
[15] Georgiou N, Kuchta M, Morayne M, Niemiec J (2008) On a universal best choice algorithm for partially ordered sets. Random Struct Algorithms 32:263-273 · Zbl 1138.06001 · doi:10.1002/rsa.20192
[16] Gharan SO, Vondrák J (2013) On Variants of the Matroid Secretary Problem. J Algorithmica 67(4):472-497 · Zbl 1307.68101 · doi:10.1007/s00453-013-9795-y
[17] Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J Am Stat Assoc 61:35-73 · doi:10.1080/01621459.1966.10502008
[18] Havil J (2003) Optimal choice. Gamma: exploring Euler’s constant. Princeton University Press, Princeton, pp 34-138 · Zbl 1023.11001
[19] Lindley DV (1961) Dynamic programming and decision theory. Appl Stat 10:39-51 · Zbl 0114.34904 · doi:10.2307/2985407
[20] Louchard G (2017) A refined and asymptotic analysis of optimal stopping problems of Bruss and Weber. Math Appl 45(2):95-118 · Zbl 1463.60064
[21] Rose JS (1982) A problem of optimal choice and assignment. Oper Res 30(1):172-181 · Zbl 0481.90049 · doi:10.1287/opre.30.1.172
[22] Presman ÈL, Sonin IM (1972) The problem of best choice in the case of a random number of objects. Teor Verojatnost i Primenen 17:695-706 · Zbl 0296.60031
[23] Soto JA (2013) Matroid secretary problem in the random-assignment model. Siam J Comput 42(1):178-211 · Zbl 1311.68197 · doi:10.1137/110852061
[24] Szajowski K (1982) Optimal choice problem of a-th object. Matem Stos 19:51-65 · Zbl 0539.62094
[25] Szajowski K (2007) A game version of the Cowan-Zabczyk-Bruss’ problem. Stat Probab Lett 77(17):1683-1689 · Zbl 1138.60317 · doi:10.1016/j.spl.2007.04.008
[26] Szajowski K (2009) A rank-based selection with cardinal payoffs and a cost of choice. Sci Math Jpn 69(2):285-293 · Zbl 1160.62075
[27] Vanderbei RJ (1983) The Postdoc variant of the secretary problem. http://www.princeton.edu/rvdb/tex/PostdocProblem/PostdocProb.pdf. Accessed 01 July 2018 (unpublished) · Zbl 1499.60133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.