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

Ekaterina Gromova; Ekaterina Marova; Dmitry Gromov

doi:10.3934/jdg.2020007

Article Contents

2020, Volume 7, Issue 2: 105-122. Doi: 10.3934/jdg.2020007

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

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

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

^* Corresponding author: Ekaterina Gromova
^* Corresponding author: Ekaterina Gromova

Received: September 2019

Published: April 2020

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

Abstract / Introduction Full Text(HTML) Figure(1) / Table(2) Related Papers Cited by

Abstract

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:

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

Citation:

Full Text(HTML)

Figure 1. Partial order diagram

Download: Full-size image 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[2]	T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd edition, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999.
[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.
[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.
[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.
[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.
[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.
[8]	A. Friedman, Differential games, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994,781–799.
[9]	J. Greenberg, Coalition structures, in Handbook of Game Theory with Economic Applications, Vol. 2, North-Holland, Amsterdam, 1994, 1306–1337.
[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.
[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.
[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.
[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.
[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.
[15]	J. Hajduková, Coalition formation games: A survey, Int. Game Theory Rev., 8 (2006), 613-641. doi: 10.1142/S0219198906001144.
[16]	S. Hart, Shapley value, in Game Theory, Palgrave Macmillan, 1989,210–216.
[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.
[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.
[19]	D. G. Hull, Optimal Control Theory for Applications, Springer-Verlag, New York, 2003. doi: 10.1007/978-1-4757-4180-3.
[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.
[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.
[22]	M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT press, Cambridge, MA, 1994.
[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.
[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.
[25]	L. A. Petrosyan and E. V. Gromova, Two-level cooperation in coalitional differential games, Tr. Inst. Mat. Mekh., 20 (2014), 193-203.
[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.
[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.
[28]	A. Sedakov, Characteristic functions in a linear oligopoly TU game, in Frontiers of Dynamic Games, Birkhäuser/Springer, Cham, 2018,219–235.
[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.
[30]	J. Von Neumann and O. Morgenstern, Game Theory and Economic Behavior, Princeton University Press, Princeton, New Jersey, 1944.
[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.