Fetching the paper…

Reading the bibliography…

2023

When is Shapley Value Computation a Matter of Counting?

Bienvenu, Meghyn, Figueira, Diego, Lafourcade, Pierre

Original
PDF
Post on X

Understand

The Shapley value provides a natural means of quantifying the contributions of facts to database query answers.

In this work, we seek to broaden our understanding of Shapley value computation (SVC) in the database setting by revealing how it relates to Fixed-size Generalized Model Counting (FGMC), which is the problem of computing the number of sub-databases of a given size and containing a given set of assumed facts that satisfy a fixed query.
Our focus will be on explaining the difficulty of SVC via FGMC, and to this end, we identify general conditions on queries which enable reductions from FGMC to SVC.
As a byproduct, we not only obtain alternative explanations for most existing results on SVC, but also new complexity results.

When is Shapley Value Computation a Matter of Counting? · Around

Built on

A Value for N-Person Games
Lloyd S Shapley. 1953 · 1953
Earlier work this paper cites.
Determinants of Matrices Related to the Pascal Triangle
Roland Bacher. 2002 · 2002
Earlier work this paper cites.
Efficient Query Evaluation on Probabilistic Databases. In
Nilesh N. Dalvi and Dan Suciu. 2004 · 2004
Earlier work this paper cites.
The dichotomy of probabilistic inference for unions of conjunctive queries
Nilesh N. Dalvi and Dan Suciu. 2012 · 2012
Earlier work this paper cites.
Dichotomies for Queries with Negation in Probabilistic Databases
Robert Fink and Dan Olteanu. 2016 · 2016
Earlier work this paper cites.

Similar

Boundedness of Conjunctive Regular Path Queries. In
Pablo Barceló, Diego Figueira, and Miguel Romero. 2019 · 2019
Cited alongside, same era.
The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries. In
Alon Reshef, Benny Kimelfeld, and Ester Livshits. 2020 · 2020
Cited alongside, same era.
A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries. In
Batya Kenig and Dan Suciu. 2021 · 2021
Cited alongside, same era.
The Shapley Value of Tuples in Query Answering
Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. 2021 · 2021
Cited alongside, same era.

Then

Computing the Shapley Value of Facts in Query Answering. In
Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet. 2022 · 2022
Later among the works it cites.
Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries. In
Antoine Amarilli. 2023 · 2023
Closest in time.
The Complexity of the Shapley Value for Regular Path Queries. In
Majd Khalil and Benny Kimelfeld. 2023 · 2023
Closest in time.
From Shapley Value to Model Counting and Back. In
Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024 · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…