Document Open Access Logo

The Shapley Value of Tuples in Query Answering

Authors Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, Moshe Sebag

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.20.pdf
  • Filesize: 0.59 MB
  • 19 pages

Document Identifiers

Author Details

Ester Livshits
  • Technion, Haifa, Israel
Leopoldo Bertossi
  • Univ. Adolfo Ibañez, Santiago, Chile
  • RelationalAI Inc., Toronto, Canada
Benny Kimelfeld
  • Technion, Haifa, Israel
Moshe Sebag
  • Technion, Haifa, Israel

Funding

The work of Ester Livshits, Benny Kimelfeld and Moshe Sebag was supported by the Israel Science Foundation (ISF), grants 1295/15 and 768/19, and the Deutsche Forschungsgemeinschaft (DFG) project 412400621 (DIP program). The work of Ester Livshits was also supported by the Technion Hiroshi Fujiwara Cyber Security Research Center and the Israel Cyber Bureau.

Cite AsGet BibTex

Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. The Shapley Value of Tuples in Query Answering. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICDT.2020.20

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data provenance
Keywords
  • Shapley value
  • query answering
  • conjunctive queries
  • aggregate queries

Metrics

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

Related Versions

Supplementary Materials

References

  1. Robert J Aumann and Roger B Myerson. Endogenous formation of links between players and of coalitions: An application of the Shapley value. In Networks and Groups, pages 207-220. Springer, 2003. Google Scholar
  2. Haris Aziz and Bart de Keijzer. Shapley meets Shapley. In STACS, pages 99-111, 2014. Google Scholar
  3. Roland Bacher. Determinants of matrices related to the Pascal triangle. Journal de Théorie des Nombres de Bordeaux, 14, January 2002. Google Scholar
  4. Leopoldo E. Bertossi and Babak Salimi. Causes for query answers from databases: Datalog abduction, view-updates, and integrity constraints. Int. J. Approx. Reasoning, 90:226-252, 2017. Google Scholar
  5. Leopoldo E. Bertossi and Babak Salimi. From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back. Theory Comput. Syst., 61(1):191-232, 2017. Google Scholar
  6. Sara Cohen, Werner Nutt, and Yehoshua Sagiv. Deciding equivalences among conjunctive aggregate queries. J. ACM, 54(2):5, 2007. Google Scholar
  7. Vincent Conitzer and Tuomas Sandholm. Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-issue Domains. In AAAI, pages 219-225. AAAI Press, 2004. Google Scholar
  8. Nilesh N. Dalvi, Christopher Ré, and Dan Suciu. Probabilistic databases: diamonds in the dirt. Commun. ACM, 52(7):86-94, 2009. Google Scholar
  9. Nilesh N. Dalvi and Dan Suciu. Efficient Query Evaluation on Probabilistic Databases. In VLDB, pages 864-875. Morgan Kaufmann, 2004. Google Scholar
  10. Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. J. ACM, 59(6):30:1-30:87, 2012. Google Scholar
  11. Pradeep Dubey and Lloyd S. Shapley. Mathematical Properties of the Banzhaf Power Index. Mathematics of Operations Research, 4(2):99-131, 1979. Google Scholar
  12. John Grant and Anthony Hunter. Measuring inconsistency in knowledgebases. J. Intell. Inf. Syst., 27(2):159-184, 2006. Google Scholar
  13. Gianluigi Greco, Francesco Lupia, and Francesco Scarcello. Structural Tractability of Shapley and Banzhaf Values in Allocation Games. In IJCAI, pages 547-553, 2015. Google Scholar
  14. Faruk Gul. Bargaining foundations of Shapley value. Econometrica: Journal of the Econometric Society, pages 81-95, 1989. Google Scholar
  15. Joseph Y. Halpern. Actual Causality. The MIT Press, 2016. Google Scholar
  16. Joseph Y. Halpern and Judea Pearl. Causes and Explanations: A Structural-Model Approach: Part 1: Causes. In UAI, pages 194-202, 2001. 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. Werner Kirsch and Jessica Langner. Power indices and minimal winning coalitions. Social Choice and Welfare, 34(1):33-46, January 2010. Google Scholar
  19. Dennis Leech. Power indices and probabilistic voting assumptions. Public Choice, 66(3):293-299, September 1990. Google Scholar
  20. 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
  21. Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. The Shapley Value of Tuples in Query Answering. CoRR, abs/1904.08679, 2019. Google Scholar
  22. 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
  23. Alexandra Meliou, Wolfgang Gatterbauer, Joseph Y. Halpern, Christoph Koch, Katherine F. Moore, and Dan Suciu. Causality in Databases. IEEE Data Eng. Bull., 33(3):59-67, 2010. Google Scholar
  24. Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, and Dan Suciu. The Complexity of Causality and Responsibility for Query Answers and non-Answers. PVLDB, 4(1):34-45, 2010. Google Scholar
  25. Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, and Dan Suciu. WHY so? or WHY no? functional causality for explaining query answers. In MUD, volume WP10-04 of CTIT Workshop Proceedings Series, pages 3-17. CTIT, 2010. Google Scholar
  26. 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
  27. 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
  28. Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2009. Google Scholar
  29. 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
  30. Alvin E Roth. The Shapley value: essays in honor of Lloyd S. Shapley. Cambridge University Press, 1988. Google Scholar
  31. Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck. Quantifying Causal Effects on Query Answering in Databases. In TAPP, 2016. Google Scholar
  32. Lloyd Shapley and Martin Shubik. A Method for Evaluating the Distribution of Power in a Committee System. American Political Science Review, 48(03):787-792, 1954. Google Scholar
  33. 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
  34. Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. Google Scholar
  35. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. Google Scholar
  36. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact