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

点击翻译按钮获取中文摘要

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.