# The Shapley Value of Inconsistency Measures for Functional Dependencies

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2020.

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

- [OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport](https://mlsanity.com/paper/2403.02372/) (2024)
- [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)
- [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)
- [Data Obsolescence Detection in the Light of Newly Acquired Valid Observations](https://mlsanity.com/paper/2101.07067/) (2021)
- [Stress-Testing Causal Claims via Cardinality Repairs](https://mlsanity.com/paper/2512.02491/) (2025)

## Abstract (arXiv)

Quantifying the inconsistency of a database is motivated by various goals including reliability estimation for new datasets and progress indication in data cleaning. Another goal is to attribute to individual tuples a level of responsibility to the overall inconsistency, and thereby prioritize tuples in the explanation or inspection of dirt. Therefore, inconsistency quantification and attribution have been a subject of much research in Knowledge Representation and, more recently, in Databases. As in many other fields, a conventional responsibility sharing mechanism is the Shapley value from cooperative game theory. In this paper, we carry out a systematic investigation of the complexity of the Shapley value in common inconsistency measures for functional-dependency (FD) violations. For several measures we establish a full classification of the FD sets into tractable and intractable classes with respect to Shapley-value computation. We also study the complexity of approximation in intractable cases.