Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games

Read full text Summarise with VIRAT
Authors: Takumi Jimbo, Tomomi Matsui
Cited by: 0
References: 25

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

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.

Fields of Study & Subjects

Game Theory and Voting Systems Complexity and Algorithms in Graphs Game Theory and Applications

Publication details

Journal / source
arXiv (Cornell University)
Publication date
24 March 2026
Language
EN
Document type
Preprint