Shapley and Banzhaf Values

ProvSQL computes Shapley values and Banzhaf values – game-theoretic measures from cooperative game theory that quantify the individual contribution of each input tuple to a query result.

Background

Given a Boolean query result whose truth depends on a set of input tuples, the Shapley value of an input tuple t is the average marginal contribution of t over all orderings of the input tuples.

The Banzhaf value is a simpler variant: the average marginal contribution over all subsets of the other inputs (not weighted by ordering).

Both measures are always computed under the probabilistic model [Karmakar et al., 2024], giving expected Shapley/Banzhaf values: each input token contributes according to its probability (set with set_prob, see Probabilities). When no probabilities are set they default to 1, which recovers the standard deterministic Shapley/Banzhaf values.

Computing Shapley Values

shapley takes the provenance token of the query result and the token of the input tuple whose contribution to measure:

SELECT person,
       shapley(provenance(), m.provenance) AS sv
FROM suspects, witness_mapping m;

To compute Shapley values for all input variables at once (more efficient than calling shapley once per variable), use shapley_all_vars. Because a set-returning function cannot appear in the FROM clause of a query that ProvSQL rewrites, materialise the result token first and call it from an untracked query:

CREATE TEMP TABLE result_token AS
  SELECT person, provenance() AS token FROM suspects;
-- the materialised table inherits provenance tracking; drop it
-- so the query below is not itself rewritten
SELECT remove_provenance('result_token');

SELECT person, m.value AS witness, s.value AS sv
FROM result_token,
     shapley_all_vars(token) s,
     witness_mapping m
WHERE m.provenance = s.variable;

Computing Banzhaf Values

banzhaf and banzhaf_all_vars have the same calling conventions as their Shapley counterparts:

SELECT person,
       banzhaf(provenance(), m.provenance) AS bv
FROM suspects, witness_mapping m;

Computation Notes

Shapley-value computation is generally $\#P$ -hard. ProvSQL compiles the provenance circuit to a d-DNNF and evaluates it efficiently. The optional third argument selects the d-DNNF construction ('tree-decomposition', 'interpret-as-dd', 'compilation'); with 'compilation', the fourth argument names the external compiler, e.g. shapley(token, var, 'compilation', 'd4'). When the third argument is empty, 'default', or 'auto', the cheapest route is selected automatically.

Choosing Between Shapley and Banzhaf

Shapley values satisfy a set of axioms (efficiency, symmetry, dummy, additivity) that uniquely characterise them as a fair measure of individual contribution.
Banzhaf values are faster to compute and satisfy a slightly different set of axioms; they are appropriate when the efficiency guarantee is not required.