Exactly Computing do-Shapley Values

Structural Causal Models (SCM) are a powerful framework for describing complicated dynamics across the natural sciences. A particularly elegant way of interpreting SCMs is via do-Shapley values, a game-theoretic method of quantifying the average effect of $d$ variables across exponentially many interventions. Like Shapley values, computing do-Shapley values generally requires evaluating exponentially many terms. The foundation of our work is a reformulation of do-Shapley values in terms of the irreducible sets of the underlying SCM. Leveraging this insight, we can exactly compute do-Shapley values in time linear in the number of irreducible sets $r$, which itself can range from $d$ to $2^d$ depending on the graph structure of the SCM. Since $r$ is unknown a priori, we complement the exact algorithm with an estimator that, like general Shapley value estimators, can be run with any query budget. As the query budget approaches $r$, our estimators can produce more accurate estimates than prior methods by several orders of magnitude, and, when the budget reaches $r$, return the Shapley values up to machine precision. Beyond computational speed, we also reduce the identification burden: we prove that non-parametric identifiability of do-Shapley values requires only the identification of interventional effects for the $d$ singleton coalitions, rather than all classes.

Understanding cause and effect is central to science: a doctor wants to know whether a drug caused a patient to improve, an economist whether a policy caused unemployment to fall. Researchers capture these relationships in mathematical models, and then try to fairly assign credit to each contributing factor — for example, how much a patient's medication versus their diet mattered for recovery. A well-established way to assign this credit fairly is borrowed from game theory, but it has a serious drawback: it requires testing every possible combination of factors, and the number of combinations doubles with each factor added. For models with many factors, this quickly becomes impossible to compute. We noticed that many of these combinations are secretly identical. Because of how causes and effects are wired together, changing certain factors often makes no difference once others are already accounted for. We developed a method that recognizes these equivalent combinations and groups them, so the expensive calculation is done only once per group rather than once per combination. When the full calculation is still too costly, we provide a fast approximation that spends its limited budget wisely. This makes explaining cause and effect dramatically faster, helping researchers draw trustworthy conclusions from complex models.