×

The best-or-worst and the postdoc problems. (English) Zbl 1416.90039

Summary: We consider two variants of the secretary problem, the best-or-worst and the postdoc problems, which are closely related. First, we prove that both variants, in their standard form with binary payoff 1 or 0, share the same optimal stopping rule. We also consider additional cost/perquisites depending on the number of interviewed candidates. In these situations the optimal strategies are very different. Finally, we also focus on the Best-or-Worst variant with different payments depending on whether the selected candidate is the best or the worst.

MSC:

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

References:

[1] Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. In: Proceedings of the SODA, pp 434-443 · Zbl 1302.68133
[2] Bearden JN (2006) A new secretary problem with rank-based selection and cardinal payoffs. J Math Psychol 50:58-59 · Zbl 1125.90028 · doi:10.1016/j.jmp.2005.11.003
[3] Daley DJ, Kendall DG (1965) Stochastic rumours. J Inst Math Appl 1:42-55 · doi:10.1093/imamat/1.1.42
[4] Dynkin EB (1963) The optimum choice of the instant for stopping a markov process. Sov Math Dokl 4:627-629 · Zbl 0242.60018
[5] Ferguson TS (1989) Who solved the secretary problem? Stat Sci 4(3):282-296 · Zbl 0788.90080 · doi:10.1214/ss/1177012493
[6] Ferguson TS (1992) The best-choice problems with dependent criteria. Contemp Math 25:135-151 · Zbl 0794.60039 · doi:10.1090/conm/125/1160616
[7] Ferguson, TS; Hardwick, JP; Tamaki, M.; Ferguson, T. (ed.); Samuels, S. (ed.), Maximizing the duration of owning a relatively best object, No. 125, 37-58 (1991), Washington · Zbl 0745.62079 · doi:10.1090/conm/125/1160608
[8] Freij R, Wastlund J (2010) Partially ordered secretaries. Electron Commun Probab 15:504-507 · Zbl 1225.60019 · doi:10.1214/ECP.v15-1579
[9] Garrod B, Morris R (2012) The secretary problem on an unknown poset. Random Struct Algorithms 43(4):429-451 · Zbl 1278.90192 · doi:10.1002/rsa.20466
[10] 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
[11] Gilbert J, Mosteller F (1966) Recognizing the maximum of a sequence. J Am Stat Assoc 61:35-73 · doi:10.1080/01621459.1966.10502008
[12] Lebensztayn E, Machado FP, Rodríguez PM (2011) Limit theorems for a general stochastic rumour model. SIAM J Appl Math 71(4):1476-1486 · Zbl 1236.60023 · doi:10.1137/100819588
[13] Lindley DV (1961) Dynamic programming and decision theory. J R Stat Soc Ser C (Appl Stat) 10(1):39-51 · Zbl 0114.34904
[14] 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
[15] Soto JA (2011) Matroid secretary problem in the random assignment model. In: Proceedings of the SODA, pp 1275-1284 · Zbl 1375.68225
[16] Szajowski K (1982) Optimal choice problem of a-th object. Mat Stos 19:51-65 · Zbl 0539.62094
[17] Szajowski KA (2009) A rank-based selection with cardinal payoffs and a cost of choice. Sci Math Jpn 69(2):285-293 · Zbl 1160.62075
[18] Vanderbei RJ (1983) The Postdoc variant of the secretary problem. http://www.princeton.edu/ rvdb/tex/PostdocProblem/PostdocProb.pdf (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.