Computing the Shapley value for minimum-cost spanning tree games is #P-hard. But expressing the game as savings rather than costs makes it polynomially approximable.
Jimbo and Matsui (arXiv:2603.22843) construct a fully polynomial-time randomized approximation scheme for the Shapley value in MCST games by converting them into saving games. The MCST game assigns each coalition its minimum-cost spanning tree — the cheapest way to connect all coalition members. The Shapley value distributes the total cost fairly, accounting for each player's marginal contribution. Computing it exactly requires summing over all n! permutations.
Note (2026-11-12; read against the paper's full text): the guarantee is stated most cleanly for simple games, where every edge weight is 0 or 1. There the paper bounds each marginal contribution by n minus 1, shows that every player who is not a null player has a Shapley value of at least 1 over n(n-1), identifies null players (whose value is exactly zero) in linear time, and gets a sample size of at least n squared times (n-1) to the fourth times ln(2/delta) over 2 epsilon squared. The lower bound on non-zero values is what turns an additive error into a relative one. The essay does not mention it and credits monotonicity alone; the paper derives monotonicity from non-negativity and super-additivity, which follow from sub-additivity of the spanning-tree cost. General non-negative weights are handled in a later section by splitting the game into simple games under an assumption I did not read in full. The paper also says existing Monte Carlo methods on the cost game give additive-error guarantees only, which is narrower than the essay's statement that sampling the cost game yields no polynomial guarantees.
The saving game reformulation measures not the cost of connecting but the savings relative to each player connecting alone. This change of variable preserves the Shapley value (up to a known shift) but reveals structural properties that the cost formulation obscures. The savings are non-negative and monotone — adding a player to a coalition never decreases total savings, because more connection options can only help. The cost game doesn't have this property directly.
The structural properties of the saving game enable a Monte Carlo FPRAS: sample random permutations, compute marginal savings for each sample, average. The approximation ratio is multiplicative, and the sample complexity is polynomial in 1/ε and 1/δ. The conversion from cost to savings is what makes this work — the same sampling strategy on the cost game doesn't yield polynomial guarantees because the cost function lacks the structural properties the approximation bound requires.
The pattern: exact computation is hard, but the right representation of the same problem makes approximation tractable. The game hasn't changed. What changed is how you measure it.