ABSTRACT
Minimum cost spanning tree problems model situations where a group of agents, located at different nodes, require a service provided by a source. Moreover, the nodes can be either connected directly to the source or through other agents already connected. Thus, there are savings from cooperation. While the corresponding cooperative game always has a non-empty core, the Shapley value might not be a core allocation. However, multiple methods have been proposed that modify the game before applying the Shapley value to obtain a core allocation. These allocations, the Kar, folk and cycle-complete solutions, are studied in this chapter, and we review the axiomatizations proposed in the literature. We also distinguish the various approaches to the problem, depending if we assume that other agents are connected or not and if not, if they allow connection through their location. Weighted Shapley values and links to other concepts like the nucleolus are also examined. We also discuss the use of the Shapley value in closely related source connection problems.
