Stationary, completely mixed and symmetric optimal and equilibrium strategies in stochastic games
Tóm tắt
In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.
Tài liệu tham khảo
Blackwell D, Ferguson TS (1968) The big match. Ann Math Stat 39:159–168
Dasgupta P, Maskin E (1986) The existence of equilibrium in discontinuous economic games, I: Theory. Rev Econ Stud 53–1:1–26
Duersch P, Oechssler J, Schipper B (2012) Pure strategy equilibria in symmetric two-player zero-sum games. Int J Game Theory 41(3):553–564
Filar J (1981) Orderfield property of stochastic games when the player who controls the transition changes from state to state. J Optim Theory Appl 34:505–517
Filar J (1984) On stationary equilibria of a single-controller stochastic game. Math Progr 30–3:313–325
Filar J (1985) The completely mixed single-controller stochastic game. Proc Am Math Soc 95–4:585–594
Fink AM (1964) Equilibrium in a stochastic n-person game. J Sci Hiroshima Uni 28–1:89–93
Flesch J, Parthasarathy T, Thuijsman F, Uyttendaele P (2013) Evolutionary stochastic games. Dyn Games Appl 3:207–219
Gale D (1960) The theory of linear economic models. McGraw-Hill Book Company, New York
Gillette D (1957) Stochastic games with zero-stop probabilities. Contributions to the theory of games. Ann Math Stud, Princeton University Press 39:179–188
Himmelberg CJ, Parthasarathy T, Raghavan TES, Van Vleck FS (1976) Existence of p-equilibrium and optimal stationary strategies in stochastic games. Proc Am Math Soc 60:245–251
Hofbauer J, Sigmund K (2003) Evolutionary game dynamics. Bull Am Math Soc 40–4:479–519
Kakutani S (1941) A generalization of Brouwer’s fixed point theorem. Duke Math J 8–3:457–459
Kaplansky I (1945) A contribution to von Neumann’s theory of games. Ann Math 46–3:474–479
Kaplansky I (1995) A contribution to von Neumann’s theory of games II. Linear Algebra Appl 226–228:371–373
Krishnamurthy N, Parthasarathy T, Ravindran G (2009) Communication complexity of stochastic games. Proceedings of the International Conference on Game Theory for Networks (GameNets‘09), Istanbul, Turkey. IEEE Press, NJ, USA, p 411–417
Krishnamurthy N (2011) Equilibria in bimatrix games and stochastic games: theoretical and computational aspects. Ph.D. Thesis (Guided by: Parthasarathy T. Co-guided by: Samir Datta, Ravindran G, Subrahmanyam KV), Chennai Mathematical Institute, India
Maitra AP, Parthasarathy T (1970) On stochastic games. J Optim Theory Appl 5(4):289–300
Maynard Smith J, Price GR (1973) The logic of animal conflict. Nature 246:15–18
Mertens JF, Neyman A (1980) Stochastic games. Core Discussion Paper 8001, Université Catholique de Louvain-la-Neuve, Belgium
Mertens JF, Neyman A (1981) Stochastic games. Int J Game Theory 10:53–66
Nash J (1951) Non-cooperative games. Ann Math 54(2):286–295
Nowak AS (2003) On a new class of nonzero-sum discounted stochastic games having stationary Nash equilibrium points. Int J Game Theory 32:121–132
Oviedo JA (1996) Payoff matrices in completely mixed bimatrix games with zero-value. Union Math Argent 40:75–81
Parthasarathy T (1982) Existence of equilibrium stationary strategies in discounted stochastic games. Sankhyā Indian J Stat 44(A–1):114–127
Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33–3:375–392
Parthasarathy T, Sinha S (1989) Existence of stationary equilibrium strategies in nonzero-sum discounted stochastic games with uncountable state space and state-independent transitions. Int J Game Theory 18:189–194
Parthasarathy T, Tijs SJ, Vrieze OJ (1984) Stochastic games with state independent transitions and separable rewards. In: Hammer G, Pallaschke D (eds) Selected topics in operations research and mathematical economics (Karlsruhe, 1983), Lecture notes in economics and mathematical systems, vol 226. Springer, Berlin, pp 262–271
Raghavan TES (1970) Completely mixed strategies in bimatrix games. J Lond Math Soc 2:709–712
Raghavan TES, Tijs SJ, Vrieze OJ (1986) Stochastic games with additive rewards and additive transitions. J Optim Theory Appl 47:451–464
Reny P (1999) On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 67–5:1029–1056
Rieder U (1979) Equilibrium plans for nonzero-sum Markov games. In: Moeshlin O, Pallaschke D (eds) Game theory and related topics. North-Holland Publishing Company, Amsterdam, pp 91–101
Shapley L (1953) Stochastic games. Proc Natl Acad Sci 39:1095–1100
Sujatha B, Parthasarathy T, Saha A (2014) Strategies in certain types of skew symmetric games. In: Mishra RK, Shaheen, Raveendran J, Deman S (eds). Applications of game theory, Academic Foundation, p 43–50
Takahashi M (1964) Equilibrium points of stochastic noncooperative n-person games. J Sci Hiroshima Uni Ser AI Math 28:95–99
Von Neumann J (1928) Zur Theorie der Gesellschaftsspiele. Math Ann 100:295–320 (in German)