Shapley Values for Piecewise-Constant Games
12 min read
The Shapley value of player \(i\) is a sum over all \(2^d\) coalitions, which is why exact Shapley values are usually out of reach: for \(d = 30\) features that is already a billion evaluations of the game. But the sum depends only on the game’s values, and real games are often repetitive: whole families of coalitions return the very same number.
The two places I have watched this pay off are decision trees, where the blocks fall out of the leaves in a single pass, and structural causal models, where finding them took us a whole paper (Witter, Parafita, Garriga, Muschalik, Fumagalli, Brando & Rosenblatt [WP+, ’26]). The decomposition underneath is the same, so let us do it in general first.
The Decomposition
Nothing so far says how a repeated value saves work, and the definition of the Shapley value is why: no value appears in it on its own. A game is a set function \(f : 2^{[d]} \to \mathbb{R}\) on \(d\) players \([d] = \{1, \dots, d\}\). Picture the players arriving in a uniformly random order, and watch how the game’s value jumps at the moment player \(i\) walks in. The Shapley value of player \(i\) is the average of these jumps, \(i\)’s marginal contributions, weighted by how often each coalition \(S\) arrives before \(i\):
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} p_{|S|}\,\big( f(S \cup \{i\}) - f(S) \big), \]
where a coalition of size \(s\) carries the weight
\[ p_s = \frac{s!\,(d - s - 1)!}{d!}. \]
The weight \(p_s\) is the probability that a uniformly random arrival order puts exactly the players of \(S\) before \(i\). Every term is a difference, so a value the game returns on many coalitions is spread across many marginal contributions. To pull a shared value out of a sum it must appear in terms of its own, and here it never does.
To bring a repeated value into view, regroup the sum by the coalition whose value is read, rather than by marginal contribution. First split the marginal contribution into two sums, one reading \(f\) on coalitions that contain \(i\) and one reading \(f\) on coalitions that omit \(i\):
\[ \phi_i(f) = \sum_{S \subseteq [d] \setminus \{i\}} p_{|S|}\, f(S \cup \{i\}) \;-\; \sum_{S \subseteq [d] \setminus \{i\}} p_{|S|}\, f(S). \]
In the first sum, reindex by the coalition actually evaluated, \(T = S \cup \{i\}\), so \(T\) ranges over coalitions that contain \(i\) and \(|S| = |T| - 1\); the second sum already runs over coalitions \(T = S\) that omit \(i\):
\[ \phi_i(f) = \sum_{T \ni i} p_{|T| - 1}\, f(T) \;-\; \sum_{T \not\ni i} p_{|T|}\, f(T). \]
Each coalition contributes exactly one term, so the Shapley value is a fixed linear combination of the game’s \(2^d\) values:
\[ \phi_i(f) = \sum_{S \subseteq [d]} c_{i,S}\, f(S), \]
with a coefficient that depends only on whether \(i\) is inside the coalition:
\[ c_{i,S} = \begin{cases} +p_{|S| - 1} & i \in S, \\ -p_{|S|} & i \notin S. \end{cases} \]
A coalition that contains \(i\) enters with a plus sign and the weight one size down, and a coalition that omits \(i\) enters with a minus sign and its own weight. Only the size and the membership of \(i\) matter.
Now for the repetition, in the smallest game that shows it. Picture three players where player 3 overrides the other two: once 3 is in a coalition, adding or dropping 1 or 2 changes nothing. The four coalitions that contain player 3 return one shared value, so the linear combination above spends four of its eight terms on a single number. In general, the game is piecewise constant when the \(2^d\) coalitions fall into blocks \(B_1, \dots, B_r\), and \(f\) takes a single value \(f_j\) on every coalition in \(B_j\). Our example has five blocks: the four coalitions containing player 3, and each of the other four coalitions alone. Split the linear combination over the blocks, then pull the shared value \(f_j\) out of each:
\[ \begin{aligned} \phi_i(f) &= \sum_{j=1}^{r} \sum_{S \in B_j} c_{i,S}\, f(S) \\ &= \sum_{j=1}^{r} f_j \sum_{S \in B_j} c_{i,S} \\ &= \sum_{j=1}^{r} f_j\, w_{i,j}. \end{aligned} \]
The last line names the inner sum the block weight, the total Shapley coefficient the block contributes to player \(i\):
\[ w_{i,j} = \sum_{S \in B_j} c_{i,S}. \]
The \(2^d\)-term sum has become \(r\) terms, one per distinct value. Everything now rides on whether the block weight \(w_{i,j}\) is cheap to compute.
It is cheap whenever a block is an interval of the coalition lattice, pinned by two coalitions: a basis \(\underline{S}_j\) (its smallest) and a closure \(\bar{S}_j\) (its largest). The block holds every coalition between them:
\[ B_j = \{ T : \underline{S}_j \subseteq T \subseteq \bar{S}_j \}. \]
These are the coalitions that contain all of \(\underline{S}_j\) and nothing outside \(\bar{S}_j\), leaving the elements of \(\bar{S}_j \setminus \underline{S}_j\) free to be in or out. The shared block in our example is exactly such an interval, drawn in the lattice below: basis \(\{3\}\), closure \(\{1,2,3\}\), players 1 and 2 free in the middle.
Where player \(i\) sits relative to the basis and closure decides \(w_{i,j}\), and there are three cases.
The first case is a cancellation. Suppose \(i\) lies in the free middle:
\[ i \in \bar{S}_j \setminus \underline{S}_j, \]
so \(i\) belongs to some members of the block but not all. The members then split into pairs \((T, T \cup \{i\})\) with \(i \notin T\), both still in \(B_j\). Their coefficients are opposite:
\[ \begin{aligned} c_{i,T} + c_{i, T \cup \{i\}} &= -p_{|T|} + p_{|T \cup \{i\}| - 1} \\ &= -p_{|T|} + p_{|T|} \\ &= 0, \end{aligned} \]
where the second line uses \(|T \cup \{i\}| = |T| + 1\), since \(i \notin T\). Adding \(i\) keeps you inside the block, so \(i\) never changes the value and the block weight vanishes:
\[ w_{i,j} = 0. \]
In the figure, players 1 and 2 sit in the free middle of the teal interval, so that block contributes nothing to their Shapley values.
In the other two cases \(i\) is fixed across the whole block: it is in every member (\(i \in \underline{S}_j\)) or in no member (\(i \notin \bar{S}_j\)). Then \(c_{i,S}\) depends only on the size of \(S\), so group the members of \(B_j\) by size. Write \(a = |\underline{S}_j|\) and \(b = |\bar{S}_j|\) for the sizes of the basis and closure. A member of size \(\ell\) takes all \(a\) basis elements plus any \(\ell - a\) of the \(b - a\) free ones, and there are \(\binom{b - a}{\ell - a}\) such members. When \(i \in \underline{S}_j\) every member contains \(i\) and contributes \(+p_{\ell - 1}\); when \(i \notin \bar{S}_j\) no member contains \(i\) and each contributes \(-p_\ell\):
\[ w_{i,j} = \begin{cases} \displaystyle +\sum_{\ell = a}^{b} \dbinom{b - a}{\ell - a}\, p_{\ell - 1} & i \in \underline{S}_j, \\[10pt] \displaystyle -\sum_{\ell = a}^{b} \dbinom{b - a}{\ell - a}\, p_\ell & i \notin \bar{S}_j. \end{cases} \]
Either way the block weight adds one weight per member, signed plus when \(i\) is in every member and minus when \(i\) is in none. Each sum has at most \(d\) terms, so a block weight costs \(O(d)\). Neither sum depends on \(i\) beyond which case it falls into, so two of them cover a whole block. Once the intervals are known, all \(d\) exact Shapley values cost \(O(rd)\): linear in the number of distinct values, not in the number of coalitions.
The work has moved entirely into finding the blocks. In a decision tree they are handed to you; in a causal model they are hidden in the graph.
Trees
A tree hands over its blocks, but only once we say what the game is: the model predicts from a complete instance, not from a coalition. A decision tree predicts by a walk from the root: each internal node tests one feature and sends you left or right, and the leaf you reach carries the prediction. Make it a game by revealing only the features in \(S\) and averaging the model over the rest (the interventional convention): \(f(S)\) is the tree’s expected prediction when the splits on features in \(S\) follow the instance and every other split branches by the background distribution. Here \(\phi_i(f)\) reads as the average change in the tree’s prediction when feature \(i\) is revealed.
This game is piecewise constant almost by construction. A feature the walk never tests cannot change the prediction, and a tested feature changes it only when revealing it reroutes the walk toward different leaves. The blocks come into view once we take the background one point at a time. Since \(\phi_i(f)\) is a fixed linear combination of the game’s values, the Shapley values computed against a single background point average to the Shapley values against the whole background. So fix one background point, and let the tree predict on the input that takes the features in \(S\) from the instance and the rest from that point. That input follows one root-to-leaf path. Either a split on the path sends the instance and the background point the same way, and its feature never matters, or it sends them different ways, and the branch taken says whether its feature is in \(S\). So the coalitions that reach a given leaf form exactly an interval: the basis is the features whose splits went the instance’s way, the closure drops the features whose splits went the background point’s way, and every other feature is free in the middle. One traversal reads off a basis and a closure per leaf, so the block count \(r\) is at most the number of leaves. Repeating that traversal once per background point computes the interventional TreeSHAP values, Algorithm 3 of Lundberg, Erion, Chen, DeGrave, Prutkin, Nair, Katz, Himmelfarb, Bansal & Lee [LE+, NMI ’20]. Zern, Broelemann & Kasneci [ZBK, AAAI ’23] rederive that algorithm from exactly this decomposition, one lattice interval per leaf, and the same decomposition extends it to trees carrying a linear model at each leaf. The better-known path-dependent variant of TreeSHAP answers a different question: it swaps the tree’s stored node counts in for the background sample and aims at the observational game, where the hidden features follow their distribution conditioned on the revealed ones. A tree is the lucky case: its structure spells out the partition, so exact Shapley values are a polynomial-time walk (see a PSA on Shapley values). A causal graph creates the same repetition and lists none of it.
Causal Models
The game is different here, since a causal model sets variables rather than revealing them. A structural causal model (SCM) is a directed acyclic graph of variables with a mechanism at each node. Pearl’s do-operator [Pearl, ’09] lets us intervene: \(\mathrm{do}(X_i = x_i)\) forces variable \(i\) to the value it takes in the instance \(x = (x_1, \dots, x_d)\), severs it from its usual causes, and shows what happens downstream. The game is the expected value of a target variable \(Y\) under such an intervention:
\[ f(S) = \mathbb{E}\big[\, Y \mid \mathrm{do}(X_S = x_S) \,\big], \]
the expected outcome when the variables in \(S\) are set to their values in the instance and the rest run their mechanisms. Its Shapley value, the do-Shapley value of Heskes, Sijben, Bucur & Claassen [HSBC, NeurIPS ’20] and Jung, Kasiviswanathan, Tian, Janzing, Blöbaum & Bareinboim [JKTJBB, ICML ’22], reads as the average change in the outcome \(Y\) when we additionally set variable \(i\).
The graph is the source of the repetition. Suppose, as in the diagram below, that every directed path from \(1\) and \(2\) to \(Y\) runs through variable \(3\). Then setting \(3\) already fixes whatever \(1\) and \(2\) could have done downstream, so intervening on any coalition that contains \(3\) gives the same outcome:
\[ f(\{3\}) = f(\{1,3\}) = f(\{2,3\}) = f(\{1,2,3\}). \]
That is a block, and exactly the interval from the decomposition: its basis is the smallest intervention with that effect, \(\{3\}\), and its closure adds every variable whose paths to \(Y\) are already cut, \(\{1,2,3\}\). How many blocks there are depends entirely on the graph. A chain \(1 \to 2 \to \cdots \to Y\) gives only \(d + 1\) blocks. The intervention closest to \(Y\) overrides every intervention behind it, so \(f(S)\) depends on \(S\) only through its largest element. That is \(d\) blocks, one per choice of largest element, plus the empty coalition, which intervenes on nothing and takes a value of its own. At the other extreme, a graph in which every variable points straight at \(Y\) gives all \(2^d\) blocks, no intervention redundant.
The catch is that an SCM does not hand you its blocks: the basis and closure of a coalition are properties of the graph’s paths, and recovering every interval takes a search over the coalition lattice. That search, and the exact do-Shapley values it yields in time linear in the number of blocks, is what [WP+, ’26] works out. Where the blocks are few, the whole computation costs the \(O(rd)\) above instead of \(2^d\) trips through the model.
The Same Idea Twice
Trees and causal models look nothing alike, yet one move computes both their Shapley values: notice that the game is constant on blocks of coalitions and compute one term per block. The decomposition is identical (a basis, a closure, and a binomial block weight), and only the blocks differ: a tree writes them on its leaves, a causal graph hides them in its paths. So before resigning yourself to \(2^d\) evaluations of a game, ask how many distinct values it really has. That count, not the number of coalitions, is what its Shapley value costs.