Shapley Values for Piecewise-Constant Games
8 min read
Let \(f(S)\) be the value produced by a group \(S\) of players. The Shapley rule assigns credit to each player by averaging how much they add to the groups they join. There may be exponentially many groups to check, yet many of them can produce the same value.
Decision trees organize these repeated values so we can combine their contributions [LE+, NMI ’20]. The beautiful saving is to assign everyone’s credit without visiting every group.
Decomposition
Index the \(d\) players by \([d] = \{1, \dots, d\}\) and call a group \(S \subseteq [d]\) a coalition. The function \(f\) is called a game.
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.
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). \]
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
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: required by the basis, freely included, or excluded by the closure. For a free player, adding or removing it never changes whether a coalition lies in the block, so that block contributes zero to its Shapley value. The other two cases count coalitions of each size with a positive or negative sign.
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} \]
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.
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.
Trees expose these intervals directly, while causal graphs require a search.
Trees
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
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.