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

Games with nested constraints given by a level structure

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.

Citation: Francisco Sánchez-Sánchez, Miguel Vargas-Valencia. Games with nested constraints given by a level structure. Journal of Dynamics and 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. 

[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.

[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.

[4]

E. CalvoJ. 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.

[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.

[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.

[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.

[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.

[9]

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

[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.

[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.

[12]

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

[13]

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

[14]

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

[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.

[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.

[17]

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

[18]

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

[19]

R. van den BrinkA. 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.

[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.

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. 

[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.

[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.

[4]

E. CalvoJ. 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.

[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.

[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.

[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.

[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.

[9]

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

[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.

[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.

[12]

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

[13]

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

[14]

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

[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.

[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.

[17]

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

[18]

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

[19]

R. van den BrinkA. 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.

[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.

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
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
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
R {1} {2} {1, 2}
vC13(R) 4 1 6
[1]

Leon Petrosyan, David Yeung. Shapley value for differential network games: Theory and application. Journal of Dynamics and Games, 2021, 8 (2) : 151-166. doi: 10.3934/jdg.2020021

[2]

Yan-An Hwang, Yu-Hsien Liao. Reduction and dynamic approach for the multi-choice Shapley value. Journal of Industrial and Management Optimization, 2013, 9 (4) : 885-892. doi: 10.3934/jimo.2013.9.885

[3]

Jun Huang, Ying Peng, Ruwen Tan, Chunxiang Guo. Alliance strategy of construction and demolition waste recycling based on the modified shapley value under government regulation. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3183-3207. doi: 10.3934/jimo.2020113

[4]

Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335

[5]

Hernán Cendra, María Etchechoury, Sebastián J. Ferraro. An extension of the Dirac and Gotay-Nester theories of constraints for Dirac dynamical systems. Journal of Geometric Mechanics, 2014, 6 (2) : 167-236. doi: 10.3934/jgm.2014.6.167

[6]

Qiang Zhang, Ping Chen. Multidimensional balanced credibility model with time effect and two level random common effects. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1311-1328. doi: 10.3934/jimo.2019004

[7]

Suresh P. Sethi, Houmin Yan, Hanqin Zhang, Jing Zhou. Information Updated Supply Chain with Service-Level Constraints. Journal of Industrial and Management Optimization, 2005, 1 (4) : 513-531. doi: 10.3934/jimo.2005.1.513

[8]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete and Continuous Dynamical Systems - S, 2021, 14 (6) : 1857-1870. doi: 10.3934/dcdss.2020461

[9]

Davide Bellandi. On the initial value problem for a class of discrete velocity models. Mathematical Biosciences & Engineering, 2017, 14 (1) : 31-43. doi: 10.3934/mbe.2017003

[10]

Piermarco Cannarsa, Peter R. Wolenski. Semiconcavity of the value function for a class of differential inclusions. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 453-466. doi: 10.3934/dcds.2011.29.453

[11]

Zheng-Jian Bai, Xiao-Qing Jin, Seak-Weng Vong. On some inverse singular value problems with Toeplitz-related structure. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 187-192. doi: 10.3934/naco.2012.2.187

[12]

Sung-Seok Ko, Jangha Kang, E-Yeon Kwon. An $(s,S)$ inventory model with level-dependent $G/M/1$-Type structure. Journal of Industrial and Management Optimization, 2016, 12 (2) : 609-624. doi: 10.3934/jimo.2016.12.609

[13]

Umakanta Mishra, Abu Hashan Md Mashud, Sankar Kumar Roy, Md Sharif Uddin. The effect of rebate value and selling price-dependent demand for a four-level production manufacturing system. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021233

[14]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[15]

X. Liang, Roderick S. C. Wong. On a Nested Boundary-Layer Problem. Communications on Pure and Applied Analysis, 2009, 8 (1) : 419-433. doi: 10.3934/cpaa.2009.8.419

[16]

Jair Koiller. Getting into the vortex: On the contributions of james montaldi. Journal of Geometric Mechanics, 2020, 12 (3) : 507-523. doi: 10.3934/jgm.2020018

[17]

Joseph J Kohn. Nirenberg's contributions to complex analysis. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 537-545. doi: 10.3934/dcds.2011.30.537

[18]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99

[19]

Peiyu Li. Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints. Journal of Industrial and Management Optimization, 2018, 14 (2) : 637-646. doi: 10.3934/jimo.2017065

[20]

Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial and Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005

 Impact Factor: 

Metrics

  • PDF downloads (319)
  • HTML views (371)
  • Cited by (11)

[Back to Top]