Tractable Responsibility Measures for Ontology-Mediated Query Answering
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade · 2025
Read Tractable Responsibility Measures for Ontology-Mediated Query Answering by Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23191.txt.
Description
When a database plus background knowledge answers a question, responsibility scores say how much each fact contributed. Meghyn Bienvenu, Diego Figueira and Pierre Lafourcade study how hard those scores are to compute in this knowledge-backed setting. They focus on new Shapley-inspired scores, built as weighted sums over the smallest fact sets that still yield the answer. Building on database results, they show the scores stay computable in reasonable time for queries rewritable as simple database queries.
The picture flips when the knowledge can express reachability. In the harder combined view, the problem is already intractable for simple questions when the language allows joining facts. The same holds for unions of well-behaved joined questions, even without any background knowledge. On the bright side, for common lightweight languages they carve out neatly structured question classes where the scores stay efficiently computable.
Catalog record
| CREATOR | Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23191