# Bounding the Estimation Error of Sampling-based Shapley Value Approximation

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2013.

## Built on by (most cited first, 30 of 58)

- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning](https://mlsanity.com/paper/2109.02053/) (2021)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [Data-OOB: Out-of-bag Estimate as a Simple and Efficient Data Value](https://mlsanity.com/paper/2304.07718/) (2023)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Attention Flows are Shapley Value Explanations](https://mlsanity.com/paper/2105.14652/) (2021)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Improving Fairness for Data Valuation in Horizontal Federated Learning](https://mlsanity.com/paper/2109.09046/) (2021)
- [Incentivizing Collaboration in Machine Learning via Synthetic Data Rewards](https://mlsanity.com/paper/2112.09327/) (2021)
- [Data Pricing in Machine Learning Pipelines](https://mlsanity.com/paper/2108.07915/) (2021)
- [An Economic Solution to Copyright Challenges of Generative AI](https://mlsanity.com/paper/2404.13964/) (2024)
- [Variance reduced Shapley value estimation for trustworthy data valuation](https://mlsanity.com/paper/2210.16835/) (2022)
- [FedCCEA : A Practical Approach of Client Contribution Evaluation for Federated Learning](https://mlsanity.com/paper/2106.02310/) (2021)
- [Helpful or Harmful Data? Fine-tuning-free Shapley Attribution for Explaining Language Model Predictions](https://mlsanity.com/paper/2406.04606/) (2024)
- [Feature Inference Attack on Shapley Values](https://mlsanity.com/paper/2407.11359/) (2024)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [Differentially Private Shapley Values for Data Evaluation](https://mlsanity.com/paper/2206.00511/) (2022)
- [Attention Mechanisms Don't Learn Additive Models: Rethinking Feature Importance for Transformers](https://mlsanity.com/paper/2405.13536/) (2024)
- [Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members](https://mlsanity.com/paper/2208.08798/) (2022)
- [Probably Approximate Shapley Fairness with Applications in Machine Learning](https://mlsanity.com/paper/2212.00630/) (2022)
- [A Survey of Privacy-Preserving Model Explanations: Privacy Risks, Attacks, and Countermeasures](https://mlsanity.com/paper/2404.00673/) (2024)
- [STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2304.07520/) (2023)
- [SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification of Top-k Features](https://mlsanity.com/paper/2307.04850/) (2023)
- [DemoShapley: Valuation of Demonstrations for In-Context Learning](https://mlsanity.com/paper/2410.07523/) (2024)
- [A Coalition Formation Game Approach for Personalized Federated Learning](https://mlsanity.com/paper/2202.02502/) (2022)
- [Shapley Based Residual Decomposition for Instance Analysis](https://mlsanity.com/paper/2305.18818/) (2023)
- [Generating Effective Ensembles for Sentiment Analysis](https://mlsanity.com/paper/2402.16700/) (2024)

## Abstract (arXiv)

The Shapley value is arguably the most central normative solution concept in cooperative game theory. It specifies a unique way in which the reward from cooperation can be "fairly" divided among players. While it has a wide range of real world applications, its use is in many cases hampered by the hardness of its computation. A number of researchers have tackled this problem by (i) focusing on classes of games where the Shapley value can be computed efficiently, or (ii) proposing representation formalisms that facilitate such efficient computation, or (iii) approximating the Shapley value in certain classes of games. For the classical textitcharacteristic function representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro textitet al. citecastro. While this algorithm provides a bound on the approximation error, this bound is textitasymptotic, meaning that it only holds when the number of samples increases to infinity. On the other hand, when a finite number of samples is drawn, an unquantifiable error is introduced, meaning that the bound no longer holds. With this in mind, we provide non-asymptotic bounds on the estimation error for two cases: where (i) the textitvariance, and (ii) the textitrange, of the players' marginal contributions is known. Furthermore, for the second case, we show that when the range is significantly large relative to the Shapley value, the bound can be improved (from O(fracrm) to O(√fracrm)). Finally, we propose, and demonstrate the effectiveness of using stratified sampling for improving the bounds further.