# Tractable Responsibility Measures for Ontology-Mediated Query Answering

arXiv: https://arxiv.org/abs/2507.23191 · HTML: https://mlsanity.com/paper/2507.23191/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 31 Jul 2025.

## Builds on (most cited first, 13 of 13)

- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [When is Shapley Value Computation a Matter of Counting?](https://mlsanity.com/paper/2312.14529/) (2023)
- [From Shapley Value to Model Counting and Back](https://mlsanity.com/paper/2306.14211/) (2023)
- [The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries](https://mlsanity.com/paper/1912.12610/) (2019)
- [Explaining Ontology-Mediated Query Answers using Proofs over Universal Models (Technical Report)](https://mlsanity.com/paper/2208.14381/) (2022)
- [Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases](https://mlsanity.com/paper/2401.06493/) (2024)
- [The Complexity of the Shapley Value for Regular Path Queries](https://mlsanity.com/paper/2212.07720/) (2022)
- [Shapley Value Computation in Ontology-Mediated Query Answering](https://mlsanity.com/paper/2407.20058/) (2024)
- [Shapley Revisited: Tractable Responsibility Measures for Query Answers](https://mlsanity.com/paper/2503.22358/) (2025)
- [First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics](https://mlsanity.com/paper/2011.09836/) (2020)
- [Computing FO-Rewritings in EL in Practice: from Atomic to Conjunctive Queries](https://mlsanity.com/paper/1804.06907/) (2018)

## Built on by (most cited first, 1 of 1)

- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)

## Abstract (arXiv)

Recent work on quantitative approaches to explaining query answers employs responsibility measures to assign scores to facts in order to quantify their respective contributions to obtaining a given answer. In this paper, we study the complexity of computing such responsibility scores in the setting of ontology-mediated query answering, focusing on a very recently introduced family of Shapley-value-based responsibility measures defined in terms of weighted sums of minimal supports (WSMS). By exploiting results from the database setting, we can show that such measures enjoy polynomial data complexity for classes of ontology-mediated queries that are first-order-rewritable, whereas the problem becomes "shP"-hard when the ontology language can encode reachability queries (via axioms like exists R. A sqsubseteq A). To better understand the tractability frontier, we next explore the combined complexity of WSMS computation. We prove that intractability applies already to atomic queries if the ontology language supports conjunction, as well as to unions of `well-behaved' conjunctive queries, even in the absence of an ontology. By contrast, our study yields positive results for common DL-Lite dialects: by means of careful analysis, we identify classes of structurally restricted conjunctive queries (which intuitively disallow undesirable interactions between query atoms) that admit tractable WSMS computation.