An apartment problem

• Autorzy: Szajowski K.

Identyfikatory

DOI

10.14708/ma.v42i2.597

Warianty tytułu

PL

Sekwncyjne poszukiwanie lokalu do wynajęcia

• Języki publikacji: EN

Abstrakty

EN

In the 60 - ies of the last century, several optimization problems referring to the sequential methods were investigated. These tasks may include the Robbins’ problem of optimal stopping, the secretary problem (see the discussion paper by Ferguson [18]), the parking problem or the job search problem. Subtle details of the wording in these issues cause that each of these terms include family of problems that differ significantly in detail. These issues focused attention of a large group of mathematicians. One of the related topic has been the subject of Professor Jerzy Zabczyk attention. Based on the discussions with Professor Richard Cowan1 the model of choosing the best facility available from a random number of offers was established. In contemporary classification of the best choice problems it is the noinformation, continuous time, secretary problem with the Poisson stream of options and the finite horizon.

PL

W latach 60 -tych poprzedniego wieku analizowano wielu matematyków skupiało swoja uwagę na zadaniach optymalizacyjnych nawiązujących do sekwencyjnego przeszukiwania czy obserwacji. Do tych zadań można zaliczyć problem optymalnego zatrzymania Robbinsa, problem sekretarki, (dość obszerną analizę tego zagadnienia przeprowadził Ferguson [18]), zadanie optymalnego parkowania czy też problem poszukiwania pracy. Subtelne szczegóły tych zagadnień powodują, iż każde zagadnienie z wymienionych ma liczne wersje różniące się szczegółami, które powodują, iż mamy do czynienia całą rodziną modeli. Jedno z zagadnień zainteresowało profesora Jerzy Zabczyk. W wyniku dyskusji z profesorem Richardem Cowanem (w Warszawie ) stworzyli model poszukiwania najlepszego obiektu, gdy dostępnych obiektów jest losowa liczba. Wg współczesnej klasyfikacji problemów wyboru najlepszego obiektu jest to przypadek poszukiwania najlepszego obiektu przy braku informacji, z czasem ciągłym, gdy strumień zgłoszeń jest poissonowski a horyzont jest skończony, ustalony.

Słowa kluczowe

EN

stopping time; stopping game; Markov process; compound Poisson process; non-zero sum game; random priority; randomize stopping time

PL

czas zatrzymania; gry z zatrzymywaniem procesu; proces Markowa; złożony proces Poissona; gra o sumie niezerowej; losowy priorytet; randomizowane momenty zatrzymania

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2014
• Tom: Vol. 42, No. 2
• Strony: 193--206
• Opis fizyczny: Bibliogr. 45 poz.

Twórcy

autor

Szajowski K.

• Wrocław University of Technology Instytute of Mathematics and Computer Sci. Wybrzeze Wyspianskiego 27, PL-50-370 Wrocław, Poland

Bibliografia

• [1] Katsunori Ano and Masakazu Ando. A note on Bruss’ stopping problem with random availability. In Game theory, optimal stopping, probability and statistics, volume 35 of IMS Lecture Notes Monogr. Ser., pages 71–82. Inst. Math. Statist., Beachwood, OH, 2000. doi:10.1214/lnms/1215089745, MR 1833852.
• [2] B.A. Berezovskij and A.V. Gnedin. The best-choice problem. ( Задача наилучшего выбора). Москва: Издател’ство "Наука”. 200 p., 1984. MR 0768372 , Zbl 0579.62066.
• [3] Tomasz Bojdecki. On optimal stopping of a sequence of independent random variables- probability maximizing approach. Stochastic Processes Appl., 6:153–163, 1978. doi: 10.1016/0304-4149(78)90057-1, MR MR0468066, ZBL0374.60088.
• [4] L. Breiman. Stopping rule problem. In E.F. Beckenbach, editor, Applied Combinatorial Mathematics, pages 284 – 319, New York, 1964. Wiley.
• [5] F. Thomas Bruss. What is known about Robbins’ problem? J. Appl. Probab., 42(1):108–120, 2005. doi: 10.1239/jap/1110381374, MR 2144897 (2006b:60079), Zbl 1081.62059.
• [6] F. Thomas Bruss and Stephen M. Samuels. A unified approach to a class of optimal selection problems with an unknown number of options. Ann. Probab., 15(2):824–830, 1987. doi: 10.1214/aop/1176992175, MR 885147 (88e:60050), Zbl 0592.60034.
• [7] F. Thomas Bruss and Yvik C. Swan. A continuous-time approach to Robbins’ problem of minimizing the expected rank. J. Appl. Probab., 46(1):1–18, 2009. doi: 10.1239/jap/1238592113, MR 2508502 (2010f:60129).
• [8] F.Thomas Bruss. A unified approach to a class of best choice problems with an unknown number of options. Ann. Probab., 12:882–889, 1984. doi: 10.1214/aop/1176993237.
• [9] F.Thomas Bruss. On an optimal selection problem of Cowan and Zabczyk. J. Appl. Probab., 24:918–928, 1987. doi: 10.2307/3214216, MR 913832 (88i:60082) Zbl 0596.60046.
• [10] A. Cayley. Mathematical questions with their solutions. no. 4528. The Educational Times, 23:18–19, 1875.
• [11] Y.S. Chow, S. Moriguti, H. Robbins, and D. Siegmund. Optimal selection based on relative rank ( the “secretary problem”). Israel J. Math., 2:81 – 90, 1964.
• [12] Y.S. Chow, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal
• Stopping. Houghton Miffin, Boston, 1971.
• [13] Z. Ciesielski and J. Zabczyk. A note on a selection problem. In Probability theory (Papers, VIIth Semester, Stefan Banach Internat. Math. Center, Warsaw, 1976), volume 5 of Banach Center Publ., pages 47–51. PWN, Warsaw, 1979. MR 561467 (81b:60041), 209100.
• [14] R. Cowan and J. Zabczyk. A new version of the best choice problem. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 24(9):773–778, 1976. MR 0428424, Zbl 0359.60040.
• [15] R. Cowan and J. Zabczyk. An optimal selection problem associated with the Poisson process. Teor. Veroyatnost. i Primenen., 23(3):606–614, 1978. MR 0509733 (80c:60059), Zbl 0426.62058, doi: 10.1137/1123066.
• [16] E.B. Dynkin and A.A. Yushkevich. Theorems and Problems on Markov Processes. Plenum, New York, 1969.
• [17] G. Elfving. A persistency problem connected with a point process. J. Appl. Probability, 4:77–89, 1967.
• [18] T.S. Ferguson. Who solved the secretary problem? Statistical Science, 4:282–296, 1989. MR 1015277 (91k:01011), Zbl 0788.90080, doi: 10.1214/ss/1177012493.
• [19] P.R. Freeman. The secretary problem and its extensions: a review. Int. Statist. Rev., 51:189–206, 1983. MR 0715534 (84k:62115).
• [20] J.P. Gilbert and F. Mosteller. Recognizing the maximum of a sequence. J. Amer. Statist. Assoc., 61(313):35–73, 1966. MR 0198637.
• [21] Alexander Gnedin and Alexander Iksanov. Moments of random sums and Robbins’ problem of optimal stopping. J. Appl. Probab., 48(4):1197–1199, 2011. MR 2896677.
• [22] Theodore P. Hill and Ulrich Krengel. Minimax-optimal stop rules and distributions in secretary problems. Ann. Probab., 19(1):342–353, 1991. doi: 10.1214/aop/1176990548, Zbl 0723.60043.
• [23] A. Irle. On the best choice problem with random population size. Z. Oper. Res. Ser. A-B, 24(5):177–190, 1980. MR 588147 (81k:60051).
• [24] D.V. Lindley. Dynamic programming and decision theory. Appl. Stat., 10:39–51, 1961. doi:10.2307/2985407, Zbl 0114.34904.
• [25] Anthony G. Mucci. Differential equations and optimal choice problems. Ann. Stat., 1:104–113, 1973. doi: 10.1214/aos/1193342386, Zbl 0256.60021.
• [26] Anthony G. Mucci. On a class of secretary problems. Ann. Probab., 1:417–427, 1973. doi: 10.1214/aop/1176996936, Zbl 0261.60036.
• [27] Joseph D. Petruccelli. On a best choice problem with partial information. Ann. Stat., 8:1171–1174, 1980. doi: 10.1214/aos/1176345156, Zbl 0459.62071.
• [28] Joseph D. Petruccelli. Asymptotic full information for some best choice problems with partial information. Sankhya, Ser. A, 46:370–382, 1984. Zbl 0565.62064.
• [29] E.L. Presman and I.M. Sonin. The best choice problem for a random number of objects. Theory Prob. Appl., 17:657 – 668, 1972. translation from Teori Verojatnostej i e e Primeneni, 17, 695–706, 1972. doi: 10.1137/1117078, MR 0314177, Zbl 0296.60031.
• [30] M. Rasche. Allgemeine stopprobleme. Unpublished technical report, Institut für Mathematische Statistik, 1975.
• [31] W. T. Rasmussen. A generalized choice problem. J. Optimization Theory Appl., 15:311–325, 1975. MR 0362769.
• [32] Will T. Rasmussen and Herbert Robbins. The candidate problem with unknown population size. J. Appl. Probability, 12(4):692–701, 1975. MR 0386187.
• [33] G. Ravindran and K. Szajowski. Non-zero sum game with priority as Dynkin’s game. Math. Japonica, 37(3):401–413, 1992. MR 1162449.
• [34] J.S. Rose. Twenty years of secretary problems: a survey of developments in the theory of optimal choice. Adv.in Management Studies, 1:53–64, 1982.
• [35] M. Sakaguchi. Dowry problems and OLA policies. Rep. Stat. Appl. Res., JUSE, 25:124–128, 1978. MR 0416.62058.
• [36] Minoru Sakaguchi. Optimal stopping problems for randomly arriving offers. Math. Japon., 21(2):201–217, 1976. MR 0426860.
• [37] S.M. Samuels. An explicit formula for the limiting optimal success probability in the full information best choice problem. Mimeograph series, Purdue Univ. Stat. Dept., 1980.
• [38] Stephen M. Samuels. Minimax stopping rules when the underlying distribution is uniform. J. Am. Stat. Assoc., 76:188–197, 1981. doi: 10.2307/2287066, Zbl 0459.62070.
• [39] D.A. Seale and A. Rapoport. Sequential decision making with relative ranks: An experimental investigation of the ”secretary problem”. Organizational Behaviour and Human Decision Processes, 69:221–236, 1997. doi: 10.1006/obhd.1997.2683.
• [40] T. J. Stewart. The secretary problem with an unknown number of options. Oper. Res., 29(1):130–145, 1981. doi: 10.1287/opre.29.1.130, MR 606862 (83c:62134).
• [41] Artur Suchwałko and Krzysztof Szajowski. On Bruss’ stopping problem with general gain function. In L. A. Petrosjan and V. V. Mazalov, editors, Game theory and applications IX. Papers from the workshop on networking games and resource allocation, Petrozavodsk, Russia, July 12–15, 2002., pages 157–167. Hauppauge, NY: Nova Science Publishers., 2003. MR 2040386 (2005k:60131), Zbl 1104.91011.
• [42] K. Szajowski. A game version of the Cowan-Zabczyk-Bruss problem. Statist. Probab. Letters, 77:1683–1689, 2007. doi: 10.1016/j.spl.2007.04.008.
• [43] Krzysztof Szajowski. Markov stopping games with random priority. Z. Oper. Res., 39(1):69 – 84, 1994. doi: 10.1007/BF01440735, Zbl 0805.90127.
• [44] W. Tang, J.N. Bearden, and I. Tsetlin. Ultimatum deadlines. Management Science, 55(8):1423–1437, 2009. doi: 10.1287/mnsc.1090.1034.
• [45] Ширяев, A. H. Статистический последователиыи анализ. Оптималиые правила остановки. Издат. “Наука”, Москва, 1976. Second edition, revised, MR 0445744.