• Previous Article
    Constrained stochastic differential games with additive structure: Average and discount payoffs
  • JDG Home
  • This Issue
  • Next Article
    A risk minimization problem for finite horizon semi-Markov decision processes with loss rates
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 & Games, 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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Peiyu li. Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-10. doi: 10.3934/jimo.2017065

[12]

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

[13]

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

[14]

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

[15]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279

[16]

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

[17]

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

[18]

Yuan Guo, Xiaofei Gao, Desheng Li. Structure of the set of bounded solutions for a class of nonautonomous second order differential equations. Communications on Pure & Applied Analysis, 2010, 9 (6) : 1607-1616. doi: 10.3934/cpaa.2010.9.1607

[19]

Maria Aguareles, Marco A. Fontelos, Juan J. Velázquez. The structure of the quiescent core in rigidly rotating spirals in a class of excitable systems. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1605-1638. doi: 10.3934/dcdsb.2012.17.1605

[20]

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

 Impact Factor: 

Metrics

  • PDF downloads (7)
  • HTML views (26)
  • Cited by (0)

[Back to Top]