On cost allocation for a spanning tree: A game theoretic approach

✍ Scribed by C. G. Bird

• Publisher: John Wiley and Sons
• Year: 1976
• Tongue: English
• Weight: 705 KB
• Volume: 6
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230060404

✦ Synopsis

Abstract

Cooperative game theory solution concepts are used to allocate costs in a spanning tree network. Stable cost allocations are related to the core of a cooperative game and it is proved that every game generated from a minimum cost spanning tree with an immovable source has a core. A refinement of the core, called the irreducible core, is introduced and the extreme points of the solution can be characterized by permutations of the minimal cost spanning tree. Points in the irreducible core are shown to be stable under unions of additional players. A weighted Shapley value is used to obtain a unique allocation of costs. This value coincides with the marginal costs of the spanning tree when there is only one minimal spanning tree. When multiple sources are allowed, counterexamples to the existence of a core are presented unless extra taxes are levied on the users.