![[2407.20058] Shapley Value Computation in Ontology-Mediated Query Answering](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2407.20058] Shapley Value Computation in Ontology-Mediated Query Answering
Summary
This paper explores the application of the drastic Shapley value in ontology-mediated query answering, presenting a complexity analysis that reveals tractable and #P-hard cases.
Why It Matters
Understanding the complexity of Shapley value computation in ontology-mediated queries is crucial for advancing database query evaluation techniques. This research bridges concepts from cooperative game theory and artificial intelligence, offering insights that can enhance query optimization and knowledge representation.
Key Takeaways
- The drastic Shapley value can be applied to ontology-mediated query answering (OMQA).
- The paper establishes a dichotomy in the complexity of the Shapley value computation problem, indicating both tractable and #P-hard cases.
- Connections between Shapley value computation and probabilistic query evaluation are explored, enhancing understanding of OMQA.
- Results can inform future research on query optimization and database management.
- The findings have implications for both theoretical and practical applications in artificial intelligence.
Computer Science > Artificial Intelligence arXiv:2407.20058 (cs) [Submitted on 29 Jul 2024 (v1), last revised 24 Feb 2026 (this version, v3)] Title:Shapley Value Computation in Ontology-Mediated Query Answering Authors:Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade View a PDF of the paper titled Shapley Value Computation in Ontology-Mediated Query Answering, by Meghyn Bienvenu and 2 other authors View PDF Abstract:The Shapley value was originally introduced in cooperative game theory as a wealth distribution mechanism. It has since found use in knowledge representation and databases for the purpose of assigning scores to formulas and database tuples based upon their contribution to obtaining a query result or inconsistency. The application of the Shapley value outside of its original setting relies upon defining a numeric wealth function that captures the phenomenon of interest. In the case of database queries, recent work has focused on the so-called drastic Shapley value, obtained by translating a Boolean query into a 0/1 function based upon whether the query is satisfied or not. The present paper explores the use of the drastic Shapley value in the context of ontology-mediated query answering (OMQA). We present a detailed complexity analysis of the drastic Shapley value computation (SVC$^{dr}$) problem in the OMQA setting. In particular, we establish a dichotomy result that shows that for every ontology-mediated query (T,q) composed of an ontology T formulated in th...