Approximative solutions of best choice problems

Andreas Faller (University Freiburg)
Ludger Rüschendorf (University Freiburg)

Abstract


We consider the full information best choice problem from a sequence $X_1,\dots, X_n$ of independent random variables. Under the basic assumption of convergence of the corresponding imbedded point processes in the plane to a Poisson process we establish that the optimal choice problem can be approximated by the optimal choice problem in the limiting Poisson process. This allows to derive approximations to the optimal choice probability and also to determine approximatively optimal stopping times. An extension of this result to the best $m$-choice problem is also given.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: July 17, 2012

DOI: 10.1214/EJP.v17-2172

References

  • Berezovskiĭ, B. A.; Gnedin, A. V. \cyr Zadacha nailuchshego vybora. (Russian) [The problem of optimal choice] ``Nauka'', Moscow, 1984. 197 pp. MR0768372
  • Bruss, F. Thomas. On a class of optimal stopping problems with mixed constraints. Discrete Math. Theor. Comput. Sci. 12 (2010), no. 2, 363--380. MR2676679
  • Bruss, F. Thomas; Ferguson, Thomas S. Minimizing the expected rank with full information. J. Appl. Probab. 30 (1993), no. 3, 616--626. MR1232739
  • Bruss, F. Thomas; Ferguson, Thomas S. Multiple buying or selling with vector offers. J. Appl. Probab. 34 (1997), no. 4, 959--973. MR1484028
  • A. Faller, phApproximative Lösungen von Mehrfachstoppproblemen, Dissertation, University of Freiburg, 2009.
  • Faller, Andreas; Rüschendorf, Ludger. On approximative solutions of multistopping problems. Ann. Appl. Probab. 21 (2011), no. 5, 1965--1993. MR2884056
  • Faller, Andreas; Rüschendorf, Ludger. On approximative solutions of optimal stopping problems. Adv. in Appl. Probab. 43 (2011), no. 4, 1086--1108. MR2867947
  • T. S. Ferguson, phOptimal stopping and applications, Electronic Texts on homepage, 2007, Available online at rlhttp://www.math.ucla.edu/~tom/Stopping/Contents.html;.
  • Gilbert, John P.; Mosteller, Frederick. Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61 1966 35--73. MR0198637
  • Gnedin, A. V. Multicriterial problem of optimum stopping of the selection process. (Russian) Automat. Remote Control 1981, no. 7, 161--166 MR0647673
  • Gnedin, Alexander V. Multicriteria extensions of the best choice problem: sequential selection without linear order. Strategies for sequential search and selection in real time (Amherst, MA, 1990), 153--172, Contemp. Math., 125, Amer. Math. Soc., Providence, RI, 1992. MR1160617
  • Gnedin, Alexander V. On the full information best-choice problem. J. Appl. Probab. 33 (1996), no. 3, 678--687. MR1401465
  • Gnedin, Alexander V.; Sakaguchi, Minoru. On a best choice problem related to the Poisson process. Strategies for sequential search and selection in real time (Amherst, MA, 1990), 59--64, Contemp. Math., 125, Amer. Math. Soc., Providence, RI, 1992. MR1160609
  • Goldstein, Larry; Samuel-Cahn, Ester. Optimal two-choice stopping on an exponential sequence. Sequential Anal. 25 (2006), no. 4, 351--363. MR2271920
  • Kühne, Robert; Rüschendorf, Ludger. Approximation of optimal stopping problems. Stochastic Process. Appl. 90 (2000), no. 2, 301--325. MR1794541
  • Kühne, R.; Rüschendorf, L. On a best choice problem for discounted sequences. Teor. Veroyatnost. i Primenen. 45 (2000), no. 4, 789--792; translation in Theory Probab. Appl. 45 (2002), no. 4, 673--677 MR1968733
  • Kühne, Robert; Rüschendorf, Ludger. Optimal stopping with discount and observation costs. J. Appl. Probab. 37 (2000), no. 1, 64--72. MR1761661
  • Kühne, R.; Rüschendorf, L. On optimal two-stopping problems. Limit theorems in probability and statistics, Vol. II (Balatonlelle, 1999), 261--271, János Bolyai Math. Soc., Budapest, 2002. MR1979997
  • Saario, Vesa; Sakaguchi, Minoru. Multistop best choice games related to the Poisson process. Math. Japon. 37 (1992), no. 1, 41--51. MR1148515
  • Sakaguchi, Minoru; Saario, Vesa. A class of best-choice problems with full information. Math. Japon. 41 (1995), no. 2, 389--398. MR1326972
  • Sakaguchi, Minoru. Optimal stopping problems for randomly arriving offers. Math. Japon. 21 (1976), no. 2, 201--217. MR0426860
  • Sakaguchi, Minoru. Best-choice games with random priority on a two-Poisson stream. Math. Japon. 36 (1991), no. 4, 731--745. MR1120457
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.