Shapley Values for Piecewise-Constant Games
9 min read
Computing a Shapley value means combining a player’s contributions across many possible groups. With thirty features there are already more than a billion groups, so evaluating every one is often out of reach. But a model may give exactly the same result for many different groups. Treating each of those repeated values as a separate computation wastes that structure.
We can collect groups with the same value into blocks and add their Shapley weights together. When those block weights can be computed directly, the calculation needs one term per block instead of one term per group. This explains efficient exact calculations for decision trees [LE+, NMI ’20], their interval formulation [ZBK, AAAI ’23], and certain structural causal models [WP+, ’26]. The algebra is shared; the work lies in finding blocks whose weights we can sum.
Decomposition
Why can equal values be combined at all, when the definition sums differences? A game is a set function \(f : 2^{[d]} \to \mathbb{R}\) on players \([d] = \{1, \dots, d\}\). Picture the players arriving in a uniformly random order and watch the game’s value jump when player \(i\) arrives. The Shapley value of player \(i\) is the average jump:
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} p_{|S|}\,\big(f(S \cup \{i\}) - f(S)\big), \]
where a particular coalition of size \(s\) appears before \(i\) with probability:
\[ p_s = \frac{s!\,(d-s-1)!}{d!}. \]
The difference hides repeated game values across separate marginal contributions. Expand the difference and reindex the positive terms by the coalition whose value is evaluated:
\[ \phi_i(f) = \sum_{T \ni i} p_{|T|-1}\,f(T) - \sum_{T \not\ni i} p_{|T|}\,f(T). \]
Now every coalition appears once. Its coefficient depends only on its size and whether it contains \(i\):
\[ c_{i,T} = \begin{cases} +p_{|T|-1} & i \in T, \\ -p_{|T|} & i \notin T. \end{cases} \]
The Shapley value is therefore a linear combination of the game’s values:
\[ \phi_i(f) = \sum_{T \subseteq [d]} c_{i,T}\,f(T). \]
Consider three players where player 3 overrides the other two. Once 3 joins a coalition, adding or removing 1 or 2 changes nothing, so the four coalitions containing 3 share one value. The other four coalitions may each have values of their own.
In general, a game is piecewise constant when its coalitions split into blocks \(B_1, \dots, B_r\) and every coalition in \(B_j\) has one value \(f_j\). The total coefficient assigned to a block is its block weight:
\[ w_{i,j} = \sum_{T \in B_j} c_{i,T}. \]
Grouping equal values reduces the Shapley sum to one term per block:
\[ \phi_i(f) = \sum_{j=1}^{r} f_j\,w_{i,j}. \]
The original \(2^d\) terms have disappeared. We only need a cheap way to compute each block weight. Blocks shaped like intervals of the lattice have one, and trees and causal models both produce interval blocks.
Interval Blocks
Which blocks have a weight we can compute without visiting every coalition in them? A useful block is an interval of the coalition lattice. It has a smallest coalition, the basis \(\underline{S}_j\), and a largest coalition, the closure \(\bar{S}_j\):
\[ B_j = \{T : \underline{S}_j \subseteq T \subseteq \bar{S}_j\}. \]
Every coalition in the block contains the basis, excludes everything outside the closure, and may choose freely among the elements of \(\bar{S}_j \setminus \underline{S}_j\). In the three-player example, the shared block runs from basis \(\{3\}\) to closure \(\{1,2,3\}\).
A player relates to an interval in one of three ways, inside the basis, free, or outside the closure, and the block weight depends only on which.
Claim: let \(a = |\underline{S}_j|\) and \(b = |\bar{S}_j|\). The block weight of the interval \(B_j\) for player \(i\) is:
\[ w_{i,j} = \begin{cases} \displaystyle \sum_{\ell=a}^{b} \binom{b-a}{\ell-a}\,p_{\ell-1} & i \in \underline{S}_j, \\[10pt] 0 & i \in \bar{S}_j \setminus \underline{S}_j, \\[10pt] \displaystyle -\sum_{\ell=a}^{b} \binom{b-a}{\ell-a}\,p_{\ell} & i \notin \bar{S}_j. \end{cases} \]
Proof
The free elements give the main cancellation. If \(i \in \bar{S}_j \setminus \underline{S}_j\), every coalition \(T\) in the block without \(i\) pairs with \(T \cup \{i\}\) in the same block. The pair contributes zero:
\[ c_{i,T} + c_{i,T \cup \{i\}} = -p_{|T|} + p_{|T|} = 0. \]
Adding a free player never changes the block’s value, so the whole block contributes nothing to that player’s Shapley value. In the figure, this is why the teal block contributes zero to players 1 and 2.
The remaining cases depend only on coalition size. The block contains \(\binom{b-a}{\ell-a}\) coalitions of size \(\ell\), because each one chooses \(\ell-a\) of the \(b-a\) free elements. If \(i\) is in the basis, every coalition of the block contains \(i\) and carries the positive coefficient \(p_{|T|-1}\); grouping the coalitions by size gives the first line. If \(i\) is outside the closure, every coalition of the block omits \(i\) and carries the negative coefficient \(-p_{|T|}\); the same grouping gives the last line.
Each sum has at most \(d\) terms, and the same two sums serve every player in the block. Once the \(r\) intervals are known, all \(d\) Shapley values need one game evaluation per block and \(O(rd)\) arithmetic, rather than a visit to every coalition.
Trees expose these intervals directly, while causal graphs require a search.
Trees
Where does a decision tree get its blocks? A decision tree predicts by following a root-to-leaf path, with each internal node testing one feature and each leaf carrying a prediction. To make this a game, reveal the features in \(S\) from the instance and take the remaining features from a background distribution. Then \(f(S)\) is the expected tree prediction, and \(\phi_i(f)\) is the average change in prediction when feature \(i\) is revealed.
Linearity lets us handle the background distribution one point at a time. Compute the game against one background point, compute its Shapley values, and then average those values over the background points.
Fix one such point. For a coalition \(S\), the tree receives a hybrid input: features in \(S\) come from the instance and all other features come from the background point. At a split where the two points follow the same branch, the tested feature places no restriction on \(S\). At a split where they disagree, reaching a particular leaf forces that feature either into \(S\) or out of it.
Collect those constraints along a root-to-leaf path. The features forced into \(S\) form the basis, the features forced out are removed from the closure, and every other feature is free. The coalitions reaching that leaf are exactly one lattice interval. One traversal therefore reads off at most one block per leaf.
Repeating the traversal for each background point gives interventional TreeSHAP [LE+, NMI ’20]. The interval formulation also extends the calculation to trees with a linear model at each leaf [ZBK, AAAI ’23]. (The path-dependent TreeSHAP variant uses stored node counts instead of a background distribution and computes a different game.)
A tree stores its partition in its leaves, so exact Shapley values reduce to a polynomial-time traversal (see a PSA on Shapley values).
Causal Models
Where does a causal model get its blocks? A structural causal model (SCM) is a directed acyclic graph whose nodes carry mechanisms. The do-operator [Pearl, ’09] forces a variable to a chosen value and cuts its dependence on its usual causes. For an instance \(x = (x_1, \dots, x_d)\) and target variable \(Y\), intervening on the variables in \(S\) gives the game:
\[ f(S) = \mathbb{E}\big[Y \mid \mathrm{do}(X_S = x_S)\big]. \]
The do-Shapley value is the average change in \(Y\) when variable \(i\) is additionally set to its value in the instance [HSBC, NeurIPS ’20] and [JKTJBB, ICML ’22].
The graph creates equal-value blocks through redundant interventions. Suppose every directed path from variables 1 and 2 to \(Y\) passes through variable 3. Setting 3 cuts both paths, so adding interventions on 1 or 2 changes nothing:
\[ f(\{3\}) = f(\{1,3\}) = f(\{2,3\}) = f(\{1,2,3\}). \]
These four coalitions form the interval from basis \(\{3\}\) to closure \(\{1,2,3\}\). The basis is the smallest intervention with that effect, while the closure adds every variable whose path to \(Y\) is already cut.
The number of blocks depends on the graph. In a chain \(1 \to 2 \to \cdots \to Y\), only the intervention closest to \(Y\) matters, giving \(d\) nonempty blocks plus the empty coalition. If every variable points directly to \(Y\), no intervention is redundant and all \(2^d\) coalitions may have different values.
An SCM does not hand us the basis and closure of each block. Recovering them requires a search through the graph’s intervention structure [WP+, ’26]. When that search finds only \(r\) blocks, the final calculation uses \(r\) trips through the model and \(O(rd)\) arithmetic.
One Decomposition
What do we take away for a game that is neither a tree nor a causal model? Trees and causal models use the same Shapley calculation once their equal-value coalitions have been collected into intervals. A tree records the intervals in its leaves; a causal graph encodes them in its paths. Before summing over \(2^d\) coalitions, count the distinct game values and ask whether the coalitions sharing each value have a structure whose total coefficient can be computed directly.