Nowak, Andrzej S. and Szajowski, Krzysztof (1998): Nonzerosum Stochastic Games. Published in: Annals of the International Society of Dynamic Games , Vol. 4, (1999): pp. 297342.

PDF
MPRA_paper_19995.pdf Download (334Kb)  Preview 
Abstract
This paper treats of stochastic games. We focus on nonzerosum 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 nonzerosum stochastic games and stopping games which is very far from being complete.
Item Type:  MPRA Paper 

Original Title:  Nonzerosum Stochastic Games 
English Title:  Nonzerosum Stochastic Games 
Language:  English 
Keywords:  average payoff stochastic games, correlated stationary equilibria, nonzerosum 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 
Item ID:  19995 
Depositing User:  Krzysztof Szajowski 
Date Deposited:  15. Jan 2010 15:27 
Last Modified:  12. Feb 2013 10:27 
References:  Rogers, P. D. (1969) NonzeroSum Stochastic Games. PhD thesis, University of California, Berkeley, 1969. Report ORC 698. Sobel, M. (1971) Noncooperative stochastic games, Ann. Math. Statist., vol. 42, 19301935. 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, 375392. 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, 293310. Parthasarathy, T. (1973) Discounted, positive, and noncooperative stochastic games, Internat. J. Game Theory, vol. 2, 2537. Federgruen, A. (1978) On nperson stochastic games with denumerable state space, Adv. Appl. Probab., vol. 10, 452471. Borkar, V., Ghosh, M. (1993) Denumerable state stochastic games with limiting payoff, J. Optimization Theory Appl., vol. 76, pp. 539560. Nowak, A. S. (1994) Stationary overtaking equilibria for nonzerosum stochastic games with countable state spaces," mimeo, Institute of Mathematics, TU Wrocław. Duffie, D., Geanakoplos, J., MasColell, 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, 6494. Karatzas, I., Shubik, M., Sudderth, W. D. (1992) Construction of stationary Markov equilibria in a strategic market game, Technical Report 9205022, Santa Fe Institute Working Paper, Santa Fe, New Mexico. Majumdar, M., Sundaram, R. (1991) Symmetric stochastic games of resource extraction: The existence of nonrandomized stationary equilibrium. In Stochastic Games and Related Topics, pp. 175190, 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, 519526. Nowak, A.S. (1994) Stationary equilibria for nonzerosum average payoff ergodic stochastic games with general state space," in Advances in Dynamic Games and Applications (T. Basar and A. Haurie, eds.), 231246, Birkhauser. Castaing, C., Valadier, M. (1977) Convex Analysis and Measurable Multifunctions, vol. 580 of Lecture Notes in Mathematics. New York: SpringerVerlag. Himmelberg, C. J. (1975) Measurable relations, Fund. Math, vol. 87, 5372. 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 pequilibrium and optimal stationary strategies in stochastic games," Proc. Amer. Math. Soc., vol. 60, pp. 245251. Whitt, W. (1980) Representation and approximation of noncooperative sequential games, SIAM J. Control Optim., vol. 18, pp. 3348. 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. 591602. Breton, M., L'Ecuyer, P. (1989) Noncooperative stochastic games under a nstage local contraction assumption, Stochastics and Stochastic Reports, vol. 26, 227245. 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 subgameperfect equilibrium in games with simultaneous moves: a case for extensiveform correlation," mimeo, Nueld College, Oxford, U.K.. Forges, F. (1986) An approach to communication equilibria, Econometrica, vol. 54, pp. 13751385. 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. 260276, Cambridge, U. K.: Cambridge University Press. HernandezLerma, O., Hennet, J. C., Lasserre, J. B. (1991) Average cost Markov decision processes: Optimality Conditions, J. Math. Anal. Appl., vol. 158, pp. 396406. HernandezLerma, O., MontesdeOca, R., CavazosCadena, R. (1991) Recurrence conditions for Markov decision rocesses with Borel state space, Ann. Oper. Res., vol. 28, pp. 2946. Nummelin, E. (1984) General Irreducible Markov Chains and NonNegative Operators. London: Cambridge Univ. Press. Neveu, J. (1965) Mathematical Foundations of the Calculus of Probability. San Francisco: HoldenDay, 1965. Kurano, M. (1986) Markov decision processes with a Borel measurable cost function  the average case, Math. Oper. Res., vol. 11, pp. 309320. Yamada, K. (1975) Duality theorem in Markovian decision problems," J. Math. Anal. Appl., vol. 50, pp. 579595. Yakovitz, S. (1982) Dynamic programming applications in water resources, Water Resources Res., vol. 18, pp. 673696. Georgin, J. (1978) Controle de chaines de Markov sur des espaces arbitraires, Ann. Inst. H. Poincare, vol. 14, pp. 255277. T. Ueno, T. (19557) Some limit theorems for temporally discrete Markov processes, J. Fac. Science Univ. Tokyo, vol. 7, pp. 449462. 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. 114127. Parthasarathy, T., Sinha, S. (1989) Existence of stationary equilibrium strategies in nonzerosum discounted stochastic games with uncountable state space and state independent transitions," Internat. J. Game Theory, vol. 18, pp. 189194. Nowak, A. S. (1993) Zerosum 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. 163172. Dynkin, E. (1969) Game variant of a problem on optimal stopping," Soviet Math. Dokl., vol. 10, pp. 270274. Kifer, Y. (1971) Optimal stopping games," T. Probab. Appl., vol. 16, pp. 185189. Neveu, J. (1975) DiscreteParameter Martingales. Amsterdam: NorthHolland. Yasuda, M. (1985) On a randomized strategy in Neveu's stopping problem, Stochastic Proc. and their Appl., vol. 21, pp. 159166. Frid, E. (1969) The optimal stopping for a twoperson Markov chain with opposing interests, Theory Probab. Appl., vol. 14, no. 4, pp. 713716. Elbakidze, N. (1976) Construction of the cost and optimal policies in a game problem of stopping a Markov process, Theory Probab. Appl., vol. 21, 163168. Ohtsubo, Y. (1987) A nonzerosum extension of Dynkin's stopping problem, Math. Oper. Res., vol. 12, pp. 277296. Ferenstein, E.Z. (1993) A variation of the Dynkin's stopping game, Math. Japonica, vol. 38, no. 2, pp. 371379. Bensoussan, A., Friedman, A. (1974) Nonlinear variational inequalities and dierential games with stopping times," J. Funct. Anal., vol. 16, pp. 305352. Bensoussan, A., Friedman, A. (1977) Nonzerosum stochastic dierential games with stopping times and free boundary problems," Trans. Amer. Math. Soc., vol. 231, pp. 275327. Krylov, N. (1971) Control of Markov processes and Wspaces," Math. USSRIzv., vol. 5, pp. 233266. Bismut, J.M. (1977) Sur un probleme de Dynkin," Z. Wahrsch. Ver. Gebite, vol. 39, pp. 3153. Stettner, L. (1982) Zerosum 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. 2544. Szajowski, K. (1983) Double stop by two decision makers, Adv. Appl. Probab., vol. 25, 438452. Radzik, T., Szajowski, K. (1990) Sequential games with random priority, Sequential Analysis, vol. 9, no. 4, pp. 361377, 1990. Ano, K. (1990) Bilateral secretary problem recognizing the maximum or the second maximum of a sequence, J. Information & Optimization Sciences, vol. 11, pp. 177188. Enns, E., Ferenstein, E. (1987) On a multiperson timesequential game with priorities, Sequential Analysis, vol. 6, pp. 239256. Ferenstein, E. (1992) Twoperson nonzerosum games with priorities, In Strategies for Sequential Search and Selection in Real Time, Proceedings of the AMSIMSSIAM Join Summer Research Conferences held June 2127, 1990 (T. S. Ferguson and S. M. Samuels, eds.), vol. 125 of Contemporary Mathematics, (University of Massachusetts at Amherst), pp. 119133. Sakaguchi, M. (1991) Sequential games with priority under expected value maximization, Math. Japonica, vol. 36, no. 3, 545562. Enns, E., Ferenstein, E. (1985) The horse game," J. Oper. Res. Soc. Japan, vol. 28, 5162. Fushimi, M. (1981) The secretary problem in a competitive situation, J. Oper. Res. Soc. Jap., vol. 24, pp. 350358. Majumdar, A. (1986) Optimal stopping for a twoperson sequential game in the discrete case," Pure and Appl. Math. Sci, vol. 23, pp. 6775, 1986. Sakaguchi, M. (1989) Multiperson multilateral secretary problem, Math. Japonica, vol. 35, pp. 459473. Ravindran, G., Szajowski, K. (1992) Nonzero sum game with priority as Dynkin's game," Math. Japonica, vol. 37, no. 3, 401413. Szajowski, K. (1992) On nonzero sum game with priority in the secretary problem, Math. Japonica, no. 3, pp. 415426. Gilbert, J., Mosteller, F. (1966) Recognizing the maximum of a sequence," J. Amer. Statist. Assoc., vol. 61, no. 313, pp. 3573. Freeman, P. (1983) \The secretary problem and its extensions: a review, Int. Statist. Rev., vol. 51, pp. 189206, 1983. Rose, J. (1982) Twenty years of secretary problems: a survey of developments in the theory of optimal choice," Management Studies, vol. 1, pp. 5364. Ferguson, T. (1989) Who solved the secretary problem?," Statistical Science, vol. 4, pp. 282289. 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: SpringerVerlag. 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. 16181626. Stadje, W. (1987) An optimal kstopping 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. 104113, 1973. Szajowski, K. (1982)Optimal choice problem of ath object," Matem. Stos., vol. 19, pp. 5165. (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 nonzerosum Markov games, In Game Theory and Related Topics (D. Moeschlin and D. Palaschke, eds.), pp. 91101, NorthHolland 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, 6984. Bellman, R. (1957) Dynamic Programming. Princeton Press. Dynkin, E.B. (1969) Game variant of a problem on optimal stopping. Soviet Math. Dokl., 10:270274. Enns, E.G., Ferenstein, E. (1985) The horse game. J. Oper. Res. Soc. Jap., 28:5162. Ferenstein, E.Z. (1992) Twoperson nonzerosum games with priorities. In: Ferguson, T.S., Samuels, S.M. editors, Strategies for Sequential Search and Selection in Real Time, Proceedings of the AMSIMSSIAM Join Summer Research Conferences held June 2127, 1990, Contemporary Mathematics, vol. 125, 119133, University of Massachusetts at Amherst. Fushimi, M. (1981) The secretary problem in a competitive situation. J. Oper. Res. Soc. Jap., 24:350358. Radzik, T., Szajowski, K. (1988) On some sequential game. Pure and Appl. Math. Sci, 28:5163. Radzik, T., Szajowski, K. (1990) Sequential games with random priority. Sequential Analysis, 9(4):361377. Ramsey, D., Szajowski, K. (2002) Random assignment and uncertain employment in optimal stopping of Markov processes. Game Theory and Appl., 7:147157. Ravindran, G., Szajowski, K. (1992) Nonzero sum game with priority as Dynkin's game. Math. Japonica, 37(3):401413. Sakaguchi, M. (1984) Bilateral sequential games related to the noinformation secretary problem. Math. Japonica, 29:961974. Sakaguchi, M. (1985) Nonzerosum games for some generalized secretary problems. Math. Japonica, 30:585603. Smith, M.H. (1975) A secretary problem with uncertain employment. J. Appl. Probab., 12:620624. Szajowski, K. (1994) Uncertain employment in competitive best choice problems. In: K.Ano, editor, International Conference on Stochastic Models and Optimal Stopping, Nagoya 1921.12.1994}, 112, 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):13921410. Yasuda, M. (1983) On a stopping problem involving refusal and forced stopping. J. Appl. Probab., 20:7181. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/19995 