# A Multilinear Sampling Algorithm to Estimate Shapley Values

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

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

- [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)
- [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)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution](https://mlsanity.com/paper/2401.15866/) (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)
- [HarsanyiNet: Computing Accurate Shapley Values in a Single Forward Propagation](https://mlsanity.com/paper/2304.01811/) (2023)
- [A Comparative Study of Methods for Estimating Conditional Shapley Values and When to Use Them](https://mlsanity.com/paper/2305.09536/) (2023)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning](https://mlsanity.com/paper/2106.02938/) (2021)
- [Fast Data Attribution for Text-to-Image Models](https://mlsanity.com/paper/2511.10721/) (2025)
- [Probably Approximate Shapley Fairness with Applications in Machine Learning](https://mlsanity.com/paper/2212.00630/) (2022)
- [MRxaI: Black-Box Explainability for Image Classifiers in a Medical Setting](https://mlsanity.com/paper/2311.14471/) (2023)
- [Improving the Weighting Strategy in KernelSHAP](https://mlsanity.com/paper/2410.04883/) (2024)
- [A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values](https://mlsanity.com/paper/2506.05216/) (2025)
- [Using Stratified Sampling to Improve LIME Image Explanations](https://mlsanity.com/paper/2403.17742/) (2024)
- [In-Run Data Shapley for Adam Optimizer](https://mlsanity.com/paper/2602.00329/) (2026)
- [Shapley Curves: A Smoothing Perspective](https://mlsanity.com/paper/2211.13289/) (2022)
- [Game-theoretic Counterfactual Explanation for Graph Neural Networks](https://mlsanity.com/paper/2402.06030/) (2024)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Shapley Value Approximation Based on k-Additive Games](https://mlsanity.com/paper/2502.04763/) (2025)
- [Energy-Based Model for Accurate Estimation of Shapley Values in Feature Attribution](https://mlsanity.com/paper/2404.01078/) (2024)
- [WeShap: Weak Supervision Source Evaluation with Shapley Values](https://mlsanity.com/paper/2406.11010/) (2024)
- [AlphaToken: Decoupling Adaptation and Stability for Path-Aware Response Token Valuation in LLM Post-Training](https://mlsanity.com/paper/2606.01635/) (2026)
- [MBExplainer: Multilevel bandit-based explanations for downstream models with augmented graph embeddings](https://mlsanity.com/paper/2411.00287/) (2024)
- [Antithetic Sampling for Top-k Shapley Identification](https://mlsanity.com/paper/2504.02019/) (2025)
- [ShaTS: A Shapley-based Explainability Method for Time Series Artificial Intelligence Models applied to Anomaly Detection in Industrial Internet of Things](https://mlsanity.com/paper/2506.01450/) (2025)

## Abstract (arXiv)

Shapley values are great analytical tools in game theory to measure the importance of a player in a game. Due to their axiomatic and desirable properties such as efficiency, they have become popular for feature importance analysis in data science and machine learning. However, the time complexity to compute Shapley values based on the original formula is exponential, and as the number of features increases, this becomes infeasible. Castro et al. [1] developed a sampling algorithm, to estimate Shapley values. In this work, we propose a new sampling method based on a multilinear extension technique as applied in game theory. The aim is to provide a more efficient (sampling) method for estimating Shapley values. Our method is applicable to any machine learning model, in particular for either multi-class classifications or regression problems. We apply the method to estimate Shapley values for multilayer perceptrons (MLPs) and through experimentation on two datasets, we demonstrate that our method provides more accurate estimations of the Shapley values by reducing the variance of the sampling statistics.