Solution Concepts for Games with General Coalitional Structure (Replaces CentER DP 2011-025)
AbstractWe introduce a theory on marginal values and their core stability for cooperative games with arbitrary coalition structure. The theory is based on the notion of nested sets and the complex of nested sets associated to an arbitrary set system and the M-extension of a game for this set. For a set system being a building set or partition system, the corresponding complex is a polyhedral complex, and the vertices of this complex correspond to maximal strictly nested sets. To each maximal strictly nested set is associated a rooted tree. Given characteristic function, to every maximal strictly nested set a marginal value is associated to a corresponding rooted tree as in . We show that the same marginal value is obtained by using the M-extension for every permutation that is associated to the rooted tree. The GC-solution is defined as the average of the marginal values over all maximal strictly nested sets. The solution can be viewed as the gravity center of the image of the vertices of the polyhedral complex. The GC-solution differs from the Myerson-kind value defined in  for union stable structures. The HS-solution is defined as the average of marginal values over the subclass of so-called half-space nested sets. The NT-solution is another solution and is defined as the average of marginal values over the subclass of NT-nested sets. For graphical buildings the collection of NT-nested sets corresponds to the set of spanning normal trees on the underlying graph and the NT-solution coincides with the average tree solution. We also study core stability of the solutions and show that both the HS-solution and NT-solution belong to the core under half-space supermodularity, which is a weaker condition than convexity of the game. For an arbitrary set system we show that there exists a unique minimal building set containing the set system. As solutions we take the solutions for this building covering by extending in a natural way the characteristic function to it by using its Möbius inversion.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Tilburg University, Center for Economic Research in its series Discussion Paper with number 2011-119.
Date of creation: 2011
Date of revision:
Contact details of provider:
Web page: http://center.uvt.nl
Core; polytope; building set; nested set complex; Möbius inversion; permutations; normal fan; average tree solution; Myerson value;
Find related papers by JEL classification:
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Faigle, U & Kern, W, 1992. "The Shapley Value for Cooperative Games under Precedence Constraints," International Journal of Game Theory, Springer, vol. 21(3), pages 249-66.
- Herings, P.J.J. & van der Laan, G. & Talman, A.J.J. & Yang, Z., 2010.
"The average tree solution for cooperative games with communication structure,"
Games and Economic Behavior,
Elsevier, vol. 68(2), pages 626-633, March.
- Herings, P. Jean-Jacques & Laan, Gerard van der & Talman, Dolf & Yang, Zaifu, 2008. "The Average Tree Solution for Cooperative Games with Communication Structure," Research Memorandum 026, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Herings, P.J.J. & Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 2008. "The Average Tree Solution for Cooperative Games with Communication Structure," Discussion Paper 2008-73, Tilburg University, Center for Economic Research.
- P. Jean-Jacques Herings & Gerard van der Laan & Dolf Talman & Zaifu Yang, 2008. "The Average Tree Solution for Cooperative Games with Communication Structure," Tinbergen Institute Discussion Papers 08-083/1, Tinbergen Institute.
- Herings, P.J.J. & Laan, G. van der & Talman, A.J.J. & Yang, Z.F., 2010. "The average tree solution for cooperative games with communication structure," Open Access publications from Tilburg University urn:nbn:nl:ui:12-3736837, Tilburg University.
- Derks, Jean J M & Gilles, Robert P, 1995. "Hierarchical Organization Structures and Constraints on Coalition Formation," International Journal of Game Theory, Springer, vol. 24(2), pages 147-63.
- Borm, P.E.M. & Algaba, A. & Bilbao, J.M. & Lopez, J., 2002. "The Myerson value for union stable systems," Open Access publications from Tilburg University urn:nbn:nl:ui:12-90189, Tilburg University.
- Gabrielle Demange, 2004.
"On group stability in hierarchies and networks,"
- Algaba, A. & Bilbao, J.M. & Borm, P.E.M. & Lopez, J., 2000.
"The position value for union stable systems,"
Open Access publications from Tilburg University
urn:nbn:nl:ui:12-84483, Tilburg University.
- repec:hal:cesptp:hal-00625336 is not listed on IDEAS
- E. Algaba & J.M. Bilbao & J.J. LÃ³pez, 2001. "A unified approach to restricted games," Theory and Decision, Springer, vol. 50(4), pages 333-345, June.
- Danilov, V. & Koshevoy, G., 2005. "Mathematics of Plott choice functions," Mathematical Social Sciences, Elsevier, vol. 49(3), pages 245-272, May.
- Faigle, U. & Grabisch, M. & Heyne, M., 2010.
"Monge extensions of cooperation and communication structures,"
European Journal of Operational Research,
Elsevier, vol. 206(1), pages 104-110, October.
- Huseynov, T. & Talman, A.J.J., 2012. "The Communication Tree Value for TU-games with Graph Communication," Discussion Paper 2012-095, Tilburg University, Center for Economic Research.
- Koshevoy, G.A. & Suzuki, T. & Talman, A.J.J., 2013. "Solutions For Games With General Coalitional Structure And Choice Sets," Discussion Paper 2013-012, Tilburg University, Center for Economic Research.
- Selcuk, O. & Talman, A.J.J., 2013. "Games With General Coalitional Structure," Discussion Paper 2013-002, Tilburg University, Center for Economic Research.
- Khmelnitskaya, A. & Selcuk, O. & Talman, A.J.J., 2012. "The Average Covering Tree Value for Directed Graph Games," Discussion Paper 2012-037, Tilburg University, Center for Economic Research.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Richard Broekman).
If references are entirely missing, you can add them using this form.