Pratik Karmakar
email: pratik.karmakar@u.nus.edu

Mikaël Monet
email: mikael.monet@inria.fr

Pierre Senellart
email: pierre@senellart.com

Stéphane Bressan

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

Keywords: Shapley value, Banzhaf value, probabilistic databases, provenance, knowledge compilation, d-D circuits

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

The Shapley value is a popular notion from cooperative game theory, introduced by Lloyd Shapley [START_REF] Lloyd | A value for n-person games[END_REF]. Its idea is to "fairly" distribute the rewards of a game among the players. The Banzhaf power index [START_REF] Banzhaf | Weighted voting doesn't work: A mathematical analysis[END_REF], another power distribution index with slightly different weights also plays an important role in voting theory. These are two instances of power indices for coalitions, which also include the Johnston [START_REF] Johnston | National sovereignty and national power in European institutions[END_REF][START_REF] John | On the measurement of power: Some reactions to Laver[END_REF], Deegan-Packel [START_REF] Deegan | A new index of power for simple n-person games[END_REF], and Holler-Packel indices [START_REF] Manfred | Power, luck and the right index[END_REF], see [START_REF] Laruelle | On the choice of a power index[END_REF] for a survey. Shapley and Banzhaf values, in particular, have found recent applications in explainable machine learning [START_REF] Karczmarz | Improved feature importance computation for tree models based on the Banzhaf value[END_REF][START_REF] Van Den Broeck | On the tractability of SHAP explanations[END_REF] and valuation of data inputs in data management [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF][START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF].

In this work, we revisit the computation of such values (which we call Shapley-like values or scores) in a setting where data is uncertain. Our objective is then to investigate the tractability of expected Shapley-like value computations for Boolean functions, having in mind the potential application of computation of expected Shapley-like values of facts for a query over probabilistic databases. In particular, some results have been obtained in the literature that reduces the complexity of (non-probabilistic) Shapley-value computation to and from the computation of the model count of a Boolean function (or to the computation of the probability of a query in probabilistic databases) under some technical conditions [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF][START_REF] Kara | From Shapley Value to Model Counting and Back[END_REF]; we aim at understanding this connection better by investigating whether expected Shapley(-like) value computation, which combines the computation of a power index and a probabilistic setting, is harder than each of these aspects taken in isolation.

We provide the following contributions. First (in Section 2), we formally introduce the notion of Shapley-like scores and of the expected value of such scores on Boolean functions whose variables are assigned independent probabilities. In Section 3, we investigate the connection between the computation of expected Shapley-like scores and the computation of the expected value of a Boolean function. In particular, we show a very general result (Corollary 3.6) that expected Shapley value computation is interreducible in polynomial time to the expected value computation problem over any class of Boolean functions for which it is possible to compute its value over the empty set in polynomial time; we also obtain a similar result (Corollary 3.11) for the computation of expected Banzhaf values. We then assume in Section 4 that we have a tractable representation of a Boolean function as a decomposable and deterministic circuit; in this case, we show a concrete polynomial-time algorithm for Shapley-like score computation (Algorithm 1) and some simplifications thereof for specific settings. We then apply in Section 5 these results to the case of probabilistic databases, showing (Corollary 5.2) that expected Shapley value computation is interreducible in polynomial time to probabilistic query evaluation. In Section 6 we show through an experimental evaluation that the algorithms proposed in this paper are indeed feasible in practical scenarios. Before concluding the paper, we discuss related work in Section 7.

For space reason, most proofs are relegated to the appendix.

PRELIMINARIES

For 𝑛 ∈ N we write [𝑛] def = {0, . . . , 𝑛}. We denote by P the class of problems solvable in polynomial time. For a set 𝑉 , we denote by 2 𝑉 its powerset.

Boolean functions. A Boolean function over a finite set of variables 𝑉 is a mapping 𝜑 : 2 𝑉 → {0, 1}. To talk about the complexity of problems over a class of Boolean functions, one must first specify how the functions are specified as input. By a class of Boolean functions, we then mean a class of representations of Boolean functions; for instance, truth tables, decision trees, Boolean circuits, and so on, with any sensible encoding. In particular, we consider that the size of 𝑉 is always provided in unary as part of the input.

Let 𝜑 : 2 𝑉 → {0, 1} and 𝑥 ∈ 𝑉 . We denote by 𝜑 +𝑥 (resp., 𝜑 -𝑥 ) the Boolean function on 𝑉 \ {𝑥 } that maps 𝑍 ⊆ 𝑉 \ {𝑥 } to 𝜑 (𝑍 ∪ {𝑥 }) (resp., to 𝜑 (𝑍 )).

Expected value. For 𝑥 ∈ 𝑉 let 𝑝 𝑥 ∈ [0, 1] be a probability value.

For 𝑍 ⊆ 𝑉 ′ ⊆ 𝑉 , Π 𝑉 ′ (𝑍 ) def =

𝑥 ∈𝑍 𝑝 𝑥 × 𝑥 ∈𝑉 ′ \𝑍 (1 -𝑝 𝑥 ) is the probability of 𝑍 being drawn from 𝑉 ′ under the assumption that every 𝑥 ∈ 𝑉 ′ is chosen independently with probability 𝑝 𝑥 . Note that the 𝑝-values do not appear in the notation Π 𝑉 ′ (𝑍 ): this is to simplify notation. For 𝜑 : 2 𝑉 → {0, 1}, define then the expected value of 𝜑 as EV(𝜑) def = 𝑍 ⊆𝑉 Π 𝑉 (𝑍 )𝜑 (𝑍 ). Note that this is simply the probability of 𝜑 being true. We then define the corresponding problem for a class of Boolean functions F . 𝑘 -1 and 𝑐 Banzhaf (𝑘, ℓ) def = 1. Then Score 𝑐 Shapley (𝜑, 𝑉 , 𝑥) (Score 𝑐 Banzhaf (𝜑, 𝑉 , 𝑥)) is the usual Shapley (Banzhaf) value, with set of players 𝑉 and wealth function 𝜑. The Penrose-Banzhaf power [START_REF] Kirsch | Power indices and minimal winning coalitions[END_REF], a normalization of Banzhaf values, can also be defined by coefficients (𝑘, ℓ) ↦ → 2 𝑘 -1 .

For each fixed coefficient function 𝑐 and class of Boolean functions F , we define the corresponding computational problem. PROBLEM : Score 𝑐 (F ) INPUT :

A Boolean function 𝜑 ∈ F over variables 𝑉 , a variable 𝑥 ∈ 𝑉 OUTPUT : The quantity Score 𝑐 (𝜑, 𝑉 , 𝑥) Expected Shapley-like scores. We now introduce the probabilistic variant of Shapley-like scores, which is our main object of study. Definition 2.2. Let 𝑐 be a coefficient function, 𝜑 : 2 𝑉 → {0, 1} a Boolean function over variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 . Define the expected score of 𝑥 for 𝜑 as:

EScore 𝑐 (𝜑, 𝑥) def = ∑ 𝑍 ⊆𝑉 𝑥 ∈𝑍 (Π 𝑉 (𝑍 ) × Score 𝑐 (𝜑, 𝑍, 𝑥)) ,
where in Score 𝑐 (𝜑, 𝑍, 𝑥) we see 𝜑 as a function from 2 𝑍 to {0, 1}.

In words, this is the expected value of the corresponding score, when players are independently selected to be part of the cooperative game. Notice that subsets 𝑍 ⊆ 𝑉 not containing 𝑥 are not summed over: this is because in this case 𝑥 is not a player of the selected game and we thus declare its "contribution" to be null. This definition is also strongly motivated by its applications to probabilistic databases (cf. Section 5). We then define the corresponding computational problem, for a fixed 𝑐 and F :

PROBLEM : EScore 𝑐 (F ) (Expected Score) INPUT :
A Boolean function 𝜑 ∈ F over variables 𝑉 , probability values 𝑝 𝑦 for each 𝑦 ∈ 𝑉 , a variable 𝑥 ∈ 𝑉 OUTPUT : The quantity EScore 𝑐 (𝜑, 𝑥)

Reductions. For two computational problems 𝐴 and 𝐵, we write 𝐴 ⩽ P 𝐵 to assert the existence of a polynomial-time Turing reduction from 𝐴 to 𝐵, i.e., a reduction that is allowed to use 𝐵 as an oracle. We write 𝐴 ≡ P 𝐵 when 𝐴 ⩽ P 𝐵 and 𝐵 ⩽ P 𝐴, meaning that the problems are equivalent under such reductions. Using this notation we can state a first trivial fact: Fact 2.3. We have Score 𝑐 (F ) ⩽ P EScore 𝑐 (F ) for any coefficient function 𝑐 and class of Boolean functions F . This is simply because EScore 𝑐 (𝜑, 𝑥) = Score 𝑐 (𝜑, 𝑉 , 𝑥) when 𝑝 𝑦 = 1 for all 𝑦 ∈ 𝑉 , so that our probabilistic variants of such scores are proper generalizations of the non-probabilistic ones.

EQUIVALENCE WITH EXPECTED VALUES

In this section we link the complexity of computing expected Shapley-like scores with that of computing expected values. The point is that EV(F ) is a central problem that has already been studied in depth for most meaningful classes of Boolean functions, with classes for which that problem is in P while the general problem is #P-hard. In a sense then, if we can show for some problem 𝐴 that 𝐴 ≡ P EV(F ), this settles the complexity of 𝐴. We start in Section 3.1 by the direction that is most interesting in practice to obtain efficient algorithms: going from expected values to expected scores. We show that this is always possible, under the assumption that the coefficient function is computable in polynomial time. We then give results for the other direction in Section 3.2, where the picture is more complex.

From Expected Values to Expected Scores

Let us call a coefficient function 𝑐 tractable if 𝑐 (𝑘, ℓ) can be computed in P when 𝑘 and ℓ are given in unary as input. It is easy to see that 𝑐 Banzhaf and its normalized version are tractable. This is also the case of 𝑐 Shapley , using the fact that binomial coefficients can be computed in time 𝑂 (𝑘 × ℓ) by dynamic programming (assuming arguments are given in unary). Under this assumption, we show that computing expected Shapley-like scores always reduces in polynomial time to computing expected values. Theorem 3.1. We have EScore 𝑐 (F ) ⩽ P EV(F ) for any tractable coefficient function 𝑐 and any class F of Boolean functions.

We obtain for instance that EScore 𝑐 (F ) is in P for decision trees, ordered binary decision diagrams (OBDDs), deterministic and decomposable Boolean circuits, Boolean circuits of bounded treewidth [START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF], and so on, since EV(F ) is in P for these classes. By Fact 2.3, this also recovers the results from [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF][START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF][START_REF] Kara | From Shapley Value to Model Counting and Back[END_REF] that (nonexpected) Shapley and Banzhaf scores are in P for the tractable classes that they consider.

We prove Theorem 3.1 in the remaining of this section. To do so, we first define two intermediate problems.

𝜑 (𝐸)

Notice that ENV 𝑘,ℓ (𝜑) = 0 when 𝑘 < ℓ. Also, observe that EV(𝜑) =

|𝑉 |

𝑘=0 EV 𝑘 (𝜑) and that EV 𝑘 (𝜑) = ENV 𝑘,𝑘 (𝜑), so that EV(F ) ⩽ P EV ★ (F ) ⩽ P ENV ★,★ (F ) for any F .

We will then prove the chain of reductions EScore 𝑐 (F ) ⩽ P ENV ★,★ (F ) ⩽ P EV ★ (F ) ⩽ P EV(F ), in this order, which implies Theorem 3.1 indeed. Lemma 3.2. We have EScore 𝑐 (F ) ⩽ P ENV ★,★ (F ) for any tractable coefficient function 𝑐 and any class of Boolean functions F .

Proof sketch. Let 𝜑 : 2 𝑉 → {0, 1}, probabilities 𝑝 𝑦 for each 𝑦 ∈ 𝑉 , 𝑥 ∈ 𝑉 , and 𝑛 def = |𝑉 |. We first prove the following equation:

EScore 𝑐 (𝜑, 𝑥) = 𝑝 𝑥 𝑛 ∑ 𝑘=0 𝑘 ∑ ℓ=0 𝑐 (𝑘 + 1, ℓ) ENV 𝑘,ℓ (𝜑 +𝑥 ) -ENV 𝑘,ℓ (𝜑 -𝑥 ) . (1)
Then, we show how to use the oracle to ENV ★,★ (F ) to compute all the values ENV 𝑘,ℓ (𝜑 +𝑥 ) and ENV 𝑘,ℓ (𝜑 -𝑥 ) (note that this is not obvious at first glance, because F might not be closed under conditioning). □

The following lemma contains the most technical part of the proof of Theorem 3.1. It is proved using polynomial interpolation with carefully crafted probability values.

Π 𝑧 𝑖 𝑉 (𝐸)𝜑 (𝐸) = ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) 𝑥 ∈𝐸 𝑝 𝑧 𝑖 𝑥 𝑥 ∈𝑉 \𝐸 (1 -𝑝 𝑧 𝑖 𝑥 ) = 1 𝐶 𝑧 𝑖 ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) 𝑥 ∈𝐸 𝑧 𝑖 𝑝 𝑥 𝑥 ∈𝑉 \𝐸 [(𝑧 𝑖 𝑝 𝑥 ) + (1 -𝑝 𝑥 )].
Next we develop the innermost product as it is parenthesized and distribute the 𝑥 ∈𝐸 𝑧 𝑖 𝑝 𝑥 term, obtaining:

EV 𝑧 𝑖 ℓ (𝜑) = 1 𝐶 𝑧 𝑖 ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) ∑ 𝐸 ⊆𝑍 ⊆𝑉 𝑥 ∈𝑍 𝑧 𝑖 𝑝 𝑥 𝑥 ∈𝑉 \𝑍 (1 -𝑝 𝑥 ) = 1 𝐶 𝑧 𝑖 ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) 𝑛 ∑ 𝑗=0 ∑ 𝐸 ⊆𝑍 ⊆𝑉 |𝑍 |=𝑗 𝑥 ∈𝑍 𝑧 𝑖 𝑝 𝑥 𝑥 ∈𝑉 \𝑍 (1 -𝑝 𝑥 ) = 1 𝐶 𝑧 𝑖 ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) 𝑛 ∑ 𝑗=0 𝑧 𝑖 𝑗 ∑ 𝐸 ⊆𝑍 ⊆𝑉 |𝑍 |=𝑗 Π 𝑉 (𝑍 ) = 1 𝐶 𝑧 𝑖 𝑛 ∑ 𝑗=0 𝑧 𝑖 𝑗 ∑ 𝐸 ⊆𝑉 |𝐸 |=ℓ 𝜑 (𝐸) ∑ 𝐸 ⊆𝑍 ⊆𝑉 |𝑍 |=𝑗 Π 𝑉 (𝑍 ). = 1 𝐶 𝑧 𝑖 𝑛 ∑ 𝑗=0 𝑧 𝑖 𝑗 ENV 𝑗,ℓ (𝜑), (2)
where in the last equality we have inverted the two innermost sums.

Using We can finally state the last step of the proof of Theorem 3.1, again proved using polynomial interpolation. Lemma 3.4. We have EV ★ (F ) ⩽ P EV(F ) for any F .

From Expected Scores to Expected Values

In this section we show reductions in the other direction for 𝑐 Shapley and 𝑐 Banzhaf , under additional assumptions on the class F .

Shapley

= ∑ 𝑍 ⊆𝑉 Π 𝑉 (𝑍 ) 𝜑 (𝑍 ) -𝜑 (∅) = EV(𝜑) -𝜑 (∅). (3)
We can compute the left-hand size in P using oracle calls, and we can compute 𝜑 (∅) in P as well because F is reasonable, therefore we can compute EV(𝜑) in P indeed. This concludes the proof. □

This implies, for instance, that EScore 𝑐 Shapley (F ) is intractable over arbitrary circuits, even monotone bipartite 2-DNF formulas [START_REF] Scott | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF]. Combining with Theorem 3.1, we obtain in particular: Corollary 3.6. We have EScore 𝑐 Shapley (F ) ≡ P EV(F ) for any reasonable class F of Boolean functions.

Hence, at least with respect to polynomial-time computability, this settles the complexity of EScore 𝑐 Shapley (F ) for such classes.

Banzhaf score. Next, we show a similar result for the Banzhaf value, under a different, though commonplace, assumption. Definition 3.7. A class F is said to be closed under conditioning if the following problem is in P: given 𝜑 ∈ F over variables 𝑉 and 𝑥 ∈ 𝑉 , compute a representation in F of 𝜑 +𝑥 . We say F is closed under conjunctions (resp., disjunctions) with fresh variables if the following is in P: given 𝜑 ∈ F over variables 𝑉 and 𝑥 ∉ 𝑉 , compute a representation in F of the Boolean function 𝜑 ∧ 𝑥 (resp., 𝜑 ∨ 𝑥). Proposition 3.8. We have EV(F ) ⩽ P EScore 𝑐 Banzhaf (F ) for any class F that is closed under conditioning and that is also closed under either conjunctions or disjunctions with fresh variables.

This implies that

Let then 𝜑 : 2 𝑉 → {0, 1} be the Boolean function for which we want to compute ENV(𝜑), and let 𝑥 ∉ 𝑉 be a fresh variable. We use the closure property of F to compute a representation of 𝜑 ′ def = 𝜑 ⊙ 𝑥, with ⊙ being ∧ or ∨ depending on the closure property. We then show using Equation (4) that ENV(𝜑) can be recovered from the single oracle call EScore 𝑐 Banzhaf (𝜑 ′ , 𝑥), with 𝑉 ′ def = 𝑉 ∪ {𝑥 }, with same probability values for 𝑦 ∈ 𝑉 and 𝑝 𝑥 = 1. □ Lemma 3.10. We have EV(F ) ⩽ P ENV(F ) for any class F that is closed under conditioning.

Proof sketch. This is again a rather technical proof by polynomial interpolation, in which we curiously seem to need the assumption of closure under conditioning. □

And thus, combining with Theorem 3.1, we obtain: Corollary 3.11. We have EScore 𝑐 Banzhaf (F ) ≡ P EV(F ) for any class F that is closed under conditioning and that is also closed under either conjunctions or disjunctions with fresh variables.

We leave as future work a more systematic (tedious) study of when EV(F ) ⩽ P EScore 𝑐 (F ) holds for other coefficient functions.

DD CIRCUITS

We now present algorithms to compute expected Shapley-like scores in polynomial time over deterministic and decomposable Boolean circuits. Since computing expected values can be done in linear time over such circuits, the fact that computing expected Shapley-like scores over them is in P is already implied by our main result, Theorem 3.1. We nevertheless present more direct algorithms for these circuits as they are easier and more natural to implement than the convoluted chain of reductions with various oracle calls and matrix inversions from the previous section. We will moreover use these algorithms in our experimental evaluation in Section 6. We start by defining what are these circuits.

Boolean circuits. Let 𝐶 be a Boolean circuit over variables 𝑉 , featuring ∧, ∨, ¬, constant 0-and 1-gates, and variable gates (i.e., gates labeled by a variable in 𝑉 ). We write Vars(𝐶) ⊆ 𝑉 the set of variables that occur in the circuit. The size |𝐶 | of 𝐶 is its number of wires. For a gate 𝑔 of 𝐶, we write 𝐶 𝑔 the subcircuit rooted at 𝑔, and write Vars(𝑔) its set of variables. An ∧-gate 𝑔 of 𝐶 is decomposable if for every two input gates 𝑔 1 ≠ 𝑔 2 of 𝑔, Vars(𝑔 1 ) ∩ Vars(𝑔 2 ) = ∅. We call 𝐶 decomposable if all ∧-gates in it are. An ∨-gate 𝑔 of 𝐶 is deterministic if the Boolean functions captured by each pair of distinct input gates of 𝑔 are pairwise disjoint; i.e., there is no assignment that satisfies them both. We call 𝐶 deterministic if all ∨-gates in it are. A deterministic and decomposable (d-D) Boolean circuit [START_REF] Monet | Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases[END_REF] is a Boolean circuit that is both deterministic and decomposable. An ∨gate 𝑔 is smooth if for any input 𝑔 ′ of 𝑔 we have Vars(𝑔) = Vars(𝑔 ′ ), and 𝐶 is smooth is all its ∨-gates are. We say that 𝐶 is tight if it satisfies the following three conditions: (1) Vars(𝐶) = 𝑉 ; (2) 𝐶 is smooth; and (3) every ∧ and every ∨ gate of 𝐶 has exactly two children. The following is folklore. General polynomial-time algorithm. It is thus enough to explain how to compute expected Shapley-like scores for tight d-Ds; let 𝐶 be such a circuit on variables 𝑉 . We start from Equation (1), restated here for convenience:

EScore 𝑐 (𝐶, 𝑥) = 𝑝 𝑥 |𝑉 | -1 ∑ 𝑘=0 𝑘 ∑ ℓ=0 𝑐 (𝑘 + 1, ℓ) ENV 𝑘,ℓ (𝐶 1 ) -ENV 𝑘,ℓ (𝐶 0 ) .
Here, 𝐶 1 (resp., 𝐶 0 ) is the circuit 𝐶 in which we have replaced every variable gate labeled by 𝑥 by a constant 1-gate (resp., a constant 0-gate). It can easily be checked that 𝐶 0 and 𝐶 1 are tight d-Ds over 𝑉 \ {𝑥 }. Therefore, it suffices to compute, for an arbitrary tight d-D circuit 𝐶 ′ , the ENV ★,★ quantities. To do this, we crucially need the determinism and decomposability properties. The idea is to compute corresponding quantities for each gate of the circuit, in a bottom-up fashion. This is similar to what is done in [6, Theorem 2] and [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]Proposition 4.4], but the expressions we obtain are more involved because we have a quadratic number of parameters for each gate of the circuit, as opposed to a linear number of such parameters in these earlier works. The resulting algorithm for the whole procedure is shown in Algorithm 1. Intuitively, the values 𝛽 We can show that the number of bits of numerators and denominators of the 𝛽, 𝛾 and 𝛿 values is roughly 𝑂 (𝑏 × |𝑉 |), for 𝑏 the bound on the number of bits of numerators and denominators of all 𝑝 𝑦 values. Therefore to obtain the exact complexity, without ignoring the time to perform additions and multiplications over such numbers, one has to add an 𝑂 (𝑏 × |𝑉 |) multiplicative factor.

In the case where all probabilities are identical, we can obtain a lower complexity by reusing techniques from [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]: Proposition 4.3. Let 𝑐 be a tractable coefficient function. Given a d-D 𝐶 on variables 𝑉 , a unique probability value 𝑝 = 𝑝 𝑦 for all 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , EScore 𝑐 (𝐶, 𝑥) can be computed in time

𝑂 |𝑉 | 2 × (|𝐶 ||𝑉 | + |𝑉 | 2 + T 𝑐 (|𝑉 |)) assuming unit-cost arithmetic.
Quadratic-time algorithm for expected Banzhaf score. For the expected Shapley value, instantiating Algorithm 1 with 𝑐 = 𝑐 Shapley seems to be the best that we can do. For the expected Banzhaf value however, we can design a more efficient algorithm. We start from Equation (4), restated here in terms of circuits:

EScore 𝑐 Banzhaf (𝐶, 𝑥) = 𝑝 𝑥 [ENV(𝐶 1 ) -ENV(𝐶 0 )]. (5)
We Comparing to and recovering the algorithms of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] and [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF]. We end this section by discussing how this relates to the algorithms proposed in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] and [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF], respectively for Shapley and Banzhaf value computation in a deterministic (non-probabilistic) setting.

𝛽 𝑔 𝑘,ℓ ← 𝑘 𝑘 1 =0 𝑘 1 ℓ 1 =0 𝛽 𝑔 1 𝑘 1 ,ℓ 1 × 𝛽 𝑔 2 𝑘 -𝑘 1 ,ℓ -ℓ 1 for 𝑘, ℓ ∈ [𝑛 ′ ]; 30 𝛾 𝑔 𝑘,ℓ ← 𝑘 𝑘 1 =0 𝑘 1 ℓ 1 =0 𝛾 𝑔 1 𝑘 1 ,ℓ 1 × 𝛾 𝑔 2 𝑘 -𝑘 1 ,ℓ -ℓ 1 for 𝑘, ℓ ∈ [𝑛 ′ ];
First, we note that we can specialize Algorithm 1 to the computation of Shapley values by setting all 𝑝 𝑦 to 1, which means that, when computing ENV 𝑘,ℓ -values, we only need to consider the case where 𝑘 = 𝑛 as all 𝑍 ⊆ 𝑉 with |𝑍 | < 𝑛 have Π 𝑉 (𝑍 ) = 0. This leads to the following simplifications: 𝛿 𝑔 𝑘 values need not be computed as they are all 0's except for 𝛿 values need only be computed when 𝑘 = |Vars(𝑔)|, all other being set to 0. This simplifies the computation to remove a factor of |𝑉 | 2 , and we essentially recover the algorithm described in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]. Note that the final complexity obtained is 𝑂 (|𝐶 | × |𝑉 | 3 ), which is better than the complexity from Proposition 4.3.

Second, we observe that the algorithm underlying Theorem 4.4 has the same complexity as the exact algorithm in [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF] for computing (non-expected) Banzhaf values. We note that [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF] considers decomposition trees instead of d-D circuits, but any decomposition tree is in fact a d-D circuit in disguise, since a decomposable OR of the form 𝐴 ∨ 𝐵 can be rewritten as ¬(¬𝐴 ∧ ¬𝐵), with the AND being decomposable. Their algorithm works in linear time on decomposition trees that are tight (see their Section 3.1), hence we obtain the same complexity while solving a seemingly more general problem: we study the expected Banzhaf values (which degenerates to the non-expected setting when all probabilities are 1), and d-D circuits are more general than decomposition trees as they allow sharing of subexpressions (i.e., the circuit is a DAG instead of a tree).

PROBABILISTIC DATABASES

(Probabilistic) databases and queries. Let Σ = {𝑅 1 , . . . , 𝑅 𝑛 } be a signature, consisting of relation names each with their associated arity ar(𝑅 𝑖 ) ∈ N, and Const be a set of constants. A fact over (Σ, Const) is a term of the form 𝑅(𝑎 1 , . . . , 𝑎 ar(𝑅) ), for 𝑅 ∈ Σ and 𝑎 𝑖 ∈ Const. A (Σ, Const)-database 𝐷 (or simply a database 𝐷) is a finite set of facts over (Σ, Const). We assume familiarity with the most common classes of query languages and refer the reader to [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Arenas | Database Theory[END_REF] for the basic definitions. A Boolean query is a query 𝑞 that takes as input a database 𝐷 and outputs 𝑞(𝐷) ∈ {0, 1}. If 𝑞( x) is a query with free variables x and t is a tuple of constants of appropriate length, we denote by 𝑞[ x/ t] the Boolean query defined by 𝑞[ x/ t] (𝐷) = 1 if and only if t is in the output of 𝑞( x) on 𝐷. A tuple-independent probabilistic database, or TID for short, consists of a database 𝐷 together with probability values 𝑝 𝑓 for every fact 𝑓 ∈ 𝐷. For a Boolean query 𝑞 and TID D = (𝐷, (𝑝 𝑓 ) 𝑓 ∈𝐷 ), the probability that D satisfies 𝑞, written (Expected) Shapley-like scores. Let 𝑐 : N × N → Q be a coefficient function, 𝑞 a Boolean query, 𝐷 a database and 𝑓 ∈ 𝐷 a fact. Following the literature [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF], we define the Shapley-like score with coefficients 𝑐 of 𝑓 in 𝐷 with respect to 𝑞, or simply score when clear, by 1 Score 𝑐 (𝑞, 𝐷, 𝑓

Pr(D |= 𝑞), is defined as Pr(D |= 𝑞) def = 𝐷 ′ ⊆𝐷 s.t. 𝑞 (𝐷 ′ )=1 Pr(𝐷 ′ ), where Pr(𝐷 ′ ) is 𝑓 ∈𝐷 ′ 𝑝 𝑓 × 𝑓 ∈𝐷\𝐷 ′ (1 -𝑝 𝑓 ).
) def = 𝐸 ⊆𝐷\{ 𝑓 } 𝑐 (|𝐷 |, |𝐸|) × 𝑞(𝐸 ∪ {𝑓 }) -𝑞(𝐸) .
We denote by Score 𝑐 (𝑞) the corresponding computational problem. Let now D = (𝐷, (𝑝 𝑓 ) 𝑓 ∈𝐷 ) be a TID and 𝑓 ∈ 𝐷, and define the expected score of 𝑓 for 𝑞 in D as:

EScore 𝑐 (𝑞, D, 𝑓 ) def = ∑ 𝑍 ⊆𝐷,𝑓 ∈𝑍 (Pr(𝑍 ) × Score 𝑐 (𝑞, 𝑍, 𝑓 )) ,
where in Score 𝑐 (𝑞, 𝑍, 𝑓 ) we see 𝑞 as a function from 2 𝑍 to {0, 1}.

Define the problem EScore 𝑐 (𝑞) as expected. Note that all of this matches our definitions of expected values, Shapley-like and expected Shapley-like scores for Boolean functions.

As usual, if the query 𝑞( x) has free variables, for a tuple t of appropriate length we can define similarly, for 𝑓 ∈ 𝐷, the expected score of 𝑓 by using the Boolean query 𝑞[ x/ t] in the above definition. This score then represents the contribution of 𝑓 to t potentially being in the query result (one might in particular be interested in explaining why a tuple is not in the query result).

Then Theorem 3.1 directly translates into this setting of Shapleylike scores of facts over probabilistic databases: Theorem 5.1. We have EScore 𝑐 (𝑞) ⩽ P PQE(𝑞) for any tractable coefficient function 𝑐 and any Boolean query 𝑞. Proof. One direction is Theorem 5.1. The other direction comes from Corollary 3.6, using the same F 𝑞 as in the proof of Theorem 5.1, and noticing that F 𝑞 is reasonable because the query is fixed. □ In particular, this gives a dichotomy on EScore 𝑐 Shapley (𝑞) between P and #P-hard for unions of conjunctive queries (UCQs), or more generally for queries that are closed under homomorphisms [START_REF] Amarilli | Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries[END_REF][START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF]. This should be compared with the corresponding result for (nonexpected) Score 𝑐 Shapley (𝑞), where a dichotomy is currently only known for self-join-free conjunctive queries [START_REF] Kara | From Shapley Value to Model Counting and Back[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF].

For Banzhaf values, even though EScore 𝑐 Banzhaf (𝑞) ⩽ P PQE(𝑞) is true for any Boolean query by Theorem 5.1, it is not clear how to obtain the other direction from Proposition 3.8: indeed, the class F 𝑞 from above has in general no reason to be closed under conditioning nor under taking conjunctions or disjunctions with fresh variables. Yet, we mention that [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF]Proposition 5.6] shows a dichotomy for (non-expected) Score 𝑐 Banzhaf (𝑞) for self-join-free CQs: the tractable queries are the hierarchical queries, while for nonhierarchical queries the problem is #P-hard. This dichotomy then directly extends to EScore 𝑐 Banzhaf (𝑞): the tractable side follows from our Theorem 5.1 because PQE(𝑞) is in P for hierarchical queries, while the hardness result is inherited by Fact 2.3 from the hardness of Score 𝑐 Banzhaf (𝑞) shown in [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF].

Provenance computation and compilation. Unfortunately, not all queries are tractable for probabilistic query evaluation. When faced with an intractable query, another approach is to use the intensional method [START_REF] Suciu | Probabilistic Databases[END_REF], which is to compute and compile the Boolean provenance of the query on the database in a formalism from knowledge compilation that enjoys tractable computation of expected values, such as d-D circuits. When the provenance has been computed as a d-D circuit, we can use the results from Section 4 to compute the expected Shapley-like scores. This is the route that we take in the next section to compute these scores in practice.

IMPLEMENTATION AND EXPERIMENTS

In this section, we experimentally show that the computation of expected Shapley-like scores is feasible in practice on some realistic queries over probabilistic databases, despite the #P-hardness of the problem in general and the high 𝑂 (|𝐶 | × |𝑉 |5 ) upper bound (see Theorem 4.2) on the complexity of Algorithm 1 for d-Ds. The objective is not to provide a comprehensive experimental evaluation but to simply validate that algorithms presented in this work have reasonable complexity for practical applications.

Implementation. We rely on ProvSQL [START_REF] Senellart | ProvSQL: Provenance and Probability Management in PostgreSQL[END_REF], an open-source Post-greSQL extension that computes (between other things) the Boolean provenance of a query over a database. We let ProvSQL compute the Boolean provenance of SQL queries over relational databases as a Boolean circuit, and have extended this system to add the following features2 : (1) We compile Boolean provenance into a d-D in the simple but common decomposable case where every ∧or ∨-gate 𝑔 is decomposable, i.e., for every two inputs 𝑔 1 and 𝑔 2 to 𝑔, Vars(𝑔 1 ) ∩ Vars(𝑔 2 ) = ∅. Note that, as we have already observed in Section 4, a decomposable ∨-gate of the form 𝐴∨𝐵 can be rewritten, using De Morgan's laws, into a decomposable ∧-gate. (2) For cases where this is not possible, we attempt to compile Boolean provenance into a d-D by computing, if possible, a tree decomposition of the circuit of treewidth ⩽ 10, and by then following the construction detailed in [4, Section 5.1] to turn any Boolean circuit into a d-D in linear time when the treewidth is fixed. (3) Otherwise, we default to ProvSQL's default compilation of circuits into d-Ds, which amounts to coding the circuit as a CNF using the Tseitin transformation [START_REF] Tseitin | On the complexity of derivation in propositional calculus[END_REF] and then calling an external knowledge compiler, d4 [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF]. (4) We have implemented directly within ProvSQL Algorithm 1 to compute expected Shapley values on d-Ds, its simplification when all 𝑝 𝑦 are set to 1 detailed at the end of Section 4, as well as the algorithm to compute expected Banzhaf values in the proof of Theorem 4.4. They are all implemented with floating-point numbers.

Note that, in particular, this approach is not restricted to queries that fall on the tractable side of the dichotomy of [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF].

In addition, we benefit from the fact that, since late 2021, ProvSQL stores the provenance circuit in main memory, which speeds provenance computation up (earlier versions stored the provenance circuit within the database, on disk).

Experiment setup. Following [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF][START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF], we used the TPC-H 1 GB benchmark, with standard generated data and 8 standard TPC-H queries adapted to remove nesting and aggregation, as provided by the authors of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] 3 . We use the exact same queries as in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF], except that the LIMIT operator used for the experiments of that paper was removed, to obtain a larger and more realistic benchmark (we end up with 105 154 output tuples for these 8 queries). Probabilities were drawn uniformly at random for all facts.

Experiments were run on a desktop Linux PC with Xeon W3550 2.80GHz CPU, 64 GB RAM (8 GB of which were made available for PostgreSQL's shared buffers), running version 14.9 of PostgreSQL and the latest version of ProvSQL as of December 2023. Data for PostgreSQL is stored on standard magnetic hard drives in RAID 1.

Results. We show in Table 1 results of these experiments. For each query, we report: the number of output tuples; the total time required by ProvSQL to evaluate the query and compute the provenance representation of every output tuple; the total time required by the compilation of the Boolean provenance circuits of all query results to d-Ds; the method used to produce these d-Ds 4 ; the average number of gates of the resulting d-Ds; the total time needed to compute (expected) Shapley values of all query outputs for all relevant facts 5 in the deterministic case (where all probabilities are set to 1) and in the probabilistic case; the same for (expected) Banzhaf values. All times are in seconds, repeated over 20 runs of each query, with the mean and standard deviation shown. To avoid caching of provenance across multiple runs or multiple queries, the ProvSQL provenance circuit was reset each time and PostgreSQL restarted.

We have the following observations regarding the experimental results (also compare with the results from Table 1 of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]).

(1) ProvSQL is able to compute in a reasonable amount of time (at most a couple of seconds) the output of all queries, along with their Boolean provenance as a circuit; this contrasts with the results of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] where provenance computation time could take up to 6 hours for query 3, even when limited to output only 100 tuples; we assume this is the result of recent ProvSQL optimizations and in-memory storage of the Boolean provenance circuit.

(2) Compilation to a d-D takes a time that is comparable, and somewhat lower, to provenance computation, and uses a combination of interpreting the circuit as a decomposable one and the tree decomposition algorithm of [START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF]; compilation through an external knowledge compiler, which was what was done in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF], is never required. Note that compilation is much faster than reported in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] (remember that the times in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] need to be multiplied by the number of output tuples, whereas we report the sum of all compilation Table 1: Provenance computation time, knowledge compilation time and method, and total Shapley/Banzhaf computation time for all output tuples and all facts, in the deterministic case and for expected values in the probabilistic case. The queries are the same TPC-H queries used in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] (without the LIMIT operator used in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]). All times reported are in seconds. 3 0.000 ± 0.000 0.000 ± 0.000 0.000 ± 0.000 0.000 ± 0.000 times); the provenance circuits for queries 5 and 7 could not even be compiled to a d-D in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF].

(3) The total time required for deterministic Shapley value computation is of similar magnitude as query evaluation as well and comparable to those reported in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] (except in one case, for query 19, where numbers reported in [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] are abnormally high).

(4) Computing expected Shapley values in a probabilistic setting using Algorithm 1 incurs a higher cost, but remains more practical in practice than the high theoretical complexity of this algorithm may suggest -the maximum time required is for query 5, with 41 seconds to compute the expected Shapley values over five d-Ds whose average size is over a thousand of gates.

(5) There is of course virtually no difference between computing deterministic and expected Banzhaf values, since the algorithm we use (that of Theorem 4.4), is the same. The total time required for this algorithm is significantly lower than that of deterministic Shapley value computation, especially for circuits with large numbers of gates or variables, as consistent with the established complexities.

(6) Though query evaluation and provenance computation can be marred with significant performance differences from one run to the next (due to disk caching, interaction with PostgreSQL, etc.), there is little variation of the performance of knowledge compilation and expected Shapley-like value computation.

To summarize, the experiments validate the practicality of the algorithms presented in this paper for computation of expected Shapley-like scores over probabilistic databases.

RELATED WORK

There are two lines of work that our results should be compared to. The first one studies the complexity of computing (non-expected) Shapley-like values for databases and Boolean functions. The second one studies the complexity of computing the SHAP-score, a score used in explainable AI and machine learning. In both cases the problem has been studied by relating it to that of computing expected values or of computing model counts, and also by proposing tractable algorithms for deterministic and decomposable Boolean circuits. In this sense then, the structure of our paper is similar to existing literature. Yet we think that all these problem variants are worth studying because the underlying notions are solutions to different problems. We summarize the existing related literature here and compare to it, starting with what is closest to our work.

Shapley-like scores. The authors of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF] study the complexity of the problems Score 𝑐 Shapley and Score 𝑐 Banzhaf , over Boolean functions or, most often, instantiated in the setting of relational databases. See [START_REF] Bertossi | The Shapley value in database management[END_REF] for a survey for databases. In particular, [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] shows that, for any query, the problem Score 𝑐 Shapley can be reduced in polynomial time to probabilistic query evaluation for the same query. In a contemporaneous draft, the authors of [START_REF] Kara | From Shapley Value to Model Counting and Back[END_REF] show an analogous result for Boolean functions, also obtaining the other direction of the reduction (under some assumptions). Notice the resemblance between, on the one side, these last two results that we mention, and on the other side our Corollaries 3.6 and 5.2. The difference is that we study the expected Shapley values. There is a priori no reason for the tractable cases to be the same as the non-expected variant: indeed, the counting (or probabilistic) version of a problem is often much harder than the decision onefor instance probabilistic query evaluation is often intractable for queries for which regular evaluation is easy. 6 By our results, this phenomenon does not occur for EScore 𝑐 Shapley . Since EScore 𝑐 Shapley strictly generalizes Score 𝑐 Shapley (by Fact 2.3), the reduction from EScore 𝑐 Shapley to EV is more challenging, and indeed one can check that our polynomial interpolation proofs are more involved than, say, [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF]Proposition 3.1]. On the other hand, our life is made easier to prove the other direction of these equivalences. This explains why we do not need the assumption of closure under OR-substitutions in Corollary 3.6, and this is also what allows us to obtain a complete equivalence to probabilistic query evaluation in Corollary 5.2, no matter the Boolean query, whereas in the case of non-expected Shapley values this is only known for self-join-free CQs. As for algorithms for d-D circuits, we refer to the end of Section 4 for a comparison to [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] and [START_REF] Abramovich | Banzhaf Values for Facts in Query Answering[END_REF]. SHAP-score. The authors of [START_REF] Arenas | The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits[END_REF][START_REF] Arenas | On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results[END_REF][START_REF] Van Den Broeck | On the Tractability of SHAP Explanations[END_REF][START_REF] Van Den Broeck | On the tractability of SHAP explanations[END_REF] study the complexity of computing the SHAP-score. In particular [START_REF] Van Den Broeck | On the Tractability of SHAP Explanations[END_REF][START_REF] Van Den Broeck | On the tractability of SHAP explanations[END_REF] show that it is equivalent to computing expected values, and [START_REF] Arenas | The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits[END_REF][START_REF] Arenas | On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results[END_REF] propose polynomial-time algorithms for d-D circuits. Thus, the landscape is similar to what we obtain here. However, there is to the best of our knowledge no formal connection between the SHAP-score and the expected scores that we study here: in a nutshell, we compute the expected Shapley value where the game function is the Boolean function 𝜑, whereas the SHAP score is computing the Shapley value where the game function is a conditional expectation of 𝜑. Hence, the two sets of results seem to be independent.

CONCLUSION

We proposed the new notion of expected Shapley-like scores for Boolean functions, proved that computing these scores can always be reduced in polynomial-time to the well-studied problem of computing expected values, and that these two problems are often even equivalent (under commonplace assumptions). We designed algorithms for deterministic and decomposable Boolean circuits and implemented them in the setting of probabilistic databases, where our preliminary experimental results show that these scoring mechanisms could actually be used in practice. We leave as future work the study of approximation algorithms for this new notion. In particular, it is known that Score 𝑐 Shapley (𝑞) has a fully polynomial-time randomized scheme [START_REF] Mark R Jerrum | Random generation of combinatorial structures from a uniform distribution[END_REF] whenever 𝑞 is a UCQ [START_REF] Bertossi | The Shapley value in database management[END_REF], and one could study whether this stays true for the probabilistic variant. Still we note that, since the reduction from Fact 2.3 is parsimonious, we inherit the few hardness results of the non-probabilistic setting, such as those of [START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF] for conjunctive queries with negations.

A PROOFS FOR SECTION 3 (EQUIVALENCE WITH EXPECTED VALUES) A.1 From Expected Values to Expected Scores

= 𝑝 𝑥 ∑ 𝑍 ⊆𝑉 ′ Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 𝑐 (|𝑍 | + 1, |𝐸|)𝜑 +𝑥 (𝐸) = 𝑝 𝑥 ∑ 𝑍 ⊆𝑉 ′ ∑ 𝐸 ⊆𝑍 𝑐 (|𝑍 | + 1, |𝐸|)Π 𝑉 ′ (𝑍 )𝜑 +𝑥 (𝐸) = 𝑝 𝑥 𝑛 ∑ 𝑘=0 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑘 𝑘 ∑ ℓ=0 ∑ 𝐸 ⊆𝑍 |𝐸 |=ℓ 𝑐 (𝑘 + 1, ℓ)Π 𝑉 ′ (𝑍 )𝜑 +𝑥 (𝐸) = 𝑝 𝑥 𝑛 ∑ 𝑘=0 𝑘 ∑ ℓ=0 𝑐 (𝑘 + 1, ℓ) ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑘 ∑ 𝐸 ⊆𝑍 |𝐸 |=ℓ Π 𝑉 ′ (𝑍 )𝜑 +𝑥 (𝐸) = 𝑝 𝑥 𝑛 ∑ 𝑘=0 𝑘 ∑ ℓ=0 𝑐 (𝑘 + 1, ℓ)ENV 𝑘,ℓ (𝜑 +𝑥 ).
We can do exactly the same for 𝐵 (replacing 𝜑 +𝑥 by 𝜑 -𝑥 ), after which we obtain Equation (1) from the proof sketch, repeated here:

EScore 𝑐 (𝜑, 𝑥) = 𝑝 𝑥 𝑛 ∑ 𝑘=0 𝑘 ∑ ℓ=0 𝑐 (𝑘 + 1, ℓ) ENV 𝑘,ℓ (𝜑 +𝑥 ) -ENV 𝑘,ℓ (𝜑 -𝑥 ) .
We can compute the coefficients 𝑐 (𝑘 + 1, ℓ) in P because 𝑐 is tractable. Therefore, all that is left to show is that we can compute in P all the values ENV 𝑘,ℓ (𝜑 +𝑥 ) and ENV 𝑘,ℓ (𝜑 -𝑥 ) for 𝑘, ℓ ∈ [𝑛]. We point out that this is not obvious, because F might not be closed under conditioning, and unfortunately setting 𝑝 𝑥 to 0 or 1 is not enough to directly give us the values we want. In [START_REF] Kara | From Shapley Value to Model Counting and Back[END_REF], this annoying subtlety is handled by using the closure under OR-substitutions of the class F (see the proof of their Lemma 3.2). In our case, we will overcome this problem by using the fact that we can freely choose the probabilities.

Let 𝑧 ∈ [0, 1], and for 𝑦 ∈ 𝑉 ′ = 𝑉 \ {𝑥 } define 𝑝 𝑧 𝑦 def = 𝑝 𝑦 , and 𝑝 𝑧 𝑥 = 𝑧. Define Π 𝑧 and ENV 𝑧 ★,★ (𝜑) as expected. We claim that the following equation holds, for 𝑖, 𝑗 ∈ [𝑛 + 1]:

ENV 𝑧 𝑖,𝑗 (𝜑) = 𝑧 ENV 𝑖 -1,𝑗 (𝜑 -𝑥 ) + ENV 𝑖 -1,𝑗 -1 (𝜑 +𝑥 ) + (1 -𝑧)ENV 𝑖,𝑗 (𝜑 -𝑥 ), (6)
where we extended the definition of ENV ★,★ (𝜑 +𝑥 ) and ENV ★,★ (𝜑 -𝑥 ) to have value zero for out-of-bound (𝑖, 𝑗)-indices. Before proving this claim, let us explain why this allows us to conclude. Indeed, we can then use the oracle to ENV ★,★ (F ) with 𝑧 = 0 to compute all the values ENV 𝑘,ℓ (𝜑 -𝑥 ). Once these are known, we use the oracle again but this time with 𝑧 = 1, and thanks to Equation (6) again we can recover all the values ENV 𝑘,ℓ (𝜑 +𝑥 ). Therefore all that is left to do is prove Equation [START_REF] Arenas | On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results[END_REF]. We have:

ENV 𝑧 𝑖,𝑗 (𝜑) def = ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑖 Π 𝑉 (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 (𝐸) = ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑖 𝑥∉𝑍 Π 𝑉 (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 (𝐸) + ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑖 𝑥 ∈𝑍 Π 𝑉 (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 (𝐸).
Call 𝑇 the top term, 𝐵 the bottom one. We have:

𝑇 = (1 -𝑧) ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 (𝐸) = (1 -𝑧) ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 -𝑥 (𝐸) = (1 -𝑧)ENV 𝑖,𝑗 (𝜑 -𝑥 ).
Let us now inspect 𝐵.

𝐵 = 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 ∪{𝑥 } |𝐸 |=𝑗 𝜑 (𝐸) = 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 ∪{𝑥 } |𝐸 |=𝑗 𝑥∉𝐸 𝜑 (𝐸) + 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 ∪{𝑥 } |𝐸 |=𝑗 𝑥 ∈𝐸 𝜑 (𝐸).
Call 𝑇 ′ and 𝐵 ′ the top and bottom terms. Then:

𝑇 ′ = 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 𝜑 -𝑥 (𝐸) = 𝑧 × ENV 𝑖 -1,𝑗 (𝜑 -𝑥 ),
and

𝐵 ′ = 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 -1 𝜑 (𝐸 ∪ {𝑥 }) = 𝑧 ∑ 𝑍 ⊆𝑉 ′ |𝑍 |=𝑖 -1 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 |𝐸 |=𝑗 -1 𝜑 +𝑥 (𝐸) = 𝑧 × ENV 𝑖 -1,𝑗 -1 (𝜑 +𝑥 ).
Putting it all together, we indeed obtain Equation ( 6), thus concluding the proof. □ Lemma 3.4. We have EV ★ (F ) ⩽ P EV(F ) for any F .

EV 𝑧 𝑖 (𝜑) def = ∑ 𝑍 ⊆𝑉 Π 𝑧 𝑖 𝑉 (𝑍 )𝜑 (𝑍 ) = 𝑛 ∑ 𝑗=0 ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑗 Π 𝑧 𝑖 𝑉 (𝑍 )𝜑 (𝑍 ) = 𝑛 ∑ 𝑗=0 ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑗 𝜑 (𝑍 ) 𝑥 ∈𝑍 𝑝 𝑧 𝑖 𝑥 𝑥 ∈𝑉 \𝑍 (1 -𝑝 𝑧 𝑖 𝑥 ) = 1 𝐶 𝑧 𝑖 𝑛 ∑ 𝑗=0 ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑗 𝜑 (𝑍 )𝑧 𝑖 |𝑍 | 𝑥 ∈𝑍 𝑝 𝑥 𝑥 ∈𝑉 \𝑍 (1 -𝑝 𝑥 ) = 1 𝐶 𝑧 𝑖 𝑛 ∑ 𝑗=0 𝑧 𝑖 𝑗 ∑ 𝑍 ⊆𝑉 |𝑍 |=𝑗 𝜑 (𝑍 )Π 𝑉 (𝑍 ) = 1 𝐶 𝑧 𝑖 𝑛 ∑ 𝑗=0 𝑧 𝑖 𝑗 EV 𝑗 (𝜑).
We can then conclude just like in the proof of Lemma 3.3. □

A.2 From Expected Scores to Expected Values

Lemma 3.9. We have ENV(F ) ⩽ P EScore 𝑐 Banzhaf (F ) for any F closed under conjunctions (resp., disjunctions) with fresh variables.

Proof. Let us first show that for 𝜑 ′ : 2 𝑉 ′ → {0, 1} and probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 ′ and 𝑥 ∈ 𝑉 ′ we have the equation claimed in the proof sketch, restated here:

EScore 𝑐 Banzhaf (𝜑 ′ , 𝑥) = 𝑝 𝑥 [ENV(𝜑 ′ +𝑥 ) -ENV(𝜑 ′ -𝑥 )].
The derivation is similar to that of Lemma 3.2, but simpler. Observe that EScore 𝑐 Banzhaf (𝜑, 𝑥) = 𝐴 -𝐵, where

𝐴 = ∑ 𝑍 ⊆𝑉 ′ 𝑥 ∈𝑍 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 \{𝑥 } 𝜑 ′ (𝐸 ∪ {𝑥 }) 𝐵 = ∑ 𝑍 ⊆𝑉 ′ 𝑥 ∈𝑍 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 \{𝑥 } 𝜑 ′ (𝐸).
Let us focus on 𝐴. Letting 𝑉 ′′ def = 𝑉 ′ \ {𝑥 }, notice that these are the variables over which 𝜑 ′ +𝑥 is defined. Letting 𝑛 def = |𝑉 ′′ |, we have

𝐴 = ∑ 𝑍 ⊆𝑉 ′ 𝑥 ∈𝑍 Π 𝑉 ′ (𝑍 ) ∑ 𝐸 ⊆𝑍 \{𝑥 } 𝜑 ′ +𝑥 (𝐸) = 𝑝 𝑥 ∑ 𝑍 ⊆𝑉 ′′ Π 𝑉 ′′ (𝑍 ) ∑ 𝐸 ⊆𝑍 𝜑 ′ +𝑥 (𝐸) = 𝑝 𝑥 ENV(𝜑 ′ +𝑥 ).
We can do the same for 𝐵 to obtain 𝐵 = 𝑝 𝑥 ENV(𝜑 ′ -𝑥 ), hence the equation. We now prove Lemma 3.9 in the case that F is closed under conjunctions with fresh variables. Let then 𝜑 : 2 𝑉 → {0, 1}, and probabilities 𝑝 𝑦 for 𝑦 ∈ 𝑉 . We want to compute ENV(𝜑). Since F is closed under conjunctions with fresh variables, let 𝑥 ∉ 𝑉 and compute a representation of 𝜑 ′ def = 𝜑 ∧ 𝑥 in F . We call the oracle to EScore 𝑐 Banzhaf on 𝜑 ′ with same probabilities for 𝑦 ∈ 𝑉 and with 𝑝 𝑥 def = 1. By the above equation (with 𝑉 ′ = 𝑉 ∪ {𝑥 }) this immediately gives us ENV(𝜑) and concludes.

For the case when F is closed under disjunctions with fresh variables we do the same but with 𝜑 ′ def = 𝜑 ∨ 𝑥: now by Equation ( 4) the oracle call returns 𝑍 ⊆𝑉 Π 𝑉 (𝑍 ) 𝐸 ⊆𝑍 1 -ENV(𝜑), which is equal to 𝑍 ⊆𝑉 Π 𝑉 (𝑍 )2 |𝑍 | -ENV(𝜑). We conclude the proof by showing that the first term is equal to 𝑦 ∈𝑉 (1 + 𝑝 𝑦 ), which can be computed in polynomial time, hence we can indeed recover ENV(𝜑). Indeed, let 𝑛 Observe that the quantity that we want is 𝑑 𝑛 . But it is clear that 𝑑 0 = 1 and that

𝑑 𝑖 = 𝑍 ⊆𝑉 𝑖 𝑦 𝑖 ∉𝑍 Π 𝑉 𝑖 (𝑍 )2 |𝑍 | + 𝑍 ⊆𝑉 𝑖 𝑦 𝑖 ∈𝑍 Π 𝑉 𝑖 (𝑍 )2 |𝑍 | = (1 -𝑝 𝑦 𝑖 )𝑑 𝑛-1 + 𝑝 𝑦 𝑖 × 𝑑 𝑛-1 × 2 = (1 + 𝑝 𝑦 𝑖 )𝑑 𝑛-1 for 1 ⩽ 𝑖 ⩽ 𝑛, which concludes.
□ Lemma 3.10. We have EV(F ) ⩽ P ENV(F ) for any class F that is closed under conditioning.

Proof. Let 𝜑 ∈ F over variables 𝑉 with 𝑛 def = |𝑉 | and probability values 𝑝 𝑥 for each 𝑥 ∈ 𝑉 ; we want to compute EV(𝜑). We use polynomial interpolation to compute all the values EV 𝑗 (𝜑) for 𝑗 ∈ [𝑛], after which we can simply return 𝑛 𝑗=0 EV 𝑗 (𝜑) = EV(𝜑). Without loss of generality, we can assume that 𝑝 𝑥 < 1 for all 𝑥 ∈ 𝑉 . Indeed, if there is 𝑥 such that 𝑝 𝑥 = 1, we consider 𝑉 ′ = 𝑉 \ {𝑥 } and 𝜑 ′ = 𝜑 +𝑥 . Then EV 𝑗 (𝜑) = EV 𝑗 -1 (𝜑 ′ ) for any 𝑗 ⩾ 1 and EV 0 (𝜑) = 0. This is indeed without loss of generality because F is closed under conditioning, so that 𝜑 +𝑥 is in F .

Let 𝑀 def = max 𝑥 ∈𝑉 𝑝 𝑥 < 1. Let 𝑧 0 , . . . , 𝑧 𝑛 be 𝑛 + 1 distinct rational values in (0, 1 -𝑀). For 𝑖 ∈ [𝑛] and 𝑥 ∈ 𝑉 , we define this time Recall that this will be instantiated with 𝐶 ′ = 𝐶 0 and 𝐶 ′ = 𝐶 1 for the circuits 𝐶 0 and 𝐶 1 from Section 4 (which should not be confused with circuit 𝐶 of that section). Also note that, even though by Equation (1) we only need to compute the values for 𝑘 ⩾ ℓ (since they are zero when 𝑘 > ℓ), we still do as if we wanted to naively compute them all. This allows us to obtain cleaner expressions, in which the ranges for 𝑘 for all 𝑘 ∈ [𝑛 ′ ] and we are done. Decomposable ∧-gates. Let 𝑔 be a decomposable ∧-gate with inputs 𝑔 1 , 𝑔 2 . Notice that Vars(𝑔) = Vars(𝑔 1 ) ∪ Vars(𝑔 2 ) with the union being disjoint. We can then decompose 𝑍 into a "left" part 𝑍 1 ⊆ Vars(𝑔 1 ) of size 𝑘 1 ∈ {0, . . . , 𝑘 } and a "right" part 𝑍 2 ⊆ Vars(𝑔 2 ) of size 𝑘 -𝑘 1 . We then have:

𝑝 𝑧 𝑖 𝑥 def = 𝑧 𝑖 𝑝 𝑥
𝛿 𝑔 𝑘 = ∑ 𝑍 ⊆Vars(𝑔) |𝑍 |=𝑘 Π Vars(𝑔) (𝑍 ) = 𝑘 ∑ 𝑘 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 Π Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 ) = 𝑘 ∑ 𝑘 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 Π Vars(𝑔 1 ) (𝑍 1 ) ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 Π Vars(𝑔 2 ) (𝑍 2 ) = 𝑘 ∑ 𝑘 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 Π Vars(𝑔 1 ) (𝑍 1 )𝛿 𝑔 2 𝑘 -𝑘 1 = 𝑘 ∑ 𝑘 1 =0 𝛿 𝑔 2 𝑘 -𝑘 1 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 Π Vars(𝑔 1 ) (𝑍 1 ) = 𝑘 ∑ 𝑘 1 =0 𝛿 𝑔 1 𝑘 1 𝛿 𝑔 2 𝑘 -𝑘 1 ,
and we are done. The complexity of every step is 𝑂 (𝑛 ′ ) except for ∧-gates where the complexity is 𝑂 (𝑛 ′2 ); each step needs to be repeated for every gate of 𝐶 ′ , which gives the stated complexity. This concludes the proof of Lemma B. If we can show that we can compute all quantities 𝛼 𝑔 𝑘,ℓ in the required complexity then we are done: indeed, we can then take 𝑔 to be the output gate of 𝐶 ′ , which gives us the quantities ENV 𝑘,ℓ (𝐶 ′ ) that we wanted. We show just that in the next lemma.

Π Vars(𝑔) (𝑍 )𝐶 ′ 𝑔 (𝐸) = 𝑘 ∑ 𝑘 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 ∑ 𝐸 ⊆𝑍 1 ∪𝑍 2 |𝐸 |=ℓ Π Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 )𝐶 ′ 𝑔 (𝐸) = 𝑘 ∑ 𝑘 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 𝑘 1 ∑ ℓ 1 =0 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 ∑ 𝐸 2 ⊆𝑍 2 |𝐸 2 |=ℓ -ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 )𝐶 ′ 𝑔 1 (𝐸 1 )𝐶 ′ 𝑔 2 (𝐸 2 ) = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 ∑ 𝐸 2 ⊆𝑍 2 |𝐸 2 |=ℓ -ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 )𝐶 ′ 𝑔 1 (𝐸 1 )𝐶 ′ 𝑔 2 (𝐸 2 ) = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 ∑ 𝐸 2 ⊆𝑍 2 |𝐸 2 |=ℓ -ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 )𝐶 ′ 𝑔 1 (𝐸 1 )𝐶 ′ 𝑔 2 (𝐸 2 ) = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )𝐶 ′ 𝑔 1 (𝐸 1 ) ∑ 𝑍 2 ⊆Vars(𝑔 2 ) |𝑍 2 |=𝑘 -𝑘 1 ∑ 𝐸 2 ⊆𝑍 2 |𝐸 2 |=ℓ -ℓ 1 Π Vars(𝑔 2 ) (𝑍 2 )𝐶 ′ 𝑔 2 (𝐸 2 ) = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )𝐶 ′ 𝑔 1 (𝐸 1 )𝛼 𝑔 2 𝑘 -𝑘 1 ,ℓ -ℓ 1 = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 𝛼 𝑔 2 𝑘 -𝑘 1 ,ℓ -ℓ 1 ∑ 𝑍 1 ⊆Vars(𝑔 1 ) |𝑍 1 |=𝑘 1 ∑ 𝐸 1 ⊆𝑍 1 |𝐸 1 |=ℓ 1 Π Vars(𝑔 1 ) (𝑍 1 )𝐶 ′ 𝑔 1 (𝐸 1 ) = 𝑘 ∑ 𝑘 1 =0 𝑘 1 ∑ ℓ 1 =0 𝛼 𝑔 1 𝑘 1 ,ℓ 1 × 𝛼 𝑔 2 𝑘 -𝑘 1 ,ℓ -ℓ 1 .
and we are done.

The complexity is given by that of the step for ¬and ∧-gates, which are the most costly at 𝑂 (𝑛 ′4 ) (recall that computing 𝑘 ℓ is in 𝑂 (𝑘 × ℓ)), which we need to multiply by the size of the circuit. This concludes the proof of Lemma B.5. □

In Algorithm 1, the 𝛽 values are the 𝛼 values for 𝐶 1 and the 𝛾 values are the 𝛼 values for 𝐶 0 , and they are computed in a single pass over the circuit 𝐶 instead of first computing 𝐶 1 and 𝐶 0 and making passes over these two circuits. Therefore, Algorithm 1 is correct. To obtain the final complexity, we need to add the cost of line 32, which is in 𝑂 (𝑛 ′2 × T(𝑛 ′ )) ignoring the cost of arithmetic operations, and remember that |𝐶 where we set 𝐶 1 and 𝐶 0 as usual and #SAT ℓ (𝐶 ′ ) is the number of satisfying valuations of size ℓ of the circuit 𝐶 ′ . Using the techniques of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] (in particular, Lemma 4. Proof. As argued in Section 4, we need only to prove, thanks to Equation [START_REF] Arenas | The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits[END_REF], that ENV can be computed in linear time for tight d-D circuits.

Let 𝐶 ′ be a tight d-D over variables 𝑉 ′ and 𝑝 𝑥 probability values for all 𝑥 ∈ 𝑉 ′ . We want to compute ENV(𝜑) def = 𝑍 ⊆𝑉 ′ Π 𝑉 ′ (𝑍 ) 𝐸 ⊆𝑍 𝐶 ′ (𝐸). (Recall that this will be instantiated with 𝐶 ′ = 𝐶 1 and 𝐶 ′ = 𝐶 0 ) from Equation (5).) We do this again by bottom-up induction on the circuit, computing the corresponding quantities for very gate. Formally, for a gate 𝑔 of 𝐶 ′ , define: Π Vars(𝑔 1 ) (𝑍 1 ) ∑

𝛼 𝑔 def =
𝐸 1 ⊆𝑍 1 𝐶 ′ 𝑔 1 (𝐸 1 ) = 𝛼 𝑔 2 𝛼 𝑔 1 .
This concludes the proof, as all of this can be done in 𝑂 (|𝐶 ′ |), ignoring the cost of arithmetic operations (and, in any case, the number of bits stays polynomial). Note that for it to be true for negation gates, we need to compute 𝑦 ∈Vars(𝑔) (1 + 𝑝 𝑦 ) for every gate, which can be done during the bottom-up processing of the circuit as well. □

B.4 Complexity in the Case where All Probabilities are 1

As discussed at the end of Section 4, when all probabilities are set to 1, we recover the algorithm of [START_REF] Deutch | Computing the Shapley value of facts in query answering[END_REF] for non-probabilistic Shapley value computation. We briefly discuss its precise complexity.

In that setting, as discussed, we do not need to compute 𝛿

  PROBLEM : EV(F ) (Expected Value) INPUT : A Boolean function 𝜑 ∈ F over variables 𝑉 and probability values 𝑝 𝑥 for each 𝑥 ∈ 𝑉 OUTPUT : The quantity EV(𝜑) Here, we consider as usual that the probabilities values are rational numbers 𝑝 𝑞 for (𝑝, 𝑞) ∈ N × N * , provided as ordered pairs (𝑝, 𝑞) where 𝑝 and 𝑞 themselves are encoded in binary. Shapley-like scores. Let 𝑐 : N × N → Q be a function, that we call the coefficient function, and let 𝜑 : 2 𝑉 → {0, 1} and 𝑥 ∈ 𝑉 . Define the Shapley-like score with coefficients 𝑐 of 𝑥 in 𝑉 with respect to 𝜑, or simply score when clear from context, by Score 𝑐 (𝜑, 𝑉 , 𝑥) def = ∑ 𝐸 ⊆𝑉 \{𝑥 } 𝑐 (|𝑉 |, |𝐸|) × 𝜑 (𝐸 ∪ {𝑥 }) -𝜑 (𝐸) . Example 2.1. Let 𝑐 Shapley (𝑘, ℓ)

Lemma 3 . 3 .

 33 We have ENV ★,★ (F ) ⩽ P EV ★ (F ) for any F . Proof. Let 𝜑 ∈ F over variables 𝑉 , probability values 𝑝 𝑥 for each 𝑥 ∈ 𝑉 , and 𝑘, ℓ ∈ [|𝑉 |]. Let 𝑛 def = |𝑉 |. Our goal is to compute ENV 𝑘,ℓ (𝜑). We will in fact use polynomial interpolation to compute all the values ENV 𝑗,ℓ (𝜑) for 𝑗 ∈ [𝑛], and return ENV 𝑘,ℓ (𝜑).

Lemma 4 . 1 .

 41 Given as input a d-D circuit 𝐶 over variables 𝑉 , we can compute in 𝑂 (|𝐶 | × |𝑉 |) a d-D circuit 𝐶 ′ over 𝑉 that is equivalent to 𝐶 and that is tight.

  𝑔 𝑘,ℓ correspond to the ENV 𝑘,ℓ -values for the subcircuit of 𝐶 1 rooted at gate 𝑔, the values 𝛾 𝑔 𝑘,ℓ correspond to those for 𝐶 0 , and 𝛿 values are intermediate quantities that we have to compute. Thus: Theorem 4.2. Let 𝑐 be a tractable coefficient function. Given a d-D circuit 𝐶 on variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , Algorithm 1 correctly computes EScore 𝑐 (𝐶, 𝑥) in polynomial time. Moreover, if we ignore the cost of arithmetic operations, it is in time 𝑂 |𝐶 | × |𝑉 | 5 + T 𝑐 (|𝑉 |) × |𝑉 | 2 where T 𝑐 (𝛼) is the cost of computing the coefficient function on inputs ⩽ 𝛼.

  ← 𝑎, and 𝛽 𝑔 𝑘,ℓ , 𝛾 𝑔 𝑘,ℓ ← 0 for (𝑘, ℓ) ≠ (0, 0); 18 else if 𝑔 is a variable gate with Vars(𝑔) = {𝑥 } then 19 𝛽 𝑔 0,0 ← 1, 𝛾 𝑔 0,0 ← 0, and 𝛽 𝑔 𝑘,ℓ , 𝛾 𝑔 𝑘,ℓ ← 0 for (𝑘, ℓ) ≠ (0, 0); 20 else if 𝑔 is a variable gate with Vars(𝑔) = {𝑦} and 𝑦 ≠ 𝑥 then 21 𝛽 𝑔 0,0 , 𝛽 𝑔 1,0 , 𝛾 𝑔 0,0 , 𝛾 𝑔 1,0 ← 0, 𝛽 𝑔 1,1

𝑐

  (𝑘 + 1, ℓ) 𝛽 𝑔 out 𝑘,ℓ -𝛾 𝑔 out 𝑘,ℓ ; Theorem 4.4. Given a d-D 𝐶 on variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , we can compute in time 𝑂 (|𝐶 | × |𝑉 |) (ignoring the cost of arithmetic operations) the quantity EScore 𝑐 Banzhaf (𝐶, 𝑥).

  𝑔 |Vars(𝑔) | = 1; similarly, 𝛽 𝑔 𝑘,ℓ and 𝛾 𝑔 𝑘,ℓ

  For a fixed Boolean query 𝑞, we denote by PQE(𝑞) the computational problem that takes as input a TID D and outputs Pr(D |= 𝑞).

  Proof. It suffices to instantiate Theorem 3.1 with the set of Boolean functions F 𝑞 def = {𝜑 𝑞,𝐷 | 𝐷 is a database}, where 𝜑 𝑞,𝐷 : 2 𝐷 → {0, 1}, the Boolean provenance [28] of query 𝑞 over 𝐷, is defined by 𝜑 𝑞,𝐷 (𝐷 ′ ) def = 𝑞(𝐷 ′ ) for 𝐷 ′ ⊆ 𝐷. Here, it is implicit that the Boolean function 𝜑 𝑞,𝐷 is represented by 𝐷 itself. □ In the case of the Shapley value, we can even get a full equivalence from Corollary 3.6: Corollary 5.2. We have EScore 𝑐 Shapley (𝑞) ≡ P PQE(𝑞) for any Boolean query 𝑞.

  Formally, define the model counting problem for class F of Boolean functions as follows: given as input 𝜑 ∈ F over variables 𝑉 , compute #𝜑 def = {𝑍 ∈ 2 𝑉 | 𝜑 (𝑍 ) = 1}. They then show (we refer to their article for the definition of closure under OR-substitutions): Theorem 7.1 ([18, Corollary 7]). We have Score 𝑐 Shapley (F ) ≡ P MC(F ) for any class F that is closed under OR-substitutions.

= 1 -

 1 Proof. Let 𝜑 ∈ F over variables 𝑉 , probability values 𝑝 𝑥 for each 𝑥 ∈ 𝑉 , and 𝑘 ∈ [|𝑉 |]. Let 𝑛 def = |𝑉 |. We wish to compute EV 𝑘 (𝜑). We use again polynomial interpolation to compute all the values EV 𝑗 (𝜑) for 𝑗 ∈ [𝑛] and return EV 𝑘 (𝜑). Let 𝑧 0 , . . . , 𝑧 𝑛 be 𝑛 + 1 distinct positive values in Q. For 𝑖 ∈ [𝑛] and 𝑥 ∈ 𝑉 , define 𝑐 𝑧 𝑖 𝑥 def 𝑝 𝑥 + 𝑧 𝑖 𝑝 𝑥 , define 𝑝 𝑧 𝑖 𝑥 def = 𝑧 𝑖 𝑝 𝑥 𝑐 𝑧 𝑖 𝑥 , and define Π 𝑧 𝑖 and EV 𝑧 𝑖 (𝜑) as expected. Again, these are all valid probability mappings, and observe that this time 1 -𝑝 𝑧 𝑖 𝑥 = 1-𝑝 𝑥 𝑐 𝑧 𝑖 𝑥 . Defining as before 𝐶 𝑧 𝑖 def = 𝑥 ∈𝑉 𝑐 𝑧 𝑖 𝑥 , it is this time much easier to derive the equality EV 𝑧 𝑖 (𝜑) = 1 𝐶 𝑧 𝑖 𝑛 𝑗=0 𝑧 𝑖 𝑗 EV 𝑗 (𝜑):

def=

  |𝑉 |, and order the variables of 𝑉 arbitrarily as 𝑦 1 , . . . , 𝑦 𝑛 . For 𝑖 ∈ [𝑛], define 𝑉 𝑖 def = {𝑦 𝑗 | 1 ⩽ 𝑗 ⩽ 𝑖 ∈ [𝑛]} (note that 𝑉 0 = ∅), and 𝑑 𝑖 def = 𝑍 ⊆𝑉 𝑖 Π 𝑉 𝑖 (𝑍 )2 |𝑍 | .

5 +

 5 T 𝑐 (|𝑉 |) × |𝑉 | 2 where T 𝑐 (𝛼) is the cost of computing the coefficient function on inputs ⩽ 𝛼. Proving Theorem 4.2, as explained in Section 4, boils down to showing how we can compute, given a tight d-D circuit, the ENV ★,★ quantities. We then show: Proposition B.1. Given as input a tight d-D circuit 𝐶 ′ on variables 𝑉 ′ and probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 ′ we can compute all the values ENV 𝑘,ℓ (𝐶) for 𝑘, ℓ ∈ [|𝑉 ′ |] in 𝑂 (|𝐶 ′ | × |𝑉 ′ | 4 ), ignoring the cost of arithmetic operations.

  the sums are easier to read. Let us define 𝑛 ′ def = |𝑉 ′ |. We first explain how to compute an intermediate quantity that will be needed later. Definition B.2. For a gate 𝑔 ∈ 𝐶 ′ and integer 𝑘 ∈ [𝑛 ′ ], define 𝛿 𝑔 𝑘 def = 𝑍 ⊆Vars(𝑔) |𝑍 |=𝑘 Π Vars(𝑔) (𝑍 ). (Note that 𝛿 𝑔 𝑘 = 0 when 𝑘 > Vars(𝑔 ′ ).) Notice that 𝛿 𝑔 𝑘 only depends on the "structure" of the circuit, but not on its semantics. Lemma B.3. We can compute in 𝑂 (|𝐶 ′ | × 𝑛 ′2 ) all quantities 𝛿 𝑔 𝑘 , ignoring the cost of arithmetic operations. Proof. We compute them by bottom-up induction on 𝐶 ′ . Constant gates. Let 𝑔 be a constant gate. Then Vars(𝑔) = ∅, so 𝛿 𝑔 𝑘 = 0 for 𝑘 ⩾ 1, and 𝛿 𝑔 0 = 1 (indeed Π ∅ (∅) = 1 since this is the neutral element of multiplication). Input gates. Let 𝑔 be an input gate, with variable 𝑦. Then Vars(𝑔) = {𝑦}, so 𝛿 𝑔 𝑘 = 0 for 𝑘 ⩾ 2, while 𝛿 𝑔 0 = Π Vars(𝑔) (∅) = 1 -𝑝 𝑦 and 𝛿 𝑔 1 = Π Vars(𝑔) ({𝑦}) = 𝑝 𝑦 . Negation gates. Let 𝑔 be a ¬-gate with input 𝑔 ′ . Notice that Vars(𝑔) = Vars(𝑔 ′ ). So we have 𝛿 𝑔 𝑘 = 𝛿 𝑔 ′ 𝑘 for all 𝑘 ∈ [𝑛 ′ ] and we are done since the values 𝛿 𝑔 ′ 𝑘 have already been computed inductively. Deterministic smooth ∨-gates. Let 𝑔 be a smooth deterministic ∨-gate with inputs 𝑔 1 , 𝑔 2 . Since 𝑔 is smooth we have Vars(𝑔) = Vars(𝑔 1 ) = Vars(𝑔 2 ). In particular we have 𝛿 𝑔 𝑘 = 𝛿 𝑔 1

Π

  3. □We next define ENV ★,★ -quantities for all gates of the circuit 𝐶 ′ . Definition B.4. For a gate 𝑔 ∈ 𝐶 ′ and 𝑘, ℓ ∈ [𝑛 ′ ], define Vars(𝑔) (𝑍 )𝐶 ′ 𝑔 (𝐸).

Lemma B. 5 .

 5 We can compute in 𝑂 (|𝐶 ′ | × 𝑛 ′4 ) all the quantities 𝛼 𝑔 𝑘,ℓ .Proof. This is again done by bottom-up induction on 𝐶 ′ .Constant gates. Let 𝑔 be a constant gate. Then Vars(𝑔) = ∅, so 𝛼 𝑔 𝑘,ℓ = 0 when (𝑘, ℓ) ≠ (0, 0), and 𝛼 𝑔 0,0 = 1 if 𝑔 is a constant 1-gate and 𝛼 𝑔 0,0 = 0 if it is a constant 0-gate.Input gates. Let 𝑔 be input gate, with variable 𝑦. Then Vars(𝑔) = {𝑦}, so all values other than 𝛼 𝑔

1 |Π 3 Proposition 4 . 3 .𝐸××

 1343 and |𝐶 0 | are in 𝑂 (|𝐶 | × |𝑉 |) by Lemma 4.1.What remains to argue is that the number of bits (numerator and denominator) of all the 𝛼 and 𝛿 values stays polynomial. But for 𝛼 Vars(𝑔) (𝑍 )𝐶 ′ 𝑔 (𝐸)⩽ 2 2|𝑉 | max 𝑍 ⊆Vars(𝑔) Π Vars(𝑔) (𝑍 ).If the number of bits of all numerators and denominators of all 𝑝 𝑥 is bounded by 𝑏, then the numerator of𝛼 𝑔 𝑘,ℓ is bounded by 2 2|𝑉 | 2 𝑏 |𝑉 | = 2 (𝑏+2) |𝑉 | ,so indeed have a polynomial number of bits for the numerators, and similar reasoning works for denominators and for the 𝛿 values. B.2 Proof of Proposition 4.Let 𝑐 be a tractable coefficient function. Given a d-D 𝐶 on variables 𝑉 , a unique probability value 𝑝 = 𝑝 𝑦 for all 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , EScore 𝑐 (𝐶, 𝑥) can be computed in time 𝑂 |𝑉 | 2 × (|𝐶 ||𝑉 | + |𝑉 | 2 + T 𝑐 (|𝑉 |)) assuming unit-cost arithmetic. Proof. To prove Proposition 4.3 we consider a d-D circuit 𝐶 over variables 𝑉 with 𝑛 = |𝑉 |. For a variable 𝑥 ∈ 𝑉 , EScore 𝑐 (𝐶, 𝑥) = ∑ 𝑍 ⊆𝑉 𝑥 ∈𝑍 Π 𝑉 (𝑍 ) × Score 𝑐 (𝐶, 𝑍, 𝑥) = ∑ 𝑍 ⊆𝑉 𝑥 ∈𝑍 Π 𝑉 (𝑍 ) ∑ 𝐸 ⊆𝑍 \{𝑥 } 𝑐 (|𝑍 |, |𝐸|) × [𝐶 (𝐸 ∪ {𝑥 }) -𝐶 (𝐸)] ⊆𝑍 ⊆𝑉 \{𝑥 }𝑐 (|𝑍 | + 1, |𝐸|) × 𝑝 𝑥 × Π 𝑉 (𝑍 ) + 1, ℓ) × 𝑝 𝑘+1 (1 -𝑝) 𝑛-𝑘 -1 𝑐 (𝑘 + 1, ℓ) × 𝑝 𝑘+1 (1 -𝑝) 𝑛-𝑘 -1 ∑ 𝐸 ⊆𝑉 \{𝑥 } |𝐸 |=ℓ[𝐶 (𝐸 ∪ {𝑥 }) -𝐶 (𝐸)] ℓ (𝐶 1 ) -#SAT ℓ (𝐶 0 )] 𝑐 (𝑘 + 1, ℓ) × 𝑝 𝑘+1 (1 -𝑝) 𝑛-𝑘 -1

4 4. 4 .

 44 5 of this paper), we can show that all the #SATℓ (𝐶 ′ ) values for a tight circuit 𝐶 ′ over variables |𝑉 ′ | can be computed in 𝑂 (|𝐶 ′ | × |𝑉 ′ | 2 ). So, to compute all #𝑆𝐴𝑇 ℓ (𝐶 0 ), we first need to make it tight (in 𝑂 (|𝐶 | × |𝑉 |)) and then we have a cost of 𝑂 (|𝐶 | × |𝑉 | 3 ).Now, to compute the rest of the sum, we need to compute for every ℓ and 𝑘 a binomial coefficient in 𝑂 (𝑛 2 ), a value of the coefficient function in 𝑂 (T 𝑐 (𝑛)) and perform the other multiplications in 𝑂 (1) assuming unit cost arithmetic. We obtain thus an algorithm in𝑂 |𝐶 | × |𝑉 | 3 + |𝑉 | 2 × (|𝑉 | 2 + T 𝑐 (|𝑉 |)) . □ B.3 Proof of Theorem 4.Given a d-D 𝐶 on variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , we can compute in time 𝑂 (|𝐶 | × |𝑉 |) (ignoring the cost of arithmetic operations) the quantity EScore 𝑐 Banzhaf (𝐶, 𝑥).

𝑔 𝑘 values (line 3 -

 3 14) so we only need to discuss the cost of computing 𝛽 𝑔 𝑘,ℓ and 𝛾 𝑔 𝑘,ℓ (lines 15-31) on the one hand, and of line 32 on the other hand. Further, recall that only the setting where 𝑘 = |Vars(𝑔)| is relevant. This means that the main loop to compute 𝛽 and 𝛾 values is run |Vars(𝑔)| times instead of |Vars(𝑔)| 2 times, and furthermore, that in the case where 𝑔 is an ∧-gate, its computation involves a single sum, as we can set 𝑘 1 to be |Vars(𝑔 1 )| (and thus 𝑘 2 to be |Vars(𝑔 2 )|) on lines 29 and 30. Finally, on line 32, similarly, we only have one sum operator as 𝛽 𝑔 out 𝑘,ℓ and 𝛾 𝑔 out 𝑘,ℓ are zero when 𝑘 ≠ |Vars(𝑔 out )|. Remember that since the circuit needs to be made tight, its size is 𝑂 (|𝐶 | × |𝑉 |). We therefore have for complexity: 𝑂 |𝐶 | × |𝑉 | × |𝑉 | 2 + |𝑉 | × T 𝑐 Shapley (|𝑉 |) = 𝑂 |𝐶 | × |𝑉 | 3 + |𝑉 | × |𝑉 | 2 = 𝑂 |𝐶 | × |𝑉 | 3 .

  Let 𝑧 0 , . . . , 𝑧 𝑛 be 𝑛 + 1 distinct positive values in Q. For 𝑖 ∈ [𝑛] and 𝑥 ∈ 𝑉 , define 𝑐 𝑧 𝑖 𝑥 def = 2𝑧 𝑖 𝑝 𝑥 + 1 -𝑝 𝑥 and 𝑝 𝑧 𝑖 𝑧 𝑖 and EV 𝑧 𝑖 (𝜑) as expected. Notice that these are all valid probability mappings, i.e., all values 𝑝 𝑧 𝑖 𝑥 are well-defined and between 0 and 1, and observe that 1 -𝑝 𝑧 𝑖 𝑥 =

			𝑥	def =	𝑧 𝑖 𝑝 𝑥 𝑥 𝑐 𝑧 𝑖	,
	and define Π (𝑧 𝑖 𝑝 𝑥 )+(1-𝑝 𝑥 ) 𝑥 𝑐 𝑧 𝑖	. Define
	further 𝐶 𝑧 𝑖	def = 𝑥 ∈𝑉 𝑐 𝑧 𝑖 𝑥 . Then:
	EV 𝑧 𝑖 ℓ (𝜑) =	∑
			𝐸 ⊆𝑉
			|𝐸 |=ℓ

the oracle to EV ★ (F ), we compute 𝑐 𝑖 def = 𝐶 𝑧 𝑖 × EV 𝑧 𝑖 ℓ (𝜑) for 𝑖 ∈ [𝑛] in polynomial time. By Equation (2), this gives us a system of linear equations 𝐴𝑋 = 𝐶, with 𝐶 𝑖 def = 𝑐 𝑖 , 𝑋 𝑗 def = ENV 𝑗,ℓ (𝜑) and 𝐴 𝑖 𝑗 def=

  𝑧 𝑖 𝑗 . We see that 𝐴 is a non-singular Vandermonde matrix, so we can in polynomial time recover all the values 𝑋 𝑗 and return ENV 𝑘,ℓ (𝜑), as promised. This concludes the proof. □

  score. Let us call a class of Boolean functions F reasonable if the following problem is in P: given as input (a representation of) 𝜑 ∈ F , compute 𝜑 (∅). It is clear that all classes mentioned in this paper are reasonable in that sense. Then, under this assumption: Proposition 3.5. We have EV(F ) ⩽ P EScore 𝑐 Shapley (F ) for any reasonable class F of Boolean functions.Proof. For 𝜑 : 2 𝑍 → {0, 1}, it is well known that the following equation, called the efficiency property, holds: ∑

		Score 𝑐 Shapley (𝜑, 𝑍, 𝑥) = 𝜑 (𝑍 ) -𝜑 (∅).
		𝑥 ∈𝑍
	Let then 𝜑 ∈ F over variables 𝑉 and probability values 𝑝 𝑥 for each
	𝑥 ∈ 𝑉 ; our goal is to compute EV(𝜑). We have:
	∑	EScore 𝑐 Shapley (𝜑, 𝑥) =	∑	∑	Π 𝑉 (𝑍 ) × Score 𝑐 Shapley (𝜑, 𝑍, 𝑥)
	𝑥 ∈𝑉		𝑥 ∈𝑉	𝑍 ⊆𝑉
				𝑥 ∈𝑍
		=	∑	∑	Π 𝑉 (𝑍 ) × Score 𝑐 Shapley (𝜑, 𝑍, 𝑥)
			𝑍 ⊆𝑉	𝑥 ∈𝑍

  We have ENV(F ) ⩽ P EScore 𝑐 Banzhaf (F ) for any F closed under conjunctions (resp., disjunctions) with fresh variables. Proof sketch. First, for 𝜑 ′ : 2 𝑉 ′ → {0, 1} and 𝑥 ∈ 𝑉 ′ , we prove the equation EScore 𝑐 Banzhaf (𝜑 ′ , 𝑥) = 𝑝 𝑥 [ENV(𝜑 ′ +𝑥 ) -ENV(𝜑 ′ -𝑥 )].

		EScore 𝑐 Banzhaf is intractable, for instance, over
	monotone 2-CNFs or monotone 2-DNFs.
	Proposition 3.8 requires more work than Proposition 3.5: we do
	it in two steps by introducing (yet) another intermediate problem.
	PROBLEM : ENV(F )	(Expected Nested Value)
	INPUT :	A Boolean function 𝜑 ∈ F over variables 𝑉 and
		probability values 𝑝 𝑥 for each 𝑥 ∈ 𝑉
	OUTPUT : The quantity
		ENV(𝜑)	def = 𝑍 ⊆𝑉 Π 𝑉 (𝑍 ) 𝐸 ⊆𝑍 𝜑 (𝐸)
	The next two lemmas then imply Proposition 3.8.
	Lemma 3.9.

  Expected Shapley-like scores for deterministic and decomposable Boolean circuits Input : A d-D 𝐶 on variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 . Output : The value EScore 𝑐 (𝐶, 𝑥) 1 Let 𝑛 ′ = |𝑉 | -1 and let 𝑔 out be the output gate of 𝐶; 2 Make 𝐶 tight using Lemma 4.1, and call it 𝐶 again; 3 Compute values 𝛿 𝑔 𝑘 for every gate 𝑔 in 𝐶 and 𝑘 ∈ [𝑛 ′ ] by bottom-up induction on 𝐶 as follows:

	13	𝛿	𝑔 𝑘 ← 𝑘 𝑘 1 =0 𝛿	𝑔 1 𝑘 1	𝛿	𝑔 2 𝑘 -𝑘 1	for 𝑘 ∈ [𝑛 ′ ];
	14 end
	15 Compute values 𝛽

can show that ENV can be computed in linear time over tight d-D circuits, thus obtaining a 𝑂 (|𝐶 |×|𝑉 |) complexity for EScore 𝑐 Banzhaf over arbitrary d-D circuits by Lemma 4.1: Algorithm 1: 4 if 𝑔 is a constant gate or a variable gate with Vars(𝑔) = {𝑥 } then 5 𝛿 𝑔 0 ← 1 and 𝛿 𝑔 𝑘 ← 0 for 𝑘 ⩾ 1; 6 else if 𝑔 is a variable gate with Vars(𝑔) = {𝑦} and 𝑦 ≠ 𝑥 then 7 𝛿 𝑔 0 ← 1 -𝑝 𝑦 , 𝛿 𝑔 1 ← 𝑝 𝑦 , and 𝛿 𝑔 𝑘 ← 0 for 𝑘 ⩾ 2; 8 else if 𝑔 is a ¬-gate with input gate 𝑔 ′ then 9 𝛿 𝑔 𝑘 ← 𝛿 𝑔 ′ 𝑘 for 𝑘 ∈ [𝑛 ′ ]; 10 else if 𝑔 is an ∨-gate with input gates 𝑔 1 , 𝑔 2 then 11 𝛿 𝑔 𝑘 ← 𝛿 𝑔 1 𝑘 for 𝑘 ∈ [𝑛 ′ ]; 12 else if 𝑔 is an ∧-gate with input gates 𝑔 1 , 𝑔 2 then 𝑔 𝑘,ℓ and 𝛾 𝑔 𝑘,ℓ for every gate 𝑔 in 𝐶 and 𝑘, ℓ ∈ [𝑛 ′ ] by bottom-up induction on 𝐶: 16 if 𝑔 is a constant 𝑎-gate (𝑎 ∈ {0, 1}) then

  , 𝛾

						𝑔 1,1 ← 𝑝 𝑥 , and
			𝛽	𝑔 𝑘,ℓ , 𝛾	𝑔 𝑘,ℓ ← 0 for all other values of 𝑘, ℓ;
	23 𝑔 24 𝛽 𝑔 𝑘,ℓ ← 𝑘 ℓ 𝛿 𝑔 𝑘 -𝛽 𝛾 𝑔 𝑘,ℓ ← 𝑘 ℓ 𝛿 𝑔 𝑘 -𝛾 𝑔 𝑔 1 𝑘,ℓ + 𝛽 𝑔 2 𝑘,ℓ for 𝑘, ℓ ∈ [𝑛 ′ ];
	27	𝛾	𝑔 𝑘,ℓ ← 𝛾	𝑔 1 𝑘,ℓ + 𝛾	𝑔 2

22 else if 𝑔 is a ¬-gate with input gate 𝑔 ′ then ′ 𝑘,ℓ for 𝑘, ℓ ∈ [𝑛 ′ ]; ′ 𝑘,ℓ for 𝑘, ℓ ∈ [𝑛 ′ ]; 25 else if 𝑔 is an ∨-gate with input gates 𝑔 1 , 𝑔 2 then 26 𝛽 𝑔 𝑘,ℓ ← 𝛽 𝑘,ℓ for 𝑘, ℓ ∈ [𝑛 ′ ]; 28 else if 𝑔 is an ∧-gate with input gates 𝑔 1 , 𝑔 2 then 29

  Lemma 3.2. We have EScore 𝑐 (F ) ⩽ P ENV ★,★ (F ) for any tractable coefficient function 𝑐 and any class of Boolean functions F .Proof. Let 𝜑 : 2 𝑉 → {0, 1} in F , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 . We wish to compute EScore 𝑐 (𝜑, 𝑥). Observe that EScore 𝑐 (𝜑, 𝑥) = 𝐴 -𝐵, where Let us focus on 𝐴. Letting 𝑉 ′ def = 𝑉 \ {𝑥 }, notice that these are the variables over which 𝜑 +𝑥 is defined. Letting 𝑛

	𝐴 =	∑	Π 𝑉 (𝑍 )	∑	𝑐 (|𝑍 |, |𝐸|)𝜑 (𝐸 ∪ {𝑥 })
			𝑍 ⊆𝑉 𝑥 ∈𝑍		𝐸 ⊆𝑍 \{𝑥 }
	𝐵 =	∑	Π 𝑉 (𝑍 )	∑	𝑐 (|𝑍 |, |𝐸|)𝜑 (𝐸).
			𝑍 ⊆𝑉 𝑥 ∈𝑍		𝐸 ⊆𝑍 \{𝑥 }
						def = |𝑉 ′ |, we have
	𝐴 =	∑	Π 𝑉 (𝑍 )	∑	𝑐 (|𝑍 |, |𝐸|)𝜑 +𝑥 (𝐸)
		𝑍 ⊆𝑉 𝑥 ∈𝑍		𝐸 ⊆𝑍 \{𝑥 }

  1-𝑝 𝑥 , and define Π 𝑧 𝑖 and EV 𝑧 𝑖 (𝜑) as expected. Again, these are all valid probability mappings. Define 𝐶 def = 𝑥 ∈𝑉 (1 -𝑝 𝑥 ). We will show that we have ENV 𝑧 𝑖 (𝜑) = 1 𝑗 (𝜑), which allows us to conclude as in the proof of Lemma 3.3. Indeed:ENV 𝑧 𝑖 (𝜑) = ∑ 𝑝 𝑥 -𝑧 𝑖 𝑝 𝑥 ) 𝑖 𝑝 𝑥 ) + (1 -𝑝 𝑥 -𝑧 𝑖 𝑝 𝑥 )]Theorem 4.2. Let 𝑐 be a tractable coefficient function. Given a d-D circuit 𝐶 on variables 𝑉 , probability values 𝑝 𝑦 for 𝑦 ∈ 𝑉 , and 𝑥 ∈ 𝑉 , Algorithm 1 correctly computes EScore 𝑐 (𝐶, 𝑥) in polynomial time. Moreover, if we ignore the cost of arithmetic operations, it is in time 𝑂 |𝐶 | × |𝑉 |

	𝐶	𝑛 𝑗=0 𝑧	𝑗 𝑖 EV 𝑍 ⊆𝑉	Π 𝑧 𝑖 𝑉 (𝑍 )	𝐸 ⊆𝑍 ∑	𝜑 (𝐸)
			=	∑	𝜑 (𝐸)	∑	Π 𝑧 𝑖 𝑉 (𝑍 )
				𝐸 ⊆𝑉		𝐸 ⊆𝑍 ⊆𝑉
			=	∑	𝜑 (𝐸)	∑	𝑝 𝑧 𝑖 𝑥	(1 -𝑝 𝑧 𝑖 𝑥 )
				𝐸 ⊆𝑉		𝐸 ⊆𝑍 ⊆𝑉 𝑥 ∈𝑍	𝑥 ∈𝑉 \𝑍
			= (1 -= 1 𝐶 ∑ 𝐸 ⊆𝑉 𝜑 (𝐸) ∑ 𝐸 ⊆𝑍 ⊆𝑉 𝑥 ∈𝑍 𝑧 𝑖 𝑝 𝑥 𝑥 ∈𝑉 \𝑍 1 𝐶 ∑ 𝐸 ⊆𝑉 𝜑 (𝐸) 𝑥 ∈𝐸 𝑧 𝑖 𝑝 𝑥 𝑥 ∈𝑉 \𝐸 [(𝑧 = 1 ∑ 𝜑 (𝐸) 𝑧 𝑖 𝑝 𝑥 (1 -𝑝 𝑥 )
				𝐶	𝐸 ⊆𝑉	𝑥 ∈𝐸	𝑥 ∈𝑉 \𝐸
					𝑛
			=	1 𝐶	𝑗=0 ∑	𝐸 ⊆𝑉 ∑	𝑧	𝑗 𝑖 Π 𝑉 (𝐸)𝜑 (𝐸)
							|𝐸 |=𝑗
					𝑛
			=	1 𝐶	∑	𝑧	𝑗 𝑖 EV 𝑗 (𝜑).	□
					𝑗=0
	B PROOFS FOR SECTION 4 (DD CIRCUITS)
	B.1 Proof of Theorem 4.2

  = 𝑝 𝑦 . Negation gates. Let 𝑔 be a ¬-gate with input 𝑔 ′ . Notice that Vars(𝑔) = Vars(𝑔 ′ ) and that 𝐶 ′ 𝑔 (𝐸) = 1 -𝐶 ′ 𝑔 ′ (𝐸) for any 𝐸 ⊆ Vars(𝑔). We have Deterministic smooth ∨-gates. Let 𝑔 be a smooth deterministic ∨-gate with inputs 𝑔 1 , 𝑔 2 . Since 𝑔 is smooth we have Vars(𝑔) = Vars(𝑔 1 ) = Vars(𝑔 2 ), and since it is deterministic we have 𝐶 ′ 𝑔 (𝐸) = 𝐶 ′ 𝑔 1 (𝐸) + 𝐶 ′ 𝑔 1 (𝐸) for any 𝐸 ⊆ Vars(𝑔). Therefore we obtain 𝛼 𝑘,ℓ and we are done. Decomposable ∧-gates. Let 𝑔 be a decomposable ∧-gate with inputs 𝑔 1 , 𝑔 2 . Notice that Vars(𝑔) = Vars(𝑔 1 ) ∪ Vars(𝑔 2 ) with the union being disjoint, and that 𝐶 ′ 𝑔(𝐸) = 𝐶 ′ 𝑔 1 (𝐸 ∩ Vars(𝑔 1 )) × 𝐶 ′ 𝑔 2 (𝐸 ∩ Vars(𝑔 2 )) and Π Vars(𝑔) (𝑍 ) = Π Vars(𝑔 1 ) (𝑍 ∩ Vars(𝑔 1 )) × Π Vars(𝑔 2 ) (𝑍 ∩ Vars(𝑔 2)) for any 𝑍, 𝐸 ⊆ Vars(𝑔). We decompose the summations over 𝑍 and 𝐸 as we did in the proof of Lemma B.3 for ∧-gates. For readability we use colors to point out which parts of the expressions are modified or moved around.

						𝛼	𝑔 𝑘,ℓ =	∑	∑	Π Vars(𝑔) (𝑍 )(1 -𝐶 ′ 𝑔 ′ (𝐸))
						𝑍 ⊆Vars(𝑔)	𝐸 ⊆𝑍
						|𝑍 |=𝑘	|𝐸 |=ℓ
						=	𝑘 ℓ	𝑍 ⊆Vars(𝑔) ∑	Π Vars(𝑔) (𝑍 ) -𝛼	𝑔 ′ 𝑘,ℓ
						|𝑍 |=𝑘
						=	𝑘 ℓ	𝛿	𝑔 𝑘 -𝛼	𝑔 ′ 𝑘,ℓ ,
	and we are done thanks to Lemma B.3.
	𝑔 𝑘,ℓ = 𝛼	𝑔 1 𝑘,ℓ + 𝛼	𝑔 2
		𝛼	𝑔 𝑘,ℓ =	∑	∑
					𝑍 ⊆Vars(𝑔)	𝐸 ⊆𝑍
					|𝑍 |=𝑘	|𝐸 |=ℓ

  ∑Notice that we want 𝛼 𝑔 for 𝑔 the output gate of 𝐶 ′ . We show next how this can be done.Constant gates. Let 𝑔 be a constant gate. Then Vars(𝑔) = ∅, so 𝛼 𝑔 equals 1 if 𝑔 is a constant 1-gate and 0 if it is a constant 0-gate. Input gates. Let 𝑔 be an input gate, with variable 𝑦. Then Vars(𝑔) = {𝑦}, so 𝛼 𝑔 = 𝑝 𝑦 . Negation gates. Let 𝑔 be a ¬-gate with input 𝑔 ′ . Then 𝐶 ′ 𝑔(𝐸) = 1 -𝐶 ′ 𝑔 1 (𝐸), therefore 𝛼 𝑔 = 𝑍 ⊆Vars(𝑔) Π Vars(𝑔) (𝑍 ) 𝐸 ⊆𝑍 1 -𝛼 𝑔 ′ .We have already observed in the proof of Lemma 3.9 that the first term is equal to 𝑦 ∈Vars(𝑔)(1 + 𝑝 𝑦 ), therefore we obtain 𝛼 𝑔 = 𝑦 ∈Vars(𝑔) (1 + 𝑝 𝑦 ) -𝛼 𝑔 ′ . Deterministic smooth ∨-gates. Let 𝑔 be a smooth deterministic ∨-gate with inputs 𝑔 1 , 𝑔 2 . Since 𝑔 is smooth we have Vars(𝑔) = Vars(𝑔 1 ) = Vars(𝑔 2 ), and since it is deterministic we have 𝐶 ′ 𝑔 (𝐸) = 𝐶 ′ 𝑔 1 (𝐸) + 𝐶 ′ 𝑔 2 (𝐸). Therefore 𝛼 𝑔 = 𝛼 𝑔 1 + 𝛼 𝑔 2 . Decomposable ∧-gates. Let 𝑔 be a decomposable ∧-gate with inputs 𝑔 1 , 𝑔 2 . We decompose the sum similarly to what we did in the proof of Theorem 4.2: Vars(𝑔 1 ) (𝑍 1 )Π Vars(𝑔 2 ) (𝑍 2 ) ∑ 𝐶 ′ 𝑔 1 (𝐸 1 )𝛼 𝑔 2 = 𝛼 𝑔 2 ∑

						Π Vars(𝑔) (𝑍 )	∑	𝐶 ′ 𝑔 (𝐸).
				𝑍 ⊆Vars(𝑔)		𝐸 ⊆𝑍
	𝛼 𝑔 =	∑	Π Vars(𝑔) (𝑍 )	∑	𝐶 ′ 𝑔 (𝐸)
		𝑍 ⊆Vars(𝑔)		𝐸 ⊆𝑍
	=	∑
										∑	𝐶 ′ 𝑔 1 (𝐸 1 )𝐶 ′ 𝑔 2 (𝐸 2 )
									𝐸 1 ⊆𝑍 1	𝐸 2 ⊆𝑍 2
	=	∑	Π Vars(𝑔 1 ) (𝑍 1 )	∑	𝐶 ′ 𝑔 1 (𝐸 1 )	∑	Π Vars(𝑔 2 ) (𝑍 2 )	∑	𝐶 ′ 𝑔 2 (𝐸 2 )
		𝑍 1 ⊆Vars(𝑔 1 )	𝐸 1 ⊆𝑍 1		𝑍 2 ⊆Vars(𝑔 2 )	𝐸 2 ⊆𝑍 2
	=	∑	Π Vars(𝑔 1 ) (𝑍 1 )	∑
		𝑍 1 ⊆Vars(𝑔 1 )	𝐸 1 ⊆𝑍 1

𝑍 1 ⊆Vars(𝑔 1 ) ∑ 𝑍 2 ⊆Vars(𝑔 2 ) Π Vars(𝑔) (𝑍 1 ∪ 𝑍 2 ) ∑ 𝐸 1 ⊆𝑍 1 ∑ 𝐸 2 ⊆𝑍 2 𝐶 ′ 𝑔 (𝐸 2 ∪ 𝐸 2 ) = ∑ 𝑍 1 ⊆Vars(𝑔 1 ) ∑ 𝑍 2 ⊆Vars(𝑔 2 )

Π 𝑍 1 ⊆Vars(𝑔 1 )

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

We point out that the facts of 𝐷 are traditionally partitioned between endogenous and exogenous facts, but we do not make this distinction in our work. This is to simplify the presentation, as usual definitions would extend in a straightforward manner.

The corresponding code will be made freely available when anonymity requirements are removed.

https://github.com/navefr/ShapleyForDbFacts

A different method might be used for each output tuple; we report the proportion of "dec. " when the obtained circuit was already decomposable; and of "tree dec. " when we used the tree decomposition approach; none of the circuits produced required using an external knowledge compiler.

By relevant facts, we mean here the facts that appear in the provenance circuits. Indeed, the other facts have a score of zero.

So one could say that expected Shapley scores are to Shapley scores what probabilistic query evaluation is to non-probabilistic query evaluation.


M Heydari-Malayeri

C Reylé

R Samadi

F Meynadier

F Crifo

D Katz

F Thévenin

Delle Luche

A Doressoundiram

A Gomez

A Guerrier

D Hestroffer

A.-M Hubert

G Jasniewicz

H Ludwig

A.-T Nguyen

P Ocvirk

F Royer

P Sartoretti

A Siebert

C Soubiran

C Turon

L Veltz

SF2A 2009

This poster describes the current organisation of RVS data processing among the Gaia-DPAC (Data Processing & Analysis Consortium), with a particular focus on the French community's contribution.

Introduction

The Radial Velocity Spectrometer (RVS) is a slitless spectrometer which will operate in the Gaia satellite. As its name suggests it will, amongst other tasks, determine the radial velocity of a large number of sources (100 to 200 million) : this will give us access to the only component of the star's velocity which can not be determined by astrometry. It has to be noted that measuring radial velocity simultaneously with astrometric and photometric parameters measurements is a significant improvement over Gaia's precursor, the Hipparcos mission.

RVS Data reduction within the global GAIA data reduction scheme

The Gaia Data Processing & Analysis Consortium (DPAC) is organised into several coordination units which cover the whole data processing chain. One of these coordination units, CU6, is devoted to the RVS data processing, taking almost raw instrumental data as input. Its output is then directed to the Main Database (which will feed the catalogue) and to other scientific chains for further analysis.

In practice, the CU6 algorithms will be run at the CNES Data Processing Center which will also host CU4 (Object processing) and CU8 (Astrophysical Parameters) software. The CNES is responsible for integrating the software modules written by scientists in Java, and running them on dedicated hardware.

Processing chain

The processing chain is divided into 5 packages : Extraction, calibration, radial velocity zero-point, single transit analysis and multiple transits analysis.

The first step is to retrieve pixel blocks, disentangle overlapping objects, remove contaminants and perform appropriate geometric transformations in order to output a cleaned 1D spectrum.

The calibration step is indeed a self-calibration, as there is no internal calibration source. This self-calibration relies on redundant observations throughout the mission.

SF2A 2009

Zero-point determination for radial velocities supposes a wide search for RV standard stars with homogeneous coverage of the sky. This is currently performed by several ground-based observation programmes, which data will be compared to RVS measurements in order to settle the RV zero-point (see poster by Crifo et al., this meeting).

"Single Transit Analysis" (STA) consists in fitting template spectra to the measured spectra, thus determining the source's radial velocity for each "transit" (meaning "each time the source passes across the focal plane").

"Multiple Transit Analysis" (MTA) gathers data from STA every 6 months and performs additional analysis (such as variability detection and basic modelling).

Scientific objectives

Fig. 1. Uncertainty on RV determination as a function of spectral type and V magnitudes, as derived from RVS performance simulations. This radial velocity survey will cover the whole sky up to 17th magnitude for late type stars, which show the strongest lines in the RVS spectral range. For a given magnitude, RV will therefore be more accurately determined for solar-type stars. This survey will contribute to our knowledge of the Galaxy's kinematics and dynamics, but the spectra will also bring some information about effective temperature and surface gravity. Some emission lines will also be detected and will help characterizing B[e] stars or stars with envelopes or accretion discs. Other goals are reachable when analysing RVS data together with photometric data collected by the BP/RP instrument : chemical abundances will be determined for a large number of sources, which will allow to study their distribution and therefore bring insights about the dynamical and chemical of the galaxy, origin of the halo, the search for extremely metal-poor objects, studies of the thick disk. Open questions like the existence of a vertical chemical gradient in the disk may be addressed, and the chemical aspects of stellar associations and streams that Gaia will find will be studied.

French involvement

The French astrophysical community is strongly represented in the RVS data processing preparation, in collaboration with (mainly) UK (Mullard Space Science Laboratory) and Belgium (Observatoire Royal, Institut d'Astrophysique et de Géophysique).

David Katz (GEPI-Observatoire de Paris) is the coordinator of this unit, assisted by Mark Cropper (MSSL, UK) and Frédéric Meynadier (GEPI). The first two steps of the processing chain (extraction and calibration) as well as MTA are under MSSL responsibility; zero-point determination is led by Gérard Jasniewicz (GRAAL, Université de Montpellier) and STA is led by Yves Viala (GEPI). Specific CU6 simulations are realised by Paola Sartoretti (GEPI). On CNES side, technical coordinator Anne Jean-Antoine Piccolo and quality insurance manager Anne-Thérèse Nguyen are responsible for integrating and running the software for CU6.

Overall, the 26 persons whose names appear on this poster account for approximatively half of the people working for CU6 across Europe.