The Generalized Stackelberg Equilibrium of the Two-Person Stopping Game

doi:10.1007/s40305-023-00460-w

Abstract

Abstract: In modeling the bilateral selection of states of the process, Dynkin (Dokl Akad Nauk USSR 185:241–288, 1969) proposed a two-person game in which players use stopping moments as strategies. The purpose of this work is to present a model of the game in which the players have different information about the process itself, as well as various laws to stop the process and accept its state. The game model uses the stochastic process apparatus, in particular, the ability to create different filters for the same process. The sets of stopping moments based on different filters are not identical, which allows us to model different sets of strategies for players. We show that the follower, by observing the behavior of a rational leader, can recover information that is lost due to the lack of complete observation of the state of the process. In the competition of two opponents for the maximum of the i.i.d. sequence, one of whom has access to full information and the other only knows their relative ranks, we found the generalized Stackelberg equilibrium. If the priority of a player observing the relative ranks is less than 50%, then that player modifies his strategy based on the behavior of the second player. For a player with full information, information about the behavior of the player observing the relative ranks is useless.

Key words: No-zero-sum game, Optional stopping, Equilibrium, Filtration

CLC Number:

Marek Skarupski, Krzysztof J. Szajowski. The Generalized Stackelberg Equilibrium of the Two-Person Stopping Game[J]. Journal of the Operations Research Society of China, 2024, 12(1): 155-168.

TrendMD

References

[1] Ferguson, T.S.: Who solved the secretary problem? Stat. Sci. 4(3), 282-289 (1989)
[2] Cayley, A.: Mathematical questions with their solutions. The Educational Times 23, 18-19: See the collected mathematical papers of Arthur Cayley 10, 587-588 (1896). Cambridge Univ. Press, Cambridge (1875)
[3] Presman, E.L., Sonin, I.M.: The best choice problem for a random number of objects. Teor. Veroyatnost. Primenen. 17(4), 695-706 (1972). https://doi.org/10.1137/1117078
[4] Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61(313), 35-73 (1966)
[5] Dynkin, E.B.: The game variant of the optimal stopping problem. Dokl. Akad. Nauk USSR 185, 241-288 (1969). Translation from Dokl. Akad. Nauk. SSSR 185, 16-19 (1969)
[6] Szajowski, K., Skarupski, M.: On multilateral incomplete information decision models. High Freq. 2(3-4), 158-168 (2019)
[7] von Stackelberg, H.F.: Grundlagen Einer Reinen Kostentheorie. Meilensteine Nationalokonomie, p. 131. Springer, Berlin (2009). Originally published monograph. Reprint of the 1st Edn. Wien, Verlag von Julius Springer (1932). http://www.springerlink.com/content/978-3-540-85271-1
[8] Nakai, T.: Stackelberg solution for a stopping game. J. Inf. Optim. Sci. 18(3), 479-491 (1997)
[9] Ferenstein, E.Z.: Two-person non-zero-sum games with priorities. In: Ferguson, T.S., Samuels, S.M. (eds.) Strategies for Sequential Search and Selection in Real Time, Proceedings of the AMS-IMS-SIAM Join Summer Research Conferences Held June 21-27, 1990. Contemporary Mathematics, vol. 125, pp. 119-133. University of Massachusetts at Amherst (1992)
[10] Szajowski, K.: Optimal stopping of a discrete Markov process by two decision makers. SIAM J. Control Optim. 33(5), 1392-1410 (1995)
[11] Porosiński, Z., Szajowski, K.: Modified strategies in two person full-information best choice problem with imperfect observation. Math. Jpn. 52(1), 103-112 (2000)
[12] Mazalov, V.V.: Mathematical Game Theory and Applications, p. 414. John Wiley & Sons Ltd, Chichester (2014)
[13] Kurano, M., Yasuda, M., Nakagami, J.: Multivariate stopping problem with a majority rule. J. Oper. Res. Soc. Jpn. 23(3), 205-223 (1980)
[14] Enns, E.G., Ferenstein, E.: The horse game. J. Oper. Res. Soc. Jpn. 28(1), 51-62 (1985)
[15] Majumdar, A.A.K.: The horse game and the OLA policy. Indian J. Math. 30(3), 213-218 (1988)
[16] Vinnichenko, S.V., Mazalov, V.V.: Games for a stopping rule of a sequence of observations of fixed length. Kibernetika (Kiev) 1, 122-124136 (1989)
[17] Bruss, F.T., Drmota, M., Louchard, G.: The complete solution of the competitive rank selection problem. Algorithmica 22(4), 413-447 (1998)
[18] Szajowski, K.: Optimal stopping of a sequence of maxima over an unobservable sequence of maxima. Zastos. Mat. 18(3), 359-374 (1984)
[19] Porosiński, Z.: Optimal stopping of a random length sequence of maxima over a random barrier. Zastos. Mat. 20(2), 171-184 (1990)
[20] Neumann, P., Porosiński, Z., Szajowski, K.: On two person full-information best choice problem with imperfect observation. In: Game Theory and Applications, II. Game Theory Applications, pp. 47-55. Nova Science Publishers, Hauppauge, NY (1996)
[21] Sakaguchi, M.: Optimal stopping in sampling from a bivariate distribution. J. Oper. Res. Soc. Jpn. 16, 186-200 (1973)
[22] Sakaguchi, M., Szajowski, K.: Mixed-type secretary problems on sequences of bivariate random variables. Math. Jpn. 51(1), 99-111 (2000)
[23] Chow, Y.S., Robbins, H., Siegmund, D.: The Theory of Optimal Stopping, p. 141. Dover Publications, Inc., New York (1991). Corrected reprint of the 1971 original
[24] Dynkin, E.B., Yushkevich, A.A.: Markov Processes: Theorems and Problems, p. 237. Plenum Press, New York (1969). Translated from the Russian by James S. Wood
[25] Shiryaev, A.N.: Optimal Stopping Rules. Stochastic Modelling and Applied Probability, vol. 8, p. 217. Springer, Berlin (2008). Translated from СтатистическиЙ последовательныЙ аиализ.Оптимальные правила the 1976 Russian second edition by A. B. Aries, Reprint of the 1978 translation
[26] Szajowski, K.: Markov stopping games with random priority. Z. Oper. Res. 39(1), 69-84 (1994)
[27] Bojdecki, T.: On optimal stopping of a sequence of independent random variables—probability maximizing approach. Stoch. Process. Appl. 6(2), 153-163 (1978)
[28] Enns, E.G.: Optimal sequential decisions with information invariance. Sci. Math. Jpn. 60(3), 551-561 (2004)
[29] Dotsenko, S.I., Marynych, A.V.: Hint, extortion, and guessing games in the best choice problem. Cybernet. Syst. Anal. 50(3), 419-425 (2014)
[30] Skarupski, M.: Full-information best choice game with hint. Math. Methods Oper. Res. 90(2), 153-168 (2019)
[31] Basu, A., Stettner, Ł: Finite- and infinite-horizon Shapley games with nonsymmetric partial observation. SIAM J. Control Optim. 53(6), 3584-3619 (2015)
[32] Szajowski, K.J.: Sequential selections with minimization of failure. J. Math. Psychol. 111, 102723 (2022)