From Shapley Value to Model Counting and Back

Summary: Proves a polynomial-time equivalence between computing Shapley values and model counting for any Boolean class closed under substituting variables by disjunctions of fresh variables. Yields poly-time Shapley on deterministic decomposable circuits and a tight dichotomy for self‑join‑free Boolean CQs, with non‑hierarchical hardness via #P model-counting reductions on DNF lineage. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1942
Venue: PODS
Year: 2024
Pagerank: 7.0181891e-05
Overall Rank: 3,918 | 73.13%
DOI: 10.1145/3651142

Incoming Non-self Citations Over Time

Authors

1. Ahmet Kara (University of Zurich)
2. Dan Olteanu (University of Zurich)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{kara_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{From Shapley Value to Model Counting and Back}},
        url = {https://dl.acm.org/doi/10.1145/3651142},
        doi = {10.1145/3651142},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kara, Ahmet and Olteanu, Dan and Suciu, Dan},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,382	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	6.237788e-05
5,657	When is Shapley Value Computation a Matter of Counting?	2024	PODS	6.1313425e-05
8,688	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	5.3847009e-05
9,541	Shapley Value Estimation Based on Differential Matrix	2025	SIGMOD	5.2528121e-05
9,809	Shapley Revisited: Tractable Responsibility Measures for Query Answers	2025	PODS	5.214913e-05
10,183	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	5.093636e-05
10,198	ASSS: Adaptive Stratified Sampling for Shapley-like Values	2026	SIGMOD	5.093636e-05
10,214	CoShap: A Scalable Coalition Growth Approach to Shapley Value Approximation	2026	SIGMOD	5.093636e-05
10,796	Understanding the Black Box: A Deep Empirical Dive into Shapley Value Approximations for Tabular Data	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059843817
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
2,424	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.6009068e-05
2,670	The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries	2020	PODS	8.2737143e-05
5,824	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	6.0750989e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,084	Symmetric Weighted First-Order Model Counting	2015	PODS
2	10,174	A Unifying Algorithm for Hierarchical Queries	2026	PODS
3	5,441	Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games	2024	SIGMOD
4	9,809	Shapley Revisited: Tractable Responsibility Measures for Query Answers	2025	PODS
5	7,851	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS
6	10,183	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS
7	2,670	The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries	2020	PODS
8	2,424	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD
9	5,382	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS
10	5,657	When is Shapley Value Computation a Matter of Counting?	2024	PODS