The Even–Odd Decomposition
8 min read
A Shapley value measures a player’s average contribution when it joins a group of other players. Estimating it requires evaluating many groups, and each evaluation can be expensive. Covert & Lee proposed evaluating each group together with its complement, the players left out of it, to reduce noise in KernelSHAP [CL, AISTATS ’21].
Pairing helps because of a symmetry in the quantity we want to estimate. For each group and its complement, their values have an average and a difference. The Shapley value depends only on the differences; the averages contribute zero. Paired evaluations cancel the averages before they can add noise to the estimate [FBKRW, ICML ’26]. How does this cancellation follow from the Shapley rule?
The Decomposition
To answer that we first need to know what swapping every coalition for its complement does to a game. A game on \(d\) players \([d] = \{1, \dots, d\}\) is a set function \(f : 2^{[d]} \to \mathbb{R}\) assigning a value \(f(S)\) to every coalition \(S \subseteq [d]\). Write \(S^c = [d] \setminus S\) for the complement of a coalition.
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:
\[ f_{\mathrm{even}}(S) = \frac{f(S) + f(S^c)}{2}, \qquad f_{\mathrm{odd}}(S) = \frac{f(S) - f(S^c)}{2}. \]
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)\). (Which game is both even and odd?)
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].
The split matters for two reasons, both proved below: the Shapley value depends on \(f_{\mathrm{odd}}\) alone, and an estimator that samples coalitions in complement pairs never evaluates \(f_{\mathrm{even}}\) at all.
The Shapley Value
How much does each coalition count toward a player’s Shapley value? The Shapley value of player \(i\) is a weighted average of \(i\)’s marginal contributions over all coalitions that exclude \(i\):
\[ \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.
Shapley Values Ignore the Even Component
What does this weighting do to the even part of a game?
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.
For two players, the cancellation is visible directly:
\[ \phi_1(f) = \frac{1}{2}\big(f(\{1\}) - f(\emptyset)\big) + \frac{1}{2}\big(f(\{1,2\}) - f(\{2\})\big). \]
If \(f\) is even, then \(f(\emptyset) = f(\{1,2\})\) and \(f(\{1\}) = f(\{2\})\), so the two terms cancel.
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.
Paired Sampling Isolates the Odd Component
Does an estimator that evaluates only a few coalitions inherit this cancellation, or does it hold only for the full sum? 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}}\).
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.