A PSA on Shapley Values

Choose the game, fit a surrogate, and extract its Shapley values.

7 min read

Shapley values are a rule for sharing credit. The game specifies what each group is worth; choosing that function determines what the credits mean. In machine learning, the members might be input features and the group’s value a model prediction. With \(d\) members there are \(2^d\) possible groups, so evaluating every group is usually out of reach.

Some games have Shapley values we can compute exactly and cheaply. That gives us a beautiful shortcut: fit one of these games to the values we can afford to evaluate.

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 answer is exact for the fitted game and approximates the Shapley values of the original game.

First Choose the Game

A game is a function \(f(S)\) assigning a value to each group, or coalition, \(S\subseteq[d]=\{1,\ldots,d\}\). The Shapley rule turns that function into one credit per player. Put the players in a uniformly random order and let \(S_i\) be the players before \(i\). Player \(i\) receives its average marginal contribution [Shapley, ’53]:

\[ \phi_i(f)=\mathbb E\big[f(S_i\cup\{i\})-f(S_i)\big]. \]

The rule stays the same when we change \(f\), but the meaning of the credit changes. For feature attribution, called SHAP (Shapley Additive Explanations) by Lundberg and Lee [LL, NeurIPS ’17], let \(h\) be the trained model and \(\mathbf x\) the input to explain. We want \(f(S)\) to mean the prediction when only the features in \(S\) are revealed. The model still needs values for the hidden features, and the choice matters:

\[ \begin{aligned} f_{\mathrm{base}}(S)&=h(\mathbf x_S;\mathbf b_{S^c}),\\ f_{\mathrm{marg}}(S)&=\mathbb E\big[h(\mathbf x_S;\mathbf X_{S^c})\big],\\ f_{\mathrm{cond}}(S)&=\mathbb E\big[h(\mathbf X)\mid\mathbf X_S=\mathbf x_S\big]. \end{aligned} \]

Here \(S^c\) contains the hidden features, \(\mathbf b\) is a fixed reference input, and \(\mathbf X\) is a random input from the data distribution. The baseline game fills hidden slots with \(\mathbf b\). The marginal game draws their values from the data distribution without conditioning on the revealed features; the conditional game does condition on them.

Take three fair binary features: \(x_2\) duplicates \(x_1\), while \(x_3\) is independent. The model is \(h(\mathbf x)=x_1+x_3\), the input is \((1,1,1)\), and the reference is \((0,0,0)\). The model never reads \(x_2\), yet revealing it tells us \(x_1\) under the conditional game. That game therefore shares \(x_1\)’s credit with its duplicate, as the plot shows.

Only the conditional game gives the untouched duplicate \(x_2\) any credit.

All three answers are correct for their respective games. Choosing which one answers our question comes before choosing how to estimate it.

Fit Once, Then Extract the Values

Once \(f\) is fixed, sample \(m\) coalitions and evaluate it on each one. Encode a coalition as a vector of zeros and ones, one coordinate per player, and fit a regression model \(\hat f\) to these indicators and their observed values. Choose a model whose Shapley values are cheap to compute, then return \(\phi_i(\hat f)\).

Sampling and fitting determine the approximation; the final extraction is exact for the fitted game.

An affine fit has an intercept \(c_0\) and one coefficient \(c_i\) per player:

\[ \hat f(S)=c_0+\sum_{i\in S}c_i \quad\Longrightarrow\quad \phi_i(\hat f)=c_i. \]

Player \(i\) adds \(c_i\) in every ordering, so averaging changes nothing. KernelSHAP fits an affine model with weights chosen for Shapley estimation; LeverageSHAP improves the sampling design [MW, ICLR ’25].

Why Trees Work Well

Boosted trees capture interactions through successive splits, without requiring us to list the interactions to fit in advance. The original model need not be a tree: we train the tree surrogate on the coalition indicators and game values. This combines a flexible approximation of the game with a fast, exact calculation of the surrogate’s Shapley values.

For the fitted forest, ask TreeSHAP to explain the all-ones indicator against a single all-zeros background, using interventional masking. Revealing the indicator coordinates in \(S\) then gives exactly the input on which we defined \(\hat f(S)\). This background is for the surrogate’s indicator inputs; it does not replace the masking convention used to define the original game \(f\).

Each tree leaf requires some indicator coordinates to be one, others to be zero, and leaves the rest free. The coalitions reaching that leaf form a block whose Shapley weights can be summed without enumerating its members. For a sum of \(t\) trees with constant predictions at at most \(\ell\) leaves each, this fixed-background calculation takes \(O(t\ell d)\) arithmetic for all players, as derived for piecewise-constant games.

Recent Methods Through This Lens

This viewpoint connects much of the recent literature: choose a tractable surrogate, fit it from game evaluations, and compute its Shapley values. The table includes KernelSHAP as the starting point and shows where later methods change the surrogate or the way it is used.

Method	Surrogate	Shapley extraction	Notes
KernelSHAP (2017)	Affine function of coalition indicators.	Read off each player’s fitted coefficient.	Fits with the Shapley kernel and constraints at the empty and full coalitions.
LeverageSHAP (2025)	The same affine function.	Read off each player’s fitted coefficient.	Changes the sampling design using leverage scores.
Tree surrogate + TreeSHAP	Decision trees or a boosted ensemble.	Exact tree calculation with the indicator background described above.	The direct version of the recommendation above: fit the game, then explain the fitted trees.
RegressionMSR (2025)	Any model with cheap Shapley values; boosted trees in TreeMSR.	Exact tree calculation, or coefficient read-off for an affine fit.	Adds a sampled correction for the part of the game the surrogate misses.
ProxySPEX (2025)	Boosted trees, represented by a sparse Fourier polynomial.	Sum the Shapley contributions of the retained Fourier terms.	Also recovers interactions. Keeping only selected terms can introduce an additional approximation to the tree fit.
PolySHAP (2026)	Polynomial in coalition indicators, with selected interaction terms.	Split each monomial’s coefficient equally among the players in that monomial, then sum.	Adds interactions to the affine fit while retaining a closed-form extraction.
OddSHAP (2026)	A polynomial containing selected odd Fourier terms.	Sum the Shapley contributions of its odd Fourier terms.	A tree proxy selects the terms; a separate polynomial regression fits their coefficients.
Adalina (2026)	An adaptively chosen constant used to center game values.	A constant game gives every player zero.	A limiting case of this viewpoint: the constant reduces sampling variance, while the final values come from sampled game evaluations.

How polynomial coefficients give Shapley values

Let \(z_j=1\) when \(j\in S\) and \(z_j=0\) otherwise. For a nonempty set \(T\), the monomial \(\prod_{j\in T}z_j\) becomes one when the last player in \(T\) arrives. Each member of \(T\) is equally likely to be last, so each receives \(1/|T|\). For a polynomial with coefficients \(\beta_T\), linearity therefore gives

\[ \hat f(S)=\sum_T\beta_T\prod_{j\in T}z_j \quad\Longrightarrow\quad \phi_i(\hat f)=\sum_{T\ni i}\frac{\beta_T}{|T|}. \]

For the Fourier representation, use signs \(x_j=2z_j-1\) and write

\[ \hat f(S)=\sum_Ta_T\prod_{j\in T}x_j. \]

A nonconstant sign product treats its players symmetrically. Its value changes from \((-1)^{|T|}\) at the empty coalition to \(1\) at the full coalition, so those players split a total of two when \(|T|\) is odd and zero when it is even. Thus

\[ \phi_i(\hat f)=\sum_{\substack{T\ni i\\|T|\text{ odd}}}\frac{2a_T}{|T|}. \]

The constant term contributes zero in both representations. This is the even–odd decomposition behind OddSHAP.