# Estimation of the Shapley value by ergodic sampling

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

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

- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [Capturing the Temporal Dependence of Training Data Influence](https://mlsanity.com/paper/2412.09538/) (2024)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [An Economic Solution to Copyright Challenges of Generative AI](https://mlsanity.com/paper/2404.13964/) (2024)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Fast Data Attribution for Text-to-Image Models](https://mlsanity.com/paper/2511.10721/) (2025)
- [Improving the Weighting Strategy in KernelSHAP](https://mlsanity.com/paper/2410.04883/) (2024)
- [In-Run Data Shapley for Adam Optimizer](https://mlsanity.com/paper/2602.00329/) (2026)
- [Accelerated Shapley Value Approximation for Data Evaluation](https://mlsanity.com/paper/2311.05346/) (2023)
- [Antithetic Sampling for Top-k Shapley Identification](https://mlsanity.com/paper/2504.02019/) (2025)

## Abstract (arXiv)

The idea of approximating the Shapley value of an n-person game by Monte Carlo simulation was first suggested by Mann and Shapley (1960) and they also introduced four different heuristical methods to reduce the estimation error. Since 1960, several statistical methods have been developed to reduce the standard deviation of the estimate. In this paper, we develop an algorithm that uses a pair of negatively correlated samples to reduce the variance of the estimate. Although the observations generated are not independent, the sample is ergodic (obeys the strong law of large numbers), hence the name "ergodic sampling". Unlike Shapley and Mann, we do not use heuristics, the algorithm uses a small sample to learn the best ergodic transformation for a given game. We illustrate the algorithm on eight games with different characteristics to test the performance and understand how the proposed algorithm works. The experiments show that this method has at least as low variance as an independent sample, and in five test games, it significantly improves the quality of the estimation, up to 75 percent.