# From Shapley Value to Model Counting and Back

arXiv: https://arxiv.org/abs/2306.14211 · HTML: https://mlsanity.com/paper/2306.14211/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2023.

## Built on by (most cited first, 7 of 7)

- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases](https://mlsanity.com/paper/2401.06493/) (2024)
- [Shapley Value Computation in Ontology-Mediated Query Answering](https://mlsanity.com/paper/2407.20058/) (2024)
- [Shapley Revisited: Tractable Responsibility Measures for Query Answers](https://mlsanity.com/paper/2503.22358/) (2025)
- [The Causal-Effect Score in Data Management](https://mlsanity.com/paper/2502.02495/) (2025)
- [Causality-Based Scores Alignment in Explainable Data Management](https://mlsanity.com/paper/2503.14469/) (2025)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)

## Abstract (arXiv)

In this paper we investigate the problem of quantifying the contribution of each variable to the satisfying assignments of a Boolean function based on the Shapley value. Our main result is a polynomial-time equivalence between computing Shapley values and model counting for any class of Boolean functions that are closed under substitutions of variables with disjunctions of fresh variables. This result settles an open problem raised in prior work, which sought to connect the Shapley value computation to probabilistic query evaluation. We show two applications of our result. First, the Shapley values can be computed in polynomial time over deterministic and decomposable circuits, since they are closed under OR-substitutions. Second, there is a polynomial-time equivalence between computing the Shapley value for the tuples contributing to the answer of a Boolean conjunctive query and counting the models in the lineage of the query. This equivalence allows us to immediately recover the dichotomy for Shapley value computation in case of self-join-free Boolean conjunctive queries; in particular, the hardness for non-hierarchical queries can now be shown using a simple reduction from the #P-hard problem of model counting for lineage in positive bipartite disjunctive normal form.