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]

Leon Petrosyan, David Yeung. Shapley value for differential network games: Theory and application. Journal of Dynamics & Games, 2020  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 & 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 & Management Optimization, 2020  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 & 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 & Management Optimization, 2005, 1 (4) : 513-531. doi: 10.3934/jimo.2005.1.513
[8]

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
[9]

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

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

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

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 & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[13]

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

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

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

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

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

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[19]

Teresa Faria. Asymptotic behaviour for a class of delayed cooperative models with patch structure. Discrete & Continuous Dynamical Systems - B, 2013, 18 (6) : 1567-1579. doi: 10.3934/dcdsb.2013.18.1567
[20]

Cheng-Hsiung Hsu, Suh-Yuh Yang. Structure of a class of traveling waves in delayed cellular neural networks. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 339-359. doi: 10.3934/dcds.2005.13.339

 Impact Factor: 

Tools

Metrics

  • PDF downloads (115)
  • HTML views (360)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences