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
:cite:`DBLP:journals/pacmmod/KarmakarMSB24`, giving *expected*
Shapley/Banzhaf values: each input token contributes according
to its probability (set with :sqlfunc:`set_prob`, see :doc:`probabilities`).
When no probabilities are set they default to 1, which recovers the
standard deterministic Shapley/Banzhaf values.

Computing Shapley Values
-------------------------

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

.. code-block:: postgresql

    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 :sqlfunc:`shapley` once per variable), use
:sqlfunc:`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:

.. code-block:: postgresql

    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
-------------------------

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

.. code-block:: postgresql

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

Computation Notes
------------------

Shapley-value computation is generally :math:`\#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.