# Approximating the Shapley Value without Marginal Contributions

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 18 of 18)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation](https://mlsanity.com/paper/1903.10992/) (2019)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [Neuron Shapley: Discovering the Responsible Neurons](https://mlsanity.com/paper/2002.09815/) (2020)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Estimation of the Shapley value by ergodic sampling](https://mlsanity.com/paper/1906.05224/) (2019)
- [Antithetic and Monte Carlo kernel estimators for partial rankings](https://mlsanity.com/paper/1807.00400/) (2018)

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

- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions](https://mlsanity.com/paper/2405.10852/) (2024)
- [Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution](https://mlsanity.com/paper/2401.15866/) (2024)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Helpful or Harmful Data? Fine-tuning-free Shapley Attribution for Explaining Language Model Predictions](https://mlsanity.com/paper/2406.04606/) (2024)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation](https://mlsanity.com/paper/2306.02071/) (2023)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [Efficient Shapley Value-based Non-Uniform Pruning of Large Language Models](https://mlsanity.com/paper/2505.01731/) (2025)
- [PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression](https://mlsanity.com/paper/2601.18608/) (2026)
- [Improving the Weighting Strategy in KernelSHAP](https://mlsanity.com/paper/2410.04883/) (2024)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)
- [Multiply-Robust Causal Change Attribution](https://mlsanity.com/paper/2404.08839/) (2024)
- [Prediction via Shapley Value Regression](https://mlsanity.com/paper/2505.04775/) (2025)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [Solving the enigma: Enhancing faithfulness and comprehensibility in explanations of deep networks](https://mlsanity.com/paper/2405.10008/) (2024)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [DUPRE: Data Utility Prediction for Efficient Data Valuation](https://mlsanity.com/paper/2502.16152/) (2025)
- [Energy-Based Model for Accurate Estimation of Shapley Values in Feature Attribution](https://mlsanity.com/paper/2404.01078/) (2024)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [Learning the Expected Core of Strictly Convex Stochastic Cooperative Games](https://mlsanity.com/paper/2402.07067/) (2024)
- [Antithetic Sampling for Top-k Shapley Identification](https://mlsanity.com/paper/2504.02019/) (2025)
- [Owen Sampling Accelerates Contribution Estimation in Federated Learning](https://mlsanity.com/paper/2508.21261/) (2025)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [How important are the genes to explain the outcome - the asymmetric Shapley value as an honest importance metric for high-dimensional features](https://mlsanity.com/paper/2603.05317/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)

## Abstract (arXiv)

The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence. Its meaningfulness is due to axiomatic properties that only the Shapley value satisfies, which, however, comes at the expense of an exact computation growing exponentially with the number of agents. Accordingly, a number of works are devoted to the efficient approximation of the Shapley value, most of them revolve around the notion of an agent's marginal contribution. In this paper, we propose with SVARM and Stratified SVARM two parameter-free and domain-independent approximation algorithms based on a representation of the Shapley value detached from the notion of marginal contribution. We prove unmatched theoretical guarantees regarding their approximation quality and provide empirical results including synthetic games as well as common explainability use cases comparing ourselves with state-of-the-art methods.