Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Computing the Shapley Value of Tuples in Conjunctive Queries with Negation
event speaker icon
Alon Reshef, M.Sc. Thesis Seminar
event date icon
Sunday, 30.8.2020, 11:00
event location icon
Zoom Lecture:
event speaker icon
Advisor:  Prof. Benny Kimelefeld
The Shapley value is a conventional and well-studied function for determining the contribution of a player to the coalition in a cooperative game. Among its applications in a plethora of domains, it has recently been proposed to use the Shapley value for quantifying the contribution of a tuple to the result of a database query. In particular, we have a thorough understanding of the tractability frontier for the class of Conjunctive Queries (CQs) and aggregate functions over CQs. It has also been established that a tractable (randomized) multiplicative approximation exists for every union of CQs. Nevertheless, all of these results are based on the monotonicity of CQs. In this work, we investigate the implication of negation on the complexity of Shapley computation, in both the exact and approximate senses. We generalize a known dichotomy to accountfor negated atoms. We also show that negation fundamentally changes the complexity of approximation. We do so by drawing a connection to the problem of deciding whether a tuple is “relevant” to a query, and by analyzing its complexity.
[Back to the index of events]