Asymmetric Shapley Values: Efficient polynomial-time algorithms

Ezequiel Companeetz, Santiago Cifuentes and Sergio Abriola submitted a paper titled "Beyond Shapley: Efficient Computation of Asymmetric Shapley Values" to arXiv on 23 Jun 2026 (arXiv:2606.25103). The 18-page paper with 6 figures studies Asymmetric Shapley Values, proving polynomial-time computability in specific causal settings and proposing a sampling-based approximation for general causal DAGs.

What are Asymmetric Shapley Values?

Asymmetric Shapley Values are a variant of Shapley value feature attributions that incorporate causal knowledge by using a causal graph to restrict permutations and influence allocations. The paper frames ASV as a model-agnostic explanation method that uses a causal graph to encode asymmetries between features, enabling feature attributions that respect known causal structure rather than treating features as exchangeable.

The authors position ASV as a way to bring causal constraints into feature attribution. They note that this causal information changes computational properties: while standard SHAP can be #P-hard to compute in some settings, ASV admits tractable algorithms under certain graph structures.

How do the authors compute ASV efficiently?

The paper gives two complementary algorithmic results: exact polynomial-time computation for some graphs and an approximation strategy for arbitrary DAGs. First, the authors introduce equivalence classes over topological orderings of the causal graph and show that these classes reduce the number of distinct permutations that matter for ASV computation.

Building on that notion, they present a polynomial-time algorithm, polynomial in the number of equivalence classes, that computes ASV whenever the causal graph is a rooted directed tree. For general causal DAGs the paper develops an approximation algorithm that relies on sampling topological orderings uniformly at random. To implement that sampler the authors leverage known algorithms as well as simpler alternatives, and they report experimental results demonstrating practical viability in realistic causal structures.

How does this compare to SHAP's hardness?

The paper contrasts ASV and SHAP by pointing out that SHAP computation is #P-hard in certain contexts, while ASV can be exactly computed in polynomial time for rooted directed trees and in contexts where equivalence classes collapse the ordering space. That comparison is central to the technical contribution: causal structure can both change the semantics of attribution and simplify computation when the graph restricts permissible orderings.

The authors formalize the reduction in complexity by defining equivalence classes over topological orderings and giving algorithms whose runtime scales with the number of these classes rather than the factorial number of raw permutations.

Why it matters

Making causal constraints explicit in feature attributions influences both what explanations mean and how costly they are to compute. If a modeler can encode causal structure as a rooted directed tree, the paper shows exact ASV can be computed in polynomial time rather than facing #P-hardness. That opens a route for causally informed, tractable explanations in domains where causal graphs are reliable.

The approximation path for arbitrary DAGs is also practical: sampling topological orderings uniformly at random turns an intractable combinatorial problem into a procedure the authors demonstrate empirically works on realistic structures.

What to watch

Look for follow-up code releases or implementations from the authors, and for tests of the sampling-based approximation on larger, real-world causal DAGs. The paper itself is available as arXiv:2606.25103 and lists experimental results that the community can reproduce from the algorithms described.

References and concrete facts from the submission: the paper was submitted on 23 Jun 2026, is 18 pages long and contains 6 figures, and it introduces a polynomial-time algorithm (in the number of equivalence classes) for rooted directed trees while proposing a uniform topological-ordering sampler for ASV approximation in general DAGs.