{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T21:15:04Z","timestamp":1762982104000,"version":"3.44.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>The Shapley value, originating from cooperative game theory, has been employed to define responsibility measures that quantify the contributions of database facts to obtaining a given query answer. For non-numeric queries, this is done by considering a cooperative game whose players are the facts and whose wealth function assigns 1 or 0 to each subset of the database, depending on whether the query answer holds in the given subset. While conceptually simple, this approach suffers from a notable drawback: the problem of computing such Shapley values is #P-hard in data complexity, even for simple conjunctive queries. This motivates us to revisit the question of what constitutes a reasonable responsibility measure and to introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS) -- which satisfy intuitive properties. Interestingly, while the definition of WSMSs is simple and bears no obvious resemblance to the Shapley value formula, we prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game. Moreover, WSMS measures enjoy tractable data complexity for a large class of queries, including all unions of conjunctive queries. We further explore the combined complexity of WSMS computation and establish (in)tractability results for various subclasses of conjunctive queries.<\/jats:p>","DOI":"10.1145\/3725249","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Shapley Revisited: Tractable Responsibility Measures for Query Answers"],"prefix":"10.1145","volume":"3","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, Bordeaux, 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, Bordeaux, 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, Bordeaux, France"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654926"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651606"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517912"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01780630"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098--2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(80)90009--2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2026067.2026103"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/203610.203611"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--30823--9_9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.06.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651142"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651593"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.1.89.10589"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-18(2:20)2022"},{"key":"e_1_2_1_19_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Lundberg Scott M","year":"2017","unstructured":"Scott M Lundberg and Su-In Lee. 2017. A Unified Approach to Interpreting Model Predictions. In Advances in Neural Information Processing Systems, Vol. 30. Curran Associates, Inc."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3635301"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2013.01.012"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_1_24_1","volume-title":"Quantifying Causal Effects on Query Answering in Databases. 8th USENIX Workshop on the Theory and Practice of Provenance (TaPP).","author":"Salimi Babak","year":"2016","unstructured":"Babak Salimi, Leopoldo Bertossi, Dan Suciu, and Guy Van den Broeck. 2016. Quantifying Causal Effects on Query Answering in Databases. 8th USENIX Workshop on the Theory and Practice of Provenance (TaPP)."},{"key":"e_1_2_1_25_1","volume-title":"A value for n-person games. Contribution to the Theory of Games","author":"Shapley Lloyd S","year":"1953","unstructured":"Lloyd S Shapley. 1953. A value for n-person games. Contribution to the Theory of Games , Vol. 2 (1953)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/S13218-016-0451-Y"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(92)90369-Q"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000066"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:19Z","timestamp":1755904699000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725249"],"URL":"https:\/\/doi.org\/10.1145\/3725249","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}