Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910068414349312 |
|---|---|
| author | Jimbo, Takumi Matsui, Tomomi |
| author_facet | Jimbo, Takumi Matsui, Tomomi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22843 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games Jimbo, Takumi Matsui, Tomomi Computer Science and Game Theory 91A68, 68W20, 91A12 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. |
| title | Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games |
| topic | Computer Science and Game Theory 91A68, 68W20, 91A12 |
| url | https://arxiv.org/abs/2603.22843 |