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

arXiv: https://arxiv.org/abs/2401.06493 · HTML: https://mlsanity.com/paper/2401.06493/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 12 Jan 2024.

## Builds on (most cited first, 13 of 13)

- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [The Shapley Value in Database Management](https://mlsanity.com/paper/2401.06234/) (2024)
- [Connecting Knowledge Compilation Classes and Width Parameters](https://mlsanity.com/paper/1811.02944/) (2018)
- [When is Shapley Value Computation a Matter of Counting?](https://mlsanity.com/paper/2312.14529/) (2023)
- [From Shapley Value to Model Counting and Back](https://mlsanity.com/paper/2306.14211/) (2023)
- [The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries](https://mlsanity.com/paper/1912.12610/) (2019)
- [Banzhaf Values for Facts in Query Answering](https://mlsanity.com/paper/2308.05588/) (2023)
- [Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries](https://mlsanity.com/paper/2209.11177/) (2022)
- [The Prediction value](https://mlsanity.com/paper/1311.5728/) (2013)
- [Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases](https://mlsanity.com/paper/1912.11864/) (2019)

## Built on by (most cited first, 6 of 6)

- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Shapley Revisited: Tractable Responsibility Measures for Query Answers](https://mlsanity.com/paper/2503.22358/) (2025)
- [The Causal-Effect Score in Data Management](https://mlsanity.com/paper/2502.02495/) (2025)
- [Causality-Based Scores Alignment in Explainable Data Management](https://mlsanity.com/paper/2503.14469/) (2025)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [InfluenceNet: AI Models for Banzhaf and Shapley Value Prediction](https://mlsanity.com/paper/2503.08381/) (2025)

## Abstract (arXiv)

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.