Minimum-cost spanning tree game

Minimum-cost spanning tree game

A minimum-cost spanning-tree game (MCST game) is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph. The graph contains an additional node - the supply node - denoted by s. The goal of the players is that all of them will be connected by a path to s. To this end, they need to construct a spanning tree. Each edge in the graph has a cost, and the players build the minimum cost spanning tree. The question then arises, how to allocate the cost of this MCST among the players?

The solution offered by cooperative game theory is to consider the cost of each potential coalition - each subset of the players. The cost of each coalition S is the minimum cost of a spanning tree connecting only the nodes in S to the supply node s. The value of S is minus the cost of S. Using these definitions, various solution concepts from cooperative game theory can be applied. MCST games were introduced by Bird in 1976.

Properties * The [[core-(game-theory)|core]] of every MCST game is non-empty. * The [[nucleolus-(game-theory)|nucleolus]] is the unique point in the intersection of the [[core-(game-theory)|core]] and the kernel. * If the underlying network is a tree, then the nucleolus coincides with the kernel.

Computation One solution in the core can be read directly from any minimum cost spanning tree graph associated with the problem. There is an algorithm that computes the nucleolus in time O(n3|B|), where B is the set of relevant coalitions (in general, |B|=2n*, but in some special cases, only a subset of the coalitions are relevant). If the underlying network is a tree, then the nucleolus can be computed in O(n3) time, and the [[shapley-value]] can be computed in O(n) time. The run-time of computing the nucleolus can be reduced to O(n log n) using efficiently mergeable heaps. In particular cases, the nucleolus can be computed in O(n*) time.

References