# Shapley Value Approximation Based on k-Additive Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 7 Feb 2025.

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

- [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)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Trustworthy AI: From Principles to Practices](https://mlsanity.com/paper/2110.01167/) (2021)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (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)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [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)
- [KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions](https://mlsanity.com/paper/2405.10852/) (2024)
- [Evaluating and Rewarding Teamwork Using Cooperative Game Abstractions](https://mlsanity.com/paper/2006.09538/) (2020)
- [Unsupervised Features Ranking via Coalitional Game Theory for Categorical Data](https://mlsanity.com/paper/2205.09060/) (2022)

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

- [PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression](https://mlsanity.com/paper/2601.18608/) (2026)
- [Antithetic Sampling for Top-k Shapley Identification](https://mlsanity.com/paper/2504.02019/) (2025)

## Abstract (arXiv)

The Shapley value is the prevalent solution for fair division problems in which a payout is to be divided among multiple agents. By adopting a game-theoretic view, the idea of fair division and the Shapley value can also be used in machine learning to quantify the individual contribution of features or data points to the performance of a predictive model. Despite its popularity and axiomatic justification, the Shapley value suffers from a computational complexity that scales exponentially with the number of entities involved, and hence requires approximation methods for its reliable estimation. We propose SVAkADD, a novel approximation method that fits a k-additive surrogate game. By taking advantage of k-additivity, we are able to elicit the exact Shapley values of the surrogate game and then use these values as estimates for the original fair division problem. The efficacy of our method is evaluated empirically and compared to competing methods.