×

Stochastic games on a product state space: the periodic case. (English) Zbl 1211.91056

Summary: We examine so-called product-games. These are \(n\)-player stochastic games played on a product state space \(S^1 \times \dots \times S^n\) , in which player \(i\) controls the transitions on \(S^i\) . For the general \(n\)-player case, we establish the existence of 0-equilibria. In addition, for the case of two-player zero-sum games of this type, we show that both players have stationary 0-optimal strategies. In the analysis of product-games, interestingly, a central role is played by the periodic features of the transition structure. In [J. Flesch, G. Schoenmakers and K. Vrieze, Math. Oper. Res. 33, No. 2, 403–420 (2008; Zbl 1231.91020)], the authors showed the existence of 0-equilibria under the assumption that, for every player \(i\), the transition structure on \(S^i\) is aperiodic. In this article, we examine product-games with periodic transition structures. Even though a large part of the approach in [Flesch et al., loc.cit.] remains applicable, we encounter a number of tricky problems that we have to address. We provide illustrative examples to clarify the essence of the difference between the aperiodic and periodic cases.

MSC:

91A15 Stochastic games, stochastic differential games
91A06 \(n\)-person games, \(n>2\)
91A10 Noncooperative games

Citations:

Zbl 1231.91020
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altman E, Avrachenkov K, Marquez R, Miller G (2005) Zero-sum constrained stochastic games with independent state processes. Math Methods Oper Res 62: 375–386 · Zbl 1108.91011 · doi:10.1007/s00186-005-0034-4
[2] Altman E, Avrachenkov K, Bonneau N, Debbah M, El-Azouzi R, Sadoc Menasche D (2007a) Constrained cost-coupled stochastic games with independent state processes (preprint) · Zbl 1151.91350
[3] Altman E, Avrachenkov K, Garnaev A (2007b) A jamming game in wireless networks with transmission cost. Lect Notes Comp Sci 4465: 1–12 · Zbl 1181.68019 · doi:10.1007/978-3-540-72709-5_1
[4] Becker R, Zilberstein S, Lesser V, Goldman CV (2003) Transition-independent decentralized Markov decision processes. In: Proceedings of the second international joint conference on autonomous agents and multi agent systems, ACM Press, Melbourne, pp 41–48
[5] Blackwell D, Ferguson TS (1968) The big match. Ann Math Stat 39: 159–163 · Zbl 0164.50305 · doi:10.1214/aoms/1177698513
[6] Dutta PK (1995) A Folk theorem for stochastic games. J Econ Theory 66: 1–32 · Zbl 0835.90139 · doi:10.1006/jeth.1995.1030
[7] Filar JA, Vrieze OJ (1996) Competitive Markov decision processes–theory, algorithms, and applications. Springer, New York
[8] Fink AM (1964) Equilibrium in a stochastic n-person game. J Sci Hiroshima Univ Ser A–I 28: 89–93 · Zbl 0126.36506
[9] Flesch J, Thuijsman F, Vrieze OJ (1997) Cyclic Markov equilibria in a cubic game. Int J Game Theory 26: 303–314 · Zbl 0879.90200 · doi:10.1007/BF01263273
[10] Flesch J, Thuijsman F, Vrieze OJ (2007) Stochastic games with additive transitions. Eur J Oper Res 179: 483–497 · Zbl 1116.91011 · doi:10.1016/j.ejor.2006.03.031
[11] Flesch J, Schoenmakers G, Vrieze OJ (2008a) Stochastic games on a product state space. Math Oper Res 33: 403–420 · Zbl 1231.91020 · doi:10.1287/moor.1070.0304
[12] Flesch J, Schoenmakers G, Vrieze OJ (2008b) Stochastic games on a product state space: the periodic case. Research memorandum RM/08/016. University of Maastricht, The Netherlands · Zbl 1231.91020
[13] Gillette D (1957) Stochastic games with zero stop probabilities. In: Dresher M, Tucker AW, Wolfe P (eds) Contributions to the theory of games III. Annals of Mathematical Studies 39. Princeton University Press, Princeton, pp 179–187 · Zbl 0078.33001
[14] Mertens JF, Neyman A (1981) Stochastic games. Int J Game Theory 10: 53–66 · Zbl 0486.90096 · doi:10.1007/BF01769259
[15] Neyman A (2003) Existence of the minmax. In: Neyman A, Sorin S (eds) Stochastic games and applications, NATO Science series vol, 570. Kluwer, Dordrecht, pp 173–193 · Zbl 1153.91332
[16] Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33: 375–392 · Zbl 0424.90093 · doi:10.1007/BF00935250
[17] Ross KW, Varadarajan R (1991) Multichain Markov decision processes with a sample path constraint: a decomposition approach. Math Oper Res 16: 195–207 · Zbl 0734.90111 · doi:10.1287/moor.16.1.195
[18] Simon R (2003) Value and perfection in stochastic games. Working paper, Goettingen University, Germany. Israel J Math (to appear)
[19] Solan E (1999) Three-Player absorbing games. Math Oper Res 24: 669–698 · Zbl 1064.91500 · doi:10.1287/moor.24.3.669
[20] Solan E (2003) Perturbations of Markov chains with applications to stochastic games. In: Neyman A, Sorin S (eds) Stochastic games and applications, NATO science series, vol 570. Kluwer, Dordrecht, pp 265–280 · Zbl 1153.91336
[21] Solan E, Vieille N (2002) Correlated equilibrium in stochastic games. Games Econ Behav 38: 362–399 · Zbl 1022.91007 · doi:10.1006/game.2001.0887
[22] Solan E, Vohra R (2002) Correlated equilibrium and public signalling in absorbing games. Int J Game Theory 31: 91–121 · Zbl 1083.91039 · doi:10.1007/s001820200109
[23] Sorin S (1986) Asymptotic properties of a non-zerosum game. Int J Game Theory 15: 101–107 · Zbl 0633.90104 · doi:10.1007/BF01770978
[24] Takahashi M (1964) Equilibrium points of stochastic noncooperative n-person games. J Sci Hiroshima Univ Ser A–I 28: 95–99 · Zbl 0133.13103
[25] Thuijsman F, Vrieze OJ (1991) Easy initial states in stochastic games. In: Raghavan TES, Ferguson TS, Vrieze OJ, Parthasarathy T (eds) Stochastic games and related topics. Kluwer, Dordrecht, pp 85–100 · Zbl 0747.90118
[26] Vieille N (2000a) Equilibrium in 2-person stochastic games I: a reduction. Israel J Math 119: 55–91 · Zbl 0974.91005 · doi:10.1007/BF02810663
[27] Vieille N (2000b) Equilibrium in 2-person stochastic games II: the case of recursive games. Israel J Math 119: 93–126 · Zbl 0978.91007 · doi:10.1007/BF02810664
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.