Games induced by the partitioning of a graph

Michel Grabisch and Alexandre Skoda ()
Additional contact information
Alexandre Skoda: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL

Abstract: The paper aims at generalizing the notion of restricted game on a communication graph, introduced by Myerson. We consider communication graphs with weighted edges, and we define arbitrary ways of partitioning any subset of a graph, which we call correspondences. A particularly useful way to partition a graph is obtained by computing the strength of the graph. The strength of a graph is a measure introduced in graph theory to evaluate the resistance of networks under attacks, and it provides a natural partition of the graph (called the Gusfield correspondence) into resistant components. We perform a general study of the inheritance of superadditivity and convexity for the restricted game associated with a given correspondence. Our main result is to give for cycle-free graphs necessary and sufficient conditions for the inheritance of convexity of the restricted game associated with the Gusfield correspondence.

Keywords: Communication networks; Coalition structure; Cooperative game; Strength of a graph (search for similar items in EconPapers)
Date: 2012-12
New Economics Papers: this item is included in nep-gth
Note: View the original document on HAL open archive server: https://hal.science/hal-00830291v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Published in Annals of Operations Research, 2012, 201 (1), pp.229-249. ⟨10.1007/s10479-012-1200-8⟩

Downloads: (external link)
https://hal.science/hal-00830291v1/document (application/pdf)

Related works:
Journal Article: Games induced by the partitioning of a graph (2012)
Working Paper: Games induced by the partitioning of a graph (2012)
Working Paper: Games induced by the partitioning of a graph (2012)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:cesptp:hal-00830291

DOI: 10.1007/s10479-012-1200-8

Access Statistics for this paper

More papers in Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL
Bibliographic data for series maintained by CCSD ().