# The Shapley Value of Tuples in Query Answering

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2019.

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

- [Counterfactuals and Causability in Explainable Artificial Intelligence: Theory, Algorithms, and Applications](https://mlsanity.com/paper/2103.04244/) (2021)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases](https://mlsanity.com/paper/2401.06493/) (2024)
- [The Thousand Faces of Explainable AI Along the Machine Learning Life Cycle: Industrial Reality and Current State of Research](https://mlsanity.com/paper/2310.07882/) (2023)
- [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)
- [From Database Repairs to Causality in Databases and Beyond](https://mlsanity.com/paper/2306.09374/) (2023)
- [From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm](https://mlsanity.com/paper/2511.09376/) (2025)
- [Score-Based Explanations in Data Management and Machine Learning: An Answer-Set Programming Approach to Counterfactual Analysis](https://mlsanity.com/paper/2106.10562/) (2021)
- [Attribution-Scores and Causal Counterfactuals as Explanations in Artificial Intelligence](https://mlsanity.com/paper/2303.02829/) (2023)
- [Attribution-Scores in Data Management and Explainable Machine Learning](https://mlsanity.com/paper/2308.00184/) (2023)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Data Obsolescence Detection in the Light of Newly Acquired Valid Observations](https://mlsanity.com/paper/2101.07067/) (2021)
- [The Causal-Effect Score in Data Management](https://mlsanity.com/paper/2502.02495/) (2025)
- [Causality-Based Scores Alignment in Explainable Data Management](https://mlsanity.com/paper/2503.14469/) (2025)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [Database Views as Explanations for Relational Deep Learning](https://mlsanity.com/paper/2509.09482/) (2025)
- [InfluenceNet: AI Models for Banzhaf and Shapley Value Prediction](https://mlsanity.com/paper/2503.08381/) (2025)
- [CQD-SHAP: Explainable Complex Query Answering via Shapley Values](https://mlsanity.com/paper/2510.15623/) (2025)
- [WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees](https://mlsanity.com/paper/2604.10569/) (2026)
- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)
- [RelShap: Relationally Consistent Shapley Explanations](https://mlsanity.com/paper/2608.11508/) (2026)

## Abstract (arXiv)

We investigate the application of the Shapley value to quantifying the contribution of a tuple to a query answer. The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. We study this measure in the context of conjunctive and aggregate queries by defining corresponding coalition games. We provide algorithmic and complexity-theoretic results on the computation of Shapley-based contributions to query answers; and for the hard cases we present approximation algorithms.