Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games
This work addresses computational challenges in cooperative game theory for applications like network cost allocation, though it is incremental as it builds on existing approximation methods.
The paper tackles the problem of computing the Shapley value in minimum-cost spanning tree games by introducing a saving game framework, resulting in a Monte Carlo-based FPRAS that provides multiplicative approximation.
In this research, we address the problem of computing the Shapley value in minimum-cost spanning tree (MCST) games. We introduce the saving game as a key framework for approximating the Shapley value. By reformulating MCST games into their saving-game counterparts, we obtain structural properties that enable multiplicative (relative-error) approximation. Building on this reformulation, we develop a Monte Carlo based Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for the Shapley value.