Network strength games: the core and the nucleolus

Abstract

The maximum number of edge-disjoint spanning trees in a network has been used as a measure of the strength of a network. It gives the number of disjoint ways that the network can be fully connected. This suggests a game theoretic analysis that shows the relative importance of the different links to form a strong network. We introduce the Network strength game as a cooperative game defined on a graph G= (V, E). The player set is the edge-set E and the value of a coalition S⊆ E is the maximum number of disjoint spanning trees included in S. We study the core of this game, and we give a polynomial combinatorial algorithm to compute the nucleolus when the core is non-empty.