{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:44:49Z","timestamp":1787017489671,"version":"build-2736575974"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF IIS","award":["2314527"],"award-info":[{"award-number":["2314527"]}]},{"name":"UZH Global Strategy and Partnerships Funding Scheme"},{"name":"Simons Program on Logic and Algorithms in Databases and AI"},{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/3651142","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-23","source":"Crossref","is-referenced-by-count":10,"title":["From Shapley Value to Model Counting and Back"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8155-8070","authenticated-orcid":false,"given":"Ahmet","family":"Kara","sequence":"first","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Marcelo Arenas Pablo Barcel\u00f3 Leopoldo E. Bertossi and Mika\u00eb l Monet. 2021. The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits. In AAAI. 6670--6678.","DOI":"10.1609\/aaai.v35i8.16825"},{"key":"e_1_2_1_2_1","article-title":"On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results","volume":"24","author":"Arenas Marcelo","year":"2023","unstructured":"Marcelo Arenas, Pablo Barcel\u00f3, Leopoldo E. Bertossi, and Mika\u00eb l Monet. 2023. On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results. J. Mach. Learn. Res. , Vol. 24 (2023), 63:1--63:58. http:\/\/jmlr.org\/papers\/v24\/21-0389.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_3_1","unstructured":"Marcelo Arenas Pablo Barcel\u00f3 Miguel A. Romero Orth and Bernardo Subercaseaux. 2022. On Computing Probabilistic Explanations for Decision Trees. In NeurIPS."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.23.2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2015.143"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469--8.50076-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.7.9.62"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Susan B. Davidson Daniel Deutch Nave Frost Benny Kimelfeld Omer Koren and Mika\u00eb l Monet. 2022. ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values. In SIGMOD. 2373--2376. https:\/\/doi.org\/10.1145\/3514221.3520172","DOI":"10.1145\/3514221.3520172"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13283"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Daniel Deutch Nave Frost Benny Kimelfeld and Mika\u00eb l Monet. 2022. Computing the Shapley Value of Facts in Query Answering. In SIGMOD. 1570--1583. https:\/\/doi.org\/10.1145\/3514221.3517912","DOI":"10.1145\/3514221.3517912"},{"key":"e_1_2_1_13_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"1996","unstructured":"Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations, Third Edition. Johns Hopkins University Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA201009"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Todd J. Green Gregory Karvounarakis and Val Tannen. 2007. Provenance Semirings. In PODS. 31--40. https:\/\/doi.org\/10.1145\/1265530.1265535","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019732787X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2305.08103"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2004.00543.x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196--6774(89)90038--2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2049205"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Richard T. B. Ma Dah-Ming Chiu John C. S. Lui Vishal Misra and Dan Rubenstein. 2008. Interconnecting Eyeballs to Content: A Shapley Value Perspective on ISP Peering and Settlement. In SIGCOMM. 61--66. https:\/\/doi.org\/10.1145\/1403027.1403041","DOI":"10.1145\/1403027.1403041"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-021--10088-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq508"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2010.2052042"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--87993-0_26"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Alon Reshef Benny Kimelfeld and Ester Livshits. 2020. The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries. In PODS. 285--297. https:\/\/doi.org\/10.1145\/3375395.3387664","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_1_29_1","volume-title":"The Shapley Value: Essays in Honor of Lloyd S. Shapley","author":"Roth Alvin E","unstructured":"Alvin E Roth. 1988. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/778"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881970-018"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool Publishers. https:\/\/doi.org\/10.2200\/S00362ED1V01Y201105DTM016","DOI":"10.2200\/S00362ED1V01Y201105DTM016"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-017-0480-z"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651142","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:11Z","timestamp":1755898751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651142"],"URL":"https:\/\/doi.org\/10.1145\/3651142","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}