# When is Shapley Value Computation a Matter of Counting?

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2023.

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

- [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)
- [QGShap: Quantum Acceleration for Faithful GNN Explanations](https://mlsanity.com/paper/2512.03099/) (2025)
- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)

## Abstract (arXiv)

The Shapley value provides a natural means of quantifying the contributions of facts to database query answers. In this work, we seek to broaden our understanding of Shapley value computation (SVC) in the database setting by revealing how it relates to Fixed-size Generalized Model Counting (FGMC), which is the problem of computing the number of sub-databases of a given size and containing a given set of assumed facts that satisfy a fixed query. Our focus will be on explaining the difficulty of SVC via FGMC, and to this end, we identify general conditions on queries which enable reductions from FGMC to SVC. As a byproduct, we not only obtain alternative explanations for most existing results on SVC, but also new complexity results. In particular, we establish FP-#P complexity dichotomies for constant-free connected UCQs and homomorphism-closed connected graph queries. We further explore variants of SVC, either in the absence of assumed facts, or where we measure the contribution of constants rather than facts.