Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases
Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases
复制标题
最小成本生成树博弈的 Shapley 值的计算：
DOI：
10.1007/s13160-012-0078-9
复制
发表时间：
2012
影响因子：
0.9
通讯作者：
K. Ando
中科院分区：
文献类型：
--
作者：
Hirofumi Fukuyama;Kazuyuki Sekitani;K. Ando
我们证明了即使代价函数被限制为{0，1}-值，计算最小代价生成树博弈的Shapley值也是P-困难的。这个证明是通过计算无向图的最小2-端割点的个数的一个约简得到的，它是P-完全的。我们还研究了Shapley值可以在多项式时间内计算的最小成本生成树游戏。我们证明，如果给定网络的成本函数是一个子树距离，这是一个树度量的推广，那么相关的最小成本生成树游戏的Shapley值可以在O（n4）时间内计算，其中是玩家的数量。
We show that computing the Shapley value of minimum cost spanning tree games is #P-hard even if the cost functions are restricted to be {0,1}-valued. The proof is by a reduction from counting the number of minimum 2-terminal vertex cuts of an undirected graph, which is #P-complete. We also investigate minimum cost spanning tree games whose Shapley values can be computed in polynomial time. We show that if the cost function of the given network is a subtree distance, which is a generalization of a tree metric, then the Shapley value of the associated minimum cost spanning tree game can be computed in O(n4) time, wherenis the number of players.