A PSA on Shapley Values
10 min read
Lundberg and Lee introduced Shapley values to machine learning as SHAP [LL, NeurIPS ’17]. Discussions of the methods often conflate two objects: the game, a modeling choice, and the Shapley value, a property of that game. The game assigns a value to each group of players, called a coalition. The Shapley rule uses those values to divide the total gain among the players. Changing what a group is allowed to use, or how its value is measured, changes the game even if the Shapley rule stays the same.
Once the game is chosen, we still need to estimate its Shapley values without evaluating every group. Many methods fit a cheaper surrogate to a sample of game evaluations and compute the surrogate’s Shapley values exactly. The approximation is in the fitted game.
TL;DR: If you have a game and need to estimate its Shapley value, fit gradient boosted trees (e.g., XGBoost or LightGBM) to your coalition samples and run TreeSHAP [LE+, NMI ’20] on the fitted function.
The Value and the Game
What exactly is the Shapley value of a game? A game on \(d\) players \([d] = \{1, \dots, d\}\) is a set function \(f : 2^{[d]} \to \mathbb{R}\) assigning a value to every coalition \(S \subseteq [d]\). To split the value fairly, imagine seating the players in a uniformly random order: the Shapley value assigns each one the jump in value when they sit down, their marginal contribution to the players already seated.
For a general game, the Shapley value of player \(i\) is a weighted average of \(i\)’s marginal contributions:
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} \frac{|S|!\,(d - |S| - 1)!}{d!}\, \big( f(S \cup \{i\}) - f(S) \big), \]
where the weight is the probability that a uniformly random ordering of the players seats exactly the coalition \(S\) before player \(i\). It is the unique rule satisfying a short list of fairness axioms [Shapley, ’53]: the values sum to \(f([d]) - f(\emptyset)\); interchangeable players are treated equally; a player who never changes the value gets nothing; and the rule is linear across games. The estimator template below relies on the last property, linearity:
\[ \phi_i(\alpha f + \alpha' f') = \alpha\, \phi_i(f) + \alpha'\, \phi_i(f') \qquad \text{for any games } f, f' \text{ and scalars } \alpha, \alpha'. \]
The definition is a fixed linear combination of the \(2^d\) values of \(f\), so linearity holds term by term.
The definition does not specify the game; choosing \(f\) is the modeling decision.
The Game Is a Modeling Choice
Where does the game come from? Take the most common application, feature attribution. A trained model \(h\) maps a feature vector \(\mathbf{x} \in \mathbb{R}^d\) to a prediction, and we want to explain \(h(\mathbf{x})\) at one particular input. The players are the features, and we would like \(f(S)\) to mean “the prediction when only the features in \(S\) are revealed”. But \(h\) has no notion of a missing feature, so we must put something in the hidden slots, and every convention is a different game:
\[ f_{\text{base}}(S) = h(\mathbf{x}_S; \mathbf{b}_{S^c}), \qquad f_{\text{marg}}(S) = \mathbb{E}\big[ h(\mathbf{x}_S; \mathbf{X}_{S^c}) \big], \qquad f_{\text{cond}}(S) = \mathbb{E}\big[ h(\mathbf{X}) \mid \mathbf{X}_S = \mathbf{x}_S \big]. \]
Here \(h(\mathbf{x}_S; \cdot)\) pins the features in \(S\) to their observed values and fills the rest three ways. The baseline game substitutes a fixed reference input \(\mathbf{b} \in \mathbb{R}^d\). The marginal game averages the model over a random feature vector \(\mathbf{X} \in \mathbb{R}^d\) drawn from the data distribution, ignoring the correlation between hidden and revealed features. The conditional game averages over the hidden features conditioned on what was revealed.
To see how much the choice matters, take three fair-coin features in which \(x_2\) is a duplicate of \(x_1\) (the two always agree) while \(x_3\) is independent. The model \(h(\mathbf{x}) = x_1 + x_3\) never touches \(x_2\), the input is \(\mathbf{x} = (1, 1, 1)\), and the reference is \(\mathbf{b} = (0, 0, 0)\).
In the plot, all three answers are correct: they answer three different questions. Once translated, most “SHAP is wrong” arguments are arguments about which \(f\) matches the question being asked. And feature attribution is only one source of games; many more appear throughout machine learning, including:
data valuation where \(f(S)\) is the test performance of a model retrained on the training subset \(S\) [GZ, ICML ’19],
federated learning where \(f(S)\) is the performance of the clients in \(S\) together [Wang, ’19],
causality where \(f(S)\) is the expected outcome when we intervene only on the variables in \(S\) [HSBC, NeurIPS ’20],
language modeling where \(f(S)\) is the score of text when all tokens not in \(S\) are masked [CSWJ, ICLR ’19],
ensemble learning where \(f(S)\) is the performance of the sub-ensemble built from only the models in \(S\) [RS, CIKM ’21],
multi-agent reinforcement learning where \(f(S)\) is the return the agents in \(S\) earn acting as a coalition [WZKG, AAAI ’20],
graph learning where \(f(S)\) is the model’s prediction when only the nodes or edges in \(S\) are retained [DM, ECML ’21].
Games with Free Shapley Values
If the definition touches all \(2^d\) coalitions, for which games can the sum be avoided? For a generic black-box game there is no shortcut (\(2^{30}\) is already a billion evaluations, each a model call or an entire retraining). Some structured classes of games, however, have closed-form Shapley values.
Additive games. Suppose the surrogate \(\hat{f}\) is affine, a constant plus a per-player score:
\[ \hat{f}(S) = c_0 + \sum_{i \in S} c_i, \]
with constant \(c_0 \in \mathbb{R}\) and per-player scores \(c_i \in \mathbb{R}\). By linearity we handle each term separately. The constant game \(S \mapsto c_0\) has no marginal contributions at all, so it contributes nothing to any \(\phi_i\). In the singleton game \(S \mapsto c_i\, \mathbf{1}[i \in S]\), where \(\mathbf{1}[\cdot]\) is one when its argument holds and zero otherwise, player \(i\) contributes \(c_i\) in every ordering and every other player contributes zero. Summing the per-term values leaves each player with its own score:
\[ \phi_i(\hat{f}) = c_i. \]
Trees. For a decision forest, you can traverse each leaf once and compute exact Shapley values in \(O(t \ell d)\) time for \(t\) trees with at most \(\ell\) leaves each, rather than the naive \(O(t \ell 2^d)\). That makes the exact Shapley values of a gradient boosted forest a subsecond operation. The page on piecewise-constant games derives this calculation.
Sparse polynomials in the Möbius basis. Adding higher-order monomials to the affine class represents interactions. Encode a coalition by its indicator vector \(\mathbf{z} \in \{0, 1\}^d\), with \(z_i = \mathbf{1}[i \in S]\). The monomial on a subset \(T \subseteq [d]\) is then the game worth one exactly when all of \(T\) shows up:
\[ \prod_{i \in T} z_i = \mathbf{1}[T \subseteq S]. \]
These monomials are the Möbius basis (also called the interaction basis), and the coefficient \(\beta_T\) on \(\mathbf{1}[T \subseteq S]\) is the pure interaction among the players of \(T\). The Shapley axioms determine the value of a single monomial. Players outside \(T\) never change its value, so they are null; the players inside \(T\) are interchangeable; and for a nonempty \(T\) the total to split is the change from the empty coalition to the full one:
\[ \mathbf{1}[T \subseteq [d]] - \mathbf{1}[T \subseteq \emptyset] = 1. \]
Equal treatment splits that total evenly across the \(|T|\) members:
\[ \phi_i\big(\mathbf{1}[T \subseteq \cdot]\big) = \begin{cases} 1/|T| & i \in T, \\ 0 & \text{otherwise}. \end{cases} \]
By linearity, the Möbius-sparse polynomial \(\hat{f}(S) = \sum_{T} \beta_T\, \mathbf{1}[T \subseteq S]\) sums these single-monomial values:
\[ \phi_i(\hat{f}) = \sum_{T \ni i} \frac{\beta_T}{|T|}. \]
A single pass over the nonzero coefficients computes every \(\phi_i\).
Sparse polynomials in the Fourier basis. The second expansion trades presence for sign. Write the parity of \(T\) on a coalition as
\[ \chi_T(S) = (-1)^{|S \cap T|}, \]
worth \(+1\) when \(T\) meets \(S\) in an even number of players and \(-1\) when odd; these are the Fourier basis, the Walsh–Hadamard characters. A player outside \(T\) never flips the parity, so it is null, the players inside \(T\) are interchangeable, and by efficiency they share the change from the empty coalition to the full one:
\[ \chi_T([d]) - \chi_T(\emptyset) = (-1)^{|T|} - 1. \]
That total vanishes when \(|T|\) is even and equals \(-2\) when \(|T|\) is odd, so equal treatment splits it evenly across the \(|T|\) members:
\[ \phi_i(\chi_T) = \begin{cases} -\,2/|T| & i \in T \text{ and } |T| \text{ odd}, \\ 0 & \text{otherwise}. \end{cases} \]
An even-order character is therefore invisible to the Shapley value, and that blindness is the mechanism behind the even-odd decomposition.
This asymmetry drives most Shapley value estimators: the values are intractable for a black box but available in closed form for an affine function, boosted forest, or sparse polynomial.
The Template
How does a class with free Shapley values help when the game we care about is not in it? Sample \(m\) coalitions \(S_1, \dots, S_m\), where \(m\) is the evaluation budget, and evaluate the expensive game at each one. Fit a surrogate \(\hat{f}\) from a class with closed-form Shapley values to the pairs \((S_j, f(S_j))\), then return the exact \(\phi_i(\hat{f})\).
The figure separates the two design choices: which coalitions to sample and which surrogate class to fit. (Ask TreeSHAP to explain the all-ones indicator against the all-zeros baseline, so the game it masks with is exactly \(S \mapsto \hat{f}(S)\).)
Extracting the surrogate’s exact Shapley values adds no error beyond the surrogate fit, and linearity says exactly what that error is.
Claim: for any game \(f\) and any surrogate \(\hat{f}\) on the same players, the error of the read-off is the Shapley value of their difference:
\[ \phi_i(f) - \phi_i(\hat{f}) = \phi_i(f - \hat{f}). \]
Proof
Write the true game as the surrogate plus the difference and apply linearity with both scalars equal to one:
\[\begin{align} \phi_i(f) &= \phi_i\big(\hat{f} + (f - \hat{f})\big) \\ &= \phi_i(\hat{f}) + \phi_i(f - \hat{f}), \end{align}\]
where the first line adds and subtracts \(\hat{f}\) inside the argument and the second is linearity. Moving \(\phi_i(\hat{f})\) to the left side gives the claim.
The pipeline’s error is therefore the Shapley value of the residual game \(f - \hat{f}\). Its accuracy depends on that residual Shapley value, not simply on a generic measure of predictive fit. If you insist on unbiasedness, spend part of the budget on a cheap unbiased Monte Carlo estimate of \(\phi_i(f - \hat{f})\) and add it back. This residual estimate is the adjustment column in the taxonomy below.
Recent methods differ mainly in their surrogate class, sampling design, and residual adjustment.
| Method | Surrogate | Sampling | Adjustment | Citation |
|---|---|---|---|---|
| KernelSHAP | Affine | Shapley kernel, i.i.d. | None | [LL, NeurIPS ’17] |
| LeverageSHAP | Affine | Leverage scores: uniform size, then uniform set, paired | None | [MW, ICLR ’25] |
| PolySHAP | Polynomial with chosen interaction terms | Kernel or leverage weights, paired | None | [FWM, ICLR ’26] |
| OddSHAP | Odd polynomial, terms nominated by a boosted-tree proxy | Paired, complement-symmetric weights | None | [FBKRW, ICML ’26] |
| RegressionMSR | Anything with free Shapley values; boosted trees in practice | Sample reuse: every evaluation updates every player | Unbiased Monte Carlo estimate of the residual game | [WLM, NeurIPS ’25] |
| ProxySPEX | Boosted trees, read out as a sparse Fourier polynomial | Uniformly random coalitions | None | [BAKEYR, ’25] |
| Adalina | A single constant, tuned online | Variance-optimal sizes, every sample reused | The constant, subtracted as a control variate | [LYL, ICML ’26] |
The design problem is to choose a surrogate class expressive enough for the game and a sampling scheme that supports an accurate fit. Once the surrogate is fitted, extracting its Shapley values is cheap. For a general black-box game, a practical default is a gradient boosted tree surrogate followed by TreeSHAP.