A secretary problem with missing observations

• Autorzy: Ramsey D. M.

Identyfikatory

DOI

10.14708/ma.v44i1.1136

Warianty tytułu

PL

O pewnym problemie sekretarki z brakującymi obserwacjami

• Języki publikacji: EN

Abstrakty

EN

Two versions of a best choice problem in which an employer views a sequence of N applicants are considered. The employer can hire at most one applicant. Each applicant is available for interview (and, equivalently, for employment) with some probability p. The available applicants are interviewed in the order that they are observed and the availability of the i-th applicant is ascertained before the employer can observe the (i + 1)-th applicant. The employer can rank an available applicant with respect to previously interviewed applicants. The employer has no information on the value of applicants who are unavailable for interview. Applicants appear in a random order. An employer can only offer a position to an applicant directly after the interview. If an available applicant is offered the position, then he will be hired. In the first version of the problem, the goal of the employer is to obtain the best of all the applicants. The form of the optimal strategy is derived. In the second version of the problem, the goal of the employer to obtain the best of the available applicants. It is proposed that the optimal strategy for this second version is of the same form as the form of the optimal strategy for the first version. Examples and the results of numerical calculations are given.

PL

Artykuł rozważa dwie wersje problemu wyboru najlepszego obiektu, w których pracodawca obserwuje sekwencyjnie N pracobiorców. Każdy pracobiorca jest wolny z prawdopodobieństwem p, a gdy nie jest wolny pracodawca nie może ani prowadzić rozmowy z nim, ani go zatrudnić. Rozmowa o pracy z i-tym pracobiorcą (o ile ma miejsce) jest przeprowadzana zanim pojawi się (i+1)-szy pracobiorca. Pracodawca może tylko porównać pracobiorców, czyli sporządzić ranking tych, z którymi już prowadził rozmowę. Nie posiada on żadnych informacji dotyczących wartości pracobiorców, którzy nie są wolni. Pracobiorcy pojawiają się w losowej kolejności. Pracodawca może zatrudnić tylko jednego pracobiorcę i to tylko zaraz po rozmowie z nim. Wolny pracobiorca zawsze przyjmuje ofertę pracy. Według pierwszego modelu, celem pracodawcy jest zatrudnienie najlepszego z wszystkich pracobiorców. Wyznaczono postać optymalnej strategii. Według drugiego modelu, celem pracodawcy jest zatrudnienie najlepszego z wolnych pracobiorców. Podane jest uzasadnienie, iż postać optymalnej strategii jest taka sama jak przy pierwszym modelu. Rozważono parę przykładów i podano wyniki obliczeń numerycznych.

Słowa kluczowe

EN

secretary problem; missing observations; stopping problem

PL

problem sekretarki; brakujące obserwacje; problem stopowania; filtracja; niepełne obserwacje

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 149--165
• Opis fizyczny: Bibliogr. 26 poz., tab., fot.

Twórcy

autor

Ramsey D. M.

• Wrocław University of Technology, Department of Operations Research, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] Ano K., Tamaki M. and Hu M. (1996) A secretary problem with uncertain employment when the number of offers is restricted. J. Oper. Res. Soc. Jap. 39(3), 307-315. MR1413436; Zbl 0873.90108.
• [2] Bearden J. N. (2006) A new secretary problem with rank-based selection and cardinal payoffs. J. Math. Psychol. 50, 58-59.
• [3] Bruss, F. T. (1984). A unified approach to a class of best choice problems with an unknown number of options, Ann. Prob. 12, 882-889.
• [4] Bruss F. T. (1987) On an optimal selection problem of Cowan and Zabczyk. J. Appl. Prob. 24, 918-928.
• [5] Chudjakow T. and Riedel F. (2013) The best choice problem under ambiguity. Economic Theory. 54(1), 77-97.
• [6] Cowan R. and Zabczyk J. (1978) An optimal selection problem associated with the Poisson process. Theory Prob. Appl. 23, 584-592.
• [7] Ferguson T. S. (1989) Who solved the secretary problem? Stat. Sci. 4, 282-296.
• [8] Ferguson T. S., Hardwick J. P. and Tamaki M. (1992) Maximising the duration of owning a relatively best object. Contemp. Math. 125, 37-57.
• [9] Gilbert J. P. and Mosteller F. (1966) Recognising the maximum of a sequence. J. Amer. Stat. Assoc. 61, 35-73.
• [10] Petruccelli J. D. (1983) On the best-choice problem when the number of observations is random. J. Appl. Prob. 20, 165-171.
• [11] Porosiński Z. (1987) The full-information best-choice problem with a random number of observations. Stoch. Proc. Appl. 24, 293-307.
• [12] Porosiński Z. and Szajowski K. (2000) Full-information best choice problem with random starting point. Math. Jap. 52, 57-63.
• [13] Porosiński Z. and Szajowski K. (2000) Modified strategies in two person full-information best choice problem with imperfect observation. Math. Jap. 52, 103-112.
• [14] Presman E. L. and Sonin I. M. (1972) The best choice problem for a random number of objects. Theory Prob. Appl. 18, 657-668.
• [15] Ramsey D. M. (2007) A model of a 2-player stopping game with priority and asynchronous observation. Math. Meth. Oper. Res. 66 (1), 149-164. MR 2317864; doi: 10.1007/s00186-006-0136-7.
• [16] Ramsey D. M. and Szajowski K. (2008) Selection of a correlated equilibrium in Markov stopping games. Eur. J. Op. Res. 184 (1), 185-206. MR 2353354 doi: 10.1016/j.ejor.2006.10.050.
• [17] Sakaguchi M. (2001) Optimal stopping games where players have weighted privilege. Int. J. Math. Game Theory Algebra 11 (5), 81-96.
• [18] Samuel-Cahn E. (1995) The best-choice secretary problem with random freeze on jobs, Stoch. Process. Appl. 55(2), 315-327. MR 1313026 doi: 10.1016/0304-4149(94)00042-R.
• [19] Samuel-Cahn E. (1996) Optimal stopping with random horizon with application to the full-information best-choice problem with random freeze. J. Amer. Stat. Assoc. 91, 357-364. MR 1394092; doi: 10.2307/2291415.
• [20] Smith M. H. (1975) A secretary problem with uncertain employment. J. App. Prob. 12 (3), 620–624.
• [21] Szajowski K. (2007) A game version of the Cowan-Zabczyk-Bruss problem. Statist. Probab. Letters 77, 1683-1689. MR 2397452 ; doi: 10.1016/j.spl.2007.04.008.
• [22] Szajowski K. (2009) A rank-based selection with cardinal payoffs and a cost of choice. Sci. Mat. Jap. 69(2), 69-77. MR 2501553.
• [23] Szajowski K. (2010) Comparison among Some Optimal Policies in Rank-Based Selection Problems. In Petrosjan L. A. and Zenkevich N. A. (Eds.) Contributions to game theory and management. Vol. III, St. Petersburg University, St. Petersburg, pp. 409-420. MR 2866709.
• [24] Tamaki M. (1991) A secretary problem with uncertain employment and best choice of available candidates. Oper. Res. 39 (2), 274–284. doi: 10.1287/opre.39.2.274.
• [25] Tamaki M. (2009) Optimal choice of the best available applicant in full-information models. J. Appl. Prob. 46 (4), 1086-1099. doi: 10.1239/jap/1261670690.
• [26] Todd P. M. (1996) Searching for the next best mate. In emphR. Conte, R. Hegselmann and P. Terna (Eds.) Simulating social phenomena, pp. 419-436. Springer-Verlag, Heidelberg. doi: 10.1007/978-3-662-03366-1_34.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.