Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola · 2026

Read Beyond Shapley: Efficient Computation of Asymmetric Shapley Values by Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25103.txt.

Introduction

Asymmetric Shapley values adapt feature attribution to causal knowledge: a causal graph restricts which orderings of features count. Ezequiel Companeetz, Santiago Cifuentes, and Sergio Abriola study when these values can be computed exactly and fast. In some settings where the standard SHAP computation is provably hard, they show the asymmetric version is tractable.

Equivalence classes over the orderings of the graph do the compression work. For a rooted directed tree, an algorithm computes the values in time polynomial in the number of classes. For any directed acyclic graph, the team gets close to the values by sampling orderings at random, each ordering equally likely, reusing known samplers and simpler alternatives. Tests on real world causal structures show the approach is practical.

Catalog record

CREATOREzequiel Companeetz, Santiago Cifuentes, Sergio Abriola
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25103

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola Abstract We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is # P -hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures. Más allá de Shapley: Algoritmos Eficientes para calcular los Shapley Values Asimétricos 1 Introduction The field of XAI ( Explainable Artificial Intelligence ) aims to develop methods capable of making model decisions more interpretable ( 13 ) . Within this field, one of the most influential approaches is feature attribution, where each input variable is assigned a score reflecting its contribution to the prediction. In this line of work, SHAP is one of the most well-known methods ( 11 ) . It is based on the Shapley values, a concept originating in cooperative game theory ( 16 ) . Intuitively, Shapley values provide a fair way to distribute the total value achieved by a coalition among its participants, according to their average marginal contribution when joining. Translated to machine learning, features play the role of players, and the value assigned to each feature aims to quantify its contribution to the model’s prediction for a given instance. Despite its popularity, SHAP has important limitations. On the one hand, depending on the family of ML models under consideration and the underlying distribution of the data, the computation of the Shapley values can be tractable or not. For example, it is well-known that for product distributions the complexity of computing these scores is equivalent to the complexity of computing the average value of the model ( 17 ) . In particular, this implies that there exist efficient algorithms for the case where the models are given, for example, by decision trees or by restricted families of circuits ( 1 ) , while the problem is intractable whenever the models are more expressive, as in the case of neural nets. For more general families of distributions the problem becomes much harder: for instance, when considering Naive Bayes distributions, the computation of this score is intractable already when considering trivial models that only depend on one feature ( 17 ) . On the other hand, there are also concerns about the quality of the explanations it produces. In particular, it is not always clear how to interpret, in the context of AI models, the axioms inherited from game theory, and several works point out that these explanations may fail to adequately capture relationships such as dependence, relevance, or causality between variables ( 6 ; 12 ; 7 ) . More generally, there is no absolute consensus on what should be considered an “explanation” in AI: many current techniques are pragmatic approximations to a much broader problem related to understanding, causality, and human interpretability ( 14 ; 10 ) . The Asymmetric Shapley Values (ASV from now on) are a proposal introduced by 5 to overcome some of these limitations. This variant incorporates causal information into the computation of attribution scores by restricting attention to permutations of variables that respect a causal graph. In this way, instead of treating all features symmetrically, priority is given to the more fine-grained ones (in the sense that the information they provide is not present in the other variables). This can produce explanations that are more faithful to the data-generating process and can help better detect phenomena such as bias or discrimination. Moreover, although ASV was primarily proposed to improve explanatory quality, it naturally raises the question of whether this additional restriction may also provide computational benefits. Therefore, in this paper we address the problem of efficiently computing the ASV scores, which was not explored thoroughly in previous literature. We will prove that for some families of models for which computing the Shapley values is intractable there are still polynomial time algorithms for computing the ASV. Inspired by this initial result, we develop an algorithm to compute the ASV exactly in more general contexts by exploiting the fact that many permutations of the features can be grouped in a unique equivalence class to simplify computations. Finally, we also propose a flexible approximation scheme that allows to approximate the ASV as long as it is possible to (1) Sample a topological order of the causal graph uniformly at random, and (2) Sample a data point with respect to the data distribution after conditioning a subset of the features to have specific values. We instantiate all these general algorithms with particular examples of causal graphs and machine learning models and show experimentally that they are efficient. 2 Definitions Let X be a finite set of features. A (binary) entity over X is a mapping e:X\to\{0,1\} assigning a value to every feature from X . We denote by \texttt{ent}{}(X) the set of all entities, and we will assume that some probability distribution is provided over this set. A (binary) classifier is a mapping M:\texttt{ent}{}(X)\to\{0,1\} . We restrict to both binary entities and classifiers only for simplicity: all the results and algorithms we obtain can be extended to more general cases straightforwardly. Given a model M and an entity e , a feature attribution score is a mapping \phi_{M,e}:X\to\mathds{R} . Intuitively, the value \phi_{M,e}(x) indicates the relevance of feature x with respect to prediction M(e) . As mentioned before, one of the most studied feature attribution schemes is the SHAP-score ( 11 ) , which is theoretically grounded on the Shapley values ( 16 ) from cooperative game theory. In that context, the Shapley values come up as the “most fair” way to distribute some capital earned during a team game. More precisely, given a finite set of players \mathcal{I} and a characteristic function \nu:\mathcal{P}(\mathcal{I})\to\mathbb{R} describing, for each subset of the players, the reward that such coalition would obtain in some fixed game; the shapley values are the unique assignment \varphi_{\nu}:\mathcal{I}\to\mathds{R} of reward to each player i satisfying the following desired properties: 1. Efficiency: All the reward is distributed, i.e. \sum_{i\in\mathcal{I}}\varphi_{\nu}(i)=\nu(\mathcal{I})-\nu(\emptyset) . 2. Symmetry: If \nu(S\cup\{i\})=\nu(S\cup\{j\}) for every S\subseteq\mathcal{I}\setminus\{i,j\} , then \varphi_{\nu}(i)=\varphi_{\nu}(j) . 3. Null Player: If \nu(S\cup\{i\})=\nu(S) for every S\subseteq\mathcal{I} , then \varphi_{\nu}(i)=0 . 4. Linearity: For any pair of characteristic functions \nu_{1},\nu_{2} and a\in\mathds{R} it holds that \varphi_{a\nu_{1}+\nu_{2}}(i)=a\varphi_{\nu_{1}}(i)+\varphi_{\nu_{2}}(i) 1 1 1 The characteristic function a\nu_{1}+\nu_{2} is naturally defined as (a\nu_{1}+\nu_{2})(S)=a\nu_{1}(S)+\nu_{2}(S) . . Moreover, the Shapley

Read the complete text