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

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

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.

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. BretonG. 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. FreilingG. 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. BretonG. 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. FreilingG. 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
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
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
$ 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]

Kuang Huang, Xuan Di, Qiang Du, Xi Chen. A game-theoretic framework for autonomous vehicles velocity control: Bridging microscopic differential games and macroscopic mean field games. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2020131

[2]

Piernicola Bettiol. State constrained $L^\infty$ optimal control problems interpreted as differential games. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3989-4017. doi: 10.3934/dcds.2015.35.3989

[3]

John A. Morgan. Interception in differential pursuit/evasion games. Journal of Dynamics & Games, 2016, 3 (4) : 335-354. doi: 10.3934/jdg.2016018

[4]

Deng-Feng Li, Yin-Fang Ye, Wei Fei. Extension of generalized solidarity values to interval-valued cooperative games. Journal of Industrial & Management Optimization, 2020, 16 (2) : 919-931. doi: 10.3934/jimo.2018185

[5]

Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889

[6]

Alain Bensoussan, Jens Frehse, Christine Grün. Stochastic differential games with a varying number of players. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1719-1736. doi: 10.3934/cpaa.2014.13.1719

[7]

Ellina Grigorieva, Evgenii Khailov. Hierarchical differential games between manufacturer and retailer. Conference Publications, 2009, 2009 (Special) : 300-314. doi: 10.3934/proc.2009.2009.300

[8]

Ellina Grigorieva, Evgenii Khailov. Optimal control of pollution stock. Conference Publications, 2011, 2011 (Special) : 578-588. doi: 10.3934/proc.2011.2011.578

[9]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555

[10]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics & Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008

[11]

Alain Bensoussan, Shaokuan Chen, Suresh P. Sethi. Linear quadratic differential games with mixed leadership: The open-loop solution. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 95-108. doi: 10.3934/naco.2013.3.95

[12]

Alain Bensoussan, Jens Frehse, Jens Vogelgesang. Systems of Bellman equations to stochastic differential games with non-compact coupling. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1375-1389. doi: 10.3934/dcds.2010.27.1375

[13]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics & Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002

[14]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045

[15]

Lesia V. Baranovska. Pursuit differential-difference games with pure time-lag. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1021-1031. doi: 10.3934/dcdsb.2019004

[16]

Weihua Ruan. Markovian strategies for piecewise deterministic differential games with continuous and impulse controls. Journal of Dynamics & Games, 2019, 6 (4) : 337-366. doi: 10.3934/jdg.2019022

[17]

Alexei Korolev, Gennady Ougolnitsky. Optimal resource allocation in the difference and differential Stackelberg games on marketing networks. Journal of Dynamics & Games, 2020, 7 (2) : 141-162. doi: 10.3934/jdg.2020009

[18]

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa. Average optimal strategies for zero-sum Markov games with poorly known payoff function on one side. Journal of Dynamics & Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105

[19]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117

[20]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

 Impact Factor: 

Metrics

  • PDF downloads (30)
  • HTML views (78)
  • Cited by (0)

[Back to Top]