From Shapley Value to Model Counting and Back

Understand

In this paper we investigate the problem of quantifying the contribution of each variable to the satisfying assignments of a Boolean function based on the Shapley value.

• Our main result is a polynomial-time equivalence between computing Shapley values and model counting for any class of Boolean functions that are closed under substitutions of variables with disjunctions of fresh variables.
• This result settles an open problem raised in prior work, which sought to connect the Shapley value computation to probabilistic query evaluation.
• We show two applications of our result.