Document Open Access Logo

The Shapley Value of Inconsistency Measures for Functional Dependencies

Authors Ester Livshits, Benny Kimelfeld

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICDT.2021.15.pdf
  • Filesize: 0.76 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Incomplete, inconsistent, and uncertain databases
  • Information systems → Data cleaning
Keywords
  • Shapley value
  • inconsistent databases
  • functional dependencies
  • database repairs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Ester Livshits and Benny Kimelfeld. The Shapley Value of Inconsistency Measures for Functional Dependencies. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICDT.2021.15

Author Details

Ester Livshits
  • Technion - Israel Institute of Technology, Haifa, Israel
Benny Kimelfeld
  • Technion - Israel Institute of Technology, Haifa, Israel

Funding

This work was supported by the Israel Science Foundation (ISF), Grant 768/19, and the German Research Foundation (DFG) Project 412400621 (DIP program).

References

  1. Haris Aziz and Bart de Keijzer. Shapley meets Shapley. In STACS, volume 25 of LIPIcs, pages 99-111. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  2. Leopoldo E. Bertossi. Measuring and computing database inconsistency via repairs. In SUM, volume 11142 of Lecture Notes in Computer Science, pages 368-372. Springer, 2018. Google Scholar
  3. Leopoldo E. Bertossi. Repair-based degrees of database inconsistency. In LPNMR, volume 11481 of Lecture Notes in Computer Science, pages 195-209. Springer, 2019. Google Scholar
  4. Leopoldo E. Bertossi and Floris Geerts. Data quality and explainable AI. J. Data and Information Quality, 12(2):11:1-11:9, 2020. Google Scholar
  5. Omar Besbes, Antoine Désir, Vineet Goyal, Garud Iyengar, and Raghav Singal. Shapley meets uniform: An axiomatic framework for attribution in online advertising. In WWW, pages 1713-1723. ACM, 2019. Google Scholar
  6. Laurence Cholvy, Laurent Perrussel, William Raynaut, and Jean - Marc Th 'e venin. Towards consistency-based reliability assessment. In AAMAS, pages 1643-1644. ACM, 2015. Google Scholar
  7. Pradeep Dubey and Lloyd S. Shapley. Mathematical properties of the banzhaf power index. Mathematics of Operations Research, 4(2):99-131, 1979. Google Scholar
  8. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  9. John Grant and Anthony Hunter. Measuring inconsistency in knowledgebases. J. Intell. Inf. Syst., 27(2):159-184, 2006. Google Scholar
  10. John Grant and Anthony Hunter. Measuring consistency gain and information loss in stepwise inconsistency resolution. In ECSQARU, volume 6717, pages 362-373. Springer, 2011. Google Scholar
  11. John Grant and Anthony Hunter. Distance-based measures of inconsistency. In ECSQARU, volume 7958 of Lecture Notes in Computer Science, pages 230-241. Springer, 2013. Google Scholar
  12. John Grant and Anthony Hunter. Using Shapley inconsistency values for distributed information systems with uncertainty. In ECSQARU, volume 9161 of Lecture Notes in Computer Science, pages 235-245. Springer, 2015. Google Scholar
  13. John Grant and Anthony Hunter. Analysing inconsistent information using distance-based measures. Int. J. Approx. Reasoning, 89:3-26, 2017. URL: http://dx.doi.org/10.1016/j.ijar.2016.04.004.
  14. Faruk Gul. Bargaining foundations of Shapley value. Econometrica: Journal of the Econometric Society, pages 81-95, 1989. Google Scholar
  15. Anthony Hunter and Sébastien Konieczny. Shapley inconsistency values. In KR, pages 249-259. AAAI Press, 2006. Google Scholar
  16. Anthony Hunter and Sébastien Konieczny. Measuring inconsistency through minimal inconsistent sets. In KR, pages 358-366. AAAI Press, 2008. Google Scholar
  17. Anthony Hunter and Sébastien Konieczny. On the measure of conflicts: Shapley inconsistency values. Artif. Intell., 174(14):1007-1026, 2010. Google Scholar
  18. Yifan Jing and Akbar Rafiey. Counting maximal near perfect matchings in quasirandom and dense graphs. CoRR, abs/1807.04803, 2018. Google Scholar
  19. Kevin M. Knight. Two information measures for inconsistent sets. Journal of Logic, Language and Information, 12(2):227-248, 2003. Google Scholar
  20. Sébastien Konieczny, Jérôme Lang, and Pierre Marquis. Quantifying information and contradiction in propositional logic through test actions. In IJCAI, pages 106-111. Morgan Kaufmann, 2003. Google Scholar
  21. Christophe Labreuche and Simon Fossier. Explaining multi-criteria decision aiding models with an extended Shapley value. In IJCAI, pages 331-339. ijcai.org, 2018. Google Scholar
  22. Zhenliang Liao, Xiaolong Zhu, and Jiaorong Shi. Case study on initial allocation of shanghai carbon emission trading based on Shapley value. Journal of Cleaner Production, 103:338-344, 2015. Google Scholar
  23. Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. The Shapley value of tuples in query answering. In ICDT, volume 155 of LIPIcs, pages 20: 1-20: 19. Schloss Dagstuhl, 2020. Google Scholar
  24. Ester Livshits, Ihab F. Ilyas, Benny Kimelfeld, and Sudeepa Roy. Principles of progress indicators for database repairing. CoRR, abs/1904.06492, 2019. Google Scholar
  25. Ester Livshits and Benny Kimelfeld. Counting and enumerating (preferred) database repairs. In PODS, pages 289-301. ACM, 2017. Google Scholar
  26. Ester Livshits and Benny Kimelfeld. The Shapley value of inconsistency measures for functional dependencies. CoRR, abs/2009.13819, 2020. Google Scholar
  27. Ester Livshits, Benny Kimelfeld, and Sudeepa Roy. Computing optimal repairs for functional dependencies. ACM Trans. Database Syst., 45(1):4: 1-4: 46, 2020. Google Scholar
  28. Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NIPS, pages 4765-4774, 2017. Google Scholar
  29. Richard TB Ma, Dah Ming Chiu, John Lui, Vishal Misra, and Dan Rubenstein. Internet economics: The use of Shapley value for isp settlement. IEEE/ACM Transactions on Networking (TON), 18(3):775-787, 2010. Google Scholar
  30. Kedian Mu, Weiru Liu, and Zhi Jin. Measuring the blame of each formula for inconsistent prioritized knowledge bases. Journal of Logic and Computation, 22(3):481-516, February 2011. URL: http://arxiv.org/abs/https://academic.oup.com/logcom/article-pdf/22/3/481/3177718/exr002.pdf.
  31. Ramasuri Narayanam and Yadati Narahari. A Shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering, 8(1):130-147, 2011. Google Scholar
  32. Tatiana Nenova. The value of corporate voting rights and control: A cross-country analysis. Journal of financial economics, 68(3):325-351, 2003. Google Scholar
  33. Leon Petrosjan and Georges Zaccour. Time-consistent Shapley value allocation of pollution cost reduction. Journal of economic dynamics and control, 27(3):381-398, 2003. Google Scholar
  34. Alon Reshef, Benny Kimelfeld, and Ester Livshits. The impact of negation on the complexity of the Shapley value in conjunctive queries. In PODS, pages 285-297. ACM, 2020. Google Scholar
  35. Lloyd S Shapley. A value for n-person games. In Harold W. Kuhn and Albert W. Tucker, editors, Contributions to the Theory of Games II, pages 307-317. Princeton University Press, Princeton, 1953. Google Scholar
  36. Matthias Thimm. Measuring inconsistency in probabilistic knowledge bases. In UAI, pages 530-537. AUAI Press, 2009. Google Scholar
  37. Matthias Thimm. On the compliance of rationality postulates for inconsistency measures: A more or less complete picture. KI, 31(1):31-39, 2017. Google Scholar
  38. L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. URL: http://dx.doi.org/10.1016/0304-3975(79)90044-6.
  39. Bruno Yun, Srdjan Vesic, Madalina Croitoru, and Pierre Bisquert. Inconsistency measures for repair semantics in OBDA. In IJCAI, pages 1977-1983. ijcai.org, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact