A Survey on Cooperative Stochastic Games with Finite and Infinite Duration

Elena Parilina

Authors

Elena Parilina Saint Petersburg State University

Abstract

The paper is a survey on cooperative stochastic games with finite and infinite duration which based on the author's and coauthors' publications. We assume that the non-cooperative stochastic game is initially defined. The cooperative version of the game is constructed, the cooperative solutions are found. The properties of cooperative solutions of the game which are realised in dynamics are considered. Several numerical examples of stochastic games illustrate theoretical results.

Keywords:

cooperative stochastic game, cooperative solution, imputation distribution procedure, subgame consistency

Downloads

Download data is not yet available.

References

Avrachenkov, K., Cottatellucci, L. and Maggi, L. (2013). Cooperative Markov decision processes: Time consistency, greedy players satisfaction, and cooperation maintenance. International Journal of Game Theory, 42(1), 239–262.

Aumann, R. J. and Peleg, B. (1960). Von Neumann-Morgenstern Solutions to Cooperative Games without Side Payments. Bulletin of the American Mathematical Society, 66, 173–179.

Baranova, E. M. (2006). The Condition for Keeping Cooperation in Stochastic Cooperative Games. Proceedings of the Russian-Finnish Graduate School Seminar Dynamic Games and Multicriteria Optimization, edited by V.V. Mazalov, Petrozavodsk, 54–58.

Baranova, E. M. and Petrosjan, L. A. (2006). Cooperative Stochastic Games in Stationary Strategies. Game Theory and Applications, 11, 1–7.

Bellman, R. (1957). Dynamic programming. Princeton: Princeton University Press, New Jersey.

Bure, V. M. and Parilina, E. M. (2017). "Multiple access" game with in complete information. Mathematical Game Theory and Its Applications, 9(4), 3–17 (in Russian).

Chander, P., Tulkens, H. (1997). The Core of an Economy with Multilateral Environmental Externalities. International Journal of Game Theory, 23, 379–401.

Chistyakov, S. and Petrosyan, L. (2011). Strong Strategic Support of Cooperative Solutions in Differential Games. Contributions to Game Theory and Management, IV, 105–111.

Driessen, T., Muto, S. and Nakayama, M. (1992). A cooperative Game of Information Trading: the Core, the Nucleolus and the Kernel. ZOR Methods and Models of Operations Research, 36(1), 55–72.

Filar, J. and Vrieze, K. (1997). Competitive Markov Decision Processes. N.Y.: Springer-Verlag New York.

Fink, A. M. (1964). Equilibrium in a stochastic n-person game. Journal of Science of the Hiroshima University, A-I 28, 89–93.

Gillies, D. B. (1959). Solutions to general non-zero-sum games. In: Tucker, A. W.; Luce, R. D. Contributions to the Theory of Games IV. (Annals of Mathematics Studies 40). Princeton: Princeton University Press, 47–85.

Gromova, E. V. and Petrosyan, L. A. (2015). On a approach of construction of characteristic function in cooperative dierential games. Mathematical Game Theory and Its Applications, 7(4), 1939 (in Russian).

Horner, J., Rosenberg, D., Solan, E. and Vieille, N. (2010). On a Markov game with one-sided information. Operations Research, 58(4 PART 2), 1107–1115.

Jaskiewicz, A. and Nowak, A. S. (2016). Stationary almost Markov perfect equilibria in discounted stochastic games. Mathematics of Operations Research, 41(2), 430–441.

Kohlberg, E. (1971). On the Nucleolus of a Characteristic Function Game. SIAM Journal of Applied Mathematics, 20, 62–66.

Kohlberg, E. (1972). The Nucleolus as a Solution to a Minimization Problem. SIAM Journal of Applied Mathematics, 23(1), 34–39.

Kohlberg, E. and Neyman, A. (2015). The cooperative solution of stochastic games. Harvard Business School. Working Paper, No. 15–071.

Kuhn, H.W. (1950). Extensive Games. Proceedings of National Academy of Sciences of the USA, 36, 570–576.

Kuhn, H. W. (1953). Extensive Games and the Problem of Information. Annals of Mathematics Studies, 28, 193–216.

Markovkin, M. V. (2006). D. W. K. Yeung's Condition for Linear Quadratic Differential Games. In: Dynamic Games and Their Applications, eds. L. A. Petrosyan, A. Y. Garnaev, St. Petersburg State University, St. Petersburg, 207–216.

Maschler, M. and Peleg, B. (1976). Stable sets and stable points of set-valued dynamics system with applications to game theory. SIAM Journal Control Optim., 14(2), 985–995.

WOLFRAM MATHEMATICA. https://www.wolfram.com/mathematica/ Mathworks (2017). https://se.mathworks.com

Meinhardt, H. I. Graphical Extensions of the Mathematica Package TU Games. http://library.wolfram.com/infocenter/MathSource/5709/TuGamesView3D.pdf.

Mertens, J.-F. and Neyman, A. (1981a). Minimax Theorems for Undiscounted Stochastic Games. Game Theory and Mathematical Economics, pp. 83–87.

Mertens, J. F. and Neyman, A. (1981b). Stochastic Games. International Journal of Game Theory, 10, 53–66.

Montero, M. (2005). On the nucleolus as a Power Index. Homo Oeconomicus, 22(4), 551–567.

von Neumann, J. and Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton: Princeton University Press.

Neyman, A. (2008). Existence of Optimal Strategies in Markov Games with Incomplete Information. International Journal of Game Theory, 37(4), 581–596.

Neyman, A. (2013). Stochastic Games with Short-Stage Duration. Dynamic Games and Applications, 3, 236–278.

Neyman, A. and Sorin, S. (2003). Stochastic Games and Applications. Dordrecht: Kluwer Academic Press.

Nowak, A. S. (1985). Existence of equilibrium stationary strategies in discounted non cooperative stochastic games with uncountable state space. Journal of Optimization Theory and Applications, 45(4), 591–602.

Nowak, A. S. (1999). Sensitive equilibria for ergodic stochastic games with countable state spaces. Mathematical Methods of Operations Research, 50(1), 65–76.

Nowak, A. S. and Radzik, T. (1994). A solidarity value for n-person transferable utility games. International Journal of Game Theory, 23(1), 43–48.

Parilina, E. M. (2014). Strategic consistency of single-point optimality pronciples in cooperative stochastic games. Mathematical Game Theory and Its Applications, 6(1), 56–72 (in Russian).

Parilina, E. M. (2015). Stable cooperation in stochastic games. Automation and Remote Control, 76, 1111–1122.

Parilina, E. (2016). Strategic Support of the Shapley Value in Stochastic Games. Contributions to Game Theory and Management, IX, 246–265.

Parilina, E. M. (2009). Cooperative stochastic game of data transmission in wireless network. Mathematical Game Theory and Its Applications, 1(4), 93–110 (in Russian).

Parilina, E. M. (2008). Subgame Consistency of Shapley Value in Cooperative Data Transmission Game in Wireless Network. Contributions to Game Theory and Management, SPb, 1, 381–994.

Parilina, E. and Sedakov, A. (2015). Stochastic Approach for Determining Stable Coalition Structure. International Game Theory Review, 17(4), pp. 155009-1–155009-22.

Parilina, E. M. and Petrosyan, L. A. (2017). Strongly subgame consistent core in stochastic games. Mathematical Game Theory and Its Applications, 9(2), 39–61 (in Russian).

Parilina, E. and Tampieri, A. (2018). Stability and Cooperative Solution in Stochastic Games. Theory and Decision, 84(4), 601–625.

Parilina, E. and Zaccour, G. (2015). Node-Consistent Core for Games Played over Event Trees. Automatica, 53, 304–311.

Pecherski, S. L. and Yanovskaya, E. B. (2004). Cooperative games: solutions and axioms. Saint Petersburg: Publ. house of European university in SPb (in Russian).

Petrosjan, L. A. (2006). Cooperative Stochastic Games. In: Advances in Dynamic Games. Annals of the ISDG. Application to Economics, Engineering and Environmental Management, ed. by A. Haurie, S. Muto, L. A. Petrosjan, T.E.S. Raghavan, pp. 139–146.

Petrosjan, L. A. and Baranova, E. M. (2005). Cooperative Stochastic Games in Stationary Strategies. Proceedings of the Fifth International ISDG Workshop International Society of Dynamic Games, Segovia (Spain), pp. 225–234.

Petrosjan, L. and Zaccour, G. (2003). Time-consistent Shapley value allocation of pollution cost reduction. Journal of Economic Dynamics & Control, 27, 381–398.

Petrosjan, L. A. and Zenkevich, N. A. (2015). Conditions for Sustainable Cooperation. Automation and Remote Control, 76(10), 1894–1904.

Petrosyan, L. A. (1977). Time consistency of solutions in cooperative games with many participants. Vestnik Leningradskogo universiteta. Seria 1, 19, 46–52 (in Russian).

Petrosyan, L. A. (1992). Construction of strongly time-consistent solutions in cooperative differential games. Vestnik Leningradskogo universiteta. Seria 1, 2, 33–38 (in Russian).

Petrosyan, L. A. (1993). Strongly time-consistent optimality principles in multi-criteria problems of optimal control. Tekhnicheskaya kibernetika, 1, 169–174 (in Russian).

Petrosyan, L. A. (1998). Semi-cooperative games. Vestnik Leningradskogo universiteta. Seria 1, 2, 57–63 (in Russian).

Petrosyan, L. A. and Baranova, E. M. (2003). Stochastic games with random duration. Trudi XXXIVth nauchnoi konferencii aspirantov i studentov "Procesi upravleniya iustoichivost". SPb, 456–462 (in Russian).

Petrosyan, L. A. and Baranova, E. M. (2005a). Cooperative stochastic games. Tezisi dokladov Mezhdunarodnogo seminara Teoriya upravleniya i teoriya obobjennih resheniy uravneniy Hamiltona-Yacobi. Ekaterinburg, pp. 33–35 (in Russian).

Petrosyan, L. A. and Baranova, E. M. (2005b). Cooperative stochastic games in stationary strategies. Sbornik trudov Mezhdunarodnoi conferencii "Ustoichivoct i procesi upravleniya". SPb, 1, 495–503 (in Russian).

Petrosyan, L. A., Baranova, E. M. and Shevkoplyas, E. V. (2004). Multistage cooperative games with random duration. Trudi Instituta Matematiki i Mekhaniki, 10(2), 116–130 (in Russian).

Petrosyan, L. and Chistyakov, S. (2013). Strategic support of Cooperative Solutions in 2-Person Differential Games with Dependent Motions. Contributions to Game Theory and Management, 6, 388–394.

Petrosyan, L. A. and Danilov, N. A. (1979). Time consistent solutions of non-zero sum differential games with transferable payoffs. Vestnik Leningradskogo universiteta. Seria 1, 1, 46–54 (in Russian).

Petrosjan, L. A. and Grauer, L. V. (2002). Strong Nash equilibrium in multistage games. International Game Theory Review, 4(2), 255–264.

Gromova, E. V. and Petrosyan, L. A. (2015). Strongly time-consistent cooperative solution for a differential game of pollution control. Large-scale Systems Control, 55, 140–159 (in Russian).

Petrosyan, L. A. and Kuzutin, D. V. (2000). Games in extensive form: optimality and consistency. Saint Petersburg: Izd-vo S.-Peterburgskogo universiteta (in Russian).

Petrosyan, L. A. and Shevkoplyas, E. V. (2000). Cooperative dierential games with random duration. Vestnik Sankt-peterburgskogo universiteta. Seria 1, 4, 14–18 (in Russian).

Petrosyan, L. and Sedakov, A. (2015). Strategic support of cooperation in dynamic games on networks. In: "Stability and Control Processes" in Memory of V.I. Zubov (SCP), 2015 International Conference, 256–260.

Reddy, P. V. and Zaccour, G. (2016). A friendly computable characteristic function. Mathematical Social Sciences, 82, 18–25.

Schmeidler, D. (1969). The Nucleolus of a Characteristic Function game. SIAM Journal of Applied Mathematics, 17, 1163–1170.

Schneider, R. (1993). Convex bodies: the Brunn–Minkowski theory. Cambridge Univ. Press.

Shapley, L. S. (1953a). Stochastic Games. Proceedings of National Academy of Sciences of the USA, 39, 1095–1100.

Shapley, L. S. (1953b). A Value for n-person Games. In: H.W. Kuhn, A.W. Tucker, eds. Contributions to the Theory of Games II, Princeton: Princeton Univ. Press, 307–317.

Sedakov, A. A. (2015). The strong time-consistent core. Mathematical Game Theory and Its Applications, 7(2), 69–84.

Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4, 25–55.

Shevkoplyas, E. V. (2010). Stable cooperation in dierential games with random duration. Mathematical Game Theory and Its Applications, 2(3), 162–190 (in Russian).

Solan, E. (1998). Discounted Stochastic Games. Mathematics of Operations Research, 23, 1010–1021.

Solan, E. (2009). Stochastic Games. In: Encyclopedia of Database Systems, Springer.

Solan, E. and Vieille, N. (2002). Correlated Equilibrium in Stochastic Games. Games and Economic Behavior, 38, 362–399.

Solan, E. and Vieille, N. (2015). Stochastic games. Proceedings of the National Academy of Sciences of the United States of America, 112(45), 13743–13746.

Takahashi, M. (1964). Stochastic games with innitely many strategies. Journal of Science of the Hiroshima University, A-I 28, 95–99.

http://mmiras.webs.uvigo.es/TUGlab/

Tur, A. V. (2014). The irrational behavior proof condition for linear-quadratic discrete-time dynamic games with nontransferable payoffs. Contributions to Game Theory and Management, 7, 384–392.

Vieille, N. (2000). Solvable states in n-player stochastic games. SIAM Journal on Control and Optimization, 38(6), 1794–1804.

Vilkas, E. (1990). Optimality in games and solutions. Moscow: Nauka (in Russian).

Vorobiev, N. N. (1960). Stable proles in coalitional games. Dokladi Akademii USSR, 131, 493–495 (in Russian).

Vorobiev, N. N. (1967). Coalitional games. Teoriya Veroyatnostei i Ee Primenenie, 12(2), 289–306 (in Russian).

Vorobiev, N. N. (1985). Game theory for ecomonists–cybernatists. Moscow: Nauka (in Russian).

Yeung, D. W. K. (2006). An irrational-behavior-proof condition in cooperative differential games. International Game Theory Review, 8, 739–744.

Yeung, D. W. K. and Petrosyan, L. A. (2011). Subgame Consistent Cooperative Solution of Dynamic Games with Random Horizon. Journal of Optimization Theory and Applications, 150(1), 78–97.