# Exactly Computing do-Shapley Values

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 6 Feb 2026.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [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)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Asymmetric Shapley values: incorporating causal knowledge into model-agnostic explainability](https://mlsanity.com/paper/1910.06358/) (2019)
- [Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models](https://mlsanity.com/paper/2011.01625/) (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)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [TALENT: A Tabular Analytics and Learning Toolbox](https://mlsanity.com/paper/2407.04057/) (2024)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions](https://mlsanity.com/paper/2405.10852/) (2024)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [SVARM-IQ: Efficient Approximation of Any-order Shapley Interactions through Stratification](https://mlsanity.com/paper/2401.13371/) (2024)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes](https://mlsanity.com/paper/2508.14499/) (2025)
- [Practical do-Shapley Explanations with Estimand-Agnostic Causal Inference](https://mlsanity.com/paper/2509.20211/) (2025)
- [Amortized Linear-time Exact Shapley Value for Product-Kernel Methods](https://mlsanity.com/paper/2505.16516/) (2025)

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

- [cc-Shapley: Measuring Multivariate Feature Importance Needs Causal Context](https://mlsanity.com/paper/2602.20396/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Decision-Aware Proximal Bridge Learning for Optimal Treatment Selection](https://mlsanity.com/paper/2605.16989/) (2026)

## Abstract (arXiv)

Structural Causal Models (SCM) are a powerful framework for describing complicated dynamics across the natural sciences. A particularly elegant way of interpreting SCMs is do-Shapley, a game-theoretic method of quantifying the average effect of d variables across exponentially many interventions. Like Shapley values, computing do-Shapley values generally requires evaluating exponentially many terms. The foundation of our work is a reformulation of do-Shapley values in terms of the irreducible sets of the underlying SCM. Leveraging this insight, we can exactly compute do-Shapley values in time linear in the number of irreducible sets r, which itself can range from d to 2d depending on the graph structure of the SCM. Since r is unknown a priori, we complement the exact algorithm with an estimator that, like general Shapley value estimators, can be run with any query budget. As the query budget approaches r, our estimators can produce more accurate estimates than prior methods by several orders of magnitude, and, when the budget reaches r, return the Shapley values up to machine precision. Beyond computational speed, we also reduce the identification burden: we prove that non-parametric identifiability of do-Shapley values requires only the identification of interventional effects for the d singleton coalitions, rather than all classes.