{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:41:02Z","timestamp":1787244062914,"version":"build-2736575974"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:00:00Z","timestamp":1630540800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We investigate the application of the Shapley value to quantifying the\ncontribution of a tuple to a query answer. The Shapley value is a widely known\nnumerical measure in cooperative game theory and in many applications of game\ntheory for assessing the contribution of a player to a coalition game. It has\nbeen established already in the 1950s, and is theoretically justified by being\nthe very single wealth-distribution measure that satisfies some natural axioms.\nWhile this value has been investigated in several areas, it received little\nattention in data management. We study this measure in the context of\nconjunctive and aggregate queries by defining corresponding coalition games. We\nprovide algorithmic and complexity-theoretic results on the computation of\nShapley-based contributions to query answers; and for the hard cases we present\napproximation algorithms.<\/jats:p>","DOI":"10.46298\/lmcs-17(3:22)2021","type":"journal-article","created":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T09:10:10Z","timestamp":1630573810000},"source":"Crossref","is-referenced-by-count":20,"title":["The Shapley Value of Tuples in Query Answering"],"prefix":"10.46298","volume":"Volume 17, Issue 3","author":[{"given":"Ester","family":"Livshits","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leopoldo","family":"Bertossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Sebag","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2021,9,2]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/8437\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/8437\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T16:18:45Z","timestamp":1687277925000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,2]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-17(3:22)2021","relation":{"has-preprint":[{"id-type":"arxiv","id":"1904.08679v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1904.08679v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1904.08679","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1904.08679","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,2]]},"article-number":"6942"}}