The Even–Odd Decomposition
7 min read
A group of players produces a value, and we want to divide the credit among them. The Shapley rule measures how much each player adds, averaged over all orders in which the players could join the group. Computing that average requires evaluating many groups, so we usually estimate it from a sample.
A sampling rule proposed by Covert & Lee evaluates groups in pairs: whenever we evaluate a group, we also evaluate the players left out [CL, AISTATS ’21]. The beautiful part is that pairing cancels variation in the group’s value that never contributed to anyone’s credit.
The Shapley Value
Let \(f(S)\) be the value of a group \(S\), called a coalition, drawn from \(d\) players \([d] = \{1, \dots, d\}\). The function \(f\) is called a game. Player \(i\) adds \(f(S \cup \{i\}) - f(S)\) when joining a coalition that excludes them. This difference is their marginal contribution.
To average over arrival orders, we weight each coalition by the chance that exactly its members arrive before \(i\). The resulting Shapley value is:
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} w(|S|)\, \big( f(S \cup \{i\}) - f(S) \big), \qquad w(s) = \frac{s!\,(d - s - 1)!}{d!}. \]
The choice of \(w\) equally weights all coalition sizes, as shown below.
The weight \(w(s)\) is the probability that a uniformly random ordering of the players seats exactly the coalition \(S\), of size \(s\), before player \(i\): there are \(s!\) ways to order \(S\), then \(i\), then \((d - s - 1)!\) ways to order the rest, out of \(d!\) orderings in all.
For two players, the four group values enter with opposite signs:
\[ \phi_1(f) = \frac{1}{2}\big(f(\{1\}) - f(\emptyset)\big) + \frac{1}{2}\big(f(\{1,2\}) - f(\{2\})\big). \]
If each group has the same value as the players left out, then \(f(\emptyset) = f(\{1,2\})\) and \(f(\{1\}) = f(\{2\})\), so the two terms cancel. The equal part of each pair contributes nothing, even when those common values are large.
The Decomposition
Write \(S^c = [d] \setminus S\) for the players left out of \(S\). To isolate the part that cancels, split each pair of values into their average and their difference.
Complementation \(S \mapsto S^c\) is the set analogue of the reflection \(x \mapsto -x\): apply it twice and you are back where you started. So, exactly as an ordinary function splits into an even and an odd piece, a game splits into an even part, unchanged under complementation, and an odd part, negated by it:
\[ \begin{gathered} f_{\mathrm{even}}(S) = \frac{f(S) + f(S^c)}{2},\\ f_{\mathrm{odd}}(S) = \frac{f(S) - f(S^c)}{2}. \end{gathered} \]
Then \(f = f_{\mathrm{even}} + f_{\mathrm{odd}}\), and flipping \(S\) to \(S^c\) fixes the even numerator while negating the odd one, so \(f_{\mathrm{even}}(S^c) = f_{\mathrm{even}}(S)\) and \(f_{\mathrm{odd}}(S^c) = -f_{\mathrm{odd}}(S)\).
The even part contributes nothing to any player’s Shapley value [FBKRW, ICML ’26].
Shapley Values Ignore the Even Component
Claim: for every player \(i\),
\[ \phi_i(f_{\mathrm{even}}) = 0, \qquad \text{and hence} \qquad \phi_i(f) = \phi_i(f_{\mathrm{odd}}) \]
by linearity.
Proof
Each of the \(2^d\) values \(f(S)\) enters the Shapley value once, with a plus sign if \(i \in S\) (there \(S\) is a coalition \(i\) has just joined) and a minus sign if \(i \notin S\) (there \(S\) is one \(i\) has yet to join):
\[ \phi_i(f) = \sum_{S \ni i} w(|S| - 1)\, f(S) \;-\; \sum_{S \not\ni i} w(|S|)\, f(S). \]
Now pair each coalition with its complement. Because \(S\) and \(S^c\) split the players between them, \(i\) lands in exactly one of the two, so one member of the pair sits in the first sum and the other in the second. Their weights match too: with \(i \in S\) and \(|S| = s\), the first sum weights \(f(S)\) by \(w(s-1)\) and the second weights \(f(S^c)\) by \(w(d-s)\), equal by the symmetry \(w(s-1) = w(d-1-(s-1))\).
For an even game the pair also has equal values, \(f(S) = f(S^c)\), so its two contributions are negatives of each other and cancel, as the cube above shows for one pair. No coalition is its own complement, since \(S\) and \(S^c\) are disjoint, so the \(2^d\) coalitions fall into \(2^{d-1}\) such pairs, every one cancels, and \(\phi_i(f_{\mathrm{even}}) = 0\). Since \(\phi_i\) is linear in the game, \(\phi_i(f) = \phi_i(f_{\mathrm{even}}) + \phi_i(f_{\mathrm{odd}}) = \phi_i(f_{\mathrm{odd}})\): the Shapley value reads the odd part of the game and nothing else.
The efficiency constraint, \(\sum_{i=1}^d \phi_i(f) = f([d]) - f(\emptyset)\), already forces an even game’s Shapley values to sum to zero, since \(f([d]) = f(\emptyset)\). The claim is the stronger statement that each one is zero on its own.
The Fourier interpretation
For Fourier-minded readers: encode coalitions as sign vectors in \(\{-1, +1\}^d\) and complementation becomes the global sign flip, under which a parity on a player set \(T\) picks up \((-1)^{|T|}\). So \(f_{\mathrm{even}}\) and \(f_{\mathrm{odd}}\) are the even- and odd-degree halves of the Fourier expansion in O’Donnell’s Analysis of Boolean Functions [O’Donnell, ’14].
Paired Sampling Isolates the Odd Component
Instead of computing all \(2^d\) coalitions, Shapley value estimators evaluate only a handful. Sampling in pairs means selecting \(S^c\) whenever \(S\) is chosen. Each pair locally builds \(f_\textrm{odd}\) at the cost of two samples.
That cancellation used only that the coefficients on a complement pair are equal and opposite.
Lemma: Let \(\hat\theta = \sum_S c_S\, f(S)\) be a fixed, value-independent linear combination of the coalitions an estimator samples, drawn in complement pairs with \(c_{S^c} = -c_S\). Then \(\hat\theta\) is exactly what the same estimator returns on \(f_{\mathrm{odd}}\) alone, on every draw.
Proof
Within one pair, the two evaluations combine as:
\[\begin{align} c_S\, f(S) + c_{S^c}\, f(S^c) &= c_S\big(f(S) - f(S^c)\big) \\ &= 2c_S\, f_{\mathrm{odd}}(S). \end{align}\]
The first line substitutes \(c_{S^c} = -c_S\) and factors, and the second recognizes the definition of \(f_{\mathrm{odd}}\). So \(f_{\mathrm{even}}\) drops out of every pair regardless of its value, and summing over the sampled pairs gives the same number on \(f\) and on \(f_{\mathrm{odd}}\).
Pairing removes the even component exactly, but it uses two evaluations per pair. At a fixed evaluation budget, the total variance also depends on the odd component and on how the pairs are sampled.
The permutation-based Monte Carlo estimator, MSR [WJ, AISTATS ’23], KernelSHAP, LeverageSHAP [MW, ICLR ’25], and PolySHAP [FWM, ICLR ’26] are all of this form. Each assigns a fixed weight to every drawn coalition, with equal and opposite weights across a complement pair, so all five inherit the cancellation. The exception is a tree-based variant of MSR: it fits a tree to the sampled values and reports the tree’s own Shapley values, so the map from \(f\) to the estimate is no longer affine, and the lemma doesn’t apply.
For the regression estimators (KernelSHAP, LeverageSHAP, and PolySHAP), pairing keeps the even and odd fits separate, but both still get fit. The reported slopes come from the odd fit alone, and the even fit is computed and discarded. OddSHAP, our recent estimator [FBKRW, ICML ’26], instead works in the parity basis, discards the even terms, and solves the weighted regression over the odd terms only. The odd half is still \(2^{d-1}\)-dimensional and no budget fits all of it, so a boosted-tree proxy nominates the interactions worth keeping. OddSHAP is consistent, and with a budget of roughly \(100d\) evaluations it ranks first on four of their eight benchmarks and second on the other four, the best average rank in the comparison. Removing the nominated interactions turns OddSHAP into a plain linear fit, LeverageSHAP. Putting about a thousand of them back, at a fixed budget of 10,000 coalitions, cuts the error by at least \(6\times\) on every game in their ablation and by \(62\times\) on a cancer-diagnosis model. Adding the even interactions alongside them only splits the budget and adds runtime, since the Shapley value discards their coefficients anyway.