Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 17 (2020) open journal systems 

A unified approach for solving sequential selection problems

Alexander Goldenshluger, University of Haifa
Yaakov Malinovsky, University of Maryland
Assaf Zeevi, Columbia University

In this paper we develop a unified approach for solving a wide class of sequential selection problems. This class includes, but is not limited to, selection problems with no–information, rank–dependent rewards, and considers both fixed as well as random problem horizons. The proposed framework is based on a reduction of the original selection problem to one of optimal stopping for a sequence of judiciously constructed independent random variables. We demonstrate that our approach allows exact and efficient computation of optimal policies and various performance metrics thereof for a variety of sequential selection problems, several of which have not been solved to date.

AMS 2000 subject classifications: Primary 60G40; secondary 62L15

Keywords: Sequential selection, optimal stopping, secretary problems, relative ranks, full information problems, no–information problems.

Creative Common LOGO

Full Text: PDF

Goldenshluger, Alexander, Malinovsky, Yaakov, Zeevi, Assaf, A unified approach for solving sequential selection problems, Probability Surveys, 17, (2020), 214-256 (electronic). DOI: 10.1214/19-PS333.


   Ajtai, M., Megiddo, N. and Waarts, O. (2001). Improved algorithms and analysis for secretary problems and generalizations. SIAM J. Discrete Math. 14, 1–27. MR1814535

   Albright, S. C., Jr. (1972). Stochastic sequential assignment problems. Technical report No. 147, Department of Statistics, Stanford University. MR2622227

   Arlotto, A. and Gurvich, I. (2019). Uniformly bounded regret in the multi-secretary problem. Stochastic Systems 9, 231–260. MR4032682

   Arlotto, A., Nguyen, Vinh V. and Steele, J. M. (2015). Optimal online selection of a monotone subsequence: a central limit theorem. Stochastic Process. Appl. 125, 3596–3622. MR3357621

   Berezovsky, B. A. and Gnedin, A. B. (1984). The Problem of Optimal Choice. Nauka, Moscow (in Russian). MR0768372

   Bruss, F. T. (2000). Sum the odds and stop. Ann. Probab. 28, 1384–1391. MR1797879

   Bruss, F. T. (2019). Odds–theorem and monotonicity. Mathematica Applicanda 47, 25–43. MR3988930

   Bruss, F. T. and Louchard, G. (2016). Sequential selection of the κ best out of n rankable objects. Discrete Math. Theor. Comput. Sci. 18, no. 3, Paper No. 13, 1–12. MR3601362

   Bruss, F. T. and Ferguson, T. (1996). Half–prophets and Robbins’ problem of minimising the expected rank with i.i.d. random variables. Athens Conference on Applied Probability and Time Series Analysis, Vol. I (1995), 1–17, Lect. Notes Stat., 114, Springer, New York. MR1466704

   Chow, Y. S., Moriguti, S., Robbins, H. and Samuels, S. M. (1964). Optimal selection based on relative rank (the “Secretary problem”). Israel J. Math. 2, 81–90. MR0176583

   Chow, Y. S., Robbins, H. and Siegmung, D. (1971). Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin Company, Boston. MR0331675

   Coffman, E. G., Jr., Flatto, L. and Weber, R. R. (1987). Optimal selection of stochastic intervals under a sum constraint. Adv. in Appl. Probab. 19, 454–473. MR0889945

   Derman, C., Lieberman, G. J. and Ross, S. (1972). A sequential stochastic assignment problem. Management Science 18, 349–355. MR0299189

   Dietz, C., van der Laan, D. and Ridder, A. (2011). Approximate results for a generalized secretary problem. Probab. Engrg. Inform. Sci. 25, 157–169. MR2786746

   Dynkin, E. B. (1963). Optimal choice of the stopping moment of a Markov process. (Russian) Dokl. Akad. Nauk SSSR 150, 238–240. Also in: Selected papers of E. B. Dynkin with commentary, 485–488. Edited by A. A. Yushkevich, G. M. Seitz and A. L. Onishchik. American Mathematical Society, Providence, RI; International Press, Cambridge. MR0154329

   Ferguson, T. S. (1989). Who solved the secretary problem? Statist. Science 4, 282–296. MR1015277

   Ferguson, T.S. (2008). Optimal Stopping and Applications. https://www.math.ucla.edu/tom/Stopping/Contents.html.

   Frank, A. Q. and Samuels, S. M. (1980). On an optimal stopping problem of Gusein–Zade. Stoch. Proc. Appl. 10, 299–311. MR0592775

   Freeman, P. R. (1983). The secretary problem and its extensions: a review. Int. Statist. Review 51, 189–206. MR0715534

   Gianini-Pettitt, J. (1979). Optimal selection based on relative ranks with a random number of individuals. Adv. Appl. Probab. 11, 720–736. MR0544192

   Gilbert, J. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73. MR0198637

   Goldenshluger, A. and Zeevi, A. (2018). Optimal stopping of a random sequence with unknown distribution. Preprint.

   Gnedin, A. V. (1999). Sequential selection of an increasing subsequence from a sample of random size. J. Appl. Probab. 36, 1074–1085. MR1742151

   Gnedin, A. V. (2007). Optimal stopping with rank-dependent loss. J. Appl. Probab. 44, 996–1011. MR2382941

   Gnedin, A. V. and Krengel, U. (1996). Optimal selection problems based on exchangeable trials. Ann. Appl. Probab. 6, 862–882. MR1410118

   Gusein–Zade, S. M. (1966). The problem of choice and the optimal stopping rule for a sequence of independent trials. Theory Probab. Appl. 11, 472–476. MR0202256

   Haggstrom, G. W. (1967). Optimal sequential procedures when more than one stop is required. Ann. Math. Statist. 38, 1618–1626. MR0217946

   Irle, A. (1980). On the best choice problem with random population size. Zeitschrift für Operations Research 24, 177–190. MR0588147

   Kawai, M. and Tamaki, M. (2003). Choosing either the best or the second best when the number of applicants is random. Comput. Math. Appl. 46, 1065–1071. MR2023150

   Krieger, A. M. and Samuel-Cahn, E. (2009). The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations. Adv. in Appl. Probab. 41, 1041–1058 MR2663235

   Krieger, A. M., Pollak, M. and Samuel-Cahn, E. (2007). Select sets: rank and file. Ann. Appl. Probab. 17, 360–385. MR2292590

   Krieger, A. M., Pollak, M. and Samuel-Cahn, E. (2008). Beat the mean: sequential selection by better than average rules. J. Appl. Probab. 45, 244–259. MR2409324

   Lin, Y.-S., Hsiau, S.-R. and Yao, Y.-C. (2019). Optimal selection of the k-th best candidate. Probab. Engrg. Inform. Sci. 33, 327–347. MR3947259

   Lindley, D. V. (1961). Dynamic programming and decision theory. Appl. Statist. 10, 39–51. MR0123413

   Matsui T. and Ano, K. (2016). Lower bounds for Bruss’ Odds Theorem with multiple stoppings. Math. Oper. Res. 41, 700–714. MR3486816

   Moser, L. (1956). On a problem of Cayley. Scripta Math. 22, 289–292.

   Mucci, A. G. (1973). Differential equations and optimal choice problems. Ann. Statist. 1, 104–113. MR383668

   Nikolaev, A. G. and Jacobson, S. H. (2010). Stochastic sequential decision–making with a random number of jobs. Oper. Res. 58, 1023–1027. MR2683491

   Nikolaev, M. L. and Sofronov, G. (2007). A multiple optimal stopping rule for sums of independent random variables. Diskr. Mat. 17, 42–51. MR2392695

   Presman, E. L. and Sonin, I. M. (1972). The best choice problem for a random number of objects. Teor. Veroyatnost. i Primenen. 17, 695–706. MR0314177

   Quine, M. P. and Law, J. S. (1996). Exact results for a secretary problem. J. Appl. Probab. 33, 630–639. MR1401461

   Robbins, H. (1970). Optimal stopping. Amer. Math. Monthly 77, 333–343. MR0256475

   Robbins, H. (1991). Remarks on the secretary problem. Amer. J. Math. and Management Sci. 11, 25–37. MR1142412

   Rose, J.S (1982a). A problem of optimal choice and assignment. Oper. Res. 30, 172–181.

   Rose, J.S. (1982b). Selection of nonextremal candidates from a sequence. J. Optimization Theory Applic. 38, 207–219. MR0686864

   Sakaguchi, M. (1984). A sequential stochastic assignment problem with an unknown number of jobs. Math. Japonica 29, 141–152. MR0747918

   Samuels, S. (1991). Secretary problems. In: Handbook of Sequential Analysis, edited by B. K. Ghosh and P. K. Sen, Marcel Dekker Inc., New York. MR1174312

   Samuels, S. M. and Steele, J. M. (1981). Optimal sequential selection of a monotone sequence from a random sample. Ann. Probab. 9, 937–947. MR0632967

   Szajowski, K. (1982). Optimal choice of an object with ath rank (Polish). Mat. Stos. 19, 51-65. MR0664139

   Woryna, A. (2017). The solution of a generalized secretary problem via analytic expressions. J. Comb. Optim. 33, 1469–1491. MR3627527

   Vanderbei, R.J. (1980). The optimal choice of a subset of a population. Math. Oper. Res. 5, 481–486. MR0593639

   Vanderbei, R.J. (2012). The postdoc variant of the secretary problem. Tech. Report.

   Yeo, G. F. (1997). Duration of a secretary problem. J. Appl. Probab. 34, 556–558. MR1447359

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787