Development of Approximation Algorithms for the Shapley Value of Minimum Cost Spanning Tree Games

在这项研究中，我们提出了两种算法来计算最小费用生成树对策的Shapley值。第一种是随机算法，给定一个任意最小代价的生成树博弈，在伪多项式时间内以给定的精度输出其Shapley值的近似值。在给定一个最小代价生成树博弈的情况下，另一种算法首先用树度量近似关联博弈的代价函数，然后计算与近似代价函数关联的博弈的精确Shapley值。数值实验表明，当给定的代价函数接近树的度量时，后一种算法的性能较好。

In this research, we developed two algorithms for computing the Shapley value of minimum cost spanning tree games. The first one is a randomized algorithm which, given an arbitrary minimum cost spanning tree game, outputs an approximation of its Shapley value with given precision in pseudo-polynomial time. Given a minimum cost spanning tree game, the other algorithm first approximates the cost function of the associated game by a tree metric and then it computes the exact Shapley value of the game associated with the approximated cost function. Numerical experiments show that the latter algorithm performs well when the given cost function is close to a tree metric.