Asymmetric Shapley Values Computable in Polynomial Time Using Causal Graphs

Asymmetric Shapley Values (ASV) incorporate causal structure into feature attribution and can be computed exactly in polynomial time in cases where standard SHAP is #P-hard. A polynomial-time algorithm is presented for rooted directed tree causal graphs, plus an approximation algorithm for arbitrary DAGs via topological ordering sampling.