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

Shapley values offer a rigorous framework for explaining AI decisions: The paper demonstrates that Shapley values—a game theory concept—can be adapted to explain how individual data facts contribute to database query results, providing a mathematically principled approach to AI explainability beyond simpler attribution methods.

Computing explanations is computationally challenging but solvable in specific cases: The research shows that calculating expected Shapley values is generally difficult, but becomes tractable when data relationships are represented as "decomposable circuits," enabling practical implementation in real database systems like ProvSQL.

Probabilistic reasoning requires new explanation approaches: By extending Shapley values to probabilistic databases (where data has uncertainty), this work addresses a real-world challenge: explaining AI decisions when the underlying data itself is uncertain or incomplete, which is common in healthcare, finance, and scientific applications.

Theoretical advances enable practical tools: The paper bridges abstract computer science theory with implementation, demonstrating through ProvSQL experiments that the proposed algorithm works efficiently on standard benchmarks, suggesting these explanation methods could be deployed in actual database systems used by organizations.

Standardized metrics improve AI accountability: By adapting established game-theoretic measures (Shapley and Banzhaf values) rather than inventing new ones, the work promotes consistency in how organizations measure and communicate the importance of data in automated decision-making systems.