The Even–Odd Decomposition
11 min read
Paired sampling is a trick that nearly every modern Shapley value estimator uses: whenever you evaluate a coalition, also evaluate its complement. Covert & Lee [CL, AISTATS ’21] proposed it as a variance-reduction heuristic for KernelSHAP and measured a \(9\times\) average speedup: on their four datasets, KernelSHAP with pairing reached a fixed error using a ninth as many coalitions. But why it worked so well stayed open. The answer turns out to be a symmetry, worked out by Fumagalli, Butler, Kang, Ramchandran & Witter [FBKRW, ICML ’26].
The Decomposition
Half of that sentence is undefined so far: a game has no odd part until something plays the role of a sign flip.
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]\). (In machine learning, \(f(S)\) is typically a model’s prediction when only the features in \(S\) are revealed.) Write \(S^c = [d] \setminus S\) for the complement of a coalition.
Some games cannot tell a coalition from its complement. Take any graph on the players and let \(f(S)\) count the edges crossing between \(S\) and \(S^c\). An edge leaves \(S\) exactly when it leaves \(S^c\), so this cut game gives every coalition the same value as its complement.
That symmetry has a familiar shape. 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? Only the zero game. Do you see why?)
(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].)
In this language the cut game is purely even. Whether the Shapley value can see a game like this comes down to the weights inside its definition, so those come next.
The Shapley Value
The Shapley value is usually introduced through its fairness axioms, but what matters here is the exact weight it places on each coalition.
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 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. Reading an ordering backwards is still a uniformly random ordering, and it swaps the \(s\) players ahead of \(i\) for the other \(d - 1 - s\), so the weight is symmetric:
\[ w(s) = w(d - 1 - s). \]
This symmetry is easiest to see in the lattice of coalitions.
In the lattice, every edge from size \(s\) to size \(s + 1\) carries weight \(w(s)\), and the symmetry \(w(s) = w(d-1-s)\) makes those weights read the same top-down as bottom-up. Complementation is that reflection, pairing a coalition of size \(s\) with its complement at the mirror-image level of size \(d - s\).
An even game assigns the two members of such a pair the same value, and the Shapley value gives them the same weight. The signs are the only thing left to check.
The Part Shapley Cannot See
Equal weights on their own prove nothing, since a sum of equal terms is as far from zero as it gets.
Claim: \(\phi_i(f_{\mathrm{even}}) = 0\) for every player \(i\), and hence \(\phi_i(f) = \phi_i(f_{\mathrm{odd}})\) by linearity.
The smallest case makes it visible. With \(d = 2\) the sum for player \(1\) has two terms, and \(w(0) = w(1) = \tfrac{1}{2}\):
\[ \phi_1(f) = \tfrac{1}{2}\big(f(\{1\}) - f(\emptyset)\big) + \tfrac{1}{2}\big(f(\{1,2\}) - f(\{2\})\big). \]
The four coalitions form two complement pairs, \(\{\emptyset, \{1,2\}\}\) and \(\{\{1\}, \{2\}\}\). Within each pair one value carries \(+\tfrac{1}{2}\) and the other \(-\tfrac{1}{2}\), and an even game assigns the pair equal values, so everything cancels.
The general case is the same picture, once the definition is regrouped by coalition rather than by marginal contribution. Each of the \(2^d\) values \(f(S)\) enters 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))\). Equal weight, opposite sign.
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. 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.
Sanity check: efficiency 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 cut game is the sharpest example: wildly non-constant, with mostly nonzero marginal contributions, and yet every Shapley value exactly zero.
Nobody evaluates that sum directly, though: it has \(2^d\) terms.
Paired Sampling Never Looks
The estimators we run instead read a handful of coalitions, and the cancellation does not survive sampling on its own. It works pair by pair, so it needs both members of a complement pair on hand, and a random sample that draws \(S\) without \(S^c\) has nothing to cancel against. That is the one broken piece, and it costs exactly one extra evaluation to fix.
Both workhorse estimators return a fixed affine combination of the values they read, with coefficients that depend on which coalitions were drawn but not on the values themselves, and each weights a coalition and its complement equally.
The Monte Carlo marginal-contribution estimator draws a random ordering and records \(i\)’s contribution at the point where \(i\) sits: the coalition \(S\) seated before \(i\), and \(S \cup \{i\}\). Reversing the ordering is equally likely and produces the complementary split, at \(S^c\) and \(S^c \setminus \{i\}\), so a coalition and its complement are evaluated with the same probability.
KernelSHAP, the weighted least-squares estimator of Lundberg & Lee [LL, NeurIPS ’17], fits a linear surrogate to the game and reports its fitted slopes as the Shapley values:
\[ \hat{f}(S) = \hat{\phi}_0 + \sum_{j \in S} \hat{\phi}_j . \]
Here \(\hat{\phi}_0\) is the fitted intercept, the surrogate’s value on the empty coalition, and the slope \(\hat{\phi}_j\) is the estimate of \(\phi_j(f)\). The fit is weighted, with coalition \(S\) carrying the Shapley kernel weight:
\[ \mu(S) = \frac{d - 1}{\binom{d}{|S|}\, |S|\, (d - |S|)}. \]
The weight depends on \(S\) only through its size. Replacing \(S\) by \(S^c\) turns \(|S|\) into \(d - |S|\), leaving both \(\binom{d}{|S|}\) and the product \(|S|(d - |S|)\) unchanged, so \(\mu(S) = \mu(S^c)\).
Because complements come weighted equally, we can draw them two at a time: evaluate \(S\), take \(S^c\) for free. This is paired sampling, and within a pair the even part cancels. On the Monte Carlo estimator the cancellation is exact on every single draw. The plain estimator records \(f(S \cup \{i\}) - f(S)\), its paired partner from the reversed ordering records \(f(S^c) - f(S^c \setminus \{i\})\), and averaging the two gives:
\[\begin{align} & \frac{f(S \cup \{i\}) - f(S)}{2} + \frac{f(S^c) - f(S^c \setminus \{i\})}{2} \\ &= \frac{f(S \cup \{i\}) - f\big((S \cup \{i\})^c\big)}{2} - \frac{f(S) - f(S^c)}{2} \\ &= f_{\mathrm{odd}}(S \cup \{i\}) - f_{\mathrm{odd}}(S), \end{align}\]
where the first step regroups the four values into complement pairs, using \((S \cup \{i\})^c = S^c \setminus \{i\}\), and the second reads off \(f_{\mathrm{odd}}\) twice. The paired estimate is identically the plain estimate run on \(f_{\mathrm{odd}}\): the even part cancels on every draw, not just in expectation. The same holds inside KernelSHAP: with complement pairs and complement-symmetric weights, [FBKRW, ICML ’26] show that the least-squares objective splits into an odd fit and an even fit with no cross term, and only the odd fit feeds the reported slopes.
This is where the \(9\times\) comes from. The even part is usually the large part of a model’s game (every constant offset in the output is even), so an estimator that ignores it has far less left to pin down. The cut game is the limit: it is purely even, so the plain estimator averages nonzero marginal contributions that cancel only in expectation, while the paired estimator returns exactly zero on its first pair and every pair after. How much of a game this discards is a question about dimension.
The Projection
Games form a \(2^d\)-dimensional vector space, one coordinate per coalition, and for two games \(f\) and \(h\) it carries a natural inner product:
\[ \langle f, h \rangle = \sum_{S \subseteq [d]} f(S)\, h(S). \]
Under this inner product, the even games and the odd games are orthogonal subspaces of dimension \(2^{d-1}\) each, exactly half the space. Pairing \(S\) with \(S^c\) is again what makes them orthogonal: in the sum \(\langle f_{\mathrm{even}}, h_{\mathrm{odd}} \rangle\) the term at \(S\) cancels against the term at \(S^c\), where the even factor repeats and the odd factor flips sign. The Shapley value is a linear functional that annihilates the even half. Paired sampling is orthogonal projection onto the other half, carried out one complement pair at a time.
Said that way, an algorithm suggests itself. Why spend any of the fitting budget on the even half at all? That is OddSHAP, the estimator of [FBKRW, ICML ’26]: work in the parity basis, where every basis function is even or odd, discard the even half, and solve 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. The odd interactions are what earn that rank. Removing them turns OddSHAP into a plain linear fit, LeverageSHAP [MW, ICLR ’25]. 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.
The same move generalizes past Shapley values: when the quantity you are estimating is blind to half of its input, project that half out before you spend a sample on it.