{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T19:01:39Z","timestamp":1772910099954,"version":"3.50.1"},"reference-count":41,"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"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["DesCartes"],"award-info":[{"award-number":["DesCartes"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark.<\/jats:p>","DOI":"10.1145\/3651593","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-26","source":"Crossref","is-referenced-by-count":8,"title":["Expected Shapley-Like Scores of Boolean functions: Complexity and Applications to Probabilistic Databases"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-1111-8801","authenticated-orcid":false,"given":"Pratik","family":"Karmakar","sequence":"first","affiliation":[{"name":"National University of Singapore &amp; CNRS@CREATE Ltd, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6158-4607","authenticated-orcid":false,"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"Inria, CRIStAL, Universit\u00e9 de Lille, CNRS, Villeneuve-d'Ascq, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7909-5369","authenticated-orcid":false,"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"DIENS, DI ENS, ENS, PSL University, CNRS, Inria &amp; IUF, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5536-3296","authenticated-orcid":false,"given":"Stephane","family":"Bressan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Omer Abramovich Daniel Deutch Nave Frost Ahmet Kara and Dan Olteanu. 2023. Banzhaf Values for Facts in Query Answering. arXiv preprint arXiv:2308.05588.","DOI":"10.1145\/3654926"},{"key":"e_1_2_2_3_1","volume-title":"ICDT (LIPIcs","volume":"17","author":"Amarilli Antoine","year":"2023","unstructured":"Antoine Amarilli. 2023. Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries. In ICDT (LIPIcs, Vol. 255). 14:1--14:17."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09930-2"},{"key":"e_1_2_2_5_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_2_6_1","first-page":"1","article-title":"J","volume":"24","author":"Arenas Marcelo","year":"2023","unstructured":"Marcelo Arenas, Pablo Barcel\u00f3, Leopoldo E Bertossi, and Mika\u00ebl Monet. 2023. J. Mach. Learn. Res. , Vol. 24, 63 (2023), 1--58.","journal-title":"Mach. Learn. Res."},{"key":"e_1_2_2_7_1","unstructured":"Marcelo Arenas Pablo Barcel\u00f3 Leonid Libkin Wim Martens and Andreas Pieris. 2022. Database Theory. Work in progress latest version at https:\/\/github.com\/pdm-book\/community."},{"key":"e_1_2_2_8_1","first-page":"317","article-title":"Weighted voting doesn't work: A mathematical analysis","volume":"19","author":"John F","year":"1964","unstructured":"John F Banzhaf III. 1964. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev. , Vol. 19 (1964), 317.","journal-title":"Rutgers L. Rev."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3615952.3615954"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Meghyn Bienvenu Diego Figueira and Pierre Lafourcade. 2024. When is Shapley Value Computation a Matter of Counting?. In PODS.","DOI":"10.1145\/3651606"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Surajit Borkotokey Sujata Gowala and Rajnish Kumar. 2023. The Expected Shapley value on a class of probabilistic games. arXiv preprint arXiv:2308.03489.","DOI":"10.2139\/ssrn.4784503"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.02.017"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10726-014-9425-3"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753239"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Guy Van den Broeck Anton Lykov Maximilian Schleich and Dan Suciu. 2021. On the Tractability of SHAP Explanations. In AAAI. 6505--6513.","DOI":"10.1609\/aaai.v35i7.16806"},{"key":"e_1_2_2_17_1","volume-title":"Computing the Shapley Value of Facts in Query Answering. In SIGMOD Conference. 1570--1583","author":"Deutch Daniel","year":"2022","unstructured":"Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mika\u00eb l Monet. 2022. Computing the Shapley Value of Facts in Query Answering. In SIGMOD Conference. 1570--1583."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01283881"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1068\/a090569"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1068\/a100907"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Ahmet Kara Dan Olteanu and Dan Suciu. 2024. From Shapley Value to Model Counting and Back. In PODS.","DOI":"10.1145\/3651142"},{"key":"e_1_2_2_23_1","unstructured":"Adam Karczmarz Tomasz P. Michalak Anish Mukherjee Piotr Sankowski and Piotr Wygocki. 2022. Improved feature importance computation for tree models based on the Banzhaf value. In UAI."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-009-0387-3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-016-1012-x"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Jean-Marie Lagniez and Pierre Marquis. 2017. An Improved Decision-DNNF Compiler. In IJCAI. 667--673.","DOI":"10.24963\/ijcai.2017\/93"},{"key":"e_1_2_2_27_1","unstructured":"Annick Laruelle. 1999. On the choice of a power index. Technical Report. Instituto Valenciano de Investigaciones Econ\u00f3micas."},{"key":"e_1_2_2_28_1","first-page":"73","article-title":"Potential, value, and coalition formation","volume":"16","author":"Laruelle Annick","year":"2008","unstructured":"Annick Laruelle and Federico Valenciano. 2008. Potential, value, and coalition formation. Transactions in Operations Research , Vol. 16 (2008), 73--89.","journal-title":"Transactions in Operations Research"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(3:22)2021"},{"key":"e_1_2_2_30_1","first-page":"1","article-title":"The Shapley value of tuples in query answering","volume":"155","author":"Livshits Ester","year":"2020","unstructured":"Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. 2020. The Shapley value of tuples in query answering. In ICDT, Vol. 155. 20:1--20:19.","journal-title":"ICDT"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Mika\u00ebl Monet. 2020. Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases. In PODS. 149--163.","DOI":"10.1145\/3375395.3387642"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.5.64"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/3375395.3387664"},{"key":"e_1_2_2_35_1","volume-title":"SIGMOD Record","volume":"46","author":"Senellart Pierre","year":"2017","unstructured":"Pierre Senellart. 2017. Provenance and Probabilities in Relational Databasesstring: From Theory to Practice. SIGMOD Record, Vol. 46, 4 (2017)."},{"key":"e_1_2_2_36_1","first-page":"2034","article-title":"ProvSQL","volume":"11","author":"Senellart Pierre","year":"2018","unstructured":"Pierre Senellart, Louis Jachiet, Silviu Maniu, and Yann Ramusat. 2018. ProvSQL: Provenance and Probability Management in PostgreSQL. Proc. VLDB Endow. , Vol. 11, 12 (2018), 2034--2037.","journal-title":"Provenance and Probability Management in PostgreSQL. Proc. VLDB Endow."},{"key":"e_1_2_2_37_1","volume-title":"Shapley et al","author":"Lloyd","year":"1953","unstructured":"Lloyd S. Shapley et al. 1953. A value for n-person games. (1953)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool.","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_2_39_1","volume-title":"On the complexity of derivation in propositional calculus. Studies in Constrained Mathematics and Mathematical Logic","author":"Tseitin G","year":"1968","unstructured":"G Tseitin. 1968. On the complexity of derivation in propositional calculus. Studies in Constrained Mathematics and Mathematical Logic (1968)."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13283"},{"key":"e_1_2_2_41_1","volume-title":"Probabilistic values for games. The Shapley Value. Essays in Honor of Lloyd S. Shapley","author":"Weber Robert J","year":"1988","unstructured":"Robert J Weber. 1988. Probabilistic values for games. The Shapley Value. Essays in Honor of Lloyd S. Shapley (1988), 101--119."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:13Z","timestamp":1755898813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651593"],"URL":"https:\/\/doi.org\/10.1145\/3651593","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}