American Institute of Mathematical Sciences

Advanced
April  2018, 5(2): 95-107. doi: 10.3934/jdg.2018007

Games with nested constraints given by a level structure

Francisco Sánchez-Sánchez and  Miguel Vargas-Valencia ,

Jalisco S/N, Valenciana, CP: 36240, CIMAT, A.C., Guanajuato, Gto, México

* Corresponding author: mvargas@cimat.mx

Received  December 2016 Revised  November 2017 Published  February 2018

In this paper we propose new games that satisfy nested constraints given by a level structure of cooperation. This structure is defined by a family of partitions on the set of players. It is ordered in such a way that each partition is a refinement of the next one. We propose a value for these games by adapting the Shapley value. The value is characterized axiomatically. For this purpose, we introduce a new property called class balance contributions by generalizing other properties in the literature. Finally, we introduce a multilinear extension of our games and use it to obtain an expression for calculating the adapted Shapley value.

Keywords: Nested constraints, level structure, Shapley value, class balanced contributions, multilinear extension.
Mathematics Subject Classification: Primary: 91A12, 91A44; Secondary: 91A46.
Citation: Francisco Sánchez-Sánchez, Miguel Vargas-Valencia. Games with nested constraints given by a level structure. Journal of Dynamics & Games, 2018, 5 (2) : 95-107. doi: 10.3934/jdg.2018007
References:
[1]

M. Álvarez-Mozos and O. Tejada, Parallel characterizations of a generalized shapley value and a generalized banzhaf value for cooperative games with level structure of cooperation, Decision Support Systems, 52 (2011), 21-27.   Google Scholar

[2]

R. J. Aumann and J. H. Dreze, Cooperative games with coalition structures, International Journal of Game Theory, 3 (1974), 217-237.  doi: 10.1007/BF01766876.  Google Scholar

[3]

J. M. Bilbao and P. H. Edelman, The shapley value on convex geometries, Discrete Applied Mathematics, 103 (2000), 33-40.  doi: 10.1016/S0166-218X(99)00218-8.  Google Scholar

[4]

E. Calvo, J. J. Lasaga and E. Winter, The principle of balanced contributions and hierarchies of cooperation, Mathematical Social Sciences, 31 (1996), 171-182.  doi: 10.1016/0165-4896(95)00806-3.  Google Scholar

[5]

U. Faigle and W. Kern, The shapley value for cooperative games under precedence constraints, International Journal of Game Theory, 21 (1992), 249-266.  doi: 10.1007/BF01258278.  Google Scholar

[6]

M. Gómez-Rúa and J. Vidal-Puga, Balanced per capita contributions and level structure of cooperation, Top, 19 (2011), 167-176.  doi: 10.1007/s11750-009-0122-3.  Google Scholar

[7]

J. C. Harsanyi, A simplified bargaining model for the n-person cooperative game, Part of the Theory and Decision Library book series, 28 (1960), 44-70.  doi: 10.1007/978-94-017-2527-9_3.  Google Scholar

[8]

S. Hart and A. Mas-Colell, Potential, value, and consistency, Econometrica: Journal of the Econometric Society, 57 (1989), 589-614.  doi: 10.2307/1911054.  Google Scholar

[9]

E. Kalai and D. Samet, On weighted shapley values, International Journal of Game Theory, 16 (1987), 205-222.  doi: 10.1007/BF01756292.  Google Scholar

[10]

Y. Kamijo, The collective value: A new solution for games with coalition structures, Top, 21 (2013), 572-589.  doi: 10.1007/s11750-011-0191-y.  Google Scholar

[11]

G. Koshevoy and D. Talman, Solution concepts for games with general coalitional structure, Mathematical Social Sciences, 68 (2014), 19-30.  doi: 10.1016/j.mathsocsci.2013.12.004.  Google Scholar

[12]

R. B. Myerson, Graphs and cooperation in games, Mathematics of Operations Research, 2 (1977), 225-229.  doi: 10.1287/moor.2.3.225.  Google Scholar

[13]

R. B. Myerson, Conference structures and fair allocation rules, International Journal of Game Theory, 9 (1980), 169-182.  doi: 10.1007/BF01781371.  Google Scholar

[14]

G. Owen, Values of graph-restricted games, SIAM Journal on Algebraic Discrete Methods, 7 (1986), 210-220.  doi: 10.1137/0607025.  Google Scholar

[15]

G. Owen, Multilinear extensions of games, in The Shapley value: essays in honor of Lloyd S. Shapley (ed. A. E. Roth), Cambridge University Press, 1988, chapter 10, 139-151.  Google Scholar

[16]

G. Owen and E. Winter, The multilinear extension and the coalition structure value, Games and Economic Behavior, 4 (1992), 582-587.  doi: 10.1016/0899-8256(92)90038-T.  Google Scholar

[17]

G. Owen, Values of games with a priori unions, in Mathematical Economics and Game Theory, Springer, 141 (1977), 76-88.  Google Scholar

[18]

R. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986.  Google Scholar

[19]

R. van den Brink, A. Khmelnitskaya and G. van der Laan, An owen-type value for games with two-level communication structure, Annals of Operations Research, 243 (2016), 179-198.  doi: 10.1007/s10479-015-1808-6.  Google Scholar

[20]

E. Winter, A value for cooperative games with levels structure of cooperation, International Journal of Game Theory, 18 (1989), 227-240.  doi: 10.1007/BF01268161.  Google Scholar

show all references

References:
[1]

M. Álvarez-Mozos and O. Tejada, Parallel characterizations of a generalized shapley value and a generalized banzhaf value for cooperative games with level structure of cooperation, Decision Support Systems, 52 (2011), 21-27.   Google Scholar

[2]

R. J. Aumann and J. H. Dreze, Cooperative games with coalition structures, International Journal of Game Theory, 3 (1974), 217-237.  doi: 10.1007/BF01766876.  Google Scholar

[3]

J. M. Bilbao and P. H. Edelman, The shapley value on convex geometries, Discrete Applied Mathematics, 103 (2000), 33-40.  doi: 10.1016/S0166-218X(99)00218-8.  Google Scholar

[4]

E. Calvo, J. J. Lasaga and E. Winter, The principle of balanced contributions and hierarchies of cooperation, Mathematical Social Sciences, 31 (1996), 171-182.  doi: 10.1016/0165-4896(95)00806-3.  Google Scholar

[5]

U. Faigle and W. Kern, The shapley value for cooperative games under precedence constraints, International Journal of Game Theory, 21 (1992), 249-266.  doi: 10.1007/BF01258278.  Google Scholar

[6]

M. Gómez-Rúa and J. Vidal-Puga, Balanced per capita contributions and level structure of cooperation, Top, 19 (2011), 167-176.  doi: 10.1007/s11750-009-0122-3.  Google Scholar

[7]

J. C. Harsanyi, A simplified bargaining model for the n-person cooperative game, Part of the Theory and Decision Library book series, 28 (1960), 44-70.  doi: 10.1007/978-94-017-2527-9_3.  Google Scholar

[8]

S. Hart and A. Mas-Colell, Potential, value, and consistency, Econometrica: Journal of the Econometric Society, 57 (1989), 589-614.  doi: 10.2307/1911054.  Google Scholar

[9]

E. Kalai and D. Samet, On weighted shapley values, International Journal of Game Theory, 16 (1987), 205-222.  doi: 10.1007/BF01756292.  Google Scholar

[10]

Y. Kamijo, The collective value: A new solution for games with coalition structures, Top, 21 (2013), 572-589.  doi: 10.1007/s11750-011-0191-y.  Google Scholar

[11]

G. Koshevoy and D. Talman, Solution concepts for games with general coalitional structure, Mathematical Social Sciences, 68 (2014), 19-30.  doi: 10.1016/j.mathsocsci.2013.12.004.  Google Scholar

[12]

R. B. Myerson, Graphs and cooperation in games, Mathematics of Operations Research, 2 (1977), 225-229.  doi: 10.1287/moor.2.3.225.  Google Scholar

[13]

R. B. Myerson, Conference structures and fair allocation rules, International Journal of Game Theory, 9 (1980), 169-182.  doi: 10.1007/BF01781371.  Google Scholar

[14]

G. Owen, Values of graph-restricted games, SIAM Journal on Algebraic Discrete Methods, 7 (1986), 210-220.  doi: 10.1137/0607025.  Google Scholar

[15]

G. Owen, Multilinear extensions of games, in The Shapley value: essays in honor of Lloyd S. Shapley (ed. A. E. Roth), Cambridge University Press, 1988, chapter 10, 139-151.  Google Scholar

[16]

G. Owen and E. Winter, The multilinear extension and the coalition structure value, Games and Economic Behavior, 4 (1992), 582-587.  doi: 10.1016/0899-8256(92)90038-T.  Google Scholar

[17]

G. Owen, Values of games with a priori unions, in Mathematical Economics and Game Theory, Springer, 141 (1977), 76-88.  Google Scholar

[18]

R. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986.  Google Scholar

[19]

R. van den Brink, A. Khmelnitskaya and G. van der Laan, An owen-type value for games with two-level communication structure, Annals of Operations Research, 243 (2016), 179-198.  doi: 10.1007/s10479-015-1808-6.  Google Scholar

[20]

E. Winter, A value for cooperative games with levels structure of cooperation, International Journal of Game Theory, 18 (1989), 227-240.  doi: 10.1007/BF01268161.  Google Scholar

Table 1.  Characteristic function for maintenance cost of a highway system.
S {1} {2} {3} {4} {2, 3} {1, 2, 3} {1, 2, 3, 4}
v(S) 1 1 0 1 2 4 6
Table Options

Download as excel

S {1} {2} {3} {4} {2, 3} {1, 2, 3} {1, 2, 3, 4}
v(S) 1 1 0 1 2 4 6
Table 2.  Games of classes for counties as players.
R {1} {2} {1, 2} R {3}
vC12(R) 1 2 4 vC22(R) 1
Table Options

Download as excel

R {1} {2} {1, 2} R {3}
vC12(R) 1 2 4 vC22(R) 1
Table 3.  Game of classes for states as players.
R {1} {2} {1, 2}
vC13(R) 4 1 6
Table Options

Download as excel

R {1} {2} {1, 2}
vC13(R) 4 1 6
[1]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461
[2]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082
[3]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074
[4]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[5]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[6]

Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020452
[7]

Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248
[8]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052
[9]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442
[10]

Yolanda Guerrero–Sánchez, Muhammad Umar, Zulqurnain Sabir, Juan L. G. Guirao, Muhammad Asif Zahoor Raja. Solving a class of biological HIV infection model of latently infected cells using heuristic approach. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020431
[11]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436
[12]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267

 Impact Factor: 

Tools

Metrics

  • PDF downloads (140)
  • HTML views (361)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences