🤖 machine learning

Shapley Value Approximation Based on k-Additive Games

Original authors: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Published 2026-05-13

📖 5 min read🧠 Deep dive

Original authors: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Splitting the Pie Fairly

Imagine you and a group of friends are running a lemonade stand. At the end of the day, you make a profit. The big question is: Who deserves how much of the money?

Did the person who squeezed the lemons do the most work?
Did the person who stood at the sign attract the most customers?
Did the person who brought the sugar make the drink taste better?

In the world of machine learning (AI), this is the same problem. An AI model makes a prediction (like diagnosing a disease or guessing if an email is spam). We want to know: Which specific piece of data (feature) was responsible for that prediction?

The "Shapley Value" is a mathematical formula invented by a game theorist named Lloyd Shapley. It is the gold standard for fairness. It calculates exactly how much each "player" (feature) contributed to the final result by looking at every possible combination of players.

The Problem: The Math is Too Hard

Here is the catch: To calculate the Shapley Value perfectly, you have to check every single possible team combination.

If you have 10 friends, there are 1,024 combinations.
If you have 20 friends, there are over 1 million combinations.
If you have 50 friends, the number is so huge it would take longer than the age of the universe to calculate.

Because modern AI models often have hundreds or thousands of features, calculating the exact Shapley Value is impossible. It's like trying to count every grain of sand on a beach to split the beach's value fairly. We need a shortcut, but the shortcut has to be accurate enough to be trusted.

The Solution: SVAkADD (The "Smart Surrogate" Method)

The authors of this paper propose a new method called SVAkADD. Instead of trying to count every grain of sand, they build a simplified model (a "surrogate") that mimics the real game but is much easier to solve.

Here is how they do it, using a creative analogy:

1. The "Teamwork" Assumption (k-Additivity)

The authors assume that while everyone's contribution matters, complex teamwork usually stops at a certain size.

1-Additive: Only individual effort matters. (You are good at your job, regardless of who you work with).
2-Additive: Pairs matter. (You and your best friend work great together, but a group of three might get chaotic).
3-Additive: Small groups matter. (A trio works well, but a committee of ten is too messy to have a unique "magic" effect).

The paper calls this k-additivity. They assume that interactions between 4, 5, or 10 people at once are so rare or negligible that we can ignore them. This turns a mathematically impossible problem into a manageable one.

2. The "Taste Test" (Sampling)

Instead of testing every possible lemonade recipe (coalition), the researchers take a random sample of recipes.

They mix a few specific combinations of ingredients.
They taste the result (calculate the value).
They use these few taste tests to "fit" their simplified model.

3. The "Magic Formula" (The Optimization)

Once they have the taste tests, they solve a specific math puzzle (an optimization problem) to find the parameters of their simplified model.

The Cool Part: The authors proved mathematically that if they choose the right "weights" for their taste tests, the answer they get from this simplified model is exactly the same as the perfect Shapley Value would be, if they had tested every single combination.
Even though they are ignoring complex 10-person interactions, the math guarantees that the final "fair share" numbers come out correct for the scenarios they tested.

Why This is Better Than Other Shortcuts

Other methods try to guess the answer by randomly guessing and averaging (like rolling dice many times).

The Paper's Method: It's like building a blueprint based on a few measurements. Once the blueprint is built, you can instantly read off the answer.
The Result: The paper shows that their method converges (gets accurate) much faster than the random guessing methods. You need fewer "taste tests" (samples) to get a reliable answer.

What They Found (The Results)

The researchers tested this on real-world data sets (like predicting Titanic survival, wine quality, or breast cancer detection).

Speed vs. Accuracy: They found that assuming interactions happen in groups of 3 (3-additive) was usually the "sweet spot." It was complex enough to be accurate but simple enough to be fast.
Beating the Competition: In many tests, their method (SVAkADD) was more accurate than the current top methods (like KernelSHAP) when given the same amount of computing time or data samples.
No Special Rules Needed: This method works on any type of game or AI model. It doesn't care if the data is about medical records, stock prices, or sports stats.

Summary in One Sentence

The paper introduces a new way to fairly split credit among AI features by building a simplified "teamwork model" that ignores overly complex group interactions, allowing us to calculate fair shares quickly and accurately without needing to check every single possibility.

Technical Summary: Shapley Value Approximation Based on k-Additive Games

Problem Statement

The Shapley value is the standard solution for fair division problems, widely adopted in Explainable AI (XAI) to quantify the individual contribution of features or data points to a model's performance. However, its exact computation requires evaluating all $2^n$ possible coalitions of $n$ players, resulting in exponential computational complexity. This makes exact calculation infeasible for models with a moderate number of features or when evaluating complex, resource-intensive models. Consequently, approximation methods are necessary, but existing approaches often struggle to balance computational efficiency with the accuracy of the resulting importance scores.

Methodology: SVAkADD

The authors propose SVAkADD (Shapley Value Approximation under k-additivity), a novel method that approximates Shapley values by fitting a structured k-additive surrogate game to a sampled subset of coalition values.

Core Concept: k-Additivity

Instead of estimating the Shapley value directly via Monte Carlo sampling of marginal contributions, SVAkADD assumes the underlying game can be approximated by a k-additive game. In such a game, interaction indices (Shapley interactions) for coalitions larger than size $k$ are assumed to be zero.

Representation: The value function $\nu_k$ of the surrogate game is expressed as a linear transformation of Shapley interaction indices $I(B)$ for all coalitions $B$ where $|B| \leq k$ .
Parameter Reduction: This assumption drastically reduces the number of parameters required to define the game from $2^n$ to a polynomial number (e.g., $O(n^k)$ ), making the optimization tractable.

Optimization Framework

The method formulates the approximation as a constrained weighted least squares problem:

Objective: Minimize the weighted squared error between the observed coalition values $\nu(A)$ from the original game and the values predicted by the k-additive surrogate $\nu_k(A)$ .
Constraints: The optimization enforces the efficiency axiom, ensuring that the sum of the surrogate's Shapley values equals the difference between the grand coalition's worth and the empty set's worth ( $\nu(N) - \nu(\emptyset)$ ).
Weighting: The authors analytically derive specific weights $w^*_A = \binom{n-2}{|A|-1}^{-1}$ for the least squares problem. They prove that if all coalitions were observed, solving this specific optimization yields the exact Shapley values, regardless of whether the original game is truly k-additive.

Algorithm

The SVAkADD algorithm proceeds as follows:

Sampling: It deterministically evaluates the empty set $\emptyset$ and the grand coalition $N$ . It then samples $T-2$ additional coalitions from the power set (excluding $\emptyset$ and $N$ ) based on a probability distribution proportional to the derived weights $w^*_A$ .
Fitting: It solves the constrained weighted least squares problem using the sampled data to estimate the interaction indices $I(B)$ for $|B| \leq k$ .
Extraction: The Shapley values for the surrogate game are immediately obtained as the singleton interaction indices ( $I(\{i\})$ ), which serve as the estimates for the original game.

Key Contributions

Novel Approximation Method: Introduction of SVAkADD, which fits a k-additive surrogate game to sampled data, offering a structured alternative to direct marginal contribution sampling.
Theoretical Soundness: Analytical proof that for $k=1, 2, 3$ , the proposed weighted least squares optimization yields the exact Shapley values when the full set of coalitions is observed. This establishes that k-additivity is a tool for approximation rather than a restrictive assumption on the game's structure.
Model and Domain Agnosticism: The method does not require specific structural properties of the value function, making it applicable to any cooperative game, including both local and global feature explanations in machine learning.
Empirical Evaluation: Comprehensive comparison against state-of-the-art baselines (KernelSHAP, Stratified SVARM, Stratified sampling) across various datasets and explanation types (global, local, unsupervised).

Experimental Results

The authors evaluated SVAkADD on datasets ranging from 9 to 14 features across global, local, and unsupervised tasks.

Convergence: The method demonstrates competitive performance. While it may exhibit higher error at very low sample budgets compared to some baselines, it converges faster to the exact Shapley values as the budget increases, particularly for local attribution tasks on the Adult and ImageNet datasets.
Choice of $k$ : The experiments highlight a trade-off between flexibility and convergence speed.
- Low $k$ (1 or 2) often converges slowly due to insufficient flexibility to model complex feature interactions.
- Higher $k$ (3 or 4) generally converges significantly faster and outperforms lower-order models after a few samples.
- The authors suggest $k=3$ as a preferable default, offering a good balance between error reduction and the number of required parameters.
Comparison: SVAkADD consistently competes with or outperforms KernelSHAP and Stratified SVARM, particularly in scenarios requiring high precision with moderate sample budgets.

Significance and Claims

The paper claims that SVAkADD provides a theoretically grounded and practically effective approach to Shapley value approximation. By leveraging the structure of k-additive games, the method transforms the estimation problem into a polynomial-time optimization that guarantees exact recovery under specific weighting conditions.

The authors emphasize that their approach is model-agnostic and domain-independent, capable of handling any cooperative game formulation. They conclude that while no single approximation method dominates across all scenarios (depending on dataset, task, and budget), SVAkADD offers a robust alternative that leverages the theoretical properties of Shapley interactions to achieve high accuracy. The paper also notes that the method naturally provides estimates for interaction effects (redundancy or complementarity) when $k \geq 2$ , offering additional interpretability beyond individual feature importance.