Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract)

Bienvenu, Meghyn; Figueira, Diego; Lafourcade, Pierre

doi:10.24963/ijcai.2025/1208

Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract)

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Sister Conferences Best Papers. Pages 10875-10880.

https://doi.org/10.24963/ijcai.2025/1208

Keywords

Sister Conferences Best Papers: Knowledge Representation and Reasoning

Abstract

In this work, we explore the use of the Shapley value in ontology-mediated query answering (OMQA) and provide 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 formulated in the description logic ELHI-bot and a connected constant-free homomorphism-closed query q. We further strengthen the #P-hardness side of the dichotomy 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.

Meghyn Bienvenu, Diego Figueira, and Pierre Lafourcade. 2025. Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract). In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 10875–10880. https://doi.org/10.24963/ijcai.2025/1208

@inproceedings{ijcai2025p1208,
  title     = {Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract)},
  author    = {Bienvenu, Meghyn and Figueira, Diego and Lafourcade, Pierre},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {10875--10880},
  year      = {2025},
  month     = {8},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2025/1208},
  url       = {https://doi.org/10.24963/ijcai.2025/1208},
}

TY  - CPAPER
TI  - Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract)
AU  - Bienvenu, Meghyn
AU  - Figueira, Diego
AU  - Lafourcade, Pierre
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 10875
EP  - 10880
DO  - 10.24963/ijcai.2025/1208
UR  - https://doi.org/10.24963/ijcai.2025/1208
ER  -