Nonzero-sum Stochastic Games

Nowak, Andrzej S. and Szajowski, Krzysztof (1998): Nonzero-sum Stochastic Games. Published in: Annals of the International Society of Dynamic Games , Vol. 4, (1999): pp. 297-342.

Abstract

This paper treats of stochastic games. We focus on nonzero-sum games and provide a detailed survey of selected recent results. In Section 1, we consider stochastic Markov games. A correlation of strategies of the players, involving ``public signals'', is described, and a correlated equilibrium theorem proved recently by Nowak and Raghavan for discounted stochastic games with general state space is presented. We also report an extension of this result to a class of undiscounted stochastic games, satisfying some uniform ergodicity condition. Stopping games are related to stochastic Markov games. In Section 2, we describe a version of Dynkin's game related to observation of a Markov process with random assignment mechanism of states to the players. Some recent contributions of the second author in this area are reported. The paper also contains a brief overview of the theory of nonzero-sum stochastic games and stopping games which is very far from being complete.

• Item Type: MPRA Paper
• Language: English
• Keywords: average payoff stochastic games, correlated stationary equilibria, nonzero-sum games, stopping time, stopping games
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling; C - Mathematical and Quantitative Methods > C4 - Econometric and Statistical Methods: Special Topics > C44 - Operations Research ; Statistical Decision Theory; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

Rogers, P. D. (1969) Nonzero-Sum Stochastic Games. PhD thesis, University of California, Berkeley, 1969. Report ORC 69-8.

Sobel, M. (1971) Noncooperative stochastic games, Ann. Math. Statist., vol. 42, 1930-1935.

Parthasarathy, T. and Raghavan, T. E. S. (1981) An ordereld property for stochastic games when one player controls transition probabilities," J. Optim. Theory Appl., vol. 33, 375-392.

Thuijsman, F. (1989) Optimality and Equilibria in Stochastic Games. PhD thesis, University of Limburg, Maastricht, The Netherlands.

Vrieze, O. J. and Thuijsman, F. (1989) On equilibria in repeated games with absorbing states, Internat. J. Game Theory, vol. 18, 293-310.

Parthasarathy, T. (1973) Discounted, positive, and non-cooperative stochastic games, Internat. J. Game Theory, vol. 2, 25-37.

Federgruen, A. (1978) On n-person stochastic games with denumerable state space, Adv. Appl. Probab., vol. 10, 452-471.

Borkar, V., Ghosh, M. (1993) Denumerable state stochastic games with limiting payoff, J. Optimization Theory Appl., vol. 76, pp. 539-560.

Nowak, A. S. (1994) Stationary overtaking equilibria for non-zero-sum stochastic games with countable state spaces," mimeo, Institute of Mathematics, TU Wrocław.

Duffie, D., Geanakoplos, J., Mas-Colell, A., McLennan, A. (1988) Stationary Markov equilibria, Technical Report, Dept. of Economics, Harvard University.

Dutta, P. K. (1991) What do discounted optima converge to? A theory of discount rate asymptotics in economics models, J. Economic Theory, vol. 55, 64-94.

Karatzas, I., Shubik, M., Sudderth, W. D. (1992) Construction of stationary Markov equilibria in a strategic market game, Technical Report 92-05-022, Santa Fe Institute Working Paper, Santa Fe, New Mexico.

Majumdar, M., Sundaram, R. (1991) Symmetric stochastic games of resource extraction: The existence of non-randomized stationary equilibrium. In Stochastic Games and Related Topics, pp. 175-190, Dordrecht, The Netherlands: Kluwer Academic Publishers.

P. K. Dutta and R. Sundaram, (Markovian equilibrium in a class of stochastic games: Existence theorems for discounted and undiscounted models, Economic Theory, vol. 2, 1992.

Ghosh, M. K. and Bagchi, A. (1991) Stochastic games with average payo criterion, Technical Report 985, Faculty of Applied Mathematics, University of Twente, Enschede, The Netherlands.

Nowak, A. S. and Raghavan, T. E. S. (1992) Existence of stationary correlated equilibria with symmetric information for discounted stochastic games, Math. Oper. Res., vol. 17, 519-526.

Nowak, A.S. (1994) Stationary equilibria for nonzero-sum average payoff ergodic stochastic games with general state space," in Advances in Dynamic Games and Applications (T. Basar and A. Haurie, eds.), 231-246, Birkhauser.

Castaing, C., Valadier, M. (1977) Convex Analysis and Measurable Multifunctions, vol. 580 of Lecture Notes in Mathematics. New York: Springer-Verlag.

Himmelberg, C. J. (1975) Measurable relations, Fund. Math, vol. 87, 53-72.

Bertsekas, D. P., Shreve, S. E. (1978) Stochastic Optimal Control: The Discrete Time Case. New York: Academic Press.

Himmelberg, C. J., Parthasarathy, T., Raghavan, T. E. S., van Vleck, F. S. (1976) Existence of p-equilibrium and optimal stationary strategies in stochastic games," Proc. Amer. Math. Soc., vol. 60, pp. 245-251.

Whitt, W. (1980) Representation and approximation of noncooperative sequential games, SIAM J. Control Optim., vol. 18, pp. 33-48.

Nowak, A.S. (1985) Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space, J. Optim. Theory Appl., vol. 45, pp. 591-602.

Breton, M., L'Ecuyer, P. (1989) Noncooperative stochastic games under a n-stage local contraction assumption, Stochastics and Stochastic Reports, vol. 26, 227-245.

Mertens, J.-F., Parthasarathy, T. (1987) Equilibria for discounted stochastic games," Technical Report 8750, CORE Discussion Paper, Universite Catholique de Louvain.

Harris, C. (1990) The existence of subgame-perfect equilibrium in games with simultaneous moves: a case for extensive-form correlation," mimeo, Nueld College, Oxford, U.K..

Forges, F. (1986) An approach to communication equilibria, Econometrica, vol. 54, pp. 1375-1385.

Tweedie, R. L. (1983) Criteria for rates of convergence of Markov chains, with an application to queueing and storage theory," in Papers in Probability Statistics and Analysis (J. F. C. Kingman and G. E. H. Reuter, eds.), pp. 260-276, Cambridge, U. K.: Cambridge University Press.

Hernandez-Lerma, O., Hennet, J. C., Lasserre, J. B. (1991) Average cost Markov decision processes: Optimality Conditions, J. Math. Anal. Appl., vol. 158, pp. 396-406.

Hernandez-Lerma, O., Montes-de-Oca, R., Cavazos-Cadena, R. (1991) Recurrence conditions for Markov decision rocesses with Borel state space, Ann. Oper. Res., vol. 28, pp. 29-46.

Nummelin, E. (1984) General Irreducible Markov Chains and Non-Negative Operators. London: Cambridge Univ. Press.

Neveu, J. (1965) Mathematical Foundations of the Calculus of Probability. San Francisco: Holden-Day, 1965.

Kurano, M. (1986) Markov decision processes with a Borel measurable cost function - the average case, Math. Oper. Res., vol. 11, pp. 309-320.

Yamada, K. (1975) Duality theorem in Markovian decision problems," J. Math. Anal. Appl., vol. 50, pp. 579-595.

Yakovitz, S. (1982) Dynamic programming applications in water resources, Water Resources Res., vol. 18, pp. 673-696.

Georgin, J. (1978) Controle de chaines de Markov sur des espaces arbitraires, Ann. Inst. H. Poincare, vol. 14, pp. 255-277.

T. Ueno, T. (19557) Some limit theorems for temporally discrete Markov processes, J. Fac. Science Univ. Tokyo, vol. 7, pp. 449-462.

Hordijk, A. (1977) Dynamic Programming and Markov Potential Theory. Amsterdam: Math. Centrum.

Doob, J.L. (1953) Stochastic Processes. New York: Wiley.

Parthasarathy, T. (1982) Existence of equilibrium stationary strategies in discounted stochastic games," Sankhya Series A, vol. 44, pp. 114-127.

Parthasarathy, T., Sinha, S. (1989) Existence of stationary equilibrium strategies in non-zero-sum discounted stochastic games with uncountable state space and state independent transitions," Internat. J. Game Theory, vol. 18, pp. 189-194.

Nowak, A. S. (1993) Zero-sum average payo stochastic games with general state space, Games and Economic Behavior, (to appear).

Schal, M. (1993) Average optimality in dynamic programming with general state space, Math. Oper. Res., vol. 18, pp. 163-172.

Dynkin, E. (1969) Game variant of a problem on optimal stopping," Soviet Math. Dokl., vol. 10, pp. 270-274.

Kifer, Y. (1971) Optimal stopping games," T. Probab. Appl., vol. 16, pp. 185-189.

Neveu, J. (1975) Discrete-Parameter Martingales. Amsterdam: North-Holland.

Yasuda, M. (1985) On a randomized strategy in Neveu's stopping problem, Stochastic Proc. and their Appl., vol. 21, pp. 159-166.

Frid, E. (1969) The optimal stopping for a two-person Markov chain with opposing interests, Theory Probab. Appl., vol. 14, no. 4, pp. 713-716.

Elbakidze, N. (1976) Construction of the cost and optimal policies in a game problem of stopping a Markov process, Theory Probab. Appl., vol. 21, 163-168.

Ohtsubo, Y. (1987) A nonzero-sum extension of Dynkin's stopping problem, Math. Oper. Res., vol. 12, pp. 277-296.

Ferenstein, E.Z. (1993) A variation of the Dynkin's stopping game, Math. Japonica, vol. 38, no. 2, pp. 371-379.

Bensoussan, A., Friedman, A. (1974) Nonlinear variational inequalities and dierential games with stopping times," J. Funct. Anal., vol. 16, pp. 305-352.

Bensoussan, A., Friedman, A. (1977) Nonzero-sum stochastic dierential games with stopping times and free boundary problems," Trans. Amer. Math. Soc., vol. 231, pp. 275-327.

Krylov, N. (1971) Control of Markov processes and W-spaces," Math. USSR-Izv., vol. 5, pp. 233-266.

Bismut, J.-M. (1977) Sur un probleme de Dynkin," Z. Wahrsch. Ver. Gebite, vol. 39, pp. 31-53.

Stettner, L. (1982) Zero-sum Markov games with stopping and impulsive strategies, Appl. Math. Optim., vol. 9, pp. 1 { 24.

Lepeltier, J., Maingueneau, M. (1984) Le jeu de Dynkin en theorie generale sans l'hypothese de Mokobodski, Stochastics, vol. 13, pp. 25-44.

Szajowski, K. (1983) Double stop by two decision makers, Adv. Appl. Probab., vol. 25, 438-452.

Radzik, T., Szajowski, K. (1990) Sequential games with random priority, Sequential Analysis, vol. 9, no. 4, pp. 361-377, 1990.

Ano, K. (1990) Bilateral secretary problem recognizing the maximum or the second maximum of a sequence, J. Information & Optimization Sciences, vol. 11, pp. 177-188.

Enns, E., Ferenstein, E. (1987) On a multi-person time-sequential game with priorities, Sequential Analysis, vol. 6, pp. 239-256.

Ferenstein, E. (1992) Two-person non-zero-sum games with priorities, In Strategies for Sequential Search and Selection in Real Time, Proceedings of the AMS-IMS-SIAM Join Summer Research Conferences held June 21-27, 1990 (T. S. Ferguson and S. M. Samuels, eds.), vol. 125 of Contemporary Mathematics, (University of Massachusetts at Amherst), pp. 119-133.

Sakaguchi, M. (1991) Sequential games with priority under expected value maximization, Math. Japonica, vol. 36, no. 3, 545-562.

Enns, E., Ferenstein, E. (1985) The horse game," J. Oper. Res. Soc. Japan, vol. 28, 51-62.

Fushimi, M. (1981) The secretary problem in a competitive situation, J. Oper. Res. Soc. Jap., vol. 24, pp. 350-358.

Majumdar, A. (1986) Optimal stopping for a two-person sequential game in the discrete case," Pure and Appl. Math. Sci, vol. 23, pp. 67-75, 1986.

Sakaguchi, M. (1989) Multiperson multilateral secretary problem, Math. Japonica, vol. 35, pp. 459-473.

Ravindran, G., Szajowski, K. (1992) Non-zero sum game with priority as Dynkin's game," Math. Japonica, vol. 37, no. 3, 401-413.

Szajowski, K. (1992) On non-zero sum game with priority in the secretary problem, Math. Japonica, no. 3, pp. 415-426.

Gilbert, J., Mosteller, F. (1966) Recognizing the maximum of a sequence," J. Amer. Statist. Assoc., vol. 61, no. 313, pp. 35-73.

Freeman, P. (1983) \The secretary problem and its extensions: a review, Int. Statist. Rev., vol. 51, pp. 189-206, 1983.

Rose, J. (1982) Twenty years of secretary problems: a survey of developments in the theory of optimal choice," Management Studies, vol. 1, pp. 53-64.

Ferguson, T. (1989) Who solved the secretary problem?," Statistical Science, vol. 4, pp. 282-289.

Szajowski, K. (1978) Optimal stopping of a discrete Markov processes by two decision makers, 1992. submitted for publication in SIAM J. on Control and Optimization. [75] A. Shiryaev, Optimal Stopping Rules. New York, Heidelberg, Berlin: Springer-Verlag.

Eidukjavicjus, R. (1979) Optimalna ostanovka markovskoj cepi dvumia momentami ostanovki," Lit. Mat. Sbornik, vol. 19, pp. 181{183. Inf. XIX conf. math.

Luce, R., Raiaffa, H. (1957) Games and Decisions. New York: John Wiley and Sons.

Haggstrom, G. (1967) Optimal sequential procedures when more then one stop is required, Ann. Math. Statist., vol. 38, pp. 1618-1626.

Stadje, W. (1987) An optimal k-stopping problem for the Poisson process, In Proc. of the 6th Pannonian Symp. on Math. Stat. Bad Tazmannsdorf, (Austria), D.Reidel Pub. Comp., 1987. in Mathematical Statistics and Probability Theory vol. B.

Dynkin, E., Yushkevich, A. (1969) Theorems and Problems on Markov Processes. New York: Plenum.

Mucci, A. (1973) Dierential equations and optimal choice problem, Ann. Statist., vol. 1, pp. 104-113, 1973.

Szajowski, K. (1982)Optimal choice problem of a-th object," Matem. Stos., vol. 19, pp. 51-65. (in Polish).

Kuhn, H. W. (1953) Extensive games and the problem of information, In Contribution to the Theory of Games (H. Kuhn and A. Tucker, eds.), vol. 24 of Annals of Mathematics Study, Princeton University Press. Vol. I.

Rieder, U. (1979) Equilibrium plans for non-zero-sum Markov games, In Game Theory and Related Topics (D. Moeschlin and D. Palaschke, eds.), pp. 91-101, North-Holland Publishing Company.

Moulin, H. (1986) Game Theory for the Social Sciences. New York: New York University Press, 1986.

Szajowski, K. (1993) Markov stopping games with random priority, Zeitschrift fuer Operations Research, no. 3, 69-84.

Bellman, R. (1957) Dynamic Programming. Princeton Press.

Dynkin, E.B. (1969) Game variant of a problem on optimal stopping. Soviet Math. Dokl., 10:270-274.

Enns, E.G., Ferenstein, E. (1985) The horse game. J. Oper. Res. Soc. Jap., 28:51-62.

Ferenstein, E.Z. (1992) Two-person non-zero-sum games with priorities. In: Ferguson, T.S., Samuels, S.M. editors, 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, 119-133, University of Massachusetts at Amherst.

Fushimi, M. (1981) The secretary problem in a competitive situation. J. Oper. Res. Soc. Jap., 24:350-358.

Radzik, T., Szajowski, K. (1988) On some sequential game. Pure and Appl. Math. Sci, 28:51-63.

Radzik, T., Szajowski, K. (1990) Sequential games with random priority. Sequential Analysis, 9(4):361-377.

Ramsey, D., Szajowski, K. (2002) Random assignment and uncertain employment in optimal stopping of Markov processes. Game Theory and Appl., 7:147-157.

Ravindran, G., Szajowski, K. (1992) Non-zero sum game with priority as Dynkin's game. Math. Japonica, 37(3):401-413.

Sakaguchi, M. (1984) Bilateral sequential games related to the no-information secretary problem. Math. Japonica, 29:961-974.

Sakaguchi, M. (1985) Non-zero-sum games for some generalized secretary problems. Math. Japonica, 30:585-603.

Smith, M.H. (1975) A secretary problem with uncertain employment. J. Appl. Probab., 12:620-624.

Szajowski, K. (1994) Uncertain employment in competitive best choice problems. In: K.Ano, editor, International Conference on Stochastic Models and Optimal Stopping, Nagoya 19-21.12.1994}, 1-12, Nagoya, Japan, 1994. Faculty of Business Administration, Nanzan University, Nanzan University.

Szajowski, K. (1995) Optimal stopping of a discrete Markov processes by two decision makers. SIAM J.~Control and Optimization, 33(5):1392-1410.

Yasuda, M. (1983) On a stopping problem involving refusal and forced stopping. J. Appl. Probab., 20:71-81.