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.
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.