Exactly Computing do-Shapley Values R. Teal Witter * 1 Álvaro Parafita * 2 Tomàs Garriga 2 3 Maximilian Muschalik 4 Fabian Fumagalli 4 Axel Brando 2 Lucas Rosenblatt 5 Abstract Structural Causal Model (SCM) Structural Causal Models (SCM) are a powerful X1 X3 framework for describing complicated dynamics closure S = {X1, X2, X3, X4} Y basis S = {X3} arXiv:2602.07203v1 [cs.LG] 6 Feb 2026 across the natural sciences. A particularly ele- gant way of interpreting SCMs is do-Shapley, a X2 X4 game-theoretic method of quantifying the average effect of d variables across exponentially many 1, 2, 3, 4 interventions. Like Shapley values, computing do-Shapley values generally requires evaluating 1, 2, 4 1, 2, 3 1, 3, 4 2, 3, 4 exponentially many terms. The foundation of our work is a reformulation of do-Shapley val- 1, 4 1, 2 1, 3 2, 3 3, 4 2, 4 ues in terms of the irreducible sets of the under- 1 2 3 4 lying SCM. Leveraging this insight, we can ex- actly compute do-Shapley values in time linear Ø in the number of irreducible sets r, which itself Lattice of Coalitions can range from d to 2d depending on the graph structure of the SCM. Since r is unknown a pri- Figure 1. An example Structural Causal Model (SCM) and the ori, we complement the exact algorithm with an corresponding lattice of coalitions. Because of the graph structure, intervening on some nodes is redundant. For example, setting estimator that, like general Shapley value estima- {X1 , X2 , X3 , X4 } has the same effect as setting {X3 } because tors, can be run with any query budget. As the X3 blocks all directed paths from the other nodes to Y . For such a query budget approaches r, our estimators can class, we refer to its smallest coalition (e.g., {X3 }) as the basis, produce more accurate estimates than prior meth- and the largest coalition (e.g., {X1 , X2 , X3 , X4 }) as the closure. ods by several orders of magnitude, and, when the budget reaches r, return the Shapley values up to machine precision. Beyond computational speed, cient due to the fundamental problem of causal inference: we also reduce the identification burden: we prove because we cannot observe the counterfactual world where that non-parametric identifiability of do-Shapley a specific intervention did not occur, we cannot definitively values requires only the identification of interven- state, based on data alone, that one event caused another tional effects for the d singleton coalitions, rather (Holland, 1986; Rubin, 1974). than all classes. Structural Causal Models (SCMs) offer a powerful solu- tion by explicitly modeling the underlying mechanisms of a system (Pearl, 2009). Whether derived from established do- 1. Introduction main knowledge or learned via causal discovery algorithms The question of causality is crucial to scientific inquiry, rang- (Peters et al., 2017), SCMs formalize the data-generating ing from policy evaluation in economics to treatment effects process: a directed acyclic graph G representing causal re- in healthcare. Yet, observational data alone is often insuffi- lationships, and a set of structural equations that determine 1 the value of each node as a function of its parents and ex- Mathematical Sciences Department, Claremont McKenna College 2 Barcelona Supercomputing Center, Barcelona, Spain ogenous noise (Bareinboim & Pearl, 2016). We provide a 3 Novartis 4 LMU Munich, MCML 5 Department of Computer more formal introduction to SCMs in Appendix B. Science and Engineering, New York University. Correspon- With a fully specified SCM, we can rigorously evaluate the dence to: R. Teal Witter , Álvaro Parafita . effect of specific actions using the do-operator (Pearl, 2009). This operator simulates an intervention where a subset of Preprint. February 10, 2026. variables is forced to take specific values, independent of 1 Exactly Computing do-Shapley Values 1.0 Bid Ask Est. (Normalized) Close Volume Ask 0.5 High Bid Bid Volume High 0.0 Bid Open Ask 0.5 Ask Open Low RegressionMSR LeverageSHAP 1.0 doRegressionMSR doLeverageSHAP 1.0 0.5 0.0 0.5 1.0 1.0 0.5 0.0 0.5 1.0 True (Normalized) Figure 2. Left: A learned SCM from a TALENT dataset. Nodes and edges represent the learned causal graph used to define the interventional value function ν(S) = E[Y | do(S = xS )] for a fixed instance x. Right: Plots of estimated vs true do-Shapley values on the learned SCM for randomly sampled x. Compared to the value-function-agnostic state-of-the-art RegressionMSR and LeverageSHAP estimators, our doEstimator variants provide substantially more accurate do-Shapley value estimates. their natural causes. Consider a specific instance of interest Lee, 2017) or restrictive path-dependent permutations (Frye x ∈ Rd . We define the value function ν(S) as the expected et al., 2020), this metric strictly isolates the total causal ef- value of the target outcome Y when the subset of features fect of a feature intervention. This rigorous isolation allows S ⊆ [d] is intervened upon to match their observed values us to translate abstract model dynamics into concrete causal in x: attributions, such as statements like “High family income increased acceptance probability by 10%” or “Prescribing ν(S) = E[Y | do(S = xS )]. (1) prednisone decreased reported pain by two marks.” This formulation enables us to precisely answer hypothetical The challenge in computing the Shapley value, of course, queries, such as: “If we explicitly set this student’s income is that there are still 2d terms ν(S). So, without additional and tutoring time, how would their probability of admission structure in ν, exactly computing the Shapley value would change?” or “If a patient were administered prednisone take exponential time. To address this, the standard ap- and made to stop smoking, what would be their expected proach is to approximate the Shapley value using stochas- pain level?” However, characterizing the system’s behavior tic estimators that evaluate ν(S) on a limited budget of purely through these individual queries is challenging. As sampled coalitions. A diverse array of model-agnostic es- the number of features d grows, the number of possible timators has been developed for this purpose, including interventional subsets scales as 2d . To extract interpretable direct Monte Carlo estimators (Štrumbelj & Kononenko, insights from this combinatorial landscape, we need a uni- 2014), permutation-based sampling (Castro et al., 2009), fied framework to attribute the complicated dynamics of the and regression-based formulations such as KernelSHAP SCM to individual features. and LeverageSHAP (Lundberg & Lee, 2017; Covert & Lee, 2021; Musco & Witter, 2025). The Shapley value (Shapley, 1953) provides a rigorous framework for such explanations by attributing the changes For do-Shapley values, recent work has exploited the obser- in the outcome Y to individual variables based on their vation that the topological structure of SCMs often renders marginal contributions. Formally, the ith Shapley value cap- specific interventions redundant (Parafita et al., 2025). For tures the weighted average effect of adding variable i to a example, in the causal graph depicted in Figure 1, the inter- coalition S: vention on {X3 } results in the same value as the intervention X on {X1 , X3 , X4 }, because the paths from X1 and X2 to Y ϕi = [ν(S ∪ i) − ν(S)]p|S| (2) are blocked by X3 . To formalize this, define the basis of a S⊆[d]\i coalition S as the subset S ⊆ S containing precisely those where the weight pℓ = d1 d−1 −1 can be interpreted as a variables j ∈ S that possess a directed path to Y that does ℓ probability distribution. not traverse any other node in S. In effect, any variable in S \ S is intercepted by S and yields no additional impact When the value function is defined via the interventional do- on the outcome, ensuring ν(S) = ν(S). A set is irreducible operator (Equation 1), the result is the do-Shapley value if it is its own basis. This property enables a caching strat- (Jung et al., 2022), also referred to as the causal Shap- egy: rather than naively evaluating the SCM for every query ley value (Heskes et al., 2020).1 Unlike standard formu- ν(S), the estimator first computes the basis S and checks lations that rely on conditional expectations (Lundberg & simply as the value function, and the do-Shapley value as the 1 Shapley value. For conciseness, we henceforth refer to the do-value function 2 Exactly Computing do-Shapley Values if ν(S) has been previously memoized. If so, the cached ··· 1 2 d Y value is returned; if not, the SCM is evaluated and the result stored. This mechanism avoids redundant evaluations of (a) Since there is a directed path from each node to Y , there the underlying model, resulting in significant computational are at least d irreducible sets. The figure depicts a graph with speedups (Parafita et al., 2025). d irreducible sets. We extend this insight by observing that every basis S is 1 2 ··· d associated with a unique closure S̄ ⊇ S—the maximal coalition such that intervening on S̄ yields the identical Y effect as intervening on S. For example, the closure of {X3 } in Figure 1 is {X1 , X2 , X3 , X4 }. Together, these (b) Since there are 2d sets total, there are at most 2d irreducible bounds define an equivalence class of coalitions {S ⊆ [d] : sets. The figure depicts a graph with 2d irreducible sets. S ⊆ S ⊆ S̄}, all of which map to the same value ν(S). Figure 3. The number of irreducible sets ranges between d and 2d . Crucially, these classes constitute a partition of the powerset of all d features. Letting r denote the total number of such classes c1 , . . . , cr , we leverage this structure to compress proaches is sample redundancy. Standard estimators sam- the Shapley summation into a linear combination of class ple coalitions without knowledge of the underlying causal values: structure, meaning they can (wastefully) query different r X coalitions that belong to the same large equivalence class. ϕi = ν(cj )wi (cj ) (3) Thus, a budget of m queries often produces far fewer than m j=1 unique values. We resolve this inefficiency by introducing a boundary sampler, a targeted exploration strategy guaran- where the class weight wi (cj ) is derived in Equation 5. A teed to identify min(m, r) distinct equivalence classes when similar decomposition is known for trees (Zern et al., 2023b; run with m queries. By feeding these distinct values into a Witter et al., 2025); but, unlike trees where the structure can simulated estimator, we maximize the information extracted be read in a linear pass of the leaves, efficiently finding the from the available budget. We find that this method can class structure of an SCM is non-trivial. reduce estimation error by orders of magnitude compared This formulation reduces the exact computation of Shapley to the best value-function-agnostic estimators run with the values to a sum over r terms. To identify these classes caching scheme of Parafita et al. (2025). Furthermore, the efficiently, we propose a lattice exploration algorithm that estimator exhibits seamless convergence: as the budget m circumvents the exhaustive enumeration of the powerset. approaches r, the approximation error vanishes, achieving Leveraging a structural property of closed sets (Lemma 3.1), exact computation (up to machine precision) once m ≥ r. our algorithm enumerates all r classes in O(r(d + e + T )) In practice, SCMs are frequently learned from observational time, where e is the number of edges in the causal graph data and a hypothesized graph structure. A critical prerequi- and T is the time to query the value function once. site for this process is identifiability: determining whether a The efficiency of this approach is strictly governed by the causal query can be uniquely estimated from the observed underlying graph topology. As illustrated in Figure 3, the number of classes r varies with the graph structure, ranging 105 70 from a linear d in the best case to 2d in the worst case. Observed (r) Exhaustive (2d) 60 104 Linear Lower Bound (d) Number of Classes r To quantify how much this compression manifests in prac- Number of Edges |E| 50 tice, we plot the number of irreducible sets r against the 103 40 number of variables d across real datasets in Figure 4. The observed scaling typically lies below the worst-case 2d , re- 102 30 flecting the sparsity of learned causal graphs in real-world 20 tabular domains. 101 10 Although our exact algorithm scales linearly with r, the number of classes r is unknown a priori. Since real-world 2 4 6 8 10 12 14 16 Dimension d (Nodes) applications demand strict resource limits, we must often operate within a fixed computational budget of m value Figure 4. Complexity Reduction. The number of irreducible sets function queries. To address this, we propose a class of r (colored points) versus the dimension d. While the theoretical worst-case complexity is 2d (red dashed line), real-world causal estimators explicitly tailored to this constrained setting. structures are often sparse, resulting in r scaling in between the The fundamental limitation of prior caching-based ap- exponential and the linear lower bound d (black dotted line). 3 Exactly Computing do-Shapley Values probability distribution given the graph (Pearl, 2009). For 1997), capturing the joint causal impact of coalitions. instance, in the presence of unobserved confounding, differ- ent structural parameters could yield the exact same obser- 1.1. Additional Related Work vational distribution but different interventional outcomes. The gold standard for verifying non-parametric identifia- Exactly computing Shapley values is generally feasible only bility is the ID algorithm (Shpitser & Pearl, 2006; Tian & when the underlying model possesses exploitable structure Pearl, 2002), which determines if a specific query ν(S) is (Rozemberczki et al., 2022). This has led to efficient, model- computable from the observational distribution. specific algorithms for decision trees and ensembles, includ- ing TreeSHAP (Lundberg et al., 2020; Yu et al., 2022), This creates a practical bottleneck for Shapley value es- interventional variants (Zern et al., 2023b), and extensions timation. Since the Shapley value aggregates r terms, a like TreeSHAP-IQ (Muschalik et al., 2024c). Similar exact practitioner using prior methods would be forced to run methods exist for linear models (Štrumbelj & Kononenko, the estimator and iteratively check identifiability for each 2014), product-kernel networks (Mohammadi et al., 2025a), irreducible set encountered. If a single coalition proved Gaussian processes (Mohammadi et al., 2025b), graph neu- unidentifiable, the entire estimation would be invalidated af- ral networks (Muschalik et al., 2025), and KNN-based data ter significant computation (Parafita et al., 2025). In Section valuation (Jia et al., 2019; Wang et al., 2023; 2024). When 5, we resolve this burden by proving a structural sufficiency black-box access precludes exact methods, practitioners rely theorem: to guarantee the identifiability of all 2d coalitions, on model-agnostic estimators (Chen et al., 2023; Muschalik it suffices to verify identifiability for only the d singleton et al., 2024b) such as Monte Carlo sampling (Castro et al., interventions {i} ⊂ [d]. This allows practitioners to run a 2009; Kolpaczki et al., 2024b;a; Fumagalli et al., 2023; rapid, O(d) sanity check before model training begins, en- Wang & Jia, 2023) or regression-based approaches like suring that the resulting Shapley values will be valid without KernelSHAP (Lundberg & Lee, 2017), which has been the risk of costly mid-computation failures. enhanced via leverage scores (Musco & Witter, 2025) and In summary, our contributions are three-fold: interaction support (Fumagalli et al., 2024; Tsai et al., 2023). Finally, exact computation has recently merged with esti- 1. Exact Computation via Irreducible Sets: We propose mation via surrogate modeling (Butler et al., 2025), where an algorithm that computes exact do-Shapley values by auxiliary models are fit to the value function to allow effi- exploiting the graph’s equivalence classes. By traversing cient extraction of Shapley values (Witter et al., 2025). the lattice of closed sets, the algorithm runs in time linear in the number of irreducible sets r (and the graph size e), rather than the worst-case exponential complexity of 2d . 2. Reformulating do-Shapley Values 2. Structure-Aware Estimation: We introduce a class of In this section, we leverage the underlying structure of an boundary sampling estimators designed for fixed-budget SCM to reformulate do-Shapley values in terms of equiva- settings. Unlike prior methods that sample blindly, our ap- lence classes. proach targets distinct equivalence classes. This yields error Firstly, we will assume that all nodes in [d] are ancestors of reductions of several orders of magnitude as m approaches the target node Y , since non-ancestors have null do-Shapley r, and seamlessly transitions to exact machine-precision value. We will start with the definition of basis, derived computation once the budget satisfies m ≥ r. from the concept of irreducible sets in Parafita et al. (2025). 3. Efficient Identifiability Check: We prove that non- Definition 2.1 (Basis). The basis of S, denoted S, is the parametric identifiability of the full do-Shapley value is subset of nodes j ∈ S such that there exists a directed path guaranteed if and only if the d singleton interventions are from j to Y that intersects S only at j. non-parametrically identifiable. This result enables a rapid O(d) sanity check, allowing practitioners to verify the fea- A set S ⊆ [d] is irreducible if it is its own basis. sibility of the explanation task before incurring the cost of Similarly, we will define the closure of S as the superset of model training or estimation. nodes that can be blocked from reaching Y by S. While we focus on the Shapley value due to its Definition 2.2 (Closure). The closure of S, denoted S̄, is widespread adoption, our theoretical insights generalize to the set of all nodes j ∈ [d] such that every directed path the broader class of probabilistic values—e.g., Banzhaf val- from j to Y intersects S. ues (Banzhaf III, 1964), beta Shapley values (Kwon & Zou, 2022), and weighted Banzhaf values (Li & Yu, 2024)—by We say a set S ⊆ [d] is closed if it is its own closure. simply changing the marginal weights in Equation 4. Fur- Let S and S̄ be the basis and closure of a coalition S, re- thermore, in Section 7, we demonstrate how to adapt our spectively. S belongs to an equivalence class with all T methods to compute Shapley Interaction Indices (Grabisch, such that S ⊆ T ⊆ S̄. By definition, all nodes in T \ S 4 Exactly Computing do-Shapley Values are blocked from reaching Y by S, so, by the third rule of Algorithm 1 FindClass do-Calculus (Pearl, 2009), Input: Set S ⊆ [d], graph G Output: basis S ⊆ S, and closure S̄ ⊇ S ν(S) = ν(T ) = ν(S̄). G′ ← G with all incoming edges to nodes in S removed Nanc ← ancestor nodes i.e., a directed path to Y in G′ It is easy to see that the classes form a partition of all 2d S̄ ← S ∪ ([d] \ Nanc ) ▷ S and nodes not connected to Y coalitions. S ← S ∩ Nanc ▷ Subset of S still connected to Y Let r be the number of irreducible sets, and denote the return S, S̄ classes by c1 , . . . , cr . In an abuse of notation, we will define ν(cj ) = ν(S) where S is any set in class cj . We will use this structure to rewrite the Shapley values: there are 2d sets on the lattice, so even constant work per set is infeasible. Instead, we can efficiently traverse the set lattice by only generating sets which are guaranteed to ϕi = X p|S| [ν(S ∪ {i}) − ν(S)] be closed, amortizing the work to each class, rather than each subset. The key tool is a structural lemma on alternate S⊆[d]\{i} definitions of closed sets. ν(S) 1[i ∈ S]p|S|−1 − 1[i ∈ X   = / S]p|S| Lemma 3.1. Let S̄ ⊂ [d] be a closed set with basis S. Then S⊆[d] r X 1. For all j ∈ S, S̄ \ {j} is closed. = ν(cj ) · wi (cj ) (4) j=1 2. If S̄ ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is closed and j is in the basis of S̄ ∪ {j}. where, with S̄ as the closure of class c and S as the basis of class c, we define We defer the proof of the lemma to Appendix A. 1[i ∈ T ]p|T |−1 − 1[i ∈/ T ]p|T | . X   wi (c) = Algorithm 2 describes our method. We efficiently find each T :S⊆T ⊆S̄ class by iterating over closed sets, in decreasing order of size. We start with the full set [d]. For each closed set S̄ of Even though there could be exponentially many subsets in a size ℓ, we compute its basis S. By Lemma 3.1, S̄ \ {j} is class, we can compute wi (c) in O(d) time. In particular, it closed for all j ∈ S. We then add each of these closed sets, is easy to show that and further explore them when we reach size ℓ − 1. We can see that Algorithm 2 correctly returns all closed sets P by an inductive argument. Suppose that we have identified |S̄| pℓ−1 |S̄|−|S| all closed sets of size ℓ; the base case is trivial since there    ℓ=|S| ℓ−|S| i∈S is only one set, and it must be closed. By Lemma 3.1,     wi (c) = − |ℓ=|S| P S̄| pℓ |S̄|−|S|  i∈/ S̄ (5) for every closed set S̄ of size ℓ − 1, there is a closed set ℓ−|S|    S̄ ∪ {j} for some j in the basis of S̄ ∪ {j}. By the inductive assumption, we must have identified this set, and also found   0 else. S̄ by removing j from S̄ ∪ {j}. It follows that every closed set of size ℓ − 1 gets generated by some closed set of size ℓ. We will use this structure to compute Shapley values. If we have O(r(d + e)) time, then we can exactly compute Shapley values as described in Section 3. Since r is initially Algorithm 2 AllClasses unknown, we may also want to estimate Shapley values Input: Number of elements d, graph G given a fixed query budget m. In Section 4, we describe Output: All closed sets C estimators that run in O(m(d + e)) time. C0 ← . . . ← Cd ← ∅ ▷ Closed sets of each size Cd ← {{1, . . . , d}} ▷ Only closed set of size d 3. Exactly Computing do-Shapley Values for ℓ = d, . . . , 1 do for S̄ ∈ Cℓ do By Equation 4, computing all irreducible sets is sufficient S, S̄ ← FindClass(S̄, G) to exactly compute the Shapley value. It remains to find all ▷ Use Lemma 3.1 irreducible sets. for j ∈ S do Add S̄ \ {j} to Cℓ−1 A naive strategy is to traverse the set lattice by subset size, return C0 ∪ . . . ∪ Cd determining the class of each set via Algorithm 1. Of course, 5 Exactly Computing do-Shapley Values Algorithm 2 runs in O(r(d + e)) time: for each closure— sample classes proportional to their weights wi (cj ) because there is one closure for each of the r classes—the algorithm the classes (and thus their weights) are unknown without runs a graph exploration in time d + e, and then adds at most graph exploration. Furthermore, a stratified sampling ap- d closed sets of size ℓ − 1 to explore. proach—sampling coalitions without replacement to ensure unique classes—proves computationally expensive. As de- Simple Class Optimization Sometimes running Algo- tailed in Appendix D, such a stratified sampling method rithm 1 as a subroutine in Algorithm 2 can be avoided. For incurs a cost quadratic in m, which defeats the purpose of a closed set S̄ that is simple—S̄ is both its own closure and fast approximation. basis—all of its subsets are also simple. To see why, observe that all nodes j ∈ S̄ have a directed path to Y that does not intersect any other node in S̄, and hence any other node in a Boundary Sampling We propose a boundary sampler, subset of S̄. It follows that all subsets are irreducible; with a targeted graph exploration strategy that achieves sample Lemma 3.1, we have that all such subsets are also closed. efficiency in time linear in m. Instead of sampling blindly For a simple set, we add an optimization to Algorithm 2 in from the powerset, we maintain candidate classes adjacent our implementation so that all the bases of its candidates are to those we have already visited. cached, avoiding the O(d + e) cost of Algorithm 1 for all The algorithm, described in Algorithm 3, proceeds by main- subsets of a simple set. taining a priority queue of candidate classes, ordered by Together, Equation 4 and Algorithm 2 can compute Shapley their expected weight magnitude Ei [|wi (c)|]. In each it- values in time linear in r. eration, we sample a class c proportional to the expected magnitude of its weight, evaluate ν(c), and add it to our Proposition 3.2. Shapley values of the intervention value sampled set. We then expand the candidate by generating function can be exactly computed in O(r(d + e + T )) time, the neighbors of c in the lattice. Specifically, for a class where T is the time to evaluate the game ν on a given c with basis S and closure S̄, the neighbors are defined as coalition, and r is the number of irreducible sets. either lower neighbors {S̄ \{j} | j ∈ S} or upper neighbors {S̄ ∪{j} | j ∈/ S̄}. For each neighbor, we run FindClass 4. Approximating do-Shapley Values to determine its canonical representation and weight, adding it to the queue if it has not been seen. This ensures that While Algorithm 2 allows for exact computation in O(r(d + every query results in a new class. By starting at each level e)) time, the number of irreducible sets r is unknown a in the lattice, and adding neighbors above and below, we priori. In resource constrained settings where r may be explore the lattice in a balanced way. too large, we would like an approximation technique that operates within a fixed computational budget of m value We state Algorithm 3, and prove the following upper bound function queries. on its runtime, in Appendix A. Standard value-function-agnostic estimators sample coali- Proposition 4.1. Algorithm 4 runs in O(m · d(d + e)) time, tions from a fixed distribution. While caching can prevent where m is the query budget, d is the number of features, re-evaluation of the SCM for known classes, these estima- and e is the number of edges in the graph. tors suffer from sample redundancy: they blindly generate coalitions that may belong to equivalence classes already Estimation via Simulation After running the boundary queried. As a result, a budget of m queries often yields far sampler, we utilize the set of sampled classes C to compute fewer than m distinct class values, wasting computational the Shapley values, as shown in Algorithm 3. resources on redundant parts of the lattice. Case m ≥ r: If the queue empties before the budget is To address this, we seek an estimator that guarantees the reached, we have identified all irreducible sets. We proceed discovery of min(m, r) distinct equivalence classes. If m ≥ to compute the exact Shapley values using Equation 6. r, the method should naturally recover the exact Shapley values to machine precision. If m < r, it should prioritize Case m < r: We leverage the fact that we have paid the classes with weight to minimize estimation error. cost to evaluate ν(c) for all c ∈ C. We construct a simulated estimator, described in Appendix C. This allows us to gener- Recall that the Shapley value can be expressed as a weighted ate many samples at no additional query cost, reducing the sum over equivalence classes: variance of the estimator while balancing time complexity. r ϕi = X ν(cj ) · wi (cj ). (6) We run Algorithm 3 where the base estimators are the cur- j=1 rent state-of-the-art value-function-agnostic Shapley value estimators LeverageSHAP (Musco & Witter, 2025) and Directly estimating this sum presents a challenge: we cannot RegressionMSR (Witter et al., 2025). 6 Exactly Computing do-Shapley Values Algorithm 3 doEstimator key questions: (1) To what extent does the number of irre- Input: Budget m, Game v, BaseEstimator, Sam- ducible sets r reduce the complexity compared to the worst- pling multiplier k case 2d in real-world dependencies? (2) Do our structure- Output: Shapley values estimates ϕ ∈ Rd aware estimators outperform state-of-the-art model-agnostic ▷ Step 1: Sampling Phase baselines under fixed query budgets? (3) How does the C, allSampled ← BoundarySampler(m, G) learned causal structure qualitatively influence feature attri- Query ν(c) for all c ∈ C ▷ min(r, m) queries bution error? ▷ Step 2A: Exact Computation Data. We utilize the TALENT benchmark (Liu et al., 2025), if allSampled then a large-scale repository of tabular datasets. To enable reli- ϕ←0 able evaluation against exhaustive baselines, we restrict to for each class c ∈ C do datasets whose post-pruning dimension (after restricting to ϕi ← ϕi + ν(c) · wi (c) for all i the ancestors of the target Y ) permits exact computation of return ϕ ν(S) over all coalitions S ⊆ [d] within our computational ▷ Step 2B: Run BaseEstimator budget. For each dataset, we select a set of test instances x D ← SimulatedSampler(C, k · m) ▷ Algorithm 5 and report errors aggregated across instances and datasets. return BaseEstimator(D) Additional dataset-level details (including the resulting di- mensions after pruning) are provided in the appendix. SCM Generation. Since real-world datasets lack ground- 5. Identifiability truth causal graphs, we learn SCMs from data to serve as Whenever a causal query PS (T ) is uniquely determined the ground-truth games ν. For each dataset, we employ by the graph and dataset, we say the query is (non- the Greedy Relaxed Search Procedure (GRaSP) (Lam et al., parametrically) identifiable. However, this is not always 2022) with a BIC score to learn a Completed Partially Di- the case; we include an illustrative example in Appendix E. rected Acyclic Graph (CPDAG), which is converted to a DAG greedily. Not all features in a dataset causally influ- Computing the do-Shapley value requires verifying the iden- ence the target. Following the definition of do-Shapley, we tifiability of component queries ν(S) via the ID algorithm prune the learned graph to the ancestral set of the target vari- (Shpitser & Pearl, 2006). Even with class-based grouping, able Y ; nodes with no directed path to Y have a null Shap- this necessitates r separate tests. Conducting these checks ley value and are removed. We then fit non-linear structural sequentially during estimation is risky, as a late discovery of equations using Gradient Boosting Regressors (Friedman, non-identifiability renders all prior computation wasted. To 2001) to model the conditional distributions E[Xi | Pa(Xi )]. eliminate this overhead, we present a theorem establishing This learned SCM acts as our oracle ν(S). a linear-time check for global identifiability. Methods. We evaluate our framework against two state- Theorem 5.1. The do-Shapley value ϕi is identifiable if, of-the-art model-agnostic estimators: RegressionMSR and only if, ∀j ∈ [d], ν({j}) is identifiable. (Witter et al., 2025) and LeverageSHAP (Musco & Wit- The necessary background knowledge and proof is left for ter, 2025). These serve as our structure-agnostic base- Appendix E. lines, estimating Shapley values by directly sampling and querying coalitions from the full powerset. To explic- Consequently, we can execute the ID algorithm on the d itly isolate the gains attributable to our graph-theoretic in- singleton coalition queries and, if all are identifiable, the sights, our proposed estimators doRegressionMSR and do-Shapley value will be identifiable and we can proceed doLeverageSHAP are not fundamentally new regression with its estimation. If not, further parametric assumptions, techniques. Rather, they repurpose the same estimation ma- or the inclusion of instrumental variables, will be required chinery used in the baselines. The main difference lies in to ensure identifiability. Regardless, this result prevents the data generation process: whereas the baselines query practitioners from training estimating do-Shapley values random coalitions, our methods train the estimators on the only to learn the outcome was not identifiable to begin distinct equivalence classes recovered by the boundary sam- with. Additionally, it reduces the number of calls to the ID pler (as described in Algorithm 3). This allows us to com- algorithm from r to d. pare “structure-aware” versus “structure-agnostic” sampling while holding the estimation logic constant. 6. Experiments We evaluate the performance of our exact algorithm and Lattice Complexity Reduction The efficiency of our ex- boundary sampling estimators on a diverse set of real-world act algorithm relies on r ≪ 2d . In Figure 4, we plot the datasets. Our experiments are designed to investigate three number of irreducible sets r against the dimension d for 156 7 Exactly Computing do-Shapley Values Estimator Convergence (Aggregated) do-Shapley values do-Shapley interactions do-Shapley interactions (order 1) (order 2) (order 7, Möbius Transform) −1 10 10 −5 Relative MSE 10 −9 10 −13 Method 10 −17 doRegressionMSR doLeverageSHAP 10 −21 RegressionMSR LeverageSHAP 10 −25 Budget = r Expressivity 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Budget Ratio m/r Figure 6. Interactions offer an expressive explanation framework. Figure 5. Estimator Convergence (Aggregated). The relative MSE of Shapley value estimates versus the budget ratio m/r, aggregated across all datasets. Shaded regions indicate 95% confi- b) The framework is not limited to single-feature attribu- dence intervals. Our structure-aware estimators consistently out- tions but naturally extends to interaction values, i.e., perform the baseline variants. Notably, as the budget exceeds the changes in the value function with respect to subsets T number of classes (m > r, red dotted line), our error vanishes to rather than singletons i, as described in Appendix F. machine precision, whereas baselines continue to exhibit variance. While the Shapley values provides a principled framework for attributing value to individuals, they are limited in expres- datasets from the TALENT benchmark. We observe that sivity. For instance, assessing interactions like synergies or for real-world data, the number of irreducible sets r often redundancies across multiple features, is not possible based remains significantly below 2d . on individual Shapley values. n-Shapley values (Lundberg et al., 2018b; Bordt & von Luxburg, 2023) enrich this expla- Estimation Efficiency We evaluate estimation error by nation by adding interactions up to order n. These interac- query budget m, defined relative to the number of irre- tions are based on the Shapley interaction index (Grabisch ducible sets r. Figure 5 presents Relative MSE for all & Roubens, 1999), an axiomatic extension of the Shapley estimators. value. Similar to the Shapley value, n-Shapley values satisfy In the sparse budget regime where we cannot fully explore an extended efficiency axiom (Muschalik et al., 2024b), and the lattice, doRegressionMSR (blue) demonstrates su- provide a more granular and expressive explanation of ν perior sample efficiency, consistently achieving the lowest (see Figure 6). Their explicit form is given in Appendix F. error. This advantage becomes increasingly pronounced With n = d, n-Shapley values yield the Möbius transform as the budget approaches r. By prioritizing the discovery (Rota, 1964), which provides the exact additive decomposi- of distinct equivalence classes via boundary sampling, our tion of ν (Bordt & von Luxburg, 2023). Importantly, they method minimizes redundant queries that plague the stan- satisfy the linearity axiom and their weights only depend on dard samplers. the cardinality of the coalition and the interaction, which al- lows a similar decomposition as Equation (4). Consequently, A phase transition occurs at m = r (indicated by the red ver- once the irreducible sets are known, we can efficiently com- tical line). Once the budget allows for full lattice exploration, pute the Shapley interaction index and n-Shapley values, as our boundary sampler identifies that all irreducible sets have shown in Appendix F. been found. At this point, the algorithm switches to the exact computation described in Section 3. Consequently, the MSE Conclusion for both doRegressionMSR and doLeverageSHAP drops precipitously to machine precision. In contrast, the We address the computational challenges of do-Shapley structure-agnostic baselines (green and purple) continue to values by reformulating the estimation via structural equiva- sample coalitions with replacement, exhibiting a slow con- lence classes. Our proposed algorithm, based on irreducible vergence rate and failing to achieve exactness even with sets, scales with causal complexity (r) rather than dimension double the necessary budget (m = 2r). (2d ) and employs boundary sampling to reduce redundancy. Additionally, we show that verifying identifiability requires 7. Generalizations only a linear O(d) check of singletons. By prioritizing structure-aware exploration, this framework facilitates attri- Our result immediately generalizes in two ways: bution in complex systems, offering a practical step toward scalable causal explainability. Future work could extend a) The weighting function p is not restricted to Shapley these methods to larger graphs, such as in genomics, or values and may correspond to alternative probabilistic investigate sensitivity to graph misspecification. value concepts, such as the Banzhaf index, weighted Banzhaf values, or Beta Shapley values. 8 Exactly Computing do-Shapley Values Impact Statement Behavior, 55(1):72–99, 2006. doi: 10.1016/j.geb.2005. 03.002. This paper presents work whose goal is to advance the field of machine learning. There are many potential societal Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier, consequences of our work, none of which we feel must be E., and Hammer, B. SHAP-IQ: Unified Approxima- specifically highlighted here. tion of any-order Shapley Interactions. In Proceedings of Advances in Neural Information Processing Systems References (NeurIPS), 2023. Banzhaf III, J. F. Weighted voting doesn’t work: A mathe- Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier, matical analysis. Rutgers Law Review, 19:317, 1964. E., and Hammer, B. KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions. In Pro- Bareinboim, E. and Pearl, J. Causal inference and the data- ceedings of the International Conference on Machine fusion problem. Proceedings of the National Academy of Learning (ICML), pp. 14308–14342, 2024. Sciences, 113(27):7345–7352, 2016. Grabisch, M. k-order additive discrete fuzzy measures Bordt, S. and von Luxburg, U. From Shapley Values to and their representation. Fuzzy Sets and Systems, 92(2): Generalized Additive Models and back. In Proceedings 167–189, 1997. doi: 10.1016/S0165-0114(97)00168-1. of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 709–745, 2023. Grabisch, M. and Roubens, M. An axiomatic approach to the concept of interaction among players in cooperative Butler, L., Agarwal, A., Kang, J. S., Erginbas, Y. E., Yu, games. International Journal of Game Theory, 28(4): B., and Ramchandran, K. Proxy-SPEX: Sample-efficient 547–565, 1999. doi: 10.1007/s001820050125. interpretability via sparse feature interactions in LLMs. In The Thirty-ninth Annual Conference on Neural In- Heskes, T., Sijben, E., Bucur, I. G., and Claassen, T. Causal formation Processing Systems, 2025. URL https: Shapley values: exploiting causal knowledge to explain //openreview.net/forum?id=KI8qan2EA7. individual predictions of complex models. Advances in Neural Information Processing Systems (NeurIPS), 33: Castro, J., Gómez, D., and Tejada, J. Polynomial calculation 4778–4789, 2020. of the Shapley value based on sampling. Computers Holland, P. W. Statistics and causal inference. Journal of & Operations Research, 36(5):1726–1730, 2009. doi: the American statistical Association, 81(396):945–960, 10.1016/j.cor.2008.04.004. 1986. Chen, H., Covert, I. C., Lundberg, S. M., and Lee, S.-I. Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gürel, Algorithms to estimate Shapley value feature attributions. N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J. Nature Machine Intelligence, pp. 1–12, 2023. Towards efficient data valuation based on the shapley Covert, I. and Lee, S.-I. Improving kernelshap: Practi- value. In Proceedings of the 22nd International Confer- cal shapley value estimation using linear regression. In ence on Artificial Intelligence and Statistics (AIStats), pp. International conference on artificial intelligence and 1167–1176. PMLR, 2019. statistics, pp. 3457–3465. PMLR, 2021. Jung, Y., Kasiviswanathan, S., Tian, J., Janzing, D., Dubey, P., Neyman, A., and Weber, R. J. Value theory Blöbaum, P., and Bareinboim, E. On measuring causal without efficiency. Mathematics of Operations Research, contributions via do-interventions. In International Con- 6(1):122–128, 1981. doi: 10.1287/MOOR.6.1.122. ference on Machine Learning, pp. 10476–10501. PMLR, 2022. Friedman, J. H. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189– Kolpaczki, P., Bengs, V., Muschalik, M., and Hüllermeier, 1232, 2001. doi: 10.1214/aos/1013203451. E. Approximating the shapley value without marginal contributions. In Proceeedings of the AAAI Conference on Frye, C., Rowat, C., and Feige, I. Asymmetric Shapley val- Artificial Intelligence (AAAI), pp. 13246–13255, 2024a. ues: incorporating causal knowledge into model-agnostic explainability. Advances in Neural Information Process- Kolpaczki, P., Muschalik, M., Fumagalli, F., Hammer, B., ing Systems (NeurIPS), 33:1229–1239, 2020. and Hüllermeier, E. SVARM-IQ: efficient approximation of any-order shapley interactions through stratification. In Fujimoto, K., Kojadinovic, I., and Marichal, J. Ax- Proceedings of the International Conference on Artificial iomatic characterizations of probabilistic and cardinal- Intelligence and Statistics (AISTATS), pp. 3520–3528, probabilistic interaction indices. Games and Economic 2024b. 9 Exactly Computing do-Shapley Values Kwon, Y. and Zou, J. Beta shapley: a unified and noise- Muschalik, M., Fumagalli, F., Hammer, B., and Hüllermeier, reduced data valuation framework for machine learning. E. Beyond TreeSHAP: Efficient Computation of Any- In Proceedings of the International Conference on Artifi- Order Shapley Interactions for Tree Ensembles. In Pro- cial Intelligence and Statistics (AISTATS), pp. 8780–8802, ceedings of the 38th AAAI Conference on Artificial Intel- 2022. ligence, volume 38, pp. 14388–14396, 2024c. Lam, W.-Y., Andrews, B., and Ramsey, J. Greedy relax- Muschalik, M., Fumagalli, F., Frazzetto, P., Strotherm, J., ations of the sparsest permutation algorithm. In Uncer- Hermes, L., Sperduti, A., Hüllermeier, E., and Hammer, tainty in Artificial Intelligence, pp. 1052–1062. PMLR, B. Exact Computation of Any-Order Shapley Interactions 2022. for Graph Neural Networks. In The Thirteenth Interna- tional Conference on Learning Representations, 2025. Li, W. and Yu, Y. Robust data valuation with weighted banzhaf values. Advances in Neural Information Process- Musco, C. and Witter, R. T. Provably Accurate Shapley ing Systems, 36, 2024. Value Estimation via Leverage Score Sampling. In Proc- Liu, S.-Y., Cai, H.-R., Zhou, Q.-L., Yin, H.-H., Zhou, T., cedings of the International Conference on Learning Rep- Jiang, J.-P., and Ye, H.-J. Talent: A tabular analytics resentations (ICLR), 2025. and learning toolbox. Journal of Machine Learning Parafita, Á. and Vitrià, J. Estimand-agnostic causal query Research, 26(226):1–16, 2025. URL http://jmlr. estimation with Deep Causal Graphs. IEEE Access, 10: org/papers/v26/25-0512.html. 71370–71386, 2022. Lundberg, S. M. and Lee, S.-I. A unified approach to inter- Parafita, Á., Garriga, T., Brando, A., and Cazorla, F. J. preting model predictions. Advances in neural informa- Practical do-shapley explanations with estimand-agnostic tion processing systems, 30, 2017. causal inference. In The Thirty-ninth Annual Con- Lundberg, S. M., Erion, G. G., and Lee, S.-I. Consistent in- ference on Neural Information Processing Systems, dividualized feature attribution for tree ensembles. arXiv 2025. URL https://openreview.net/forum? preprint arXiv:1802.03888, 2018a. id=Qabko39AS5. Lundberg, S. M., Erion, G. G., and Lee, S.-I. Consistent in- Pearl, J. Causality: Models, Reasoning and Inference. Cam- dividualized feature attribution for tree ensembles. arXiv bridge University Press, second edition, 2009. preprint arXiv:1802.03888, 2018b. Peters, J., Janzing, D., and Schölkopf, B. Elements of causal Lundberg, S. M., Erion, G. G., Chen, H., DeGrave, A. J., inference: foundations and learning algorithms. The MIT Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, press, 2017. N., and Lee, S. From local explanations to global under- standing with explainable AI for trees. Nature Machine Rota, G.-C. On the foundations of combinatorial theory: I. Intelligence, 2(1):56–67, 2020. theory of möbius functions. In Classic Papers in Combi- natorics, pp. 332–360. Springer, 1964. Mohammadi, M., Chau, S. L., and Muandet, K. Comput- ing exact shapley values in polynomial time for product- Rozemberczki, B., Watson, L., Bayer, P., Yang, H., Kiss, kernel methods. arXiv preprint arXiv:2505.16516, 2025a. O., Nilsson, S., and Sarkar, R. The shapley value in machine learning. In Proceedings of International Joint Mohammadi, M., Muandet, K., Tiddi, I., Teije, A. T., and Conference on Artificial Intelligence (IJCAI), pp. 5572– Chau, S. L. Exact shapley attributions in quadratic- 5579, 2022. time for fanova gaussian processes. arXiv preprint arXiv:2508.14499, 2025b. Rubin, D. B. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of edu- Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., cational Psychology, 66(5):688, 1974. Hammer, B., and Hüllermeier, E. shapiq: Shapley Interac- tions for Machine Learning. In Proceedings of Advances Shapley, L. A value for n-person games. In Contributions in Neural Information Processing Systems (NeurIPS), pp. to the Theory of Games (AM-28), Volume II, pp. 307–317. 130324–130357, 2024a. Princeton University Press, 1953. Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Shpitser, I. and Pearl, J. Identification of joint interventional Hammer, B., and Hüllermeier, E. shapiq: Shapley Inter- distributions in recursive semi-Markovian causal models. actions for Machine Learning. In Advances in Neural In Proceedings of 21st National Conference on Artificial Information Processing Systems (NeurIPS), volume 37, Intelligence (AAAI), pp. 1219–1226, Boston, MA, USA, pp. 130324–130357, 2024b. 2006. 10 Exactly Computing do-Shapley Values Štrumbelj, E. and Kononenko, I. Explaining prediction mod- els and individual predictions with feature contributions. Knowledge and information systems, 41:647–665, 2014. Tian, J. and Pearl, J. On the testable implications of causal models with hidden variables. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 519–527, Edmonton, Canada, 2002. Tsai, C., Yeh, C., and Ravikumar, P. Faith-Shap: The Faithful Shapley Interaction Index. Journal of Machine Learning Research, 24(94):1–42, 2023. Wang, J. T. and Jia, R. Data banzhaf: A robust data valuation framework for machine learning. In Ruiz, F. J. R., Dy, J. G., and van de Meent, J. (eds.), Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 6388–6421, 2023. Wang, J. T., Zhu, Y., Wang, Y.-X., Jia, R., and Mittal, P. A privacy-friendly approach to data valuation. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2023. Wang, J. T., Mittal, P., and Jia, R. Efficient data shapley for weighted nearest neighbor algorithms. In Proceedings of the 27th International Conference on Artificial Intel- ligence and Statistics (AIStats), pp. 2557–2565. PMLR, 2024. Witter, R. T., Liu, Y., and Musco, C. Regression-adjusted monte carlo estimators for shapley values and probabilis- tic values. In The Thirty-ninth Annual Conference on Neu- ral Information Processing Systems, 2025. URL https: //openreview.net/forum?id=Qabko39AS5. Yu, P., Bifet, A., Read, J., and Xu, C. Linear tree shap. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, 2022. Zern, A., Broelemann, K., and Kasneci, G. Interventional SHAP values and interaction values for piecewise linear regression trees. In Proceeedings of the AAAI Confer- ence on Artificial Intelligence (AAAI), pp. 11164–11173, 2023a. Zern, A., Broelemann, K., and Kasneci, G. Interventional SHAP values and interaction values for piecewise linear regression trees. In Proceedings of the 37th AAAI Con- ference on Artificial Intelligence, volume 37, pp. 11164– 11173, 2023b. 11 Exactly Computing do-Shapley Values A. Delayed Proofs Lemma 3.1 Let S̄ ⊂ [d] be a closed set with basis S. Then 1. For all j ∈ S, S̄ \ {j} is closed. 2. If S̄ ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is closed and j is in the basis of S̄ ∪ {j}. Proof of Lemma 3.1. We will first show that S̄ \ {j} is closed for all j ∈ S. To do so, it suffices to show that, for all nodes not in S̄ \ {j}, there is a directed path to Y that does not intersect S̄ \ {j}. This is clearly true for all nodes not in S̄ since S̄ is itself closed. It must also be true for j since j ∈ S, i.e., there is a directed path from j to Y that does not intersect S. The first statement follows. Next, we will show that for S ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is closed. Let T = [d] \ S̄. Since G is a finite DAG, there is a topological order on the nodes. Consider a node j ∈ T with no ancestors in T , either because they are all in S̄, or it has no ancestors. To prove that S̄ ∪ {j} is closed, it suffices to show that, for all nodes not in S̄ ∪ {j}, there is a directed path to Y that does not intersect S̄ ∪ {j}. Since S̄ is closed, all of the nodes in T \ {j} have paths to Y that do not intersect S̄. Note that j cannot be in any of these paths, since j has no ancestors in T , hence all nodes in T \ {j} must actually have paths that do not intersect S̄ or j. Furthermore, since j ∈ T , it must have a directed path to Y that does not intersect S̄. Therefore, j must be in the basis of S̄ ∪ {j}. The second statement follows. Proposition 4.1. Algorithm 4 runs in O(m · d(d + e)) time, where m is the query budget, d is the number of features, and e is the number of edges in the graph. Proof of Proposition 4.1. The algorithm performs exactly m iterations of the main while loop. In each iteration, we process one class c. The cost of processing a class is dominated by generating its neighbors and invoking FindClass for each. A class with closure S̄ and basis S has |S| lower neighbors and d − |S̄| upper neighbors; thus, the total number of neighbors is bounded by d. For each neighbor, we execute FindClass, which requires a graph traversal taking O(d + e) time. Therefore, the work per iteration is O(d(d + e)). Over m iterations, the total time complexity is O(m · d(d + e)). This is linear in the budget m, ensuring the method is scalable for anytime estimation. 12 Exactly Computing do-Shapley Values Algorithm 4 BoundarySampler Input: Budget m, Graph G Output: Sampled classes C, flag allSampled C←∅ ▷ Sampled classes Q←∅ ▷ Queue mapping classes to weights Cseen ← ∅ ▷ Helper to calculate weight and enqueue function Enqueue(S) c ← FindClass(S, G) ▷ Get basis and closure if c ∈ Cseen then return Add c to Cseen Q[c] ← Ei [|wi (c)|] + ϵ ▷ Add ϵ to ensure valid dist. ▷ Phase 1: Warm-start for ℓ = 1 to d do Sample random set S ⊂ [d] where |S| = ℓ Enqueue(S) ▷ Phase 2: Weighted Graph Traversal while |C| < m and Q ̸= ∅ do Sample c from Q with prob ∝ Q[c] Remove c from Q and add to C S, S̄ ← basis and closure of c Nbelow ← {S̄ \ {j} | j ∈ S} Nabove ← {S̄ ∪ {j} | j ∈ / S̄} for candidate set S ′ ∈ Nbelow ∪ Nabove do Enqueue(S ′ ) return C, Q == ∅ 13 Exactly Computing do-Shapley Values B. Background on Structural Causal Models A Causal graph is usually described as a Directed Acyclic Graph (DAG) G, where every node represents a measured random variable and every directed edge represents a relationship cause → effect. These graphs often include dashed bidirected edges between pairs of nodes (X ↔ Y ) as a shorthand for the existence of an unobserved latent variable U that acts as a confounder between them (X ← U → Y ). Additionally, it is assumed that every measured node X has a latent exogenous noise variable, denoted EX , with the associated edge EX → X. A Structural Causal Model (SCM) is a probabilistic model based on such a causal graph G with a probability distribution for all latent nodes (i.e., all confounders and EX ) and, for each measured node X, functions fX such that X := fX (P aG (X)), taking the values of all parents of X in G including latent variables. From this model, a probability distribution over the measured variables V emerges, P (V ), as well as the intervened model Mdo(S=s) , where the do operator conveys an intervention on all nodes X ∈ S replacing their functions fX by the assignment x := sX . This effectively removes all incoming edges to the intervened nodes from the graph, and results in a new probability distribution for the intervened model, P (V | do(S = s)), also denoted Ps (V ) or, for arbitrary intervention values, PS (V ). Given a dataset and its assumed underlying causal structure, we can train an SCM following that graph to learn the distribution of the dataset. Afterwards, one can employ procedures on the SCM to estimate causal queries of the form PX (Y ). Additionally, if the causal query is non-parametrically identifiable (more details in Section 5), these estimations resulting from the SCM are necessarily equivalent to what the true data generating process would return if we had access to it. Therefore, we can employ these trained SCMs to estimate the do-SHAP value functions ν(S) as long as they are identifiable. For more details about this approach, please refer to (Parafita & Vitrià, 2022). 14 Exactly Computing do-Shapley Values C. Simulated Sampling from Irreducible Sets In this appendix, we detail the SimulatedSampler, the engine behind Step 2B of the doEstimator. This component allows us to sample coalitions efficiently from the specific sub-lattice defined by the discovered equivalence classes. C.1. Algorithm and Explanation The challenge in simulating samples from the discovered classes is that the union of these classes does not form a simple structure (like a full powerset). A naive rejection sampling approach—sampling from the full powerset and keeping only those in C—would be inefficient if the volume of C is small relative to 2d . Instead, our sampler (Algorithm 5) adopts a constructive approach: • Normalization: We first calculate the total “volume” of available coalitions within the known classes. For each class c with basis S and closure S̄, the number of subsets of size s contained in c is given by |S̄|−|S|  s−|S| . • Scale Calibration: Standard Shapley weights are defined for the entire powerset. To sample validly from our restricted support, we solve for a scaling factor γ such that the expected number of samples drawn matches our target budget Bsim . This is achieved via binary search (Lines 7-15). • Stratified Generation: We iterate through each class c ∈ C and each valid subset size s. For each size, we compute the expected number of samples Nc,s . We use probabilistic rounding to convert this expectation into an integer count, and then generate that many unique subsets from class c using a combinatorial number system (Lines 22-26). Algorithm 5 SimulatedSampler 1: Input: Discovered classes C, Simulation Budget Bsim , Weights w (per size) 2: Output: Dataset of coalitions D = {(Sk , ν(ck ), pk )} 3: D ← ∅ 4: ▷ Step 1: Count available coalitions per size across all classes 5: Navail [s] ← 0 for s ∈ 0 . . . d 6: for each class c ∈ C do 7: Let nfree = |S̄| − |S| 8: for j = 0 to nfree do Navail [|S| + j] ← Navail [|S| + j] + njfree  9: 10: ▷ Step 2: Calibrate sampling scale γ   Pd 11: Define E[samples](γ) = s=0 Navail [s] · minγ wds , 1 (s) 12: Find γ ∗ via binary search such that E[samples](γ ∗ ) ≈ Bsim 13: ▷ Step 3: Constructive Sampling 14: for each class c ∈ C do 15: Let Ifree be indices in S̄ \ S 16: for j = 0 to |Ifree | do 17: Size s ← |S| +j  18: Prob p ← min γ ∗ wds , 1 () |Ifree |  s 19: Count K ← j 20: Expected count µ ← K · p 21: Ndraw ← ⌊µ⌋ + Bernoulli(µ − ⌊µ⌋) ▷ Probabilistic rounding 22: if Ndraw > 0 then 23: Generate Ndraw unique combinations Csub ⊆ Ifree of size j 24: for each combination σ ∈ Csub do 25: S ←S∪σ 26: Add (S, ν(c), p) to D 27: return D 15 Exactly Computing do-Shapley Values C.2. Runtime Analysis Proposition C.1. The SimulatedSampler generates Nsim samples in O(Nsim · d + |C| · d) time. Proof. The algorithm consists of three main parts: 1. Counting (O(|C| · d)): We iterate over each class once. For each class, we perform a loop over its ”free” size range, which is at most d. The binomial coefficient calculations can be done in O(1) with pre-computation. 2. Calibration (O(d · log(1/ϵ))): The binary search evaluates the expected sample sum a constant number of times. Each evaluation sums over d sizes. 3. Generation (O(Nsim · d)): The outer loops iterate over classes and sizes, but the inner generation logic (Lines 24-28) executes exactly Nsim times in total (by definition of the calibrated budget). Generating a combination of size k using the combinatorial number system or direct sampling takes O(d). Thus, the generation phase scales linearly with the number of output samples. Dominating terms yield a total complexity of O(Nsim · d + |C| · d), which is highly efficient given that no SCM evaluations are performed. 16 Exactly Computing do-Shapley Values D. Stratified Sampling Ideally, to estimate the Shapley value for player i, we would sample each class c proportional to the magnitude of its weight wi (c). However, the underlying class structure (the mapping of sets to values) is unknown prior to sampling, making the direct computation of wi (c) impossible. To address this, we consider an adaptive sampling scheme based on the natural distribution suggested by the Shapley weights. We sample a set S containing i with probability pℓ−1 , and a set S excluding i with probability pℓ . Note that while these probabilities are derived from the Shapley weights, they do not perfectly correspond to the final importance weights because the contribution of i cancels to zero when i is effectively a “null” player (i.e., in the closure but not in the basis). The proposed do-Good estimator samples according to these distributions without replacement. Sampling classes without replacement is crucial for the estimator to achieve exactness when the sampling budget covers the effective support of the game (m ≥ r). To achieve this, we maintain weighted counts of the remaining “mass” of the distributions for each player i. We define the remaining mass for sets including i (µ(+) ) and excluding i (µ(−) ) as: (+) 1[S not seen], X µℓ,i = pℓ−1 (7) S:|S|=ℓ,i∈S (−) 1[S not seen]. X µℓ,i = pℓ (8) S:|S|=ℓ,i∈S / (+) (−) Initially, before any classes have been sampled, these initialize to the full binomial sums: µℓ,i = pℓ−1 d−1  ℓ−1 and µℓ,i = pℓ d−1  ℓ . Sampling Procedure − The sampling process proceeds hierarchically to determine whether to sample proportional to µ+ ℓ,i or µℓ,i : 1. We first select an index i uniformly from [d]. 2. We sample an inclusion indicator z ∈ {−, +}, where Pd (+) ℓ=1 µℓ,i Pr(z = +) = Pd (+) Pd−1 (−) . ℓ=1 µℓ,i + ℓ=0 µℓ,i (z) 3. We sample a set size ℓ with probability proportional to the remaining mass µℓ,i . Once ℓ and z are determined, we must sample a specific set S of size ℓ (containing i if and only if z = +) uniformly from the collection of all such sets that belong to currently unseen classes. This step is non-trivial; it depends on the number of valid completions available in the unseen space. As detailed in Algorithm 7, computing these counts requires a linear pass through the history of previously discovered classes. We analyze the computational complexity of the ClassSampler (Algorithm 6). The runtime is dominated by the requirement to sample uniformly from unseen sets, which necessitates checking consistency against all previously discovered classes. Proposition D.1 (Stratified Sampling Complexity). Let m be the sampling budget (number of iterations) and d be the number of elements (dimension). Assuming set operations (union, intersection, subset checks) take O(d) time, the total time complexity of the ClassSampler is O(m2 d2 ). Because the algorithm is quadratic in m, we turn to the boundary sampling method described in Section 4. Proof of Proposition D.1. The analysis proceeds by examining the cost of the helper functions from the bottom up. 1. Cost of CountSeen: This function iterates through the set of seen classes C. In the k-th iteration of the main loop, |C| ≤ k. Inside the loop, we perform standard set operations (checking S ⊆ S ∪ R, etc.). Tcount (k) = O(|C| · d) = O(k · d). (9) 17 Exactly Computing do-Shapley Values Algorithm 6 ClassSampler Input: Number of elements d, budget m, value function ν, graph G Output: Set of seen classes C Initialize seen classesC ← ∅ (1) Set µℓ,i ← pℓ−1 d−1ℓ−1 for all ℓ ∈ {1, . . . , d} and i ∈ [d] (0) d−1  Set µℓ,i ← pℓ ℓ for all ℓ ∈ {0, . . . , d − 1} and i ∈ [d] for idx = 1 to m do ▷ Sample set from unseen classes Sample i ∼ Uniform([d])  Pd (1) ℓ=1 µℓ,i Sample z ∼ Bernoulli Pd (1) Pd−1 (0) ℓ=1 µℓ,i + ℓ=0 µℓ,i (z) Sample ℓ ∝ µℓ,i S ← {i} if z = 1 else ∅ S ← SampleUnseenBySize(ℓ, S, C) S, S̄ ← FindClass(S, G) ▷ Find class c (1) (0) Update all µℓ,i and µℓ,i ▷ Constant time per ℓ and i Add class c to C return C 2. Cost of SampleUnseenBySize: This function constructs a set S of size ℓ element-by-element. The while loop runs at most ℓ ≤ d times. In every iteration, it calls CountSeen twice to calculate Nin and Nout . ℓ X Tsample (k) = 2 · Tcount (k) j=1 = O(d · (k · d)) = O(kd2 ). (10) 3. Total Cost of ClassSampler: The main algorithm runs for m iterations. In iteration k, it calls SampleUnseenBySize, performs a graph lookup (FindClass), and updates weights. The function FindClass runs in O(d + e) time where e is the number of edges in the graph. Since e ≤ d2 , the dominant cost remains the combinatorial counting step. The update of µ values takes O(d2 ) but is repeated only m times. Summing over m iterations: m X Tsample (k) + O(d2 )  Ttotal = k=1 Xm = O(kd2 ) k=1 m X = O(d2 ) k ≈ O(d2 m2 ). (11) k=1 Thus, the total complexity is quadratic in both the dimension and the sample budget. 18 Exactly Computing do-Shapley Values Algorithm 7 SampleUnseenBySize Input: Size ℓ, Initial set S (i.e., {i} or ∅), seen classes C Output: A set S of size ℓ sampled uniformly from unseen sets R ← [d] \ S ▷ Available candidates C ′ ← {c : |S| ≤ ℓ ≤ |S̄|} ▷ Relevant classes while |S| < ℓ do Pick j uniformly from R ▷ Completions in seen classes with and without j Nin , Cin′ ← CountSeen(ℓ, S ∪ {j}, R \ {j}, C ′ ) ′ Nout , Cout ← CountSeen(ℓ, S, R \ {j}, C ′ ) ▷ Calculate count  of unseen completions |R|−1 Uin ← ℓ−|S|−1 − Nin Uout ← |R|−1  ℓ−|S| − Nout ▷ Pick j proportional to  unseen completions Sample b ∼ Bernoulli UinU+U in out C ′ ← Cout ′ if b = 1 then C ′ ← Cin′ S ← S ∪ {j} R ← R \ {j} return S Algorithm 8 CountSeen Input: Size ℓ, current set S, remaining set R, seen classes C Output: Number of completions N , applicable classes C ′ N ←0 C′ ← ∅ ▷ Initialize applicable classes for class c ∈ C do Let S be the basis and S̄ be the closure of c ▷ Check if S and R are consistent with class if S ̸⊆ (S ∪ R) or S ̸⊆ S̄ then continue Add c to C ′ ▷ Applicable class ▷ Calculate available optional elements in this class noptions ← |R ∩ (S̄ \ S)| ▷ Calculate available, optional spaces nspaces ← ℓ − |S| − |R ∩ S| N ← N + nnoptions spaces return N 19 Exactly Computing do-Shapley Values E. Identifiability Criterion In this section, we operate exclusively with non-parametric identifiability, following (Pearl, 2009) (Definition 3.2.4), where an interventional causal query Q[M ], defined on a causal model M with DAG G = (V ∪ U, E) with V measured nodes and U latent nodes, is (non-parametrically) identifiable from G if the query can be computed uniquely from any positive probability of the observed variables Markov-relative2 to the graph. In other words, if two causal models M1 and M2 with positive probability distributions PM1 and PM2 are both Markov-relative to G and observationally identical to each other (PM1 (V ) = PM2 (V )), then both models must have the same value for the given query. Note that this definition does not include any assumptions about the functional forms of the causal models nor the probability distributions of the unobserved variables. In other words, non-parametric identifiability cannot assume anything other than the shape of the graph G (including latent confounders). U X Y Figure 7. Bow-arc graph, with non-identifiable PX (Y ). Non-identifiable example. Consider the Directed Acyclic Graph (DAG) G = ({X, Y } ∪ {U }, E) in Figure 7, where U is an unmeasured variable acting as a latent confounder between X and Y . In this graph, PX (Y ) is not identifiable. Let us demonstrate by creating two equivalent positive distributions P 1 and P 2 Markov-relative to G, with different intervened distributions for PX (Y ). We define two latent variables: U , the latent confounder between X and Y , and EY , the exogenous noise variable for Y , both with the same distribution in both models, N (0, 1). In terms of their functional assignments, 1 2 x := fX (u) = fX (u) = u, while y := fY1 (x, u, ey ) = x − u + ey and y := fY2 (x, u, ey ) = x · 0 + ey . Note that all distributions P (X), P 2 (X), P 1 (Y | X), P 2 (Y | X) are identical, N (0, 1), and so is P 1 (X, Y ) = P 1 (X)P 1 (Y | 1 X) = P 2 (X)P 2 (Y | X) = P 2 (X, Y ), and they are positive. However, P 1 (Y | do(X = 0)) ∼ N (0, 2) while P 2 (Y | do(X = 0)) ∼ N (0, 1). Therefore, PX (Y ) is not identifiable. Non-parametric identifiability can be demonstrated if we can find an estimand of the causal query only containing observational terms. In particular, the ID algorithm (Shpitser & Pearl, 2006), described in Section E.1 and presented in simplified form in Algorithm 9, determines non-parametric identifiability w.r.t. a causal graph G of any non-conditional, interventional query PX (Y ), for any disjoint subsets of variables X, Y . Note that any coalition value ν(S) = E[Y | do(S = s)] is non-parametrically identifiable if, and only if, PS (Y ) is non-parametrically identifiable. Trivially, identifiability in the probability terms guarantees identifiability in the expectation (since the expectation’s summation or integral is an observational estimand only consisting of identifiable terms Ps (y)). Conversely, non-identifiability in the terms PS (Y ) must imply non-identifiability for the expectation in the absence of further parametrical assumptions (e.g., assuming that Ps (y) = Ps (−y), in which case the terms cancel each other out and make the expectation identifiable). For this reason, we will focus on non-parametric identifiability, and only on queries of the form PS (Y )—which can be determined thanks to the ID algorithm—as a proxy for identifiability of ν(S). E.1. The ID algorithm Let us provide the necessary background definitions and properties to understand the ID algorithm and follow the proofs of our identifiability criterion. Definition E.1. Let G = (V ∪ U, E) be a Directed Acyclic Graph (DAG) with nodes V ∪ U (measured and latent nodes, respectively) and edges E. Its latent projection is an Acyclic Directed Mixed Graph (ADMG) G∗ = (V, E ∗ ), which is a graph containing directed and bidirected edges and no directed cycles. In particular, G∗ only contains the measured nodes in G and: (1) any directed edge in G between measured nodes; (2) an edge between measured nodes if both are connected in G by a directed path where all intermediate nodes are in U ; and (3) a bidirected edge Vi ↔ Vj between measured nodes if both are connected by a path of the form Vi ← · · · ← · → · · · → Vj where all intermediate nodes are in U . 2 Q A probability distribution is Markov-relative to a DAG G = (V ∪ U, E) if P (V, U ) = X∈V ∪U P (X | P aG (X)), where P aG (X) is the set of parents of X in G. 20 Exactly Computing do-Shapley Values Algorithm 9 ID(T, S, G) Input: Disjoint sets T, S ⊆ V, ADMG G = (V, E). Output: Boolean indicating whether PS (T ) is identifiable. 1: If S = ∅, return TRUE. 2: If V ̸= AnG (T ), return ID(T, S ∩ AnG (T ), G[AnG (T )]). 3: Let W := (V \ S) \ AnGS (T ). If W ̸= ∅, return ID(T, S ∪ W, G). 4: If V \ S ̸∈ C(G[V \ S]), return ∧Ci ∈C(G[V\S]) ID(Ci , V \ Ci , G). 5: If V ∈ C(G), return FALSE. 6: If V \ S ∈ C(G), return TRUE. 7: Let C ∈ C(G) s.t. C ⊃ V \ S, return ID(T, S ∩ C, G[C]). In the following, when talking about a graph, we refer to the ADMG latent projection of the DAG under study. Notation. Let G be an ADMG. We denote by V (G) the set of nodes of G. We denote by G[S] the induced subgraph of G filtering to the nodes S ⊆ V (G) and only preserving those edges connecting preserved nodes. For a node Y ∈ V (G), we denote by AnG (Y ) the set of (directed) ancestors of node Y in G including Y , and by DeG (Y ) the set of (directed) descendants S of node Y in G including Y . We overload the notation with the ancestors of a set of nodes T ⊆ V (G), AnG (T ) := t∈T AnG (t), and equivalently for DeG (T ). We denote the intervened graph GS as the subgraph of G such that any incoming edge to the nodes in S is removed. For this reason, in this section, we will avoid denoting the closure of a coalition S by S to avoid ambiguity. Definition E.2. The root set R of an ADMG G is the set of nodes in G with no proper descendants: R := {X ∈ V (G) | DeG (X) = {X}}. Definition E.3. Let G be an ADMG. We say that a set of nodes V is a C-component within an ADMG G if all nodes are connected via bidirected arcs. We denote the set of maximal C-components of a graph G by C(G). In particular, C(G) constitutes a partition of V (G). We also say G is a C-component when V (G) is a C-component in G. Definition E.4. We say an ADMG G is an R-rooted C-forest if R is its root set, G is a C-component, and all its nodes have at most one (directed) child. Definition E.5. Let G be an ADMG, and S, T disjoint subsets of variables in V (G). We say a pair (F, F ′ ) is an R- rooted hedge for PS (T ) if both F and F ′ are R-rooted C-forests such that F ′ ⊆ F ⊆ G, F ∩ S ̸= ∅, F ′ ∩ S = ∅ and R ⊆ AnGS (T ). Hedges are the reason for non-identifiability of causal effects. See the following theorem from (Shpitser & Pearl, 2006) (Theorem 4). Theorem E.6. If (F, F ′ ) is a hedge for PS (T ) in an ADMG G, PS (T ) is not identifiable in G. We are now ready to study the ID algorithm (Shpitser & Pearl, 2006), with which we can ascertain the identifiability of any query PS (T ). We present a simplified version in Algorithm 9. E.2. Identifiability criterion When evaluating do-SHAP, one must evaluate causal queries ν(S) := E[Y | do(S = s)] for multiple coalitions S ⊆ [d]. If one such query is not identifiable, we cannot continue evaluating do-SHAP and must raise an error. However, this forces practitioners to execute do-SHAP without knowing if an estimate can be raised, while also running the ID algorithm for every single coalition that must be evaluated. Instead, we present the following result, which allows us to determine the identifiability of all 2d coalition values ν(S) just by determining the identifiability of the d singleton coalitions {i} ⊆ [d]. Theorem E.7. Let G be an ADMG over V, with a single Y ∈ V target node. If ∃X ⊆ V \ {Y } such that PX (Y ) is not identifiable, then ∃s ∈ X ∪ (V \ AnGX (Y )) such that P{s} (Y ) is not identifiable. We will devote the remainder of this section to proving this theorem. Let us first prove a set of lemmas that will progressively build towards the proof. 21 Exactly Computing do-Shapley Values Lemma E.8. Let G be an ADMG over V, with a set Y ⊆ V the target nodes. If ∃X ⊆ V \ Y such that PX (Y ) is not identifiable, then the ID algorithm ends at line 5 in a recursive call ID(T, S, G′ ) for S and T non-empty disjoint subsets of V ′ ⊆ V, and G′ an induced subgraph G′ = G[V ′ ] ⊆ G. Then, there exists R-rooted C-forests (F, F ′ ), R ⊆ V ′ such that they constitute a hedge for PS (T ). Proof. Firstly, the ID algorithm (Shpitser & Pearl, 2006) always terminates (Lemma 3 in their paper), it is sound (Theorem 5) and complete (Corollary 2). Since we assume that PX (Y ) is not identifiable, it must be that when we evaluate ID(Y, X, G), we will eventually return FALSE from line 5 at a certain recursion level ID(T, S, G′ ). Both X and S must be non-empty (otherwise line 1 would have returned TRUE). Both S and T must be subsets of V and disjoint (since all recursive calls maintain them being disjoint given the initial assumption that Y ∩ X = ∅). Finally, G′ is an induced subgraph G′ = G[V ′ ] ⊆ G, since all recursive calls will at most remove nodes from G. Let R be the root set of G′ [V ′ \ S]. In particular, R ∩ S = ∅. Let F ′ be an edge subgraph of G′ [V ′ \ S] such that its root set remains R but all observable nodes have at most one child, and all confounding arcs in G′ [V ′ \ S] are present. Note that G′ [V ′ \ S] is a C-component (otherwise, line 4 would have triggered) and in creating F ′ we did not remove any confounding arcs, so F ′ is also a C-component, and therefore an R-rooted C-forest. Now, let us define an edge subgraph F ⊆ G′ by starting from F ′ , adding all nodes in S and, for every such node adding only one edge to one of its children in G′ , as well as all bidirected edges. Since every new node has a child in V (F ), the root set remains R, and F is an R-rooted C-forest by the same reasoning as before because line 5 guarantees C(G′ ) = {V ′ }. Additionally, F ′ ⊆ F , V (F ′ ) ∩ S = ∅ and V (F ) ∩ S = S ̸= ∅. All that remains is to prove that R ⊆ AnG′ (T ). First, note that R ⊆ AnG′ (T ) by line 2, so there S exist paths from nodes r ∈ R to nodes t ∈ T . Let us assume that one such r has all its directed paths blocked by S. Then, r ̸∈ AnGS (T ) and r ̸∈ S (because R ∩ S = ∅), which means that W in line 3 would have contained r. By contradiction, R ⊆ AnG′ (T ) and, finally, (F, F ′ ) is a hedge for PS (T ) in G′ . S We now define some notation that will guide the proofs that follow. Let G be an ADMG over V, with a single target node Y ∈ V. If ∃X ⊆ V \ {Y } such that PX (Y ) is not identifiable, let us focus on a single call-path returning FALSE, and denote the i-deep call ID(T i , S i , Gi ) (with corresponding V i := V (Gi )) along the call-path, starting on ID({Y }, X, G) (with {Y } = T 0 , X = S 0 , G = G0 ) and ending at depth d ≥ 0 in line 5 for the found hedge. Whenever line 4 or 7 are called at depth i, let us denote by C i the C-component that appears either: in line 4, for the recursive call to ID in the particular branch following the call-path, or the one in line 7 that filters S. Let d′ be the first depth level at which line 4 is triggered or d + 1 if it never does. Lemma E.9. If line 7 triggers at ID(T i , S i , Gi ), then V i \ S i ⊊ C i ⊊ V i . In particular, S i+1 ⊊ S i . Proof. V i \ S i ⊂ C i ⊂ V i and it is a maximal C-component in Gi by construction. If C i = V i \ S i , then V i \ S i ∈ C(Gi ) and line 6 would have triggered. If C i = V i , then V i ∈ C(G) and line 5 would have triggered. Finally, since C i ̸= V i and C i ⊋ V i \ S i , then S i ∩ C ⊊ S i . Lemma E.10. Some observations that will become relevant throughout the following discussion are: • Line 1 never triggers along the failing call-path, and ∀i ≤ d, S i ̸= ∅; otherwise, the call-path would not end at line 5. • Line 6 never triggers along the failing call-path; otherwise, the call-path would not end at line 5. • Line 5 does not trigger along the failing call-path for depths i < d. • G can only have nodes removed: Gi+1 ⊆ Gi , ∀i < d. • We can only remove nodes from the local set of intervened variables S on lines 2 and 7, while also removing them from the local graph G. • We can only add nodes to the local set of intervened variables S on lines 3 and 4, while also removing them from the set of unused nodes U := V \ (T ∪ S). • The set of unused nodes can never grow: U i+1 ⊆ U i , ∀0 ≤ i < d. • T does not change until line 4 is called: ∀i ≤ d′ , T i = {Y }. 22 Exactly Computing do-Shapley Values Lemma E.11. Under the previous assumptions, line 4 can trigger at most once. ′ Proof. Assuming that line 4 triggers at least once, let d′ < d be the depth of its first call, and C d the C-component ′ ′ ′ ′ ′ ′ whose recursive call we follow along the call-path. Right after that, T d +1 = C d , S d +1 = V d \ C d , and U d +1 = ′ ′ ′ V d +1 \ (T d +1 ∪ S d +1 ) = ∅. Assume there is a minimal d′′ > d′ in which line 4 triggers again. Then, since only line ′′ ′ ′ ′′ ′′ ′′ ′ ′′ 4 can change T , T d = T d +1 = C d . Note that V d \ S d = T d = C d (otherwise U d would increase). Therefore, ′′ ′′ ′′ ′′ ′ ′ ′ ′ ′′ ′ ′ C(Gd [V d \ S d ]) = C(Gd [C d ]) = C(Gd [C d ]) = {C d } since Gd ⊆ Gd and C d is a maximal C-component in ′ ′ ′ ′ ′ ′ Gd [V d \ S d ] ⊋ Gd [C d ], which means that line 4 cannot trigger again. In particular, T i = C d , ∀i : d′ < i ≤ d. Lemma E.12. Under the previous assumptions, if V = AnG (Y ) and X is closed (i.e., X = X ∪ (V \ AnGX (Y ))), then line 3 never triggers. Proof. By the fact that the closure of a closed set is itself, line 3 cannot trigger at depth 0. Let us prove the statement by induction. Firstly, consider a depth i, 0 < i < d′ , in which line 3 is triggered, while assuming it has not been triggered before. From Lemma E.10, T i = {Y }. For depth i, it must be that W i := (V i \ S i ) \ AnGi (Y ) ̸= ∅, with nodes w ̸∈ S i and Si w ̸∈ AnGi (Y ), but w ∈ AnGi (Y ) (since we skip line 2 to trigger 3), so there are directed paths from w to Y , all blocked Si by S i . Let us now study depth i − 1. Since w ̸∈ S i and S i−1 ⊇ S i , if w ∈ S i−1 it must have been removed by lines 2 or 7, but that would also remove it from V i , which is not the case, so we know that w ̸∈ S i−1 . Additionally, if we assumed that w ̸∈ AnGi−1 (Y ), since w ̸∈ S i , then w ∈ W i−1 but because line 3 did not trigger at depth i − 1, W i−1 = ∅. S i−1 Consequently, w ∈ AnGi−1 (Y ) and w ̸∈ S i−1 , so there are directed paths from w to Y unblocked by S i−1 , going through S i−1 nodes in a set Z ⊆ V i−1 \ S i−1 , which all must have disappeared from Gi to make it so w ̸∈ AnGi (Y ). Since line 2 Si preserves all directed paths to Y , this can only happen if line 7 was triggered at depth i − 1. However, this cannot be the case either: the C-component C i−1 ⊋ V i−1 \ S i−1 preserves all non-intervened nodes, which is the case for Z. Therefore, it must be that our initial assumption was false, W i is empty, and so line 3 was not triggered at depth i < d′ after all. ′ ′ ′ For depth d′ , we naturally skip line 3 to reach line 4. Afterwards, V d +1 = T d +1 ⊔ S d +1 so ∀d′ < i ≤ d, U i := V i \ (T i ∪ S i ) = ∅ (Lemma E.10), so W i = ∅, and line 3 is never called either. Lemma E.13. Let G be an ADMG over V, with a single Y ∈ V target node. If ∃X ⊆ V \ {Y } such that PX (Y ) is not identifiable, let ID(T d , S d , Gd ) be the last call resulting in the hedge given by Lemma E.8. Then S d ∩ (X ∪ (V \ AnGX (Y ))) ̸= ∅. Proof. Let X ′ be the closure of X, X ′ := X ∪ (V \ AnGX (Y )) (here denoted X ′ instead of X to avoid ambiguity of notation), and let us prove that S d ∩ X ′ ̸= ∅. Note that if line 2 or 3 trigger on the first calls, we end up in a recursive call ID({Y }, S i , Gi ) where V i = AnG (Y ) and S i = AnG (Y ) ∩ (X ∪ (V \ AnGX (Y ))), so we can assume without loss of generality that V = AnG (Y ) and X ′ = X at the start of the call-path. Consequently, S 0 ∩ X ′ = X ′ ̸= ∅ trivially. Let us proceed by induction, proving that ∀i < d, S i ∩ X ′ ̸= ∅ implies that S i+1 ∩ X ′ ̸= ∅, and then so will be the case for S d , which will prove the lemma. Let us now consider any depth level 0 < i ≤ min(d, d′ ) and assume that S i−1 ⊆ X ′ . Let us study what happens at depth i − 1. Lines 1, 3, 4, and 6 cannot trigger (by Lemmas E.10 and E.12 and the fact that i ≤ d′ ). If line 2 were to remove any nodes, it would still result in a non-empty proper subset S i ⊊ S i−1 ⊆ X ′ . If line 7 triggered, S i := S i−1 ∩ C i−1 ⊊ S i−1 ⊆ X ′ and S i ̸= ∅ by Lemma E.9. In all cases, the next recursive S is not empty and only contains nodes in X ′ : ∅ ̸= S i+1 ⊊ S i ⊆ X ′ . ′ If line 4 never triggers, we have already proved the result. Otherwise, d′ < d, and C d is the C-component whose recursive ′ ′ ′ ′ ′ ′ ′ ′ call we follow along the call-path. In particular, V d +1 = V d , T d +1 = C d , S d +1 = V d \ C d ⊋ S d , so it contains ′ ′ elements of X ′ and outside X ′ (because the nodes in X ′ \ S d have been removed from Gd as well). Additionally, ∀i > d′ , U i = ∅, and can never increase. ′ ′ ′ For d′ ≤ i ≤ d, let us define S i = Ai ⊔ B i ̸= ∅, with Ai := S i ∩ X ′ and B i := S i \ X ′ . Note that Ad = S d , B d = ∅, and ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ Ad +1 = S d , B d +1 = (V d \C d )\Ad ̸= ∅, since S d +1 = V d \C d ⊋ S d ⊆ X ′ . Additionally, ∀i > d′ +1, Ai ⊆ Ai−1 23 Exactly Computing do-Shapley Values and B i ⊆ B i−1 since we can only remove nodes at this point, given that line 3 and line 4 will not run again (Lemmas E.12 and E.11). Let us prove that if ∀i : d′ < i < d, Ai ̸= ∅, then Ai+1 ̸= ∅, for which we must check lines 2 and 7. If line 2 was triggered at step i and Ai+1 = ∅, the next recursion level would have T i+1 = T i , S i+1 = B i+1 ̸= ∅ and Gi+1 = Gi [AnGi (T i )] ⊆ Gi . At level i + 1, line 6 would trigger: neither line 3 nor line 4 can trigger again; if we ′ ′ assume that line 5 triggers, then V i+1 ∈ C(Gi+1 ), but B i+1 ⊆ B d +1 and no node in B d +1 belonged in the same maximal d′ d′ d′ d′ i+1 d′ ′ C-component as C in G [V \ A ], then all bidirected paths from B to C were blocked by Ad , and now that i+1 i+1 i+1 i+1 d′ A = ∅, these paths are cut; finally, for line 6, if V \S =T = C were not a maximal C-component of the induced subgraph Gi+1 = Gi [AnGi (T i )], it must be that a node b ∈ S i+1 = B i+1 is connected through a bidirected path ′ to C d in this graph, which we have just proved to be false, hence proving that the call would return TRUE at line 6. By ′ contradiction, this proves that line 2 would have not removed all of Ad +1 ⊆ X ′ . ′ Finally, if line 7 was triggered at step i and Ai+1 = ∅, when before it was not, necessarily B i+1 ̸= ∅, and ∀c ∈ T i = C d , ′ ′ ∀b ∈ B i+1 = B i ∩ C i , there are bidirected paths connecting c and b in Gi ⊋ Gi+1 , and all are intersected by S d = Ad ′ (otherwise b ∈ C d ). Consequently, either these intersecting nodes are in Ai , in which case they would not have been removed from Ai+1 , or they are not in Ai , in which case b would have been removed as well for its paths would be cut. Both cases contradict the assumption that Ai+1 = ∅. Bringing everything together and by induction, ∅ ⊊ Ad ⊆ X ′ , proving the lemma. We now have all we need to prove the theorem. Proof of Theorem E.7. Finally, let us finish the proof by showing that if (F, F ′ ) is the R-rooted hedge for PS (T ) found at the end of the call-stack, ∀s ∈ S ∩ X ′ , with X ′ := X ∪ (V \ AnGX (Y )) the closure of X, then (F, F ′ ) is also a hedge for P{s} (Y ). Note that the hedge still fulfills the conditions F ′ ⊆ F, F ∩ {s} ̸= ∅, F ′ ∩ {s} = ∅, both R-rooted, both C-forests. So now we only need to check that R ⊆ AnGs (Y ), but if one such r ∈ R were not in AnGs (Y ) ⊇ AnGX ′ (Y ), then r would belong in X ′ by definition of the closure of X and the fact that the closure of a closure is itself. Additionally, throughout the call-stack, r would have never left the set of intervened nodes without leaving the graph itself, hence r ∈ S, contradicting the fact that S ∩ R = ∅ by construction (see Lemma E.8). Therefore, it must be that R ⊆ AnGs (Y ), proving that (F, F ′ ) is a hedge for P{s} (Y ). By Theorem 4 in (Shpitser & Pearl, 2006), P{s} (Y ) is not identifiable. Corollary E.14. Any do-Shapley value ϕi for i ∈ [d] is (non-parametrically) identifiable if, and only if, all singleton coalition probabilities (P{k} (Y ))k∈[d] are (non-parametrically) identifiable. Proof. If all singleton coalitions {k} ⊆ [d] have identifiable probability terms P{k} (Y ), there cannot be any coalition S ⊆ [d] for which PS (Y ) is not identifiable (otherwise, by Theorem E.7, ∀k ∈ S ∪ (V \ AnGS (Y )), P{k}P (Y ) would not be r identifiable). Then, all the respective ν(S) = E[Y | do(S = s)] are identifiable, and consequently, ϕi = j=1 ν(cj )wi (cj ) is also identifiable. Conversely, if one such P{k} (Y ) were not identifiable, its ν({k}) term cannot be either, nor can ϕk . 24 Exactly Computing do-Shapley Values F. Extensions of the Shapley value The Shapley value was extended in multiple ways. Semivalues (Dubey et al., 1981) , such as the Banzhaf value (Banzhaf III, 1964), extend the Shapley values to alternative weighting schemes (qs )s=0,...,n−1 ≥ 0 as X ϕqi = [ν(S ∪ i) − ν(S)]q|S| . (12) S⊆[d]\i If q is a probability distribution over 2[d] , then they are also referred to as cardinal-probabilistic values (Fujimoto et al., 2006). By replacing the weights in Equation (4), we can derive an efficient computation for any semivalue. Another line of work extends the Shapley value to higher-order interactions, known as the Shapley interaction index (Grabisch & Roubens, 1999), and defined by |U | X X ϕU = ∆U (S)p|S| with ∆U (S) := (−1)|U |−|S| ν(S ∪ L), S⊆[d]\U L⊆U 1 and pus := (d−u+1)· . The discrete derivative ∆U (S) thereby measures the interaction of U in the presence of S, and (d−u s ) directly extends the marginal contribution. We now utilize a result by Zern et al. (2023b)[Proposition 1] to efficiently compute the Shapley interaction index for value functions of the shape 1[S ⊆ S ⊆ S]. Proposition F.1 (Zern et al. (2023a)). Given subsets S ⊆ S ⊆ [d] and value function ν(S) = 1[S ⊆ S ⊆ S], the Shapley 1 a+b −1  interaction index is given by the weights ωa,b := a+b+1 a and ϕU = (−1)|U ∩([d]\S)| ω|S|−|S∩U |,|[d]\(S∪U )| , if U ⊆ A ∪ ([d] \ B), and ϕU = 0 otherwise. Notably, the weights ω can be precomputed. Consequently, we obtain the following result by the linearity of the Shapley interaction index (Grabisch & Roubens, 1999). Proposition F.2. The do-Shapley interaction index is given by r X ϕU = ν(cj )(−1)|U ∩([d]\S j )| ω|S |−|S j ∩U |,|[d]\(S j ∪U )| . j j=1 Proof. We define νj (S) := 1[S j ⊆ S ⊆ S j ] for each irreducible set from j = 1, . . . , r. Furthermore, we denote ϕU [ν] as the Shapley interaction index with respect to ν. Then, by linearity (Grabisch & Roubens, 1999) of ϕU , we obtain r X r X r X ϕU [ν] = ϕU [ ν(cj ) · 1[S j ⊆ S ⊆ S j ]] = ν(cj )ϕU [νj ] = ν(cj )(−1)|U ∩([d]\S j )| ω|S |−|S j ∩U |,|[d]\(S j ∪U )| . j j=1 j=1 j=1 With the efficient computation of the Shapley interaction index (Grabisch & Roubens, 1999), we can directly extract the n-Shapley values (Lundberg et al., 2018a; Bordt & von Luxburg, 2023) using the following recursion:  ϕU if |U | = n, ΦnU := n−1 P if |U | < n, ΦU + Bd−|U | K⊆[d]\U ϕU ∪K |K|+|S|=n with Φ1i := ϕi for all i ∈ [d]. The n-Shapley values have first been introduced by Lundberg et al. (2018b), and were later genearlized to arbitrary order n (Bordt & von Luxburg, 2023). Importantly, they satisfy the generalized efficiency axiom for Shapley interactions (Bordt & von Luxburg, 2023), i.e. X ΦnU = ν([d]), U ⊆[d]:|U |≤n 25 Exactly Computing do-Shapley Values where we defined Φ0∅ := ν(∅). do-Shapley Interactions for SCMs. Generalizations of the Shapley value to higher-order interactions provide a principled framework for explanations with varying degrees of granularity and expressivity. To illustrate this for do-Shapley values and their interaction-based extensions, we compute Shapley interactions using shapiq (Muschalik et al., 2024a) for SCMs derived from four datasets from the TALENT benchmark (Liu et al., 2025). Following Section 6, the SCMs are learned from data using GRaSP (Lam et al., 2022), with the corresponding variables described in Tables 1 to 4. The resulting do-Shapley interactions are visualized in Figures 8 to 11. First-order explanations recover the standard do-Shapley values, while the highest-order interactions correspond to the Möbius transform of the value function. We present the shapiq explanations as overlays on the learned SCMs, where node sizes represent main effects and edge or hyperedge widths encode interaction strength. The color indicates the direction of the effects (blue denotes a negative interaction and red a positive interaction). While first-order do-Shapley values summarize aggregated causal effects of individual features, increasing the interaction order yields progressively finer-grained insights into the causal structure. At the same time, the growing number of interaction terms poses interpretability challenges, motivating application-specific post-processing and selection of relevant interaction orders. X6 X8 X6 X8 X6 X8 X6 X8 X2 X3 X2 X3 X2 X3 X2 X3 X5 X7 Y X5 X7 Y X5 X7 Y X5 X7 Y X4 X1 X4 X1 X4 X1 X4 X1 SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions (order 1) (order 2) (order 8) Figure 8. do-Shapley values and interactions for B RAZILIAN HOUSES REPRODUCED of increasing order (feature names in Table 1). The size of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive). X4 X7 X4 X7 X4 X7 X4 X7 X3 X3 X3 X3 X1 Y X1 Y X1 Y X1 Y X6 X6 X6 X6 X5 X5 X5 X5 X2 X2 X2 X2 SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions (order 1) (order 2) (order 7) Figure 9. do-Shapley values and interactions for FOREX AUDJPY- HOUR -H IGH of increasing order (feature names in Table 4). The size of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive). 26 Exactly Computing do-Shapley Values X1 X1 X1 X1 X3 X4 X5 Y X3 X4 X5 Y X3 X4 X5 Y X3 X4 X5 Y X2 X2 X2 X2 SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions (order 1) (order 2) (order 5) Figure 10. do-Shapley values and interactions for L APTOP P RICES DATASET of increasing order (feature names in Table 3). The size of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive). X2 X4 X2 X4 X2 X4 X2 X4 X5 Y X5 Y X5 Y X5 Y X1 X3 X1 X3 X1 X3 X1 X3 SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions (order 1) (order 2) (order 5) Figure 11. do-Shapley values and interactions for Y EAST of increasing order (feature names in Table 2). The size of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive). Node Feature Name X1 hoa (BRL) X2 fire insurance (BRL) X3 parking spaces X4 rent amount (BRL) X5 rooms X6 property tax (BRL) X7 target X8 bathroom Y area Table 1. Variables for B RAZILIAN HOUSES REPRODUCED: d = 8 input features and 9 nodes in total (including target Y ). Node Feature Name X1 alm X2 nuc X3 vac X4 gvh X5 mcg Y mit Table 2. Variables for YEAST: d = 5 input features and 6 nodes in total (including target Y ). 27 Exactly Computing do-Shapley Values Node Feature Name X1 N0 X2 N1 X3 N5 X4 target X5 N4 Y N2 Table 3. Variables for L APTOP P RICES DATASET: d = 5 input features and 6 nodes in total (including target Y ). Node Feature Name X1 Ask Low X2 Bid Low X3 Bid Close X4 Ask Open X5 Ask Close X6 Bid Open X7 Ask High Y Bid High Table 4. Variables for FOREX AUDJPY- HOUR -H IGH: d = 7 input features and 8 nodes in total (including target Y ). 28 Exactly Computing do-Shapley Values G. Additional Experiments 10 0 Estimator Convergence (Aggregated) 10 −1 Relative MSE 10 −2 10 −3 Method doRegressionMSR 10 −4 doLeverageSHAP RegressionMSR 10 −5 LeverageSHAP Budget = r 10 −6 0.2 0.4 0.6 0.8 1.0 Budget Ratio m/r Figure 12. Estimator Convergence (Aggregated), Clipped View. The Relative Mean Squared Error (MSE) of Shapley value estimates versus the budget ratio m/r, aggregated across all datasets. This is the same plot as Figure 5, but where we have adjusted the view to more clearly show the distinctions in estimator performance for when m/r ≤ 1. Computation Cost vs. Budget Method doRegressionMSR doLeverageSHAP 10 0 Computation Time (s) RegressionMSR LeverageSHAP Budget = r 10 −1 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Budget Ratio m/r Figure 13. Computational Cost. Average wall-clock time (seconds) versus budget ratio (m/r). The structure-aware estimators (i.e. “do”-variants) incur a consistent runtime overhead compared to their structure-agnostic counterparts. This additional cost represents the time required for graph traversal and boundary sampling to identify distinct equivalence classes. The more computationally demanding structural exploration is the necessary trade-off to achieve the orders-of-magnitude reduction in estimation error seen in e.g. Figure 5. 29 Exactly Computing do-Shapley Values Table 5. Relative MSE statistics by budget ratio (m/r). Metric LeverageSHAP doLeverageSHAP RegressionMSR doRegressionMSR Budget Ratio m/r = 0.25 Mean 1.5e-1 1.2e-1 3.5e-1 6.0e-2 Median 8.2e-3 9.8e-3 7.9e-3 3.8e-4 Q1 (25%) 8.5e-4 4.1e-4 1.5e-4 8.1e-8 Q2 (50%) 8.2e-3 9.8e-3 7.9e-3 3.8e-4 Q3 (75%) 2.2e-1 5.9e-2 3.0e-1 1.1e-2 Q4 (Max) 2.5e+00 5.6e+00 2.4e+00 1.2e+00 Budget Ratio m/r = 0.5 Mean 5.8e-2 6.8e-2 1.4e-1 2.5e-2 Median 1.9e-3 4.8e-3 8.8e-4 1.1e-5 Q1 (25%) 2.0e-4 1.4e-4 1.5e-5 5.9e-9 Q2 (50%) 1.9e-3 4.8e-3 8.8e-4 1.1e-5 Q3 (75%) 1.3e-2 1.9e-2 9.7e-3 1.4e-3 Q4 (Max) 1.2e+00 5.6e+00 2.0e+00 7.0e-1 Budget Ratio m/r = 0.75 Mean 1.8e-2 9.1e-3 5.5e-2 6.1e-3 Median 4.8e-4 9.9e-4 1.4e-4 5.7e-7 Q1 (25%) 7.7e-5 2.2e-5 2.8e-6 3.8e-10 Q2 (50%) 4.8e-4 9.9e-4 1.4e-4 5.7e-7 Q3 (75%) 2.5e-3 6.0e-3 2.3e-3 1.5e-4 Q4 (Max) 6.6e-1 3.6e-1 2.0e+00 3.3e-1 Budget Ratio m/r = 1.0 Mean 6.2e-3 4.2e-6 4.8e-3 2.0e-5 Median 2.4e-4 4.1e-29 4.4e-6 3.5e-13 Q1 (25%) 2.8e-5 1.1e-30 2.0e-7 2.6e-14 Q2 (50%) 2.4e-4 4.1e-29 4.4e-6 3.5e-13 Q3 (75%) 1.2e-3 6.1e-26 5.1e-4 2.6e-12 Q4 (Max) 3.3e-1 3.7e-4 3.0e-1 3.7e-3 30