Control Systems and Computers

https://doi.org/10.15407/usim.2019.01.011

Upr. sist. maš., 2019, Issue 1 (279), pp. 11-21.

UDC 65.01:62-505

L.S. Fainzilberg, Doctor (Eng.), Professor, Head of the department, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, fainzilberg@gmail.com

MODIFIED OPTIMAL STOPING METHOD IN THE PROBLEM OF A SEQUENTIAL ALTERNATIVES ANALYSIS

Introduction. The traditional formulation of the optimal stopping problem is aimed at choosing the moment of making a decision about the appearance of the best option during the sequential viewing of ranked alternatives in a random order. A distinctive feature of the proposed method generalization is that the decision on an applicant appearance, which by some criterion differs from the absolute leader by no more than a specified amount (assignment), is considered correct.

The purpose of the article is to explore the possibilities of a modified optimal stopping method based on a statistical experiment.

Methods. The statistical experiment is based on the Monte Carlo method and provides for the multiple generation of the arrays of independent identically distributed random variables that mimic the values of the super alternative criterion, which the person observes at the current step. Based on a series of multiple tests, the probability of an applicant selecting, which differs by a given amount from the absolute leader, is estimated. The dependence probability analysis of the correct decisions on the assignment value is done.

Result. It is established that already at a value of 4% assignment, the required amount of experimental sampling for making a final decision decreases from 37% (the classical method) to 15%. At the same time, the probability of right decision increases to  (when is concession of 10%) compared with the probability  of the right decision, achieved by the classical method.

Conclusion. By introducing an insignificant concession to the deviations of the chosen applicant from the absolute leader, the possibilities of the optimal stopping method are expanded to solve the practical problems.

 Download full text! (In Russian)

Keywords: optimal stopping, alternative, probability of correct decision.

1. Voloshin, O.F., Maschenlo, C.O., 2010. Models and Methods of Decision Making: Teach. Manual, Kiev: View-polygraph. center “Kyiv. un-t “, 336 p. (In Ukrainian).
2. Fainzilberg, L.S., Zhukovska, O.A., Yakumchuk, V.S., 2018. Theory of decision-making: a textbook for students of the specialty “Computer Science and Information Technologies”, specialization “Information Technologies in Biology and Medicine”. Kyiv: Education of Ukraine, 246 p. (In Ukrainian).
3. Maheswari, U.A., Kumari, P. A., 2012. “Fuzzy Mathematical Model for Multi Criteria Group Decision Making-An Application in Supply Chain Management”, International Journal of Computer Applications, 54 (7), pp. 5-10.
   https://doi.org/10.5120/8576-2314
4. Rasmusen, E., 2006. Games and Information: An Introduction to Game Theory, 4th Edition. Oxford: Wiley-Blackwell, 445 p.
5. DeGroot M. (1974) Optimal statistical decision, Moscow: Mir, 491 p. (In Russian).
6. Dotcenko, S.I., Negadaylov, P.A., 2014. “The optimal order of viewing groups in the task of choosing the best element with a group view of the cardidates”, Cybernetics and Computer Engineering, 175, pp. 32-39. (In Ukrainian).
7. Robbins, G, Sigmund, D., Chao, I., 1975. The theory of optimal stopping rules, Moscow; Nauka, 188 p. (In Russian).
8. Gusein-Zade, S.M., 1966. The problem of choice and the optimal stopping rule for the sequence of independent tests. Theory of probabilities and its applications, 11 (3), pp. 534-537.
   https://doi.org/10.1137/1111050
9. Sakaguchi, M., 1976. “Optimal stopping problems for randomly arriving offers”, Math. Japan, 21, pp. 201-217.
10. Gusein-Zade, S.M., 2003. Clever bride, Moscow: MCNMO, 24 p. (In Russian).
11. Ferguson, T.S., 2003. “Who Solved the Secretary Problem?”, Statistical Science, 4 (3), pp. 282-289.
    https://doi.org/10.1214/ss/1177012493
12. Keeney, R.L., Raiffa, H., 1981. Decisions with Multiple Objectives, Moscow: Radio and communication, 500 p. (In Russian).
13. Saati, T., 1993. Decision making. Hierarchy analysis method, Moscow: Radio and communication, 278 p. (In Russian).
14. Rubinstein, R.Y., Kroese, D.P., 2016. Simulation and the Monte Carlo Method, New York: John Wiley & Sons,
    432 p.
    https://doi.org/10.1002/9781118631980
15. Robert, C.P., Casella, G., 2004. Monte Carlo statistical methods. New York: Springer, 397 p. http://dx.doi.org/10. 1007/978-1-4757-4145-2.
16. Fainzilberg, L., Yaremenko, Yu., 2018. “Computer Modeling of the Modified Method of Optimal Stopping”, Proceedings of the International Scientific Conference “Information Technologies and Computer Modeling” (2018, May, 14th to 19th, Ivano-Frankivsk). Ivano-Frankivsk, pp. 270-273. (In Ukrainian).

Received 24.02.2019