Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games
Takumi Jimbo, Tomomi Matsui · 2026
Read Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games by Takumi Jimbo, Tomomi Matsui (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22843.txt.
Introduction
Jimbo and Matsui study how to approximate the Shapley value in minimum cost spanning tree games. Exact computation is hard, so they turn to a related saving game. Recasting the game this way reveals structure that supports relative-error estimates. On that base, they build a Monte Carlo approximation scheme. The scheme is fully polynomial-time and randomized. It gives a principled route to fair cost sharing in network building games.
Catalog record
| CREATOR | Takumi Jimbo, Tomomi Matsui |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46916 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22843
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games Takumi Jimbo, Tomomi Matsui 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. keywords minimum cost spanning tree game, Shapley value, Monte Carlo method, FPRAS August 10, 2026 1 Introduction Minimum spanning tree problems arise in network design settings where a group of agents, located at different nodes, require a service provided by a common source and must share the cost of the connecting network. Beyond the problem of constructing a minimum spanning tree, a central question concerns how the total connection cost should be allocated among the participating agents. Claus and Kleitman 10 first examined cost allocation in the minimum spanning tree. Bird 7 introduced a game-theoretic formulation of minimum spanning tree problems by associating a cooperative cost allocation game with each instance. This line of work laid the foundation for analyzing minimum spanning tree problems by formulating them as a minimum‑cost spanning tree game (MCST game), thereby enabling the use of cooperative game‑theoretic solution concepts to investigate fairness and stability in cost sharing. Further theoretical developments were provided in 13 ; 14 ; 15 . Early works and reviews are due to 1 ; 11 ; 12 ; 8 . For more recent developments, see the reviews 26 ; 25 ; 6 . The Shapley value proposed in 22 is a solution concept in cooperative game theory. Despite its strong normative appeal, computing the Shapley value is computationally challenging. In particular, Ando 4 showed that the exact calculation of the Shapley value in MCST games is #P-hard, even under highly restricted settings, indicating that an efficient exact algorithm is unlikely to exist in general. To circumvent this computational difficulty, existing studies have mainly followed two distinct directions. The first line of research focuses on identifying restricted classes of MCST games for which the Shapley value can be computed exactly in polynomial time 2 ; 4 . The second line of research addresses approximation algorithms for general MCST games. Ando and Takase 3 proposed Monte Carlo based sampling algorithms that approximate the Shapley value with additive-error (absolute-error) guarantees. Furthermore, Takase and Ando 23 introduced a deterministic polynomial-time approximation method based on structural approximations using chordal graphs. While these approaches are applicable to general MCST games, the former relies on random sampling and provides only additive-error guarantees. In this study, we investigate Monte Carlo–based approximation of the Shapley value in MCST games, with a focus on achieving relative‑error guarantees. Existing Monte Carlo methods provide only additive‑error bounds, which can be inadequate when Shapley values vary widely across players or instances. To address this issue, we introduce the saving game, which is a framework that converts the cost formulation into a value formulation based on coalition savings. For the saving game associated with the MCST game, this reformulation enables multiplicative (relative‑error) approximation of the Shapley value. Computational experiments further show that the proposed method exhibits empirical performance consistent with an FPRAS. The rest of this paper is organized as follows. Section 2 introduces the necessary notation and reviews fundamental concepts related to MCST games, saving games, and the Shapley value. Section 3 establishes structural properties of MCST‑saving games, including a characterization of null players and lower bounds on the Shapley value. Section 4 presents the Monte Carlo–based FPRAS and analyzes its computational complexity. Section 5 reports computational experiments demonstrating the practical performance of the proposed method. Section 6 summarizes several results obtained in this paper. 2 Preliminaries This section describes notations, definitions, and some known properties. For any finite set V , let {\rm K}[V] denote the undirected complete graph with vertex set V and edge set E=\left(\begin{array}[]{c}V\\ 2\end{array}\right) . Each edge e=\{i,j\}\in E is assigned a non-negative edge-weight, denoted by w(e) , w(i,j) and/or w(j,i) . A pair \langle{\rm K}[V],\mbox{\boldmath$w$}\rangle is called a non-negatively weighted complete graph . If the edge-weight satisfies \mbox{\boldmath$\widetilde{w}$}\in\{0,1\}^{E} , then \langle{\rm K}[V],\mbox{\boldmath$\widetilde{w}$}\rangle is a 0-1 weighted complete graph . A graph G=(V,E) is called a tree if it is connected and contains no cycles. For a graph G=(V,E) , a subgraph G^{\prime}=(V^{\prime},E^{\prime}) of G is called a spanning tree if V=V^{\prime} and G^{\prime} is a tree. A spanning tree is identified by its set of edges. For any edge subset E^{\prime} of a non-negatively weighted complete graph \langle{\rm K}[V],\mbox{\boldmath$w$}\rangle , the sum of edge weights \sum_{e\in E^{\prime}}w(e) is referred to as the cost of E^{\prime} . A minimum spanning tree problem defined on \langle{\rm K}[V],\mbox{\boldmath$w$}\rangle finds a spanning tree E^{\prime} of {\rm K}[V] that minimizes the cost \sum_{e\in E^{\prime}}w(e) . Let N=\{1,2,\dots,n\} be a set of players. Fix a distinguished node r , referred to as the root , and set N_{r}=\{r,1,2,\dots,n\} . Let \langle{\rm K}[N_{r}],\mbox{\boldmath$w$}\rangle be a non-negatively weighted complete graph. For each non-empty player subset S\subseteq N , let c(S) denote the cost of a minimum spanning tree of the induced subgraph {\rm K}[S\cup\{r\}] with respect to the edge-weight w . We define c(\emptyset)=0. The minimum cost spanning tree game (MCST game) is the cooperative (cost) game given by the pair (N,c) . If the edge-weights are restricted to the set \{0,1\} , then the resulting game (N,c) is called the simple minimum cost spanning tree game (simple MCST game). Given a cooperative cost game, the associated saving game transforms this cost perspective into a value perspective by measuring how much cost the coalition saves compared to acting individually. Formally, we define the saving game (N,v) by the characteristic function v(S)=\sum_{i\in S}c(\{i\})-c(S) , with v(\emptyset)=0. In this paper, we study the saving game associated with the minimum cost spanning tree game (N,c) . This game, denoted by (N,v) , will be referred to as the MCST‑saving game , which was discussed in a seminal paper by Bird 7 . When the underlying game is a simple MCST game, the corresponding saving game will be called the simple MCST‑saving game. The definition of the saving game (N,v) directly implies that v(\{j\})=c(\{j\})-c(\{j\})=0 (\forall j\in N) . The MCST-saving game satisfies that v(S)=\sum_{j\in S}w(r,j)-c(S) (\emptyset\neq\forall S\subseteq N) . To begin with, we note that the MCST-saving game is nonnegative and super-additive (see 7 ). For any non-empty set S\subseteq N, the edge set \{\{r,i\}\mid i\in S\} forms a spanning tree on {\rm K}[S\cup\{r\}]. Thus, v(S)=\sum_{i\in S}w(r,i)-c(S)\geq 0. Moreover, for any disjoint pair of coalitions S,T\subseteq N , we have v(S\cup T)=\sum_{i\in S\cup T}c({i})-c(S\cup T)\geq\sum_{i\in S}c({i})-c(S)+\sum_{i\in T}c({i})-c(T)=v(S)+v(T), since the cost function c is sub-additive with respect to spanning trees. The non-negativity together with super-additivity implies the monotonicity of v . We see that, if N\supseteq T\supseteq S , then v(T)=v(T\setminus S\cup S)\geq v(T\setminus S)+v(S)\geq v(S). The Shapley value, formally defined below, is a payoff vector introduced by Shapley 22 . A permutation \pi of players in N is a bijection \pi:\{1,2,\ldots,n\}\rightarrow N , and we write \pi(j) for the player in