Duration problem with multiple exchanges

Charles E. M.  Pearce; Krzysztof  Szajowski; Mitsushi Tamaki

doi:10.3934/naco.2012.2.333

Article Contents

2012, Volume 2, Issue 2: 333-355. Doi: 10.3934/naco.2012.2.333

This issue Previous Article A sufficient optimality condition for nonregular problems via a nonlinear Lagrangian Next Article Performance analysis of transmission rate control algorithm from readers to a middleware in intelligent transportation systems

Duration problem with multiple exchanges

1.
The University of Adelaide, Department of Applied Mathathematics, Adelaide, South Australia 5005
2.
Institute of Mathematics and Computer Science, Wrocław University of Techechnology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław
3.
Department of Business Administration, Aichi University, Nagoya Campus, Hiraike 4-60-6, Nakamura, Nagoya, Aichi 453-8777

Received: October 2011

Revised: May 2012

Published: April 2012

Abstract Related Papers Cited by

Abstract

We treat a version of the multiple-choice secretary problem called the multiple-choice duration problem, in which the objective is to maximize the time of possession of relatively best objects. It is shown that, for the $m$--choice duration problem, there exists a sequence $(s_1,s_2,\ldots,s_m)$ of critical numbers such that, whenever there remain $k$ choices yet to be made, then the optimal strategy immediately selects a relatively best object if it appears at or after time $s_k$ ($1\leq k\leq m$). We also exhibit an equivalence between the duration problem and the classical best-choice secretary problem. A simple recursive formula is given for calculating the critical numbers when the number of objects tends to infinity. Extensions are made to models involving an acquisition or replacement cost.

Keywords:

Mathematics Subject Classification: Primary: 60G40, 90A46; Secondary: 62L15, 60K99.

Citation:

Related Papers

Cited by

References

[1]	M. Abramowitz and I. A. Stegun, "Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables," Dover, New York, 2000.
[2]	K. Ano, Optimal selection problem with three stops, J. Oper. Res. Soc., 32 (1989), 491-504.
[3]	D. Assaf, L. M. Goldstein and E. Samuel-Cahn, Ratio prophet inequalities when the mortal has several choices, Ann. Appl. Probab., 12 (2002), 972-984.doi: 10.1214/aoap/1031863177.
[4]	D. Assaf, L. M. Goldstein and E. Samuel-Cahn, Two-choice optimal stopping, Adv. Appl. Probab., 36 (2004), 1116-1147.doi: 10.1239/aap/1103662960.
[5]	D. Assaf and E. Samuel-Cahn, Simple ratio prophet inequalities for a mortal with multiple choices, J. Appl. Probab., 37 (4) (2000), 1084-1091.doi: 10.1239/jap/1014843085.
[6]	Y. Chow, H. Robbins and D. Siegmund, "Great Expectations: The Theory of Optimal Stopping," Houghton Mifflin Co., Boston, 1971.
[7]	E. Dynkin and A. Yushkevich, "Markov Process, Theorems and Problems," Plenum Press, New York, 1969.
[8]	R. Eidukjavicjus, Optimalna ostanovka markovskoj cepi dvumia momentami ostanovki, Lit. Mat. Sb., 13 (1979), 181-183.
[9]	T. Ferguson, Who solved the secretary problem? Statist. Sci. 4 (1989), 282-296.doi: 10.1214/ss/1177012493.
[10]	T. Ferguson, J. Hardwick and M. Tamaki, Maximizing the duration of owning a relatively best object, Strategies for sequential search and selection in real time (Amherst, MA, 1990). Contemp. Math., 125 (1992), 37-57.doi: 10.1090/conm/125/1160608.
[11]	A. Frank and S. Samuels, On an optimal problem of Gusein-Zade, Stoch. Proc. Appl., 10 (1980), 299-317.doi: 10.1016/0304-4149(80)90013-7.
[12]	J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence, J. Am. Stat. Assoc., 61 (1966), 35-73.
[13]	A. V. Gnedin, Best choice from the planar poisson process, Stoch. Proc. Appl., 111 (2004), 317-354.doi: 10.1016/j.spa.2003.12.005.
[14]	A. V. Gnedin, Objectives in the best-choice problems, Sequential Analysis, 24 (2005), 1-11.doi: 10.1081/SQA-200056196.
[15]	I. Gradshteyn and I. Ryzhik, "Tables of Integrals, Series, and Products," 6^th Edition, Academic Press, San Diego, CA, 2000.
[16]	S. M. Gusein-Zade, The problem of choice and the optimal stopping rule for a sequence of independent trials, Theory Probab. Appl., 11 (1966), 472-476.doi: 10.1137/1111050.
[17]	G. W. Haggstrom, Optimal sequential procedures when more then one stop is required, Ann. Math. Stat., 38 (1967), 1618-1626.doi: 10.1214/aoms/1177698595.
[18]	M. Hu, M. Tamaki and K. Ohno, A continuous time duration problem with an unknown number of options, Math. Japonica, 48 (1998), 233-237.
[19]	A. Kurushima and K. Ano, On optimal stopping problems for possession-period maximization associated with Poisson arrival, Mathematics of decision-making under uncertainty (Japanese) (Kyoto, 2002), Sūrikaisekikenkyūsho Kōkyūroku No. 1306 (2003), 11-17. Available from: http://ci.nii.ac.jp/naid/110000167076/en
[20]	A. Kurushima and K. Ano, Maximizing the expected duration of owning a relatively best object in a Poisson process with rankable observations, J. Appl. Probab., 46 (2009), 402-414.doi: 10.1239/jap/1245676096.
[21]	A. Kurushima and K. Ano, Maximizing the expected duration of owning a relatively best object in a Poisson process with rankable observations, 13-th International Symposium on Dyn. Games and Appl., Wrocław 2008, 8 pages. Available from: http://home.imm.uran.ru/sector3/poland2008/isdg2008/prace/Kurushima121296568071203970.pdf
[22]	R. Kühne and L. Rüschendorf, On optimal two-stopping problems, In"Limit theorems in probability and statistics. Fourth Hungarian colloquium on limit theorems in probability and statistics" ( Eds. I. Berkes et al.), Balatonlelle, Hungary, June 28-July 2, 1999, János Bolyai Mathematical Society, Budapest, II (2002), 261-271.
[23]	A. Lehtinen, The best-choice problem with an unknown number of objects, Z. Oper.Res., 37 (1993), 97-106.
[24]	V. V. Mazalov and M. Tamaki, Explicit solutions to the duration problem, Aichi Keiei Ronsyu, 147 (2003), 69-92.
[25]	V. V. Mazalov and M. Tamaki, An explicit formula for the limiting optimal gain in the full information duration problem, Mathematics of decision-making under uncertainty (Japanese) (Kyoto, 2002), Sūrikaisekikenkyūsho Kōkyūroku No. 1306 (2003), 217-222. Available from: http://ci.nii.ac.jp/naid/110000167076/en
[26]	V. V. Mazalov and M. Tamaki, An explicit formula for the optimal gain in the full-information problem of owning a relatively best object, J. Appl. Probab., 43 (2006), 87-101.doi: 10.1239/jap/1143936245.
[27]	V. V. Mazalov and M. Tamaki, Duration problem on trajectories, Stochastics, 79 (2007), 211-218.doi: 10.1080/17442500601072704.
[28]	T. F. Móri, The random secretary problem with multiple choice, Ann. Univ. Sci. Budapest. de Rolando Eötvös Nominatae. Sect. Comput., 5 (1984), 91-102.
[29]	A. G. Mucci, Differential equations and optimal choice problem, Ann. Stat., 1 (1973), 104-113.doi: 10.1214/aos/1193342386.
[30]	A. G. Mucci, On a class of secretary problems, Ann. Probab., 1 (1973), 417-427.doi: 10.1214/aop/1176996936.
[31]	M. L. Nikolaev, Zadacha vybora dvokh ob"ektov z minimal'nom sumarnym rangom, Izv. Vyss. Uchebn. Zaved. Mat., 166 (1976), 33-42.
[32]	M. L. Nikolaev, Ob odnom obobshchenii zadachi nailuchshego vybora, Teor. Veroyatn. Primen., 22, 191-194. on a generalization of the best choice problem, Theory Prob. Applications, 22 (1977), 187-190.doi: 10.1137/1122023.
[33]	M. L. Nikolaev, Obobshchennyje posledovatelnyje procedury, Litov. Mat. Sb., 191 (1979), 35-44.
[34]	M. Nikolaev, Optimal multi-stopping rules, Obozr. Prikl. Prom. Mat., 5 (1998), 309-348.
[35]	M. L. Nikolaev, On optimal multiple stopping of Markov sequences, Teor. Veroyatnost. i Primenen., 43 (1998), 374-382 in Russian; translation in Theory Probab. Appl., 43 (1999), 298-306.
[36]	J. Petruccelli, On the best-choice problem when the number of observation is random, J. Appl. Probab., 20 (1983), 165-171.doi: 10.2307/3213731.
[37]	Z. Porosiński, The full-information best choice problem with a random number of observations, Stoch. Proc. Appl., 24 (1987), 293-307.doi: 10.1016/0304-4149(87)90020-2.
[38]	Z. Porosinski, On best choice problems having similar solutions, Stat. Probab. Lett., 56 (2002), 321-327.doi: 10.1016/S0167-7152(01)00201-2.
[39]	J. Preater, On multiple choice secretary problem, Math. Oper. Res., 19, 597-602. doi: 10.1287/moor.19.3.597.
[40]	E. Presman and I. Sonin, The best choice problem for a random number of objects, Theory Prob. Appl., 17 (1972), 657-668.doi: 10.1137/1117078.
[41]	S. M. Ross, "Applied Probability Models with Optimization Applications," Holden-Day, San Francisco, Calif.-London-Amsterdam, 1970.
[42]	M. P. Quine and J. S. Law, Exact results for a secretary problem, J. Appl. Probab., 33 (1996), 630-639.doi: 10.2307/3215345.
[43]	M. Sakaguchi, Dowry problem and OLA policies, Rep. Stat. Appl. Res. Union Jap. Sci. Eng. JUSE, 25 (1978), 124-128.
[44]	M. Sakaguchi, Generalized secretary problems with three stops, Math. Japonica, 32 (1987), 105-122.
[45]	S. M. Samuels, Secretary problems, In "Handbook of Sequential Analysis" (Eds. B. Ghosh and P. Sen), Marcel Decker, New York, 1991, 381-405.
[46]	S. M. Samuels, Why do these quite different best-choice problems have the same solutions? Adv. Appl. Probab., 36 (2004), 398-416.doi: 10.1239/aap/1086957578.
[47]	W. Stadje, On multiple stopping rules, Optimization, 16 (1985), 401-418.doi: 10.1080/02331938508843030.
[48]	A. Suchwałko and K. Szajowski, Non standard, no information secretary problems, Sci. Math. Japonicae, 56 (2002), 443-456.
[49]	K. Szajowski, Optimal choice problem of $a$-th object, Matem. Stos., in Polish, 19 (1982), 51-65.
[50]	K. Szajowski, A two-disorder detection problem, Applicationes Mathematicae, 24 (1996), 231-241.
[51]	K. Szajowski and M. Tamaki, Shelf life of candidates in the generalized secretary problem, preprint, 2006, arXiv:0902.0232v2.
[52]	K. Szajowski, On a random number of disorders, Probab. Math. Statist., 31 (2011), 17-45.
[53]	K. Szajowski, On stopping games when more than one stop is possible, In "Probability Methods in Discrete Mathematics" (Eds. V. F. Kolchin et al), Proceedings of the Fifth International Petrozavodsk Conference, May 2000. International Science Publishers, 2002, 57-72.
[54]	M. Tamaki, A secretary problem with double choice, J. Oper. Res. Soc. Jap., 22 (1979), 257-265.
[55]	M. Tamaki, OLA policy and the best choice problem with random number of objects, Math. Japonica, 24 (1979), 451-457.
[56]	M. Tamaki, C. E. Pearce and K. Szajowski, Multiple choice problems related to the duration of the secretary problem, Sūrikaisekikenkyūsho Kōkyūroku 1068 (1998), 75-86. Available from: http://ci.nii.ac.jp/naid/110001138655/en.
[57]	J. Wilson, Optimal choice and assignment of the best $m$ of $n$ randomly arriving items, Stoch. Proc. Appl., 39 (1991), 325-343.doi: 10.1016/0304-4149(91)90086-R.
[58]	M. Yasuda, On a stopping problem involving refusal and forced stopping, J. Appl. Probab., 20 (1983), 71-81.doi: 10.2307/3213721.
[59]	M. Yasuda and K. Szajowski, Dynkin games and its extension to a multiple stopping model, Bulletin of the Japan Society for Industrial Mathematics 12 (2002), 17-28, in Japanese. Available from: http://www.math.s.chiba-u.ac.jp/ yasuda/accept/ouyou.pdf
[60]	A. J. Yeo and G. F. Yeo, Selecting satisfactory secretaries, Austral. J. Statist., 36 (1994), 185-198.
[61]	G. F. Yeo, Duration of a secretary problem, J. Appl. Probab., 34 (1997), 556-558.