A survey on cooperative stochastic games with finite and infinite duration

Elena Parilina

Contributions to game theory and management, Tome 11 (2018), pp. 129-195.

Résumé

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.

Détail

Keywords: cooperative stochastic game, cooperative solution, imputation distribution procedure, subgame consistency.

Bibliographie

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

[2] Aumann R. J., Peleg B., “Von Neumann-Morgenstern Solutions to Cooperative Games without Side Payments”, Bulletin of the American Mathematical Society, 66 (1960), 173–179 | DOI | MR | Zbl

[3] Baranova E. M., “The Condition for Keeping Cooperation in Stochastic Cooperative Games”, Proceedings of the Russian-Finnish Graduate School Seminar “Dynamic Games and Multicriteria Optimization” (Petrozavodsk, 2006), ed. V.V. Mazalov, 54–58 | MR

[4] Baranova E. M., Petrosjan L. A., “Cooperative Stochastic Games in Stationary Strategies”, Game Theory and Applications, 11 (2006), 1–7 | MR

[5] Bellman R., Dynamic programming, Princeton University Press, Princeton, New Jersey, 1957 | MR | Zbl

[6] Bure V. M., Parilina E. M., ““Multiple access” game with incomplete information”, Mathematical Game Theory and Its Applications, 9(4 (2017), 3–17 (in Russian) | MR

[7] Chander P., Tulkens H., “The Core of an Economy with Multilateral Environmental Externalities”, International Journal of Game Theory, 23 (1997), 379–401 | DOI | MR

[8] Chistyakov S., Petrosyan L., “Strong Strategic Support of Cooperative Solutions in Differential Games”, Contributions to Game Theory and Management IV, 2011, 105–111 | MR | Zbl

[9] Driessen T., MutoS., Nakayama M., “A cooperative Game of Information Trading: the Core, the Nucleolus and the Kernel”, ZOR Methods and Models of Operations Research, 36:1 (1992), 55–72 | DOI | MR | Zbl

[10] Filar J., Vrieze K., Competitive Markov Decision Processes, Springer-Verlag, New York, 1997 | MR | Zbl

[11] Fink A. M., “Equilibrium in a stochastic $n$-person game”, Journal of Science of the Hiroshima University, A-I 28 (1964), 89–93 | MR | Zbl

[12] Gillies D. B., “Solutions to general non-zero-sum games”, Contributions to the Theory of Games IV, Annals of Mathematics Studies, 40, eds. Tucker A. W., Luce R. D., Princeton University Press, Princeton, 1959, 47–85 | MR

[13] Gromova E. V., Petrosyan L. A., “On a approach of construction of characteristic function in cooperative differential games”, Mathematical Game Theory and Its Applications, 7:4 (2015), 19–39 (in Russian) | Zbl

[14] Kohlberg E., “On the Nucleolus of a Characteristic Function Game”, SIAM Journal of Applied Mathematics, 20 (1971), 62–66 | DOI | MR | Zbl

[15] Kohlberg E., “The Nucleolus as a Solution to a Minimization Problem”, SIAM Journal of Applied Mathematics, 23:1 (1972), 34–39 | DOI | MR | Zbl

[16] Kohlberg E., Neyman A., The cooperative solution of stochastic games, Working Paper No 15-071, Harvard Business School, 2015

[17] Kuhn H. W., “Extensive Games”, Proceedings of National Academy of Sciences of the USA, 36 (1950), 570–576 | DOI | MR | Zbl

[18] Kuhn H. W., “Extensive Games and the Problem of Information”, Annals of Mathematics Studies, 28 (1953), 193–216 | MR | Zbl

[19] Markovkin M. V., “D. W. K. Yeung's Condition for Linear Quadratic Differential Games”, Dynamic Games and Their Applications, eds. L.A. Petrosyan, A.Y. Garnaev, St. Petersburg State University, St. Petersburg, 2006, 207–216

[20] Maschler M., Peleg B., “Stable sets and stable points of set-valued dynamics system with applications to game theory”, SIAM Journal Control Optim., 14:2 (1976), 985–995 | DOI | MR | Zbl

[21] WOLFRAM MATHEMATICA, https://www.wolfram.com/mathematica/

[22] Mathworks, , 2017 https://se.mathworks.com

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

[24] Mertens J.-F., Neyman A., “Minimax Theorems for Undiscounted Stochastic Games”, Game Theory and Mathematical Economics, 1981, 83–87 | MR | Zbl

[25] Mertens J. F., Neyman A., “Stochastic Games”, International Journal of Game Theory, 10 (1981), 53–66 | DOI | MR | Zbl

[26] Montero M., “On the nucleolus as a Power Index”, Homo Oeconomicus, 22:4 (2005), 551–567

[27] von Neumann J., Morgenstern O., Theory of Games and Economic Behavior, Princeton University Press, Princeton, 1944 | MR | Zbl

[28] Neyman A., “Existence of Optimal Strategies in Markov Games with Incomplete Information”, International Journal of Game Theory, 37:4 (2008), 581–596 | DOI | MR | Zbl

[29] Neyman A., “Stochastic Games with Short-Stage Duration”, Dynamic Games and Applications, 3 (2013), 236–278 | DOI | MR | Zbl

[30] Neyman A., Sorin S., Stochastic Games and Applications, Kluwer Academic Press, Dordrecht, 2003 | MR | Zbl

[31] Nowak A. S., “Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space”, Journal of Optimization Theory and Applications, 45:4 (1985), 591–602 | DOI | MR | Zbl

[32] Nowak A. S., “Sensitive equilibria for ergodic stochastic games with countable state spaces”, Mathematical Methods of Operations Research, 50:1 (1999), 65–76 | MR | Zbl

[33] Nowak A. S., Radzik T., “A solidarity value for n-person transferable utility games”, International Journal of Game Theory, 23:1 (1994), 43–48 | DOI | MR | Zbl

[34] Parilina E. M., “Strategic consistency of single-point optimality pronciples in cooperative stochastic games”, Mathematical Game Theory and Its Applications, 6:1 (2014), 56–72 (in Russian) | MR | Zbl

[35] Parilina E. M., “Stable cooperation in stochastic games”, Automation and Remote Control, 76 (2015), 1111–1122 | DOI | MR

[36] Parilina E., “Strategic Support of the Shapley Value in Stochastic Games”, Contributions to Game Theory and Management, IX (2016), 246–265 | MR

[37] Parilina E. M., “Cooperative stochastic game of data transmission in wireless network”, Mathematical Game Theory and Its Applications, 1:4 (2009), 93–110 (in Russian) | Zbl

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

[39] Parilina E., Sedakov A., “Stochastic Approach for Determining Stable Coalition Structure”, International Game Theory Review, 17:4 (2015), 155009, 22 pp. | DOI | MR

[40] Parilina E. M., Petrosyan L. A., “Strongly subgame consistent core in stochastic games”, Mathematical Game Theory and Its Applications, 9:2 (2017), 39–61 (in Russian) | MR | Zbl

[41] Parilina E., Tampieri A., “Stability and Cooperative Solution in Stochastic Games”, Theory and Decision, 84:4 (2018), 601–625 | DOI | MR | Zbl

[42] Parilina E., Zaccour G., “Node-Consistent Core for Games Played over Event Trees”, Automatica, 53 (2015), 304–311 | DOI | MR | Zbl

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

[44] Petrosjan L. A., “Cooperative Stochastic Games”, Advances in Dynamic Games. Annals of the ISDG. Application to Economics, Engineering and Environmental Management, eds. A. Haurie, S. Muto, L. A. Petrosjan, T.E.S. Raghavan, 2006, 139–146 | MR

[45] Petrosjan L. A., Baranova E. M., “Cooperative Stochastic Games in Stationary Strategies”, Proceedings of the Fifth International ISDG Workshop International Society of Dynamic Games (Segovia, Spain, 2005), 225–234 | MR

[46] Petrosjan L., Zaccour G., “Time-consistent Shapley value allocation of pollution cost reduction”, Journal of Economic Dynamics Control, 27 (2003), 381–398 | DOI | MR | Zbl

[47] Petrosjan L. A., Zenkevich N. A., “Conditions for Sustainable Cooperation”, Automation and Remote Control, 76:10 (2015), 1894–1904 | DOI | MR

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

[49] Petrosyan L. A., “Construction of strongly time-consistent solutions in cooperative differential games”, Vestnik Leningradskogo universiteta. Seria 1, 2 (1992), 33–38 (in Russian) | MR | Zbl

[50] Petrosyan L. A., “Strongly time-consistent optimality principles in multi-criteria problems of optimal control”, Tekhnicheskaya kibernetika, 1 (1993), 169–174 (in Russian) | MR | Zbl

[51] Petrosyan L. A., “Semi-cooperative games”, Vestnik Leningradskogo universiteta. Seria 1, 2 (1998), 57–63 (in Russian) | Zbl

[52] Petrosyan L. A., Baranova E. M., “Stochastic games with random duration”, Trudi XXXIVth nauchnoi konferencii aspirantov i studentov “Procesi upravleniya i ustoichivost”, SPb, 2003, 456–462 (in Russian)

[53] Petrosyan L. A., Baranova E. M., “Cooperative stochastic games”, Tezisi dokladov Mezhdunarodnogo seminara “Teoriya upravleniya i teoriya obobjennih resheniy uravneniy Hamiltona-Yacobi” (Ekaterinburg, 2005), 33–35 (in Russian) | Zbl

[54] Petrosyan L. A., Baranova E. M., “Cooperative stochastic games in stationary strategies”, Sbornik trudov Mezhdunarodnoi conferencii “Ustoichivoct i procesi upravleniya”, v. 1, SPb, 2005, 495–503 (in Russian)

[55] Petrosyan L. A., Baranova E. M., Shevkoplyas E. V., “Multistage cooperative games with random duration”, Trudi Instituta Matematiki i Mekhaniki, 10:2 (2004), 116–130 (in Russian) | MR | Zbl

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

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

[58] Petrosjan L. A., Grauer L. V., “Strong Nash equilibrium in multistage games”, International Game Theory Review, 4:2 (2002), 255–264 | DOI | MR | Zbl

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

[60] Petrosyan L. A., Kuzutin D. V., Games in extensive form: otimality and consistency, Izd-vo S.-Peterburgskogo universiteta, Saint Petersburg, 2000 (in Russian) | MR

[61] Petrosyan L. A., Shevkoplyas E. V., “Cooperative differential games with random duration”, Vestnik Sankt-peterburgskogo universiteta. Seria 1, 4 (2000), 14–18 (in Russian) | MR | Zbl

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

[63] Reddy P. V., Zaccour G., “A friendly computable characteristic function”, Mathematical Social Sciences, 82 (2016), 18–25 | DOI | MR | Zbl

[64] Schmeidler D., “The Nucleolus of a Characteristic Function game”, SIAM Journal of Applied Mathematics, 17 (1969), 1163–1170 | DOI | MR | Zbl

[65] Schneider R., Convex bodies: the Brunn–Minkowski theory, Cambridge Univ. Press, 1993 | MR | Zbl

[66] Shapley L. S., “Stochastic Games”, Proceedings of National Academy of Sciences of the USA, 39 (1953), 1095–1100 | DOI | MR | Zbl

[67] Shapley L. S., “A Value for n-person Games”, Contributions to the Theory of Games II, eds. H.W. Kuhn, A.W. Tucker, Princeton Univ. Press, Princeton, 1953, 307–317 | MR

[68] Sedakov A. A., “The strong time-consistent core”, Mathematical Game Theory and Its Applications, 7:2 (2015), 69–84 | Zbl

[69] Selten R., “Reexamination of the perfectness concept for equilibrium points in extensive games”, International Journal of Game Theory, 4 (1975), 25–55 | DOI | MR | Zbl

[70] Shevkoplyas E. V., “Stable cooperation in differential games with random duration”, Mathematical Game Theory and Its Applications, 2:3 (2010), 162–190 (in Russian)

[71] Solan E., “Discounted Stochastic Games”, Mathematics of Operations Research, 23 (1998), 1010–1021 | DOI | MR | Zbl

[72] Solan E., “Stochastic Games”, Encyclopedia of Database Systems, Springer, 2009

[73] Solan E., Vieille N., “Correlated Equilibrium in Stochastic Games”, Games and Economic Behavior, 38 (2002), 362–399 | DOI | MR | Zbl

[74] Solan E., Vieille N., “Stochastic games”, Proceedings of the National Academy of Sciences of the United States of America, 112:45 (2015), 13743–13746 | DOI | MR | Zbl

[75] Takahashi M., “Stochastic games with infinitely many strategies”, Journal of Science of the Hiroshima University, A-I 28 (1964), 95–99 | MR | Zbl

[76] http://mmiras.webs.uvigo.es/TUGlab/

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

[78] Vieille N., “Solvable states in n-player stochastic games”, SIAM Journal on Control and Optimization, 38:6 (2000), 1794–1804 | DOI | MR | Zbl

[79] Vilkas E., Optimality in games and solutions, Nauka, M., 1990 (in Russian) | MR | Zbl

[80] Vorobiev N. N., “Stable profiles in coalitional games”, Dokladi Akademii USSR, 131 (1960), 493–495 (in Russian) | MR

[81] Vorobiev N. N., “Coalitional games”, Teoriya Veroyatnostei i Ee Primenenie, 12:2 (1967), 289–306 (in Russian) | MR

[82] Vorobiev N. N., Game theory for ecomonists–cybernatists, Nauka, M., 1985 (in Russian) | MR

[83] Yeung D. W. K., “An irrational-behavior-proof condition in cooperative differential games”, International Game Theory Review, 8 (2006), 739–744 | DOI | MR | Zbl

[84] Yeung D. W. K., Petrosyan L. A., “Subgame Consistent Cooperative Solution of Dynamic Games with Random Horizon”, Journal of Optimization Theory and Applications, 150:1 (2011), 78–97 | DOI | MR | Zbl