{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T19:02:36Z","timestamp":1772910156901,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>The Shapley value, originally introduced in cooperative game theory for wealth distribution, has found use in KR and databases for the purpose of assigning scores to formulas and database tuples based upon their contribution to obtaining a query result or inconsistency. In the present paper, we explore the use of Shapley values in ontology-mediated query answering (OMQA) and present a detailed complexity analysis of Shapley value computation (SVC) in the OMQA setting. In particular, we establish a FP \/ #P-hard dichotomy for SVC for ontology-mediated queries (T, q) composed of an ontology T is formulated in the description logic ELHIbot and a connected constant-free homomorphism-closed query q. We further show that the #P-hardness side of the dichotomy can be strengthened to cover possibly disconnected queries with constants. Our results exploit recently discovered connections between SVC and probabilistic query evaluation and allow us to generalize existing results on probabilistic OMQA.<\/jats:p>","DOI":"10.24963\/kr.2024\/15","type":"proceedings-article","created":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:28Z","timestamp":1729924228000},"page":"156-166","source":"Crossref","is-referenced-by-count":3,"title":["Shapley Value Computation in Ontology-Mediated Query Answering"],"prefix":"10.24963","author":[{"given":"Meghyn","family":"Bienvenu","sequence":"first","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"},{"name":"Japanese-French Laboratory for Informatics, CNRS, NII, IRL 2537"}]},{"given":"Diego","family":"Figueira","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"}]},{"given":"Pierre","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800"}]}],"member":"10584","event":{"name":"21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}","theme":"Artificial Intelligence","location":"Hanoi, Vietnam","acronym":"KR-2024","number":"21","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2024,11,1]]},"end":{"date-parts":[[2024,11,8]]}},"container-title":["Proceedings of the TwentyFirst International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:31Z","timestamp":1729924231000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2024\/15"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2024\/15","relation":{},"subject":[],"published":{"date-parts":[[2024,11]]}}}