Abstract
We present a new tool for the study of multiplayer stochastic games, namely the modified game, which is a normal-form game that depends on the discount factor, the initial state, and for every player a partition of the set of states and a vector that assigns a real number to each element of the partition. We study properties of the modified game, like its equilibria, min–max value, and max–min value. We then show how this tool can be used to prove the existence of a uniform equilibrium in a certain class of multiplayer stochastic games.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A state in a stochastic games is absorbing if the play cannot leave it once this state was reached. A stochastic game is absorbing if all states but one are absorbing.
A team game is a multiplayer game in which the players are divided into two teams, and the players in each team share the same payoff function.
The notation \([(1-p)(s^1),p(s^2)]\) means a lottery in which the outcome is \(s^1\) with probability \(1-p\) and the outcome is \(s^2\) with probability p.
Abraham Neyman advised the author that Jean-François Mertens and himself were aware of this result.
References
Altman E (1999) Constrained Markov decision processes. Chapman and Hall/CRC, Boca Raton
Bewley T, Kohlberg E (1976) The asymptotic theory of stochastic games. Math Oper Res 1:197–208
Billingsley P (1995) Probability and measure. Wiley, Hoboken
Blackwell D, Ferguson TS (1968) The big match. Ann Math Stat 39:159–163
Buhuvsky L, Solan E, Solan ON (2018) Monovex sets, Fundamenta Mathematicae, Forthcoming
Eilenberg S, Montgomery D (1946) Fixed point theorems for multi-valued transformations. Am J Math 68:214–222
Fink AM (1964) Equilibrium in a stochastic \(n\)-person game. J Sci Hiroshima Univ Ser A-I Math 28:89–93
Flesch J, Schoenmakers G, Vrieze K (2008) Stochastic games on a product state space. Math Oper Res 33:403–420
Flesch J, Schoenmakers G, Vrieze K (2009) Stochastic games on a product state space: the periodic case. Int J Game Theory 38:263–289
Flesch J, Thuijsman F, Vrieze OJ (1997) Stochastic games with additive transitions. Eur J Oper Res 179:483–497
Flesch J, Thuijsman F, Vrieze OJ (1997) Cyclic Markov equilibria in stochastic games. Int J Game Theory 26:303–314
Flesch J, Thuijsman F, Vrieze OJ (2007) Stochastic games with additive transitions. Eur J Oper Res 179:483–497
Gillette D (1957) Stochastic games with zero stop probabilities. Contributions to the theory of games, vol 3. Princeton University Press, Princeton, pp 179–187
Hörner J, Sugaya T, Takahashi S, Vieille N (2011) Recursive methods in discounted stochastic games: an algorithm for \(\delta \rightarrow 1\) and a Folk theorem. Econometrica 79:1277–1318
Kuhn HW (1957) Extensive games and the problem of information. In: Kuhn H, Tucker AW (eds) Contributions to the Theory of Games, vol 2. Annals of Mathematical Studies 2. Princeton University Press, Princeton, pp 193–216
Mertens JF, Neyman A (1981) Stochastic games. Int J Game Theory 10:53–66
Mertens JF, Parthasarathy T (1987) Equilibria for discounted stochastic games, CORE Discussion Paper No. 8750. Appeared in Stochastic games and applications. In: Neyman A and Sorin S (eds), Kluwer Academic Publishers, pp 131–172
Mertens JF, Sorin S, Zamir S (2015) Repeated Games. Cambridge University Press, Cambridge
Neyman A (2003) Real algebraic tools in stochastic games. In: Neyman A, Sorin S (eds) Stochastic games and applications. Kluwer Academic Publishers, Dordrecht, pp 57–75
Shapley LS (1953) Stochastic games. Proc Nat Acad Sci U.S.A. 39:1095–1100
Simon RS (2007) The structure of non-zero-sum stochastic games. Adv Appl Math 38:1–26
Simon RS (2012) A topological approach to quitting games. Math Oper Res 37:180–195
Solan E (1999) Three-player absorbing games. Math Oper Res 24:669–698
Solan E (2000) Absorbing team games. Games Econ Behav 31:245–261
Solan E (2017) The modified stochastic game. arXiv:1703.04026
Solan E (2018) Acceptable strategy profiles in stochastic games. Games and Economic Behavior, Forthcoming
Solan E, Vieille N (2001) Quitting games. Math Oper Res 26:265–285
Solan E, Vieille N (2002) Correlated equilibrium in stochastic games. Games Econ Behav 38:362–399
Solan E, Vohra R (2002) Correlated equilibrium payoffs and public signalling in absorbing games. Int J Game Theory 31:91–121
Takahashi M (1964) Equilibrium points of stochastic non-cooperative \(n\)-person games. J Sci Hiroshima Univ Ser A-I Math 28:95–99
Thuijsman F (2003) The Big Match and the Paris Match. In: Neyman A, Sorin S (eds) Stochastic games and applications, vol 570. NATO Science Series (Series C: Mathematical and Physical Sciences). Springer, Dordrecht, pp 195–204
Vieille N (2000a) Two-player stochastic games I: a reduction. Isr J Math 119:55–91
Vieille N (2000b) Two-player stochastic games II: the case of recursive games. Isr J Math 119:93–126
Vrieze OJ, Thuijsman F (1989) On equilibria in repeated games with absorbing states. Int J Game Theory 18:293–310
Author information
Authors and Affiliations
Corresponding author
Additional information
The author thanks Eitan Altman for helping in identifying relevant references, Omri Solan for helpful discussions, Sylvain Sorin for useful comments, and the Associate Editor and two anonymous referees for their careful reading of the paper and for their comments, and acknowledges the support of the Israel Science Foundation, Grant #323/13.
Rights and permissions
About this article
Cite this article
Solan, E. The modified stochastic game. Int J Game Theory 47, 1287–1327 (2018). https://doi.org/10.1007/s00182-018-0619-9
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-018-0619-9