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]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[2]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329
[3]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[4]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[5]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[6]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[7]

Jing Feng, Bin-Guo Wang. An almost periodic Dengue transmission model with age structure and time-delayed input of vector in a patchy environment. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3069-3096. doi: 10.3934/dcdsb.2020220
[8]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[9]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277
[10]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017
[11]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513
[12]

Zhouxin Li, Yimin Zhang. Ground states for a class of quasilinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, 2021, 20 (2) : 933-954. doi: 10.3934/cpaa.2020298
[13]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[14]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91
[15]

Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1747-1756. doi: 10.3934/dcdss.2020452
[16]

Yahui Niu. A Hopf type lemma and the symmetry of solutions for a class of Kirchhoff equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021027
[17]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[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]

Brahim Alouini. Finite dimensional global attractor for a class of two-coupled nonlinear fractional Schrödinger equations. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021013

 Impact Factor: 

Tools

Metrics

  • PDF downloads (169)
  • HTML views (363)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences