# Statistical Cost Sharing

arXiv: https://arxiv.org/abs/1703.03111 · HTML: https://mlsanity.com/paper/1703.03111/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2017.

## Built on by (most cited first, 8 of 8)

- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [Improving Cooperative Game Theory-based Data Valuation via Data Utility Learning](https://mlsanity.com/paper/2107.06336/) (2021)
- [On Blame Attribution for Accountable Multi-Agent Sequential Decision Making](https://mlsanity.com/paper/2107.11927/) (2021)
- [Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members](https://mlsanity.com/paper/2208.08798/) (2022)
- [In-Context Credit Assignment via the Core](https://mlsanity.com/paper/2605.06920/) (2026)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [Fair Effect Attribution in Parallel Online Experiments](https://mlsanity.com/paper/2210.08338/) (2022)
- [varepsilon-fractional Core Stability in Hedonic Games](https://mlsanity.com/paper/2311.11101/) (2023)

## Abstract (arXiv)

We study the cost sharing problem for cooperative games in situations where the cost function C is not available via oracle queries, but must instead be derived from data, represented as tuples (S, C(S)), for different subsets S of players. We formalize this approach, which we call statistical cost sharing, and consider the computation of the core and the Shapley value, when the tuples are drawn from some distribution D. Previous work by Balcan et al. in this setting showed how to compute cost shares that satisfy the core property with high probability for limited classes of functions. We expand on their work and give an algorithm that computes such cost shares for any function with a non-empty core. We complement these results by proving an inapproximability lower bound for a weaker relaxation. We then turn our attention to the Shapley value. We first show that when cost functions come from the family of submodular functions with bounded curvature, kappa, the Shapley value can be approximated from samples up to a √1 - kappa factor, and that the bound is tight. We then define statistical analogues of the Shapley axioms, and derive a notion of statistical Shapley value. We show that these can always be approximated arbitrarily well for general functions over any distribution D.