# Shapley Revisited: Tractable Responsibility Measures for Query Answers

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 51 references that are in the map.
- First posted on arXiv 28 Mar 2025.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [Explainability is NOT a Game](https://mlsanity.com/paper/2307.07514/) (2023)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [Quantifying Causal Effects on Query Answering in Databases](https://mlsanity.com/paper/1603.02705/) (2016)
- [The Shapley Value of Inconsistency Measures for Functional Dependencies](https://mlsanity.com/paper/2009.13819/) (2020)
- [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)
- [Banzhaf Values for Facts in Query Answering](https://mlsanity.com/paper/2308.05588/) (2023)
- [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)

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

- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [Sufficient Explanations in Databases and their Connections to Database Repairs](https://mlsanity.com/paper/2511.15623/) (2025)
- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)
- [Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations](https://mlsanity.com/paper/2605.08688/) (2026)

## Abstract (arXiv)

The Shapley value, originating from cooperative game theory, has been employed to define responsibility measures that quantify the contributions of database facts to obtaining a given query answer. For non-numeric queries, this is done by considering a cooperative game whose players are the facts and whose wealth function assigns 1 or 0 to each subset of the database, depending on whether the query answer holds in the given subset. While conceptually simple, this approach suffers from a notable drawback: the problem of computing such Shapley values is #P-hard in data complexity, even for simple conjunctive queries. This motivates us to revisit the question of what constitutes a reasonable responsibility measure and to introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS) -- which satisfy intuitive properties. Interestingly, while the definition of WSMSs is simple and bears no obvious resemblance to the Shapley value formula, we prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game. Moreover, WSMS measures enjoy tractable data complexity for a large class of queries, including all unions of conjunctive queries. We further explore the combined complexity of WSMS computation and establish (in)tractability results for various subclasses of conjunctive queries.