A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games

Ekaterina Gromova; Ekaterina Marova; Dmitry Gromov

doi:10.3934/jdg.2020007

Previous Article
Discrete processes and their continuous limits
JDG Home
This Issue
Next Article
On the uniqueness of Nash equilibrium in strategic-form games

April 2020, 7(2): 105-122. doi: 10.3934/jdg.2020007

A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games

Ekaterina Gromova ^, , Ekaterina Marova and Dmitry Gromov

Faculty of Applied Mathematics and Control Processes, Saint Petersburg State University, St. Petersburg, Russia

^* Corresponding author: Ekaterina Gromova

Received September 2019 Published April 2020

Fund Project: The reported study was funded by RFBR under the grant 18-00-00727 (18-00-00725)

In this paper, we present a systematic overview of different endogenous optimization-based characteristic functions and discuss their properties. Furthermore, we define and analyze in detail a new, $ \eta $-characteristic function. This characteristic function has a substantial advantage over other characteristic functions in that it can be obtained with a minimal computational effort and has a reasonable economic interpretation. In particular, the new characteristic function can be seen as a reduced version of the classical Neumann-Morgenstern characteristic function, where the players both from the coalition and from the complementary coalition use their previously computed strategies instead of solving respective optimization problems. Our finding are illustrated by a pollution control game with $ n $ non-identical players. For the considered game, we compute all characteristic functions and compare their properties. Quite surprisingly, it turns out that both the characteristic functions and the resulting cooperative solutions satisfy some symmetry relations.

Keywords: Cooperative games, differential games, characteristic function, pollution control.

Mathematics Subject Classification: Primary: 91A12, 91A23, 49N70; Secondary: 49N90, 91A25.

Citation: Ekaterina Gromova, Ekaterina Marova, Dmitry Gromov. A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games. Journal of Dynamics & Games, 2020, 7 (2) : 105-122. doi: 10.3934/jdg.2020007

References:

[1]	T. Başar, On the uniqueness of the Nash solution in linear-quadratic differential games, Internat. J. Game Theory, 5 (1976), 65-90. doi: 10.1007/BF01753310. Google Scholar
[2]	T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Google Scholar
[3]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser Boston, Inc., Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1. Google Scholar
[4]	M. Breton, G. Zaccour and M. Zahaf, A differential game of joint implementation of environmental projects, Automatica J. IFAC, 41 (2005), 1737-1749. doi: 10.1016/j.automatica.2005.05.004. Google Scholar
[5]	P. Chander and H. Tulkens, The core of an economy with multilateral environmental externalities, Internat. J. Game Theory, 26 (1997), 379-401. doi: 10.1007/BF01263279. Google Scholar
[6]	J. A. Filar and P. S. Gaertner, A regional allocation of world CO2 emission reductions, Mathematics and Computers in Simulation, 43 (1997), 269-275. doi: 10.1016/S0378-4754(97)00009-8. Google Scholar
[7]	G. Freiling, G. Jank and H. Abou-Kandil, On global existence of solutions to coupled matrix Riccati equations in closed-loop Nash games, IEEE Trans. Automat. Control, 41 (1996), 264-269. doi: 10.1109/9.481532. Google Scholar
[8]	A. Friedman, Differential games, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994,781–799. Google Scholar
[9]	J. Greenberg, Coalition structures, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994, 1306–1337. Google Scholar
[10]	D. Gromov and E. Gromova, On a class of hybrid differential games, Dyn. Games Appl., 7 (2017), 266-288. doi: 10.1007/s13235-016-0185-3. Google Scholar
[11]	E. Gromova, A. Malakhova and E. Marova, On the superadditivity of a characteristic function in cooperative differential games with negative externalities, in 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), St. Petersburg, 2017, 1–4. doi: 10.1109/CNSA.2017.7973963. Google Scholar
[12]	E. Gromova, The Shapley value as a sustainable cooperative solution in differential games of three players, in Recent Advances in Game Theory and Applications, Birkhäuser/Springer, Cham, 2016, 67–89. Google Scholar
[13]	E. V. Gromova and E. V. Marova, Coalition and anti-coalition interaction in cooperative differential games, IFAC-PapersOnLine, 51 (2018), 479-483. doi: 10.1016/j.ifacol.2018.11.466. Google Scholar
[14]	E. V. Gromova and L. A. Petrosyan, On an approach to constructing a characteristic function in cooperative differential games, Autom. Remote Control, 78 (2017), 1680-1692. doi: 10.1134/s0005117917090120. Google Scholar
[15]	J. Hajduková, Coalition formation games: A survey, Int. Game Theory Rev., 8 (2006), 613-641. doi: 10.1142/S0219198906001144. Google Scholar
[16]	S. Hart, Shapley value, in Game Theory, Palgrave Macmillan, 1989,210–216. Google Scholar
[17]	A. Haurie and G. Zaccour, Differential game models of global environmental management, in Control and Game-Theoretic Models of the Environment, Vol. 2, Birkhäuser Boston, Boston, MA, 1995, 3–23. doi: 10.1007/978-1-4612-0841-9_1. Google Scholar
[18]	C.-Y. Huang and T. Sjöström, The recursive core for non-superadditive games, Games, 1 (2010), 66-88. doi: 10.3390/g1020066. Google Scholar
[19]	D. G. Hull, Optimal Control Theory for Applications, Springer-Verlag, New York, 2003. doi: 10.1007/978-1-4757-4180-3. Google Scholar
[20]	S. Jørgensen and E. Gromova, Sustaining cooperation in a differential game of advertising goodwill accumulation, European J. Oper. Res., 254 (2016), 294-303. doi: 10.1016/j.ejor.2016.03.029. Google Scholar
[21]	H. Moulin, Equal or proportional division of a surplus, and other methods, Internat. J. Game Theory, 16 (1987), 161-186. doi: 10.1007/BF01756289. Google Scholar
[22]	M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT press, Cambridge, MA, 1994. Google Scholar
[23]	L. Petrosjan and G. Zaccour, Time-consistent Shapley value allocation of pollution cost reduction, J. Econom. Dynam. Control, 27 (2003), 381-398. doi: 10.1016/S0165-1889(01)00053-7. Google Scholar
[24]	L. A. Petrosyan and N. N. Danilov, Stability of solutions in non-zero sum differential games with transferable payoffs, Vestnik Leningrad. Univ. Mat. Mekh. Astronom., 1 (1979), 52-59. Google Scholar
[25]	L. A. Petrosyan and E. V. Gromova, Two-level cooperation in coalitional differential games, Tr. Inst. Mat. Mekh., 20 (2014), 193-203. Google Scholar
[26]	P. V. Reddy and G. Zaccour, A friendly computable characteristic function, Math. Social Sci., 82 (2016), 18-25. doi: 10.1016/j.mathsocsci.2016.03.008. Google Scholar
[27]	Alvin E. Roth (ed.), Introduction to the Shapley value, in The Shapley value: Essays in honor of Lloyd S. Shapley, Cambridge University Press, Cambridge, 1988. doi: 10.1017/CBO9780511528446.002. Google Scholar
[28]	A. Sedakov, Characteristic functions in a linear oligopoly TU game, in Frontiers of Dynamic Games, Birkhäuser/Springer, Cham, 2018,219–235. Google Scholar
[29]	L. S. Shapley, A value for n-person games, Contributions to the Theory of Games, Vol. 2, Princeton University Press, Princeton, New Jersey, 1953,307-317. Google Scholar
[30]	J. Von Neumann and O. Morgenstern, Game Theory and Economic Behavior, Princeton University Press, Princeton, New Jersey, 1944. Google Scholar
[31]	E. Winter, R. J. Aumann and S. Hart (eds.), The Shapley value, in Handbook of Game Theory with Economic Applications, Vol. 3, Elsevier/North-Holland, Amsterdam, 2002, 1521–2351. Google Scholar

show all references

References:

[1]	T. Başar, On the uniqueness of the Nash solution in linear-quadratic differential games, Internat. J. Game Theory, 5 (1976), 65-90. doi: 10.1007/BF01753310. Google Scholar
[2]	T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Google Scholar
[3]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser Boston, Inc., Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1. Google Scholar
[4]	M. Breton, G. Zaccour and M. Zahaf, A differential game of joint implementation of environmental projects, Automatica J. IFAC, 41 (2005), 1737-1749. doi: 10.1016/j.automatica.2005.05.004. Google Scholar
[5]	P. Chander and H. Tulkens, The core of an economy with multilateral environmental externalities, Internat. J. Game Theory, 26 (1997), 379-401. doi: 10.1007/BF01263279. Google Scholar
[6]	J. A. Filar and P. S. Gaertner, A regional allocation of world CO2 emission reductions, Mathematics and Computers in Simulation, 43 (1997), 269-275. doi: 10.1016/S0378-4754(97)00009-8. Google Scholar
[7]	G. Freiling, G. Jank and H. Abou-Kandil, On global existence of solutions to coupled matrix Riccati equations in closed-loop Nash games, IEEE Trans. Automat. Control, 41 (1996), 264-269. doi: 10.1109/9.481532. Google Scholar
[8]	A. Friedman, Differential games, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994,781–799. Google Scholar
[9]	J. Greenberg, Coalition structures, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994, 1306–1337. Google Scholar
[10]	D. Gromov and E. Gromova, On a class of hybrid differential games, Dyn. Games Appl., 7 (2017), 266-288. doi: 10.1007/s13235-016-0185-3. Google Scholar
[11]	E. Gromova, A. Malakhova and E. Marova, On the superadditivity of a characteristic function in cooperative differential games with negative externalities, in 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), St. Petersburg, 2017, 1–4. doi: 10.1109/CNSA.2017.7973963. Google Scholar
[12]	E. Gromova, The Shapley value as a sustainable cooperative solution in differential games of three players, in Recent Advances in Game Theory and Applications, Birkhäuser/Springer, Cham, 2016, 67–89. Google Scholar
[13]	E. V. Gromova and E. V. Marova, Coalition and anti-coalition interaction in cooperative differential games, IFAC-PapersOnLine, 51 (2018), 479-483. doi: 10.1016/j.ifacol.2018.11.466. Google Scholar
[14]	E. V. Gromova and L. A. Petrosyan, On an approach to constructing a characteristic function in cooperative differential games, Autom. Remote Control, 78 (2017), 1680-1692. doi: 10.1134/s0005117917090120. Google Scholar
[15]	J. Hajduková, Coalition formation games: A survey, Int. Game Theory Rev., 8 (2006), 613-641. doi: 10.1142/S0219198906001144. Google Scholar
[16]	S. Hart, Shapley value, in Game Theory, Palgrave Macmillan, 1989,210–216. Google Scholar
[17]	A. Haurie and G. Zaccour, Differential game models of global environmental management, in Control and Game-Theoretic Models of the Environment, Vol. 2, Birkhäuser Boston, Boston, MA, 1995, 3–23. doi: 10.1007/978-1-4612-0841-9_1. Google Scholar
[18]	C.-Y. Huang and T. Sjöström, The recursive core for non-superadditive games, Games, 1 (2010), 66-88. doi: 10.3390/g1020066. Google Scholar
[19]	D. G. Hull, Optimal Control Theory for Applications, Springer-Verlag, New York, 2003. doi: 10.1007/978-1-4757-4180-3. Google Scholar
[20]	S. Jørgensen and E. Gromova, Sustaining cooperation in a differential game of advertising goodwill accumulation, European J. Oper. Res., 254 (2016), 294-303. doi: 10.1016/j.ejor.2016.03.029. Google Scholar
[21]	H. Moulin, Equal or proportional division of a surplus, and other methods, Internat. J. Game Theory, 16 (1987), 161-186. doi: 10.1007/BF01756289. Google Scholar
[22]	M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT press, Cambridge, MA, 1994. Google Scholar
[23]	L. Petrosjan and G. Zaccour, Time-consistent Shapley value allocation of pollution cost reduction, J. Econom. Dynam. Control, 27 (2003), 381-398. doi: 10.1016/S0165-1889(01)00053-7. Google Scholar
[24]	L. A. Petrosyan and N. N. Danilov, Stability of solutions in non-zero sum differential games with transferable payoffs, Vestnik Leningrad. Univ. Mat. Mekh. Astronom., 1 (1979), 52-59. Google Scholar
[25]	L. A. Petrosyan and E. V. Gromova, Two-level cooperation in coalitional differential games, Tr. Inst. Mat. Mekh., 20 (2014), 193-203. Google Scholar
[26]	P. V. Reddy and G. Zaccour, A friendly computable characteristic function, Math. Social Sci., 82 (2016), 18-25. doi: 10.1016/j.mathsocsci.2016.03.008. Google Scholar
[27]	Alvin E. Roth (ed.), Introduction to the Shapley value, in The Shapley value: Essays in honor of Lloyd S. Shapley, Cambridge University Press, Cambridge, 1988. doi: 10.1017/CBO9780511528446.002. Google Scholar
[28]	A. Sedakov, Characteristic functions in a linear oligopoly TU game, in Frontiers of Dynamic Games, Birkhäuser/Springer, Cham, 2018,219–235. Google Scholar
[29]	L. S. Shapley, A value for n-person games, Contributions to the Theory of Games, Vol. 2, Princeton University Press, Princeton, New Jersey, 1953,307-317. Google Scholar
[30]	J. Von Neumann and O. Morgenstern, Game Theory and Economic Behavior, Princeton University Press, Princeton, New Jersey, 1944. Google Scholar
[31]	E. Winter, R. J. Aumann and S. Hart (eds.), The Shapley value, in Handbook of Game Theory with Economic Applications, Vol. 3, Elsevier/North-Holland, Amsterdam, 2002, 1521–2351. Google Scholar

Figure 1. Partial order diagram

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. Computational effort required for computing different characteristic functions

C.F.	# of optimization problems (# of variables)	# of Nash equilibrium problems
$ \alpha $ ($ \beta $)	$ 2^n-1 (n) $	0
$ \delta $	$ 2^n-n-1 (2\div n) $	1
$ \zeta $	$ 2^n-1 (1\div n) $	0
$ \eta $	1 (n)	1

Table Options

Download as excel

C.F.	# of optimization problems (# of variables)	# of Nash equilibrium problems
$ \alpha $ ($ \beta $)	$ 2^n-1 (n) $	0
$ \delta $	$ 2^n-n-1 (2\div n) $	1
$ \zeta $	$ 2^n-1 (1\div n) $	0
$ \eta $	1 (n)	1

Table 2. Possible strategic interactions between the coalition $ S $ and its complement $ N\setminus S $ and the respective characteristic functions

		$ S $
		$ \max\limits_{u_i\in \mathcal{U}_i\atop i\in S} \sum\limits_{i\in S} J_i $	$ u_i=u_i^{NE} $, $ i\in S $	$ u_i=u_i^* $, $ i\in S $
	$ \min\limits_{u_j\in \mathcal{U}_j\atop j\in N\setminus S} \sum\limits_{i\in S} J_i $	$ \alpha/\beta $	$ F_1 $	$ \zeta $
$ N\setminus S $	$ u_j=u_j^{NE} $, $ j\in N\setminus S $	$ \delta $	Nash equilibrium	$ \eta $
	$ u_j=u_j^* $, $ j\in N\setminus S $	$ F_2 $	$ F_3 $	Cooperative agreement

Table Options

Download as excel

		$ S $
		$ \max\limits_{u_i\in \mathcal{U}_i\atop i\in S} \sum\limits_{i\in S} J_i $	$ u_i=u_i^{NE} $, $ i\in S $	$ u_i=u_i^* $, $ i\in S $
	$ \min\limits_{u_j\in \mathcal{U}_j\atop j\in N\setminus S} \sum\limits_{i\in S} J_i $	$ \alpha/\beta $	$ F_1 $	$ \zeta $
$ N\setminus S $	$ u_j=u_j^{NE} $, $ j\in N\setminus S $	$ \delta $	Nash equilibrium	$ \eta $
	$ u_j=u_j^* $, $ j\in N\setminus S $	$ F_2 $	$ F_3 $	Cooperative agreement

[1]	İsmail Özcan, Sirma Zeynep Alparslan Gök. On cooperative fuzzy bubbly games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021010
[2]	Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021026
[3]	Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[4]	Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021006
[5]	Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021014
[6]	Qi Lü, Xu Zhang. A concise introduction to control theory for stochastic partial differential equations. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021020
[7]	Wensheng Yin, Jinde Cao, Guoqiang Zheng. Further results on stabilization of stochastic differential equations with delayed feedback control under $ G $-expectation framework. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021072
[8]	M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202
[9]	Tian Hou, Yi Wang, Xizhuang Xie. Instability and bifurcation of a cooperative system with periodic coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021026
[10]	Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[11]	Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021050
[12]	Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[13]	Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[14]	Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004
[15]	Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[16]	Gheorghe Craciun, Abhishek Deshpande, Hyejin Jenny Yeon. Quasi-toric differential inclusions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2343-2359. doi: 10.3934/dcdsb.2020181
[17]	Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[18]	Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021019
[19]	Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021070
[20]	Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021020

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences

A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors