Secretary problem and two almost the same consecutive applicants

• Autorzy: Rukavicka Josef

Identyfikatory

DOI

10.14708/ma.v50i2.7143

Warianty tytułu

PL

Problem sekretarki z wyborem dwóch kandydatek o bliskich absolutnych rangach

• Języki publikacji: EN

Abstrakty

EN

The classical secretary problem involves sequentially interviewing a pool of n applicants with the aim of hiring exactly the best one in the pool; nothing less is good enough. The decision maker’s strategy should maximize the probability of appropriate selection. The various modification of the aim under the probability maximization criterion does not contain the issue of selecting the pairs of secretaries of very close absolute ranks. This paper is devoted to such a concern, with is formulated in a rigorous way. The effectiveness of the threshold rules is analyzed. It is shown that the probability of success in this class of strategies is asymptotically bounded by 0.5.

PL

Klasyczny problem sekretarki to sekwencyjny problem decyzyjny, w którym celem jest wybór najlepszej kandydatki w postępowaniu rekrutacyjnym, gdy w chwili decyzji statystyk ma niepełne dane o rzeczywistej wartości akceptowanej kandydatki. Wybór kończy się niepowodzeniem, gdy wyselekcjonowana kandydatka nie jest najlepszą wśród wszystkich n, które zgłosiły się na konkurs lub żadna nie zostanie wybrana. Rekruter posługuje się strategią maksymalizującą szanse powodzenia. Zadanie rozpatrzone w tej pracy jest modyfikacją, w której celem rekrutera jest wybór dwóch bliskich co do globalnej rangi kandydatów zatrzymując się na kandydacie, którego poprzednik jest potencjalnie bliski w przyjętym sensie. Autor wyznacza strategię, która maksymalizuje prawdopodobieństwo sukcesu w tym zadaniu. Pokazano, że asymptotyczne prawdopodobieństwo sukcesu w tej klasie strategii może osiągnąć 0.5.

Słowa kluczowe

EN

secretary problem; stopping rule; probability games

PL

gry stochastyczne; problem sekretarki; reguły zatrzymania; strategie progowe

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2022
• Tom: Vol. 50, no. 2
• Strony: 165--181
• Opis fizyczny: Bibliogr. 22 poz.., tab.

Twórcy

autor

Rukavicka Josef

• Czech Technical University in Prague Department of Mathematics Faculty of Nuclear Sciences and Physical Engineering Břehová 7, 115 19 Prague 1

• https://orcid.org/0000-0002-4048-106X

Bibliografia

• [1] E. Bagno, E. Eisenberg, S. Reches, and M. Sigron. On the poset of non-attacking king permutations. European Journal of Combinatorics, 87:103-119, 2020.
• [2] L. Bayón, P. Fortuny Ayuso, J. M. Grau, A. M. Oller-Marcén, and M. M. Ruiz. The best-or-worst and the postdoc problems. Journal of Combinatorial Optimization, 35(3):703-723, 2018.
• [3] Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels. Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics, 2:81-90, 1964.
• [4] E. B. Dynkin. Optimal choice of the stopping moment of a Markov process. Doklady Akademii Nauk SSSR, 150:238-240, 1963. URL http://mi.mathnet.ru/dan27932.
• [5] A. Goldenshluger, Y. Malinovsky, and A. Zeevi. A unified approach for solving sequential selection problems. Probability Surveys, 17:214-256, 2020.
• [6] E. M. Kubicka, G. Kubicki, M. Kuchta, and M. Sulkowska. An optimal algorithm for stopping on the element closest to the center of an interval. Adv. in Appl. Math., 133:Paper No. 102281, 15, 2022.
• [7] Y.-S. Lin, S.-R. Hsiau, and Y.-C. Yao. Optimal selection of the k-th best choice. Probability in the Engineering and Informational Sciences, 33(3): 327-347, 2019.
• [8] D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society. Series C (Applied Statistics), 10(1):39-51, 1961.
• [9] T. F. Móri. The random secretary problem with multiple choice. Ann.Univ. Sci. Budapest. Sect. Comput., 5:91-102 (1985), 1984.
• [10] T. F. Móri. The secretary problem with hesitating candidates. In Mathematical statistics and applications, Vol. B (Bad Tatzmannsdorf, 1983), pages 209-225. Reidel, Dordrecht, 1985.
• [11] T. F. Móri. Is the empirical strategy optimal? Statist. Decisions, 4(1):45-60, 1986.
• [12] T. F. Móri. Hitting a small group of middle ranked candidates in the secretary problem. In Probability theory and mathematical statistics with applications (Visegrád, 1985), pages 155-169. Reidel, Dordrecht, 1988.
• [13] M. L. Nikolaev. On a generalization of the problem of best choice. Teor. Verojatnost. i Primenen., 22(1):191-194, 1977.
• [14] J. Räikkä. How to find the second-best option? In L. Magnani, editor, Social Justice in Practice: Questions in Ethics and Political Philosophy, 33-48. Springer International Publishing, Cham, 2014.
• [15] D. P. Robbins. The probability that neighbors remain neighbors after random rearrangements. Amer. Math. Monthly, 87(2):122-124, 1980.
• [16] J. S. Rose. A problem of optimal choice and assignment. Operations Research, 30(1):172-181, 1982.
• [17] J. S. Rose. Selection of nonextremal candidates from a random sequence. J. Optim. Theory Appl., 38(2):207-219, 1982.
• [18] N. J. A. Sloane and S. Plouffe. The encyclopedia of integer sequences. Incl. 1 IBM/MS-DOS disk. (3.5). Academic Press, San Diego, CA, 1995. ISBN 0-12-558630-2; 0-12-558632-9. URL https://oeis.org. "On-Line Encyclopedia of Integer Sequences" maintained by The OEIS Foundation Inc.
• [19] K. Szajowski. Optimal choice of an object with a-th rank. Mat. Stos., 10(19):51-65, 1982. ISSN 0137-2890.
• [20] K. Szajowski. A rank-based selection with cardinal payoffs and a cost of choice. Scientiae Mathematicae Japonicae, 69(2):285-293, 2009.
• [21] R. J. Vanderbei. The postdoc variant of the secretary problem. Mathematica Applicanda, 49(1):3–13, 2021.
• [22] J. G. Wilson. Optimal choice and assignment of the best m of n randomly arriving items. Stochastic Process. Appl., 39(2):325–343, 1991.

Uwagi

PL

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).