{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:34:36Z","timestamp":1770960876196,"version":"3.50.1"},"reference-count":13,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>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 existing hardness results for SVC, but also new complexity results. In particular, we establish FP-#P complexity dichotomies for constant-free unions of connected CQs and connected homomorphism-closed graph queries. We also consider some variants of the SVC problem, by disallowing assumed facts or quantifying the contributions of constants rather than facts.<\/jats:p>","DOI":"10.1145\/3651606","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-24","source":"Crossref","is-referenced-by-count":5,"title":["When is Shapley Value Computation a Matter of Counting?"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-8103","authenticated-orcid":false,"given":"Meghyn","family":"Bienvenu","sequence":"first","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0114-2257","authenticated-orcid":false,"given":"Diego","family":"Figueira","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4810-1289","authenticated-orcid":false,"given":"Pierre","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.14"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5802\/jtnb.344"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.104"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469--8.50076-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517912"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877203"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651142"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458313"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.11"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_1_13_1","volume-title":"Contributions to the Theory of Games II, Harold W","author":"Shapley Lloyd S","unstructured":"Lloyd S Shapley. 1953. A Value for N-Person Games. In Contributions to the Theory of Games II, Harold W. Kuhn and Albert W. Tucker (Eds.). Princeton University Press, 307--317."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:09Z","timestamp":1755898749000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651606"],"URL":"https:\/\/doi.org\/10.1145\/3651606","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}