Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases

Pratik Karmakar, Mikaël Monet, Pierre Senellart, Stéphane Bressan

Abstract

Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark.

Introduction

In the fields of Explainable AI (XAI) and data management, identifying the specific inputs responsible for a particular output is a critical task. Game theory offers a robust framework for this through the Shapley value, which fairly distributes "credit" among players (or database facts) for a given outcome. While extensively studied in deterministic contexts, real-world data is frequently uncertain. This uncertainty is often modeled using Probabilistic Databases, where each fact exists with a certain probability.

The primary challenge addressed in this research is the computation of these scores when the "players" themselves are probabilistic. The authors introduce the concept of the Expected Score—the average Shapley or Banzhaf value across all possible "worlds" of a probabilistic database.

Defining the Expected Score

The core objective is to compute the expected value of a contribution score $c$ (like Shapley or Banzhaf) for a Boolean function $\phi$ over a set of variables $V$, where each variable $x \in V$ has an associated probability $p_x$.

The formal definition of the Expected Score problem ($EScore_c(\mathcal{F})$).

Theoretical Framework and Reductions

A major theoretical contribution of this paper is the proof that computing expected Shapley/Banzhaf values is interreducible with computing the Expected Value (EV) of a Boolean function. This implies that the tractability landscape for both problems is identical: if the probability of a query being true can be calculated efficiently, so can the expected contribution of its constituent facts.

To establish these reductions, the authors employed polynomial interpolation techniques. By using carefully selected probability values, they were able to "extract" the necessary components of the Shapley score from the general probability function of the query.

A comparison of deterministic Shapley scores versus Expected Shapley scores ($EScore$) for a sample Boolean function, illustrating how variable probabilities ($p_x$) influence the final contribution score.

Algorithms for Tractable Computation

For practical applications, the research focuses on deterministic decomposable circuits (d-D circuits). These are a form of knowledge compilation that allows complex Boolean logic to be represented in a way that facilitates efficient processing. The authors designed a bottom-up induction algorithm that traverses these circuits to compute scores in polynomial time relative to the circuit size.

Interestingly, the complexity varies between different power indices. While both are tractable on d-D circuits, Banzhaf values can be computed in linear time, whereas Shapley values require a more complex implementation with quadratic-to-quintic complexity.

Experimental Evaluation

The proposed algorithms were implemented within ProvSQL, an open-source PostgreSQL extension for handling database provenance. The system was evaluated using the TPC-H 1 GB benchmark, focusing on 8 standard queries modified to isolate core Boolean logic.

Key findings from the experiments include:

  • Practical Feasibility: For most TPC-H queries, the combined time for provenance tracking and score computation was only a few seconds.
  • Scalability: The system handled complex queries effectively. For instance, Query 5, involving over 1,000 gates, was processed in approximately 41 seconds.
  • Efficiency: For many simpler queries, the overhead was negligible, often taking less than a second.

Conclusion

This work bridges the gap between game-theoretic importance measures and probabilistic data. By showing that the tractability of expected scores matches that of probabilistic query evaluation, the authors provide a clear roadmap for implementing explainability in uncertain databases. Future work will explore Fully Polynomial-Time Randomized Approximation Schemes (FPRAS) to handle "hard" queries (such as those with self-joins or complex negation) that cannot be efficiently compiled into small d-D circuits.

Summary updated

Abstract

Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark.
BibTeX
@inproceedings{karmakar2024expected,
  author = {Pratik Karmakar and Mikaël Monet and Pierre Senellart and Stéphane Bressan},
  title = {{Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases}},
  booktitle = {Proceedings of the ACM on Management of Data},
  year = {2024},
  doi = {10.1145/3651593},
}
Figure