Approximative solutions of optimal stopping and selection problems

• Autorzy: Rüschendorf L.

Identyfikatory

DOI

10.14708/ma.v44i1.826

Warianty tytułu

PL

Przybliżone rozwiązania zadań optymalnego zatrzymania oraz problemów wyboru najlepszego obiektu

• Języki publikacji: EN

Abstrakty

EN

In this paper we review a series of developments over the last 15 years in which a general method for the approximative solution of finite discrete time optimal stopping and choice problems has been developed. This method also allows to deal with multiple stopping and choice problems and to deal with stopping or choice problems for some classes of dependent sequences. The basic assumption of this approach is that the sequence of normalized observations when embedded in the plane converges in distribution to a Poisson or to a cluster process. For various classes of examples the method leads to explicit or numerically accessible solutions.

PL

W artykule opracowano przegląd różnych podejść z ostatnich 15 lat do przybliżonego rozwiązywania zadań optymalnego zatrzymania procesów z czasem dyskretnym, w tym także zadań wyboru najlepszego obiektu. Metody te pozwalają także na rozwiązywanie niektórych problemów wielokrotnego zatrzymania, a także radzą sobie z rozwiązaniem zadań dla ciągów zależnych. Podstawą tych analiz jest obserwacja, iż ciąg unormowanych obserwacji odwzorowanych na płaszczyźnie jest zbieżny według rozkładu do pewnego procesu punktowego. Dla różnych klas zadań metoda prowadzi do uzyskania zamkniętych analitycznych formuł lub pozwala na uzyskanie rozwiązań numerycznych.

Słowa kluczowe

EN

optimal stopping; best choice problem; multiple stopping problems; Poisson process

PL

optymalne zatrzymanie procesu; problem wyboru najlepszego obiektu; problem optymalnego wielokrotnego zatrzymania; proces Poissona

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 17--44
• Opis fizyczny: Bibliogr. 49 poz., wykr., fot.

Twórcy

autor

Rüschendorf L.

• University of Freiburg, Abteilung für Mathematische Stochastik, Albert-Ludwigs University of Freiburg, Eckerstraße 1, D–79104 Freiburg, Germany

Bibliografia

• [1] D. Assaf, L. Goldstein, and E. Samuel-Cahn. Two-choice optimal stopping. Adv. Appl. Probab., 36(4):1116–1147, 2004.
• [2] D. Assaf, L. Goldstein, and E. Samuel-Cahn. Maximizing expected value with two stage stopping rules. In Random Walk, Sequential Analysis and Related Topics., pages 3–27. Hackensack, NJ: World Scientific, 2006.
• [3] F. T. Bruss and T. S. Ferguson. Minimizing the expected rank with full information. J. Appl. Probab., 30(3):616–626, 1993.
• [4] F. T. Bruss and T. S. Ferguson. Half-prophets and Robbins’ problem of minimizing the expected rank. In Athens conference on Applied Probability and Time Series Analysis, Athens, Greece, March 22–26, 1995. Vol. I: Applied Probability. In honor of J. M. Gani, pages 1–17. Berlin: Springer, 1996.
• [5] F. T. Bruss and T. S. Ferguson. Multiple buying or selling with vector offers. J. Appl. Probab., 34(4):959–973, 1997.
• [6] F. T. Bruss and G. Louchard. Letter to the editor: Sharp bounds for winning probabilities in the competitive rank selection problem. J. Appl. Probab., 35(4):1007–1011, 1998.
• [7] F. T. Bruss and L. C. G. Rogers. Embedding optimal selection problems in a Poisson process. Stochastic Processes Appl., 38(2):267–278, 1991.
• [8] F. T. Bruss and Y. C. Swan. A continuous-time approach to Robbins’ problem of minimizing the expected rank. J. Appl. Probab., 46(1):1–18, 2009.
• [9] Y. S. Chow, H. Robbins, and D. Siegmund. Great expectations: The theory of optimal stopping. Boston etc.: Houghton Mifflin Company, 1971.
• [10] R. Davis and S. Resnick. Limit theory for moving averages of random variables with regularly varying tail probabilities. Ann. Probab., 13(1): 179–195, 1985.
• [11] R. Davis and S. Resnick. Extremes of moving averages of random variables from the domain of attraction of the double exponential distribution. Stochastic Processes Appl., 30(1):41–68, 1988.
• [12] R. Davis and S. Resnick. Extremes of moving averages of random variables with finite endpoint. Ann. Probab., 19(1):312–328, 1991.
• [13] R. Durrett and S. I. Resnick. Functional limit theorems for dependent variables. Ann. Probab., 6:829–846, 1978.
• [14] G. Elfving. A persistency problem connected with a point process. J. Appl. Probab., 4:77–89, 1967.
• [15] A. Faller. Approximative Lösungen von Mehrfachstoppproblemen. Freiburg im Breisgau: Univ. Freiburg, Fakultät für Mathematik und Physik, Dissertation, 2009.
• [16] A. Faller and L. Rüschendorf. On approximative solutions of optimal stopping problems. Adv. Appl. Probab., 43(4):1086–1108, 2011.
• [17] A. Faller and L. Rüschendorf. On approximative solutions of multistopping problems. Ann. Appl. Probab., 21(5):1965–1993, 2011.
• [18] A. Faller and L. Rüschendorf. Approximative solutions of best choice problems. Electron. J. Probab., 17(54):1–22, 2012.
• [19] A. Faller and L. Rüschendorf. Optimal multiple stopping with sumpayoff. Theory Probab. Appl., 57(2):325–336, 2013.
• [20] T. S. Ferguson. Optimal stopping an applications. Electronic Texts on homepage, 2007. Available online at http://www.math.ucla.edu/~tom/Stopping/Contents.html.
• [21] J. Flatau and A. Irle. Optimal stopping for extremal processes. Stochastic Processes Appl., 16:99–111, 1984.
• [22] J. P. Gilbert and F. Mosteller. Recognizing the maximum of a sequence. J. Amer. Statist. Assoc., 61:35–73, 1966.
• [23] A. V. Gnedin. Multicriterial problem of optimum stopping of the selection process. Automat. Remote Control, 7:161–166, 1981.
• [24] A. V. Gnedin. Multicriteria extensions of the best choice problem: sequential selection without linear order. In Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990), volume 125 of Contemp. Math., pages 153–172. Amer. Math. Soc., Providence, RI, 1992.
• [25] A. V. Gnedin. On the full information best-choice problem. J. Appl. Probab., 33(3):678–687, 1996.
• [26] A. V. Gnedin and M. Sakaguchi. On a best choice problem related to the Poisson process. In Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990), volume 125 of Contemp. Math., pages 59–64. Amer. Math. Soc., Providence, RI, 1992.
• [27] L. Goldstein and E. Samuel-Cahn. Optimal two-choice stopping on an exponential sequence. Sequential Anal., 25(4):351–363, 2006.
• [28] S. Karlin. Stochastic models and optimal policy for selling an asset. Stud. Appl. Probab. Management Sci., pages 148–159, 1962.
• [29] D. P. Kennedy and R. P. Kertz. Limit theorems for threshold-stopped random variables with applications to optimal stopping. Adv. Appl. Probab., 22(2):396–411, 1990.
• [30] D. P. Kennedy and R. P. Kertz. The asymptotic behavior of the reward sequence in the optimal stopping of i.i.d. random variables. Ann. Probab., 19(1):329–341, 1991.
• [31] D. P. Kennedy and R. P. Kertz. Comparisons of optimal stopping values and expected suprema for i.i.d. r.v.’s with costs and discounting. In Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990), volume 125 of Contemp. Math., pages 217–230. Amer. Math. Soc., Providence, RI, 1992.
• [32] R. Kühne. Probleme des asymptotisch optimalen Stoppens. Freiburg im Breisgau: Univ. Freiburg im Breisgau, Mathematische Fakultät, 1997.
• [33] R. Kühne. Probleme des asymptotisch optimalen Stoppens. Freiburg im Breisgau: Univ. Freiburg, Fakultät für Mathematik und Physik, Dissertation, 1997.
• [34] R. Kühne and L. Rüschendorf. Optimal stopping with discount and observation costs. J. Appl. Probab., 37(1):64–72, 2000.
• [35] R. Kühne and L. Rüschendorf. Approximation of optimal stopping problems. Stochastic Processes Appl., 90(2):301–325, 2000.
• [36] R. Kühne and L. Rüschendorf. On optimal two-stopping problems. In Limit Theorems in Probability and Statistics, pages 261–271. Budapest: János Bolyai Mathematical Society, 2002.
• [37] R. Kühne and L. Rüschendorf. Optimal stopping and cluster point processes. Stat. Decis., 21(3):261–282, 2003.
• [38] R. Kühne and L. Rüschendorf. Approximate optimal stopping of dependent sequences. Theory Probab. Appl., 48(3):465–480, 2003.
• [39] R. S. Liptser and A. N. Shiryaev. Statistics of Random Processes. 1: General Theory. Berlin: Springer, 2nd rev. and exp. edition, 2001.
• [40] J. Neveu. Discrete-parameter Martingales. North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, revised edition, 1975.
• [41] R. Perfekt. Extremal behaviour of stationary Markov chains with applications. Ann. Appl. Probab., 4(2):529–548, 1994.
• [42] S. I. Resnick. Extreme Values, Regular Variation, and Point Processes, volume 4 of Applied Probability. 1987.
• [43] H. Rootzén. Extremes of moving averages of stable processes. Ann. Probab., 6(5):847–869, 1978.
• [44] V. Saario. Comparison of the discrete and continuous-time stochastic selling models. Eng. Costs Product. Econ., 12:15–20, 1992.
• [45] V. Saario and M. Sakaguchi. Some generalized house-selling problems. Math. Japon., 35(5):861–873, 1990.
• [46] V. Saario and M. Sakaguchi. Multistop best choice games related to the Poisson process. Math. Japon., 37(1):41–51, 1992. ISSN 0025-5513.
• [47] A. Shiryaev. Optimal Stopping Rules. Number 8 in Applications of Mathematics. New York–Heidelberg–Berlin: Springer-Verlag, 3rd edition, 1978.
• [48] D. Siegmund. Some problems in the theory of optimal stopping rules. Ann. Math. Stat., 38:1627–1640, 1967.
• [49] W. Stadje. On multiple stopping rules. Optimization, 16(3):401–418, 1985.

Uwagi

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