View source for Minimum-cost spanning tree game

A '''minimum-cost spanning-tree game''' ('''MCST game''') is a kind of a [[Cooperative game theory|cooperative game]]. In an MCST game, each player is a node in a [[Complete graph|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|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.<ref name=":1">{{Cite journal |last=Bird |first=C. G. |date=1976 |title=On cost allocation for a spanning tree: A game theoretic approach |url=https://onlinelibrary.wiley.com/doi/10.1002/net.3230060404 |journal=Networks |language=en |volume=6 |issue=4 |pages=335–350 |doi=10.1002/net.3230060404|url-access=subscription }}</ref>

== Properties ==

* The [[Software:Core (game theory)|core]] of every MCST game is non-empty.<ref name=":1" /><ref name=":2">{{Cite journal |last1=Granot |first1=Daniel |last2=Huberman |first2=Gur |date=1981-12-01 |title=Minimum cost spanning tree games |url=https://doi.org/10.1007/BF01584227 |journal=Mathematical Programming |language=en |volume=21 |issue=1 |pages=1–18 |doi=10.1007/BF01584227 |s2cid=26198019 |issn=1436-4646|url-access=subscription }}</ref> 
* The [[Software:Nucleolus (game theory)|nucleolus]] is the unique point in the intersection of the [[Software:Core (game theory)|core]] and the kernel.<ref name=":0">{{Cite journal |last1=Granot |first1=Daniel |last2=Huberman |first2=Gur |date=1984-07-01 |title=On the core and nucleolus of minimum cost spanning tree games |url=https://doi.org/10.1007/BF02592000 |journal=Mathematical Programming |language=en |volume=29 |issue=3 |pages=323–347 |doi=10.1007/BF02592000 |s2cid=12124235 |issn=1436-4646}}</ref>
* If the underlying network is a tree, then the nucleolus coincides with the kernel.<ref name=":3">{{Cite journal |last1=Granot |first1=D. |last2=Maschler |first2=M. |last3=Owen |first3=G. |last4=Zhu |first4=W. R. |date=1996-06-01 |title=The kernel/nucleolus of a standard tree game |url=https://doi.org/10.1007/BF01247104 |journal=International Journal of Game Theory |language=en |volume=25 |issue=2 |pages=219–244 |doi=10.1007/BF01247104 |s2cid=120669939 |issn=1432-1270}}</ref>

== Computation ==

*One solution in the core can be read directly from any minimum cost spanning tree graph associated with the problem.<ref name=":2" />
* There is an algorithm that requires O(n<sup>2</sup>) elementary operations for computing each additional point in the core.<ref name=":0" />
* In general MCST games, computing the [[Software:Nucleolus (game theory)|nucleolus]] is NP-hard; the proof is by reduction from the minimum [[Set cover problem|set cover problem]].<ref>{{Cite journal |last1=Faigle |first1=Ulrich |last2=Kern |first2=Walter |last3=Kuipers |first3=Jeroen |date=1998-12-01 |title=Computing the nucleolus of min-cost spanning tree games is NP-hard |url=https://doi.org/10.1007/s001820050083 |journal=International Journal of Game Theory |volume=27 |issue=3 |pages=443–450 |doi=10.1007/s001820050083 |s2cid=46730554 |issn=0020-7276}}</ref> There is an algorithm that computes the nucleolus in time O(''n''<sup>3</sup>|''B''|), where B is the set of relevant coalitions (in general, |B|=2<sup>''n''</sup>, but in some special cases, only a subset of the coalitions are relevant).<ref>{{Cite journal |last1=Kuipers |first1=Jeroen |last2=Solymosi |first2=Tamás |last3=Aarts |first3=Harry |date=2000-09-01 |title=Computing the nucleolus of some combinatorially-structured games |url=https://doi.org/10.1007/PL00011385 |journal=Mathematical Programming |language=en |volume=88 |issue=3 |pages=541–563 |doi=10.1007/PL00011385 |s2cid=13149058 |issn=1436-4646}}</ref>
* If the underlying network is a [[Tree (graph theory)|tree]], then the nucleolus can be computed in O(''n''<sup>3</sup>) time, and the [[Shapley value]] can be computed in O(''n'') time.<ref>{{Cite journal
| date=August 1978
| title=Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
| journal=[[Mathematics of Operations Research]]
| language=en
| volume=3
| issue=3
| pages=189–196
| doi=10.1287/moor.3.3.189
| issn=0364-765X}}</ref> The run-time of computing the nucleolus can be reduced to O(''n'' log ''n'') using efficiently mergeable [[Heap (data structure)|heaps]].<ref>{{Cite journal |last=Galil |first=Zvi |date=1980-01-01 |title=Applications of efficient mergeable heaps for optimization problems on trees |url=https://doi.org/10.1007/BF00288535 |journal=Acta Informatica |volume=13 |issue=1 |pages=53–58 |doi=10.1007/BF00288535 |s2cid=39221796 |issn=0001-5903}}</ref> In particular cases, the nucleolus can be computed in O(''n'') time.<ref name=":3" />

== Spanning forest games ==
A '''minimum-cost spanning-forest game''' (MCSF game) is a generalization of an MCST game, in which multiple supply-nodes are allowed. In general, the core of an MCSF game may be empty.<ref name=":1" /> However, if the underlying network is a tree, the core is always non-empty, and core points can be computed in strongly-polynomial time.<ref>{{Cite journal |last1=Granot |first1=Daniel |last2=Granot |first2=Frieda |date=1992 |title=Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem |url=https://www.jstor.org/stable/3690069 |journal=Mathematics of Operations Research |volume=17 |issue=4 |pages=765–780 |doi=10.1287/moor.17.4.765 |jstor=3690069 |issn=0364-765X}}</ref>

== References ==
{{reflist}}

[[Category:Cooperative games]]
[[Category:Spanning tree]]

{{Sourceattribution|Minimum-cost spanning tree game}}