Games induced by the partitioning of a graph
Article dans une revue: 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.
Auteur(s)
Michel Grabisch, Alexandre Skoda
Revue
- Annals of Operations Research
Date de publication
- 2012
Mots-clés JEL
Mots-clés
- Communication networks
- Coalition structure
- Cooperative game
- Strength of a graph
Pages
- 229-249
URL de la notice HAL
Version
- 1
Volume
- 201