# On the Complexity of SHAP-Score-Based Explanations: Tractability via
Knowledge Compilation and Non-Approximability Results

Marcelo Arenas<EMAIL_ADDRESS>
(a) Department of Computer Science & Institute for Mathematical and
Computational Engineering,
School of Engineering & Faculty of Mathematics, Universidad Católica de Chile
(b) IMFD Chile
Pablo Barceló<EMAIL_ADDRESS>
(a) Institute for Mathematical and Computational Engineering,
School of Engineering & Faculty of Mathematics, Universidad Católica de Chile
(b) IMFD Chile (c) National Center for Artificial Intelligence, CENIA Chile
Leopoldo Bertossi<EMAIL_ADDRESS>
SKEMA Business School, Montreal, Canada
Mikaël Monet<EMAIL_ADDRESS>
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 - CRIStAL, F-59000 Lille,
France

###### Abstract

Scores based on Shapley values are widely used for providing explanations to
classification results over machine learning models. A prime example of this
is the influential $\mathsf{SHAP}$-score, a version of the Shapley value that
can help explain the result of a learned model on a specific entity by
assigning a score to every feature. While in general computing Shapley values
is a computationally intractable problem, we prove a strong positive result
stating that the $\mathsf{SHAP}$-score can be computed in polynomial time over
_deterministic and decomposable Boolean circuits_ under the so-called product
distributions on entities. Such circuits are studied in the field of Knowledge
Compilation and generalize a wide range of Boolean circuits and binary
decision diagrams classes, including binary decision trees, Ordered Binary
Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). Our
positive result extends even beyond binary classifiers, as it continues to
hold if each feature is associated with a finite domain of possible values.

We also establish the computational limits of the notion of SHAP-score by
observing that, under a mild condition, computing it over a class of Boolean
models is always polynomially as hard as the model counting problem for that
class. This implies that both determinism and decomposability are essential
properties for the circuits that we consider, as removing one or the other
renders the problem of computing the $\mathsf{SHAP}$-score intractable
(namely, $\\#\text{{P}}$-hard). It also implies that computing
$\mathsf{SHAP}$-scores is $\\#\text{{P}}$-hard even over the class of
propositional formulas in DNF. Based on this negative result, we look for the
existence of fully-polynomial randomized approximation schemes (FPRAS) for
computing $\mathsf{SHAP}$-scores over such class. In stark contrast to the
model counting problem for DNF formulas, which admits an FPRAS, we prove that
no such FPRAS exists (under widely believed complexity assumptions) for the
computation of $\mathsf{SHAP}$-scores. Surprisingly, this negative result
holds even for the class of monotone formulas in DNF. These techniques can be
further extended to prove another strong negative result: Under widely
believed complexity assumptions, there is no polynomial-time algorithm that
checks, given a monotone DNF formula $\varphi$ and features $x,y$, whether the
$\mathsf{SHAP}$-score of $x$ in $\varphi$ is smaller than the
$\mathsf{SHAP}$-score of $y$ in $\varphi$.

Keywords: Explainable AI, Shapley values, SHAP score, knowledge compilation,
FPRAS

##  1 Introduction

##### Context.

Explainable artificial intelligence has become an active area of research.
Central to it is the observation that artificial intelligence (AI) and machine
learning (ML) models cannot always be blindly applied without being able to
interpret or explain their results. For example, someone who applies for a
loan and sees the application rejected by an algorithmic decision-making
system would like to receive from the system an explanation for this decision.
In ML, explanations have been commonly considered for classification
algorithms, and there are different approaches. In particular, explanations
can be global – focusing on the general input/output relation of the model –,
or local – focusing on how individual features affect the decision of the
model for a specific input, as in the loan example above (Ribeiro et al.,
2016; Lundberg and Lee, 2017; Chen et al., 2018; Bertossi et al., 2020).
Recent literature has strengthened the importance of the latter by showing
their ability to provide explanations that are often overlooked by global
explanations (Molnar, 2020). In this work we concentrate on local
explanations.

One way to define local explanations is by considering feature values as
players in a coalition game that jointly contribute to the outcome. More
concretely, one treats a feature value’s contribution from the viewpoint of
game theory, and ties it to the question of how to properly distribute wealth
(profit) among collaborating players. This problem was approached in general
terms in Shapley (1953). One can use the established concepts and techniques
that he introduced in the context of cooperative game theory; and, more
specifically, use the popular Shapley value as a measure of the contribution
of a player to the common wealth associated with a multi-player game. It is
well known that the Shapley value possesses properties that cast it as natural
and intuitive. Actually, the Shapley value emerges as the only function that
enjoys those desirable properties (Roth, 1988). The Shapley value has been
widely applied in different disciplines, in particular in computer science
(Hunter and Konieczny, 2010; Michalak et al., 2013; Cesari et al., 2018;
Livshits et al., 2020, 2021); and in machine learning it has been applied to
the explanation of classification results, in its incarnation as the
_$\mathsf{SHAP}$ -score_ (Lundberg and Lee, 2017; Lundberg et al., 2020).
Here, the players are the feature values of an entity under classification.

In this paper, we concentrate on the _$\mathsf{SHAP}$ -score_ for
classification models. It has a clear, intuitive, combinatorial meaning, and
inherits all the good properties of the Shapley value. Accordingly, an
explanation for a classification result takes the form of a set of feature
values that have a high, hopefully maximum, _$\mathsf{SHAP}$ -score_. We
remark that $\mathsf{SHAP}$-scores have attracted the attention of the ML
community and have found several applications and extensions (Rathi, 2019;
Fidel et al., 2020; Bertossi et al., 2020; Merrick and Taly, 2020; Takeishi
and Kawahara, 2020; Covert and Lee, 2021; Kumar et al., 2020). However, its
fundamental and computational properties have not been investigated much.

##### Problems studied in the paper.

For a given classification model $M$, entity $\mathbf{e}$ and feature $x$, the
$\mathsf{SHAP}$-score $\mathsf{SHAP}(M,\mathbf{e},x)$ intuitively represents
the importance of the feature value $\mathbf{e}(x)$ to the classification
result $M(\mathbf{e})$. In its general formulation,
$\mathsf{SHAP}(M,\mathbf{e},x)$ is a weighted average of differences of
expected values of the outcomes (c.f. Section 2 for its formal definition).
Unfortunately, computing quantities that are based on the notion of Shapley
value is in general intractable. Indeed, in many scenarios the computation
turns out to be $\\#\text{{P}}$-hard (Faigle and Kern, 1992; Deng and
Papadimitriou, 1994; Livshits et al., 2021; Bertossi et al., 2020), which
makes the notion difficult to use – if not impossible – for practical purposes
(Arora and Barak, 2009). Therefore, natural questions are: “For what kinds of
classification models the computation of the $\mathsf{SHAP}$-score can be done
efficiently?”, “Can one obtain lower computational complexity if one has
access to the internals of the classification model?”, or again “In cases
where exact computation is intractable, can we efficiently approximate the
$\mathsf{SHAP}$-score?”.

In Lundberg et al. (2020) the claim is made that for certain models based on
decision trees the computation of the $\mathsf{SHAP}$-score is tractable. In
this work we go deeper into these results, in particular, formulating and
establishing them in precise terms, and extending them for a larger class of
classification models. We also identify classes of models for which
$\mathsf{SHAP}$-score computation is intractable. In such cases, we
investigate the problem of existence and computation of a good approximation
in the form of a fully polynomial-time randomized approximation scheme
(FPRAS). Recall that FPRAS are tractable procedures that return an answer that
is, with high probability, close to the correct answer.

Given the high computational complexity of the $\mathsf{SHAP}$-score, one
might try to solve related problems, other than the exact and approximate
computation of all the features’ scores, that could still be useful in
practice. For instance, we consider the problem that consists in deciding, for
a pair of feature values, which of the two has the highest score. This problem
could indeed be used to compute a ranking of (all or the highest)
$\mathsf{SHAP}$-scores, without computing them explicitly. We also address
this problem in this paper.

##### Model studied in the paper.

We focus mainly on binary classifiers with _binary feature values_ (i.e.,
propositional features that can take the values $0$ or $1$), and that return
$1$ (accept) or $0$ (reject) for each entity. We will call these _Boolean
classifiers_. The restriction to binary inputs can be relevant in many
practical scenarios where the features are of a propositional nature. Still,
we consider classifiers with possibly non-binary features, but binary
outcomes, in Section 4. The second assumption that we make is that the
underlying probability distributions on the population of entities are what we
call _product distributions_ , where each binary feature $x$ has a probability
$\mathrm{p}(x)$ of being equal to $1$, independently of the other feature
values. This includes, as a special case, the _uniform probability
distribution_ when each $\mathrm{p}(x)$ is $\frac{1}{2}$. Product
distributions are also known as fully-factorized in the literature (Van den
Broeck et al., 2021, 2022). They have received considerable attention in the
context of computing score-based explanations, as they combine good
computational properties with enough flexibility to model relevant practical
scenarios (Strumbelj and Kononenko, 2010; Datta et al., 2016; Lundberg and
Lee, 2017).

Positive results on the complexity of computation of $\mathsf{SHAP}$-scores in
the paper are obtained for Boolean classifiers defined as _deterministic and
decomposable Boolean circuits_. This is a widely studied model in _knowledge
compilation_ (Darwiche, 2001; Darwiche and Marquis, 2002). Such circuits
encompass a wide range of Boolean circuits and binary decision diagrams
classes that are considered in knowledge compilation, and more generally in
AI. For instance, they generalize binary decision trees, ordered binary
decision diagrams (OBDDs), free binary decision diagrams (FBDDs), and
deterministic and decomposable negation normal norms (d-DNNFs) (Darwiche,
2001; Amarilli et al., 2020; Darwiche and Hirth, 2020). These circuits are
also known under the name of tractable Boolean circuits, that is used in
recent literature (Shih et al., 2019a; Shi et al., 2020; Shih et al., 2018a,
b, 2019b; Peharz et al., 2020). Readers who are not familiar with knowledge
compilation can simply think about deterministic and decomposable circuits as
a tool for analyzing in a uniform manner the computational complexity of the
$\mathsf{SHAP}$-score on several Boolean classifier classes.

In turn, our negative results on the complexity of computation of
$\mathsf{SHAP}$-scores in the paper are obtained over the class of
propositional formulas in DNF. In addition to being a well-known restriction
of the class of propositional formulas for which the satisfiability problem is
tractable, DNF formulas define an extension of deterministic and decomposable
Boolean circuits. In fact, DNF formulas can be seen as decomposable, although
not necessarily deterministic, Boolean circuits.

##### Our results.

Our main contributions are the following.

  1. 1.

Tractability for a large class of Boolean classifiers. We provide a polynomial
time algorithm that computes the $\mathsf{SHAP}$-score for deterministic and
decomposable Boolean circuits under product distributions over the entity
population (Theorem 2). We obtain as a corollary that the
$\mathsf{SHAP}$-score for Boolean classifiers given as binary decision trees,
OBDDs, FBDDs and d-DNNFs can be computed in polynomial time.

  2. 2.

Tractability for non-binary classifiers. We extend the aforementioned
tractability result to the case of classifiers with non-binary features, which
take the form of non-binary Boolean circuits (Theorem 5). In these circuits,
the nodes may now contain equalities of the form $x=v$, where $x$ is a
feature, and $v$ is a value in the domain of $x$. The outcome of the
classifier is still binary.

  3. 3.

Limits of tractability. We observe that, under a mild condition, computing the
$\mathsf{SHAP}$-score on Boolean classifiers in a class is always polynomially
as hard as the model counting problem for that class (Lemma 7). This leads to
intractability for the problem of computing the $\mathsf{SHAP}$-score for all
classes of Boolean classifiers for which model counting is intractable. An
important example of this corresponds to the class of propositional formulas
in DNF. As a corollary, we obtain that each one of the determinism assumption
and the decomposability assumption is necessary for tractability (Theorem 6).
These results even hold for the uniform distribution.

  4. 4.

Non-approximability for DNF formulas. We give a simple proof that, under
widely believed complexity assumptions, there is no FPRAS for the computation
of the $\mathsf{SHAP}$-score with Boolean classifiers represented as DNF
formulas (Proposition 8). This holds even under the uniform distribution. This
result establishes a stark contrast with the model counting problem for DNF
formulas, which admits an FPRAS (Karp et al., 1989). We further strengthen
this by showing that the non-approximability result even holds for Boolean
formulas represented as 2-POS-DNF, i.e., with every conjunct containing at
most two positive literals (and no negative literal), and for the uniform
distribution (Theorem 9). The proof of this last result is quite involved and
is based on a non-approximability result in relation to the size of cliques in
graphs (Feige et al., 1996; Arora and Safra, 1998; Arora et al., 1998).

  5. 5.

Impossibility of comparing $\mathsf{SHAP}$-scores for DNF formulas. Consider
the problem of verifying, given a DNF formula $\varphi$ and features $x,y$,
whether the $\mathsf{SHAP}$-score of $x$ in $\varphi$ is smaller than the
$\mathsf{SHAP}$-score of $y$ in $\varphi$. Under widely believed complexity
assumptions, we establish that this problem of comparing two
$\mathsf{SHAP}$-scores cannot be approximated in polynomial time, even for the
case of monotone DNF formulas (Theorem 16).

##### Related work.

Our contributions should be compared to the results obtained in
contemporaneous papers by Van den Broeck et al. (Van den Broeck et al., 2021,
2022). There, the authors establish the following theorem: for every class
$\mathcal{C}$ of classifiers and under product distributions, the problem of
computing the $\mathsf{SHAP}$-score for $\mathcal{C}$ is polynomial-time
equivalent to the problem of computing the expected value for the models in
$\mathcal{C}$ (at least under mild assumptions on $\cal C$). Since computing
expectations is in polynomial time for tractable Boolean circuits, this in
particular implies that computing the $\mathsf{SHAP}$-score is in polynomial
time for the circuits that we consider; in other words, their results capture
our main positive result. However, there is a fundamental difference in the
approach taken to show tractability: their reduction uses multiple oracle
calls to the problem of computing expectations, whereas we provide a more
direct algorithm to compute the $\mathsf{SHAP}$-score on these circuits.

The exact computation or approximation of the Shapley value applied to
database tuples is investigated in Livshits et al. (2021); Deutch et al.
(2022). In Bertossi et al. (2020), approximations of the $\mathsf{SHAP}$-score
are used for experimental purposes and comparisons with other scores, such as
RESP and Rudin’s FICO-score (Chen et al., 2018). However, an empirical
distribution is used for the approximate computation of the
$\mathsf{SHAP}$-score, which leads to a simple, non-probabilistic weighted
average, and to the restriction of the counterfactual versions of an entity to
those in the available sample. In Bertossi and Leon (2023), the algorithm
presented in our work (c.f. Section 3.1.3) has been used to efficiently
compute $\mathsf{SHAP}$-scores, under the uniform distribution, for outcomes
from binary neural networks, after compiling the latter into deterministic and
decomposable Boolean circuits.

Building on Livshits et al. (2021) and on the conference version of the
current article, the authors of Deutch et al. (2022) use knowledge compilation
techniques that are similar to ours to develop a polynomial-time algorithm
that is able to compute a version of the Shapley value tailored to a database
context. They moreover propose an algorithm for computing approximations of
the Shapley values of tuples, but this algorithm does not come with any
theoretical guarantees.

Last, regarding approximation, there is a large body of work that aims at
approximating Shapley values using Monte Carlo techniques, see for instance
Castro et al. (2009); Okhrati and Lipani (2021); Deutch et al. (2021);
Mitchell et al. (2022). The results of such works are upper bounds for diverse
settings of Shapley values – i.e., considering different game functions – but
we are not aware of such results for the specific game function (the SHAP-
score) that we study here, for instance, theoretical results that would yield
an FPRAS for the SHAP-score. Besides, these studies do not usually contain
lower bounds, since their focus is on obtaining tractable approximations via
Monte Carlo or other sampling schemes. By contrast, obtaining lower bounds is
the topic of our Sections 6 and 7, where we show the non-existence of an FPRAS
for approximating the SHAP-score of DNF formulas, as well as the non-
membership in BPP of comparing SHAP-scores for such formulas.

This paper is a considerable extension of the conference paper (Arenas et al.,
2021). In addition to containing full proofs of all the results of (Arenas et
al., 2021), we present here several new results. Among them, we provide a
detailed analysis of approximability of the $\mathsf{SHAP}$-score, a
complexity analysis of the problem of comparing $\mathsf{SHAP}$-scores, and an
extension of the results for deterministic and decomposable Boolean circuits
to the case of non-binary features.

##### Paper structure.

We give preliminaries in Section 2. In Section 3, we prove that the
$\mathsf{SHAP}$-score can be computed in polynomial time for deterministic and
decomposable Boolean circuits under product probability distributions. We
extend this tractability result in Section 4 to non-binary deterministic and
decomposable Boolean circuits. In Section 5, we establish the computational
limits of the exact computation of the $\mathsf{SHAP}$-score, while Section 6
studies the (non-) approximability properties of this score. The problem of
comparing the $\mathsf{SHAP}$-scores of different features is studied in
Section 7. We conclude and discuss future work in Section 8.

##  2 Preliminaries

###  2.1 Entities, distributions and classifiers

Let $X$ be a finite set of _binary 111We will come back to this assumption in
Section 4, where we will consider non-binary features. features_, also called
_variables_. An _entity_ over $X$ is a function
$\mathbf{e}:X\to\\{0,1\\}$.222Equivalently, one can see an entity as a vector
of binary values, with each coordinate corresponding to a given feature. We
will however always use the functional point of view as it simplifies the
notation in our proofs. We denote by $\mathsf{ent}(X)$ the set of all entities
over $X$. On this set, we consider probability distributions that we call
_product distributions_ , defined as follows. Let $\mathrm{p}:X\to[0,1]$ be a
function that associates to every feature $x\in X$ a probability value
$\mathrm{p}(x)\in[0,1]$. Then, the _product distribution generated by
$\mathrm{p}$_ is the probability distribution $\Pi_{\mathrm{p}}$ over
$\mathsf{ent}(X)$ such that, for every $\mathbf{e}\in\mathsf{ent}(X)$ we have

$\Pi_{\mathrm{p}}(\mathbf{e})\ \ \coloneqq\ \
\bigg{(}\prod_{\begin{subarray}{c}x\in X\\\
\mathbf{e}(x)=1\end{subarray}}\mathrm{p}(x)\bigg{)}\cdot\bigg{(}\prod_{\begin{subarray}{c}x\in
X\\\ \mathbf{e}(x)=0\end{subarray}}(1-\mathrm{p}(x))\bigg{)}.$

That is, $\Pi_{\mathrm{p}}$ is the product distribution that is determined by
pre-specified marginal distributions, and that makes the features take values
independently from each other. We denote by $\mathcal{U}$ the _uniform
probability distribution_ , i.e., for every entity
$\mathbf{e}\in\mathsf{ent}(X)$, we have that
$\mathcal{U}(\mathbf{e}):=\frac{1}{2^{|X|}}$. Note that the uniform
distribution can be obtained as a special case of product distribution, with
$\Pi_{\mathrm{p}}$ invoking $\mathrm{p}(x):=\nicefrac{{1}}{{2}}$ for every
$x\in X$.

A _Boolean classifier_ $M$ over $X$ is a function
$M:\mathsf{ent}(X)\to\\{0,1\\}$ that maps every entity over $X$ to $0$ or $1$.
We say that $M$ _accepts_ an entity $\mathbf{e}$ when $M(\mathbf{e})=1$, and
that it _rejects_ it if $M(\mathbf{e})=0$. Since we consider $\mathsf{ent}(X)$
to be a probability space, $M$ can be regarded as a random variable.

###  2.2 The $\mathbf{\mathsf{SHAP}}$-score over Boolean classifiers

Let $M:\mathsf{ent}(X)\to\\{0,1\\}$ be a Boolean classifier over the set $X$
of features. Given an entity $\mathbf{e}$ over $X$ and a subset $S\subseteq X$
of features, we define the set $\mathsf{cw}(\mathbf{e},S)$ of entities that
are _consistent with $\mathbf{e}$ on $S$_ as
$\mathsf{cw}(\mathbf{e},S)\coloneqq\\{\mathbf{e}^{\prime}\in\mathsf{ent}(X)\mid\mathbf{e}^{\prime}(x)=\mathbf{e}(x)$
for each $x\in S\\}$. Then, given an entity $\mathbf{e}\in\mathsf{ent}(X)$, a
probability distribution $\mathcal{D}$ over $\mathsf{ent}(X)$, and $S\subseteq
X$, we define the expected value of $M$ over $X\setminus S$ with respect to
$\mathbf{e}$ under $\mathcal{D}$ as

$\displaystyle\phi_{\mathcal{D}}(M,\mathbf{e},S)\ $ $\displaystyle\coloneqq\
\mathbb{E}_{\mathbf{e}^{\prime}\sim\mathcal{D}}\big{[}M(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\
\in\mathsf{cw}(\mathbf{e},S)\big{]}.$

In other words, $\phi_{\mathcal{D}}(M,\mathbf{e},S)$ is the expected value of
$M$, conditioned on the inputs to coincide with $\mathbf{e}$ over each feature
in $S$. For instance, if we take $\mathcal{D}$ to be the uniform distribution
$\mathcal{U}$ over $\mathsf{ent}(X)$, this expression simplifies to

$\displaystyle\phi_{\mathcal{U}}(M,\mathbf{e},S)=\sum_{\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)}\frac{1}{2^{|X\setminus
S|}}M(\mathbf{e}^{\prime}).$

The function $\phi_{\mathcal{D}}$ is then used in the general formula of the
Shapley value (Shapley, 1953; Roth, 1988) to obtain the $\mathsf{SHAP}$-score
for feature values in $\mathbf{e}$, as follows.

######  Definition 1 (Lundberg and Lee (2017))

Given a Boolean classifier $M$ over a set of features $X$, a probability
distribution $\mathcal{D}$ on $\mathsf{ent}(X)$, an entity $\mathbf{e}$ over
$X$, and a feature $x\in X$, the $\mathsf{SHAP}$ score of feature $x$ on
$\mathbf{e}$ with respect to $M$ under $\mathcal{D}$ is defined as

$\mathsf{SHAP}_{\mathcal{D}}(M,\mathbf{e},x)\ \coloneqq\ \sum_{S\subseteq
X\setminus\\{x\\}}\frac{|S|!\,(|X|-|S|-1)!}{|X|!}\bigg{(}\phi_{\mathcal{D}}(M,\mathbf{e},S\cup\\{x\\})-\phi_{\mathcal{D}}(M,\mathbf{e},S)\bigg{)}.$
(1)

In Section 5, we will use another equivalent expression of the
$\mathsf{SHAP}$-score, that we introduce now. For a permutation
$\pi:X\to\\{1,\ldots,n\\}$ and $x\in X$, let $S_{\pi}^{x}$ denote the set of
features that appear before $x$ in $\pi$. Formally,
$S_{\pi}^{x}\coloneqq\\{y\in X\mid\pi(y)<\pi(x)\\}$. Then, letting $\Pi(X)$ be
the set of all permutations $\pi:X\to\\{1,\ldots,n\\}$, observe that Equation
(1) can be rewritten as

$\displaystyle\mathsf{SHAP}_{\mathcal{D}}(M,\mathbf{e},x)\ =\
\frac{1}{|X|!}\sum_{\pi\in\Pi(X)}\big{(}\phi_{\mathcal{D}}(M,\mathbf{e},S_{\pi}^{x}\cup\\{x\\})-\phi_{\mathcal{D}}(M,\mathbf{e},S_{\pi}^{x})\big{)}.$
(2)

Thus, $\mathsf{SHAP}_{\mathcal{D}}(M,\mathbf{e},x)$ is a weighted average of
the contribution of feature $x$ on $\mathbf{e}$ to the classification result,
i.e., of the differences between having it and not, under all possible
permutations of the other feature values. Observe that, from this definition,
a high positive value of $\mathsf{SHAP}_{\mathcal{D}}(M,\mathbf{e},x)$
intuitively means that setting $x$ to $\mathbf{e}(x)$ strongly leans the
classifier towards acceptance, while a high negative value of
$\mathsf{SHAP}_{\mathcal{D}}(M,\mathbf{e},x)$ means that setting $x$ to
$\mathbf{e}(x)$ strongly leans the classifier towards rejection.

###  2.3 Deterministic and decomposable Boolean circuits

A Boolean circuit over a set of variables $X$ is a directed acyclic graph $C$
such that

  1. (i)

Every node without incoming edges is either a variable gate or a constant
gate. A variable gate is labeled with a variable from $X$, and a constant gate
is labeled with either $0$ or $1$;

  2. (ii)

Every node with incoming edges is a logic gate, and is labeled with a symbol
$\land$, $\lor$ or $\lnot$. If it is labeled with the symbol $\lnot$, then it
has exactly one incoming edge;333Recall that the fan-in of a gate is the
number of its input gates. In our definition of Boolean circuits, we allow
unbounded fan-in $\land$\- and $\lor$-gates.

  3. (iii)

Exactly one node does not have any outgoing edges, and this node is called the
output gate of $C$.

Such a Boolean circuit $C$ represents a Boolean classifier in the expected way
– we assume the reader to be familiar with Boolean logic –, and we write
$C(\mathbf{e})$ for the value in $\\{0,1\\}$ of the output gate of $C$ when we
evaluate $C$ over the entity $\mathbf{e}$. We consider the _size_ $|C|$ of the
circuit to be its number of edges. Observe that, thanks to condition (iii),
the number of gates of $C$ is at most its number of edges plus one.

Several restrictions of Boolean circuits with good computational properties
have been studied. Let $C$ be a Boolean circuit over a set of variables $X$
and $g$ a gate of $C$. The Boolean circuit $C_{g}$ over $X$ is defined by
considering the subgraph of $C$ induced by the set of gates $g^{\prime}$ in
$C$ for which there exists a path from $g^{\prime}$ to $g$ in $C$. Notice that
$g$ is the output gate of $C_{g}$. Then, an $\lor$-gate $g$ of $C$ is said to
be _deterministic_ if for every pair $g_{1}$, $g_{2}$ of distinct input gates
of $g$, the Boolean circuits $C_{g_{1}}$ and $C_{g_{2}}$ are disjoint in the
sense that there is no entity $\mathbf{e}$ that is accepted by both
$C_{g_{1}}$ and $C_{g_{2}}$ (that is, there is no entity
$\mathbf{e}\in\mathsf{ent}(X)$ such that
$C_{g_{1}}(\mathbf{e})=C_{g_{2}}(\mathbf{e})=1$). The circuit $C$ is called
_deterministic_ if every $\lor$-gate of $C$ is deterministic. The set
$\mathsf{var}(g)$ is defined as the set of variables $x\in X$ such that there
exists a variable gate with label $x$ in $C_{g}$. An $\land$-gate $g$ of $C$
is said to be _decomposable_ , if for every pair $g_{1}$, $g_{2}$ of distinct
input gates of $g$, we have that
$\mathsf{var}(g_{1})\cap\mathsf{var}(g_{2})=\emptyset$. Then $C$ is called
_decomposable_ if every $\land$-gate of $C$ is decomposable.

###### Example 1

We want to classify papers submitted to a conference as rejected (Boolean
value $0$) or accepted (Boolean value $1$). Papers are described by
propositional features fg, dtr, nf and na, which stand for “follows
guidelines”, “deep theoretical result”, “new framework” and “nice
applications”, respectively. The Boolean classifier for the papers is given by
the Boolean circuit in Figure 1. The input of this circuit are the features
fg, dtr, nf and na, each of which can take value either $0$ or $1$, depending
on whether the feature is present ($1$) or absent ($0$). The nodes with labels
$\neg$, $\lor$ or $\land$ are logic gates, and the associated Boolean value of
each one of them depends on the logical connective represented by its label
and the Boolean values of its inputs. The output value of the circuit is given
by the top node in the figure.

The Boolean circuit in Figure 1 is decomposable, because for each $\land$-gate
the sets of features of its inputs are pairwise disjoint. For instance, in the
case of the top node in Figure 1, the left-hand side input has
$\\{\mbox{\bf\footnotesize fg}\\}$ as its set of features, while its right-
hand side input has $\\{\mbox{\bf\footnotesize dtr},\mbox{\bf\footnotesize
nf},\mbox{\bf\footnotesize na}\\}$ as its set of features, which are disjoint.
Also, this circuit is deterministic as for every $\lor$-gate two (or more) of
its inputs cannot be given value 1 by the same Boolean assignment for the
features. For instance, in the case of the only $\lor$-gate in Figure 1, if a
Boolean assignment for the features gives value 1 to its left-hand side input,
then feature dtr has to be given value 1 and, thus, such an assignment gives
value $0$ to the right-hand side input of the $\lor$-gate. In the same way, it
can be shown that if a Boolean assignment for the features gives value 1 to
the right-hand side input of this $\lor$-gate, then it gives value $0$ to its
left-hand side input.  $\square$

dtrnf$\neg$na$\land$$\lor$$\land$fg Figure 1: A deterministic and decomposable
Boolean Circuit as a classifier.

We will use the fact that deterministic and decomposable Boolean circuits are
closed under _conditioning_. Let $C$ be a Boolean circuit over variables $X$,
and let $x\in X$. We denote by $C_{+x}$ (resp., $C_{-x}$) the Boolean circuit
that is obtained from $C$ by replacing every variable gate that is labeled
with $x$ by a constant $1$-gate (resp, by a constant $0$-gate). In the
literature, $C_{+x}$ (resp., $C_{-x}$) is called the conditioning by $x$
(resp., by $\lnot x$) of $C$. It is easy to check that, if $C$ is
deterministic and decomposable, then so are $C_{+x}$ and $C_{-x}$.

As mentioned in the introduction, deterministic and decomposable Boolean
circuits generalize many decision diagrams and Boolean circuits classes. We
refer to (Darwiche, 2001; Amarilli et al., 2020) for detailed studies of
knowledge compilation classes and of their precise relationships. For the
reader’s convenience, we explain in Appendix A how FBDDs and binary decision
trees can be encoded in linear time as deterministic and decomposable Boolean
circuits.

###  2.4 Complexity classes and encoding of probability values

In Section 5, we will consider the counting complexity class #P (Valiant,
1979) of problems that can be expressed as the number of accepting paths of a
nondeterministic Turing machine running in polynomial time. Following Valiant
(1979), we define #P-hardness using Turing reductions. Prototypical examples
of #P-complete problems are counting the number of assignments that satisfy a
propositional formula and counting the number of three-colorings of a graph.
While it is known that $\mathrm{FPTIME}\subseteq\\#\text{{P}}$, where
$\mathrm{FPTIME}$ is the class of functions that can be computed in polynomial
time, this inclusion is widely believed to be strict. Therefore, proving that
a problem is #P-hard implies, under such an assumption, that it cannot be
solved in polynomial time.

In Sections 6 and 7 we will use the complexity classes RP and BPP. Recall that
RP is the class of decision problems $L$ for which there exists a polynomial-
time probabilistic Turing Machine $M$ such that: (a) if $x\in L$, then $M$
accepts with probability at least $\nicefrac{{3}}{{4}}$; and (b) if $x\not\in
L$, then $M$ does not accept $x$. Moreover, BPP is defined exactly as RP but
with condition (b) replaced by: (b’) if $x\not\in L$, then $M$ accepts with
probability at most $\nicefrac{{1}}{{4}}$. Thus, BPP is defined as RP but
allowing errors for both the elements that are and are not in $L$. Hence,
$\mathrm{PTIME}\subseteq\text{\rm RP}\subseteq\text{\rm BPP}$ by definition.
Besides, it is known that $\text{\rm RP}\subseteq\text{\rm NP}$, and this
inclusion is widely believed to be strict. Finally, it is not known whether
$\text{\rm BPP}\subseteq\text{\rm NP}$ or $\text{\rm NP}\subseteq\text{\rm
BPP}$, but it is widely believed that NP is not included in BPP.

Finally, when considering problems where probabilities can be part of the
input (such as in Theorem 2 or Theorem 5), it will always be implicit that
such probabilities are given as rational numbers $\nicefrac{{p}}{{q}}$ for
$p,q\in\mathbb{N}$, encoded as ordered pairs $(p,q)$ where $p$ and $q$ are
themselves encoded in binary.

##  3 Tractable Computation of the $\mathsf{SHAP}$-Score

In this section we prove our main tractability result, namely, that computing
the $\mathsf{SHAP}$-score for Boolean classifiers given as deterministic and
decomposable Boolean circuits can be done in polynomial time for product
probability distributions.

###### Theorem 2

Given as input a deterministic and decomposable circuit $C$ over a set of
features $X$, rational probability values $\mathrm{p}(x)$ for every feature
$x\in X$, an entity $\mathbf{e}:X\to\\{0,1\\}$, and a feature $x\in X$, the
value $\mathsf{SHAP}_{\Pi_{\mathrm{p}}}(C,\mathbf{e},x)$ can be computed in
polynomial time.

In particular, since binary decision trees, OBDDs, FBDDs and d-DNNFs are all
restricted types of deterministic and decomposable circuits, we obtain as a
consequence of Theorem 2 that this problem is also in polynomial time for
these classes. For instance, for binary decision trees we obtain the following
result.

###### Corollary 3

Given as input a binary decision tree $T$ over a set of features $X$, rational
probability values $\mathrm{p}(x)$ for every feature $x\in X$, an entity
$\mathbf{e}:X\to\\{0,1\\}$, and a feature $x\in X$, the value
$\mathsf{SHAP}_{\Pi_{\mathrm{p}}}(T,\mathbf{e},x)$ can be computed in
polynomial time.

The authors of (Lundberg et al., 2020) provide an algorithm for computing the
$\mathsf{SHAP}$-score in polynomial time for decision trees, but,
unfortunately, as stated in (Van den Broeck et al., 2021), this algorithm is
not correct. Moreover, it is important to notice that Theorem 2 is a
nontrivial extension of the result for decision trees, as it is known that
deterministic and decomposable circuits can be exponentially more succinct
than binary decision trees (in fact, than FBDDs) at representing Boolean
classifiers (Darwiche, 2001; Amarilli et al., 2020).

We prove Theorem 2 in the remaining of this section. First, we prove in
Section 3.1 that the problem can be solved in polynomial time, and we extract
from this proof a first version of our algorithm. Then, in Section 3.2, we
provide an optimized version of this algorithm, and argue why the proposed
optimization reduces the complexity of the algorithm.

###  3.1 Polynomial time computability proof

In this section we prove that the SHAP-score can be computed in polynomial
time. For a Boolean classifier $M$ over a set of variables $X$, probability
distribution $\mathcal{D}$ over $\mathsf{ent}(X)$, entity
$\mathbf{e}\in\mathsf{ent}(X)$, and natural number $k\leq|X|$, we define the
quantity

$\mathsf{H}_{\mathcal{D}}(M,\mathbf{e},k)\ \coloneqq\
\sum_{\begin{subarray}{c}S\subseteq X\\\
|S|=k\end{subarray}}\,\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\mathcal{D}}[M(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)].$

Our proof of Theorem 2 is divided into two modular parts. The first part,
which is developed in Section 3.1.1, consists in showing that the problem of
computing $\mathsf{SHAP}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ can be reduced in
polynomial time to that of computing
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$. This part of the proof is a
sequence of formula manipulations, and it only uses the fact that
deterministic and decomposable circuits are closed under conditioning on a
variable value (recall the definition of conditioning from Section 2.3). In
the second part of the proof, which is developed in Section 3.1.2, we show
that computing $\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ can be done in
polynomial time for deterministic and decomposable Boolean circuits. It is in
this part that the properties of deterministic and decomposable circuits are
used. Finally, we extract Algorithm 1 from this proof in Section 3.1.3.

####  3.1.1 Reducing in polynomial-time from
$\mathsf{SHAP}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ to
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$

In this section we show that for deterministic and decomposable Boolean
circuits, and under product distributions, the computation of the
$\mathsf{SHAP}$-score can be reduced in polynomial time to the computation of
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$.

Suppose then that we wish to compute
$\mathsf{SHAP}_{\Pi_{p}}(C,\mathbf{e},x)$, for a given deterministic and
decomposable circuit $C$ over a set of variables $X$, probability mapping
$p:X\to[0,1]$, entity $\mathbf{e}\in\mathsf{ent}(X)$, and feature $x\in X$.
Define

$\mathsf{Diff}_{k}(C,\mathbf{e},x)\ \coloneqq\
\sum_{\begin{subarray}{c}S\subseteq X\setminus\\{x\\}\\\
|S|=k\end{subarray}}(\phi_{\Pi_{p}}(C,\mathbf{e},S\cup\\{x\\})-\phi_{\Pi_{p}}(C,\mathbf{e},S)),$

and let $n=|X|$. We then have, by definition, that

$\displaystyle\mathsf{SHAP}_{\Pi_{p}}(C,\mathbf{e},x)\ $ $\displaystyle=\
\sum_{S\subseteq
X\setminus\\{x\\}}\frac{|S|!(n-|S|-1)!}{n!}(\phi_{\Pi_{p}}(C,\mathbf{e},S\cup\\{x\\})-\phi_{\Pi_{p}}(C,\mathbf{e},S))$
$\displaystyle=\ \sum_{k=0}^{n-1}\ \sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\frac{k!(n-k-1)!}{n!}(\phi_{\Pi_{p}}(C,\mathbf{e},S\cup\\{x\\})-\phi_{\Pi_{p}}(C,\mathbf{e},S))$
$\displaystyle=\ \sum_{k=0}^{n-1}\
\frac{k!(n-k-1)!}{n!}\mathsf{Diff}_{k}(C,\mathbf{e},x).$ (3)

Observe that all arithmetical terms (such as $k!$ or $n!$) can be computed in
polynomial time: this is simply because $n$ is given in unary, as it is
bounded by the size of the circuit. Therefore, it is good enough to show how
to compute in polynomial time the quantities
$\mathsf{Diff}_{k}(C,\mathbf{e},x)$ for each $k\in\\{0,\ldots,n-1\\}$. By
definition of $\phi_{{}_{\Pi_{\cdot}}}(\cdot,\cdot,\cdot)$ we have that

$\displaystyle\mathsf{Diff}_{k}(C,\mathbf{e},x)\ =$ $\displaystyle\
\bigg{[}\sum_{\begin{subarray}{c}S\subseteq X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S\cup\\{x\\})]\bigg{]}$
$\displaystyle\hskip 100.0pt-\bigg{[}\sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)]\bigg{]}.$
(4)

In this expression, let $L$ and $R$ be the left- and right-hand side terms in
the subtraction. Looking closer at $R$, we have by standard properties of
conditional expectation that

$\displaystyle R\ =$ $\displaystyle\ \sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)]$
$\displaystyle=$ $\displaystyle\
\,\mathrm{p}(x)\cdot\sum_{\begin{subarray}{c}S\subseteq X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)\text{
and $\mathbf{e}^{\prime}(x)=1$}]$ $\displaystyle\hskip
80.0pt+(1-\mathrm{p}(x))\cdot\sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)\text{
and $\mathbf{e}^{\prime}(x)=0$}].$

To continue, we need to introduce some notation. For a set of features $X$ and
$S\subseteq X$, we write $\mathrm{p}_{|S}:S\to[0,1]$ for the mapping that is
the restriction of $\mathrm{p}$ to $S$, and
$\Pi_{\mathrm{p}_{|S}}:\mathsf{ent}(S)\to[0,1]$ for the corresponding product
distribution on $\mathsf{ent}(S)$. Similarly, for an entity
$\mathbf{e}\in\mathsf{ent}(X)$ and $S\subseteq X$, let $\mathbf{e}_{|S}$ be
the entity over $S$ that is obtained by restricting $\mathbf{e}$ to the domain
$S$ (that is, formally $\mathbf{e}_{|S}\in\mathsf{ent}(S)$ and
$\mathbf{e}_{|S}(y)\coloneqq\mathbf{e}(y)$ for every $y\in S$). Now,
remembering from Section 2.3 the definition of $C_{+x}$ and $C_{-x}$, we
obtain that

$\displaystyle R\ =$ $\displaystyle\
\,p(x)\cdot\sum_{\begin{subarray}{c}S\subseteq X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|X\setminus\\{x\\}}}}[C_{+x}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|X\setminus\\{x\\}},S)]$
$\displaystyle\hskip 50.0pt+(1-p(x))\cdot\sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|X\setminus\\{x\\}}}}[C_{-x}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|X\setminus\\{x\\}},S)]$
$\displaystyle=$ $\displaystyle\
\,p(x)\cdot\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(C_{+x},\mathbf{e}_{|X\setminus\\{x\\}},k)\,+\,(1-p(x))\cdot\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(C_{-x},\mathbf{e}_{|X\setminus\\{x\\}},k),$
(5)

where the last equality is obtained simply by using the definition of
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$. Hence, if we could compute in
polynomial time $H_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ for deterministic and
decomposable Boolean circuits, then we could compute $R$ in polynomial time as
$C_{+x}$ and $C_{-x}$ can be computed in linear time from $C$, and they are
deterministic and decomposable Boolean circuits as well.

We now inspect the term $L$, which we recall is

$\displaystyle L\ =$ $\displaystyle\ \sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S\cup\\{x\\})].$

Observe that, for $S\subseteq X\setminus\\{x\\}$ and
$\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S\cup\\{x\\})$, it holds that

$C(\mathbf{e}^{\prime})\
=\begin{cases}C_{+x}(\mathbf{e}^{\prime}_{|X\setminus\\{x\\}})&\text{if
}\mathbf{e}(x)=1\\\ C_{-x}(\mathbf{e}^{\prime}_{|X\setminus\\{x\\}})&\text{if
}\mathbf{e}(x)=0\end{cases}.$

Therefore, if $\mathbf{e}(x)=1$, we have that

$\displaystyle L\ =$ $\displaystyle\ \sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|X\setminus\\{x\\}}}}[C_{+x}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|X\setminus\\{x\\}},S)]$
$\displaystyle=$ $\displaystyle\ \
\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(C_{+x},\mathbf{e}_{|X\setminus\\{x\\}},k)$
(6)

whereas if $\mathbf{e}(x)=0$, we have that

$\displaystyle L\ =\
\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(C_{-x},\mathbf{e}_{|X\setminus\\{x\\}},k).$
(7)

Hence, again, if we were able to compute in polynomial time
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ for deterministic and
decomposable Boolean circuits, then we could compute $L$ in polynomial time
(as deterministic and decomposable Boolean circuits $C_{+x}$ and $C_{-x}$ can
be computed in linear time from $C$). But then we deduce from (4) that
$\mathsf{Diff}_{k}(C,\mathbf{e},x)$ could be computed in polynomial time for
each $k\in\\{0,\ldots,n-1\\}$, from which we have that
$\mathsf{SHAP}_{\Pi_{p}}(C,\mathbf{e},x)$ could be computed in polynomial time
(by Equation (3)), therefore concluding the existence of the reduction claimed
in this section.

####  3.1.2 Computing $\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ in
polynomial time

We now take care of the second part of the proof of tractability, i.e.,
proving that computing $\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ for
deterministic and decomposable Boolean circuits can be done in polynomial
time. Formally, in this section we prove the following lemma:

###### Lemma 4

The following problem can be solved in polynomial time. Given as input a
deterministic and decomposable Boolean circuit $C$ over a set of variables
$X$, rational probability values $\mathrm{p}(x)$ for each $x\in X$, an entity
$\mathbf{e}\in\mathsf{ent}(X)$, and a natural number $k\leq|X|$, compute the
quantity $\mathsf{H}_{\Pi_{p}}(C,\mathbf{e},k)$.

We first perform two preprocessing steps on $C$.

Rewriting to fan-in $2$.

First, we modify the circuit $C$ so that the fan-in of every $\lor$\- and
$\land$-gate is exactly $2$. This can be done in linear time simply by
rewriting every $\land$-gate (resp., and $\lor$-gate) of fan-in $m>2$ with a
chain of $m-1$ $\land$-gates (resp., $\lor$-gates) of fan-in $2$, and by
attaching to each $\land$ or $\lor$-gate of fan-in $1$ a constant gate of the
appropriate type. It is clear that the resulting Boolean circuit is
deterministic and decomposable. Hence, from now on we assume that the fan-in
of every $\lor$\- and $\land$-gate of $C$ is exactly $2$.

Smoothing the circuit.

A deterministic and decomposable circuit $C$ is _smooth_ (Darwiche, 2001; Shih
et al., 2019b) if for every $\lor$-gate $g$ and input gates $g_{1},g_{2}$ of
$g$, we have that $\mathsf{var}(g_{1})=\mathsf{var}(g_{2})$ (we call such an
$\lor$-gate smooth). Recall that by the previous paragraph, we assume that the
fan-in of every $\lor$-gate is exactly $2$. We then repeat the following
operation until $C$ becomes smooth. For an $\lor$-gate $g$ of $C$ having two
input gates $g_{1},g_{2}$ violating the smoothness condition, define
$S_{1}\coloneqq\mathsf{var}(g_{1})\setminus\mathsf{var}(g_{2})$ and
$S_{2}\coloneqq\mathsf{var}(g_{2})\setminus\mathsf{var}(g_{1})$, and let
$d_{S_{1}}$, $d_{S_{2}}$ be Boolean circuits defined as follows. If
$S_{1}=\emptyset$, then $d_{S_{1}}$ consist of the single constant $1$-gate.
Otherwise, $d_{S_{1}}$ encodes the propositional formula $\land_{x\in
S_{1}}(x\lor\lnot x)$ but it is constructed as a circuit in such a way that
every $\land$\- and $\lor$-gate has fan-in exactly $2$. Boolean circuit
$d_{S_{2}}$ is constructed exactly as $d_{S_{1}}$ but considering the set of
variables $S_{2}$ instead of $S_{1}$. Observe that
$\mathsf{var}(d_{S_{1}})=S_{1}$, $\mathsf{var}(d_{S_{2}})=S_{2}$, that
$d_{S_{1}}$ and $d_{S_{2}}$ always evaluate to $1$, and that all $\lor$-gates
appearing in $d_{S_{1}}$ and in $d_{S_{2}}$ are deterministic. Then, we
transform $g$ into a smooth $\lor$-gate by replacing gate $g_{1}$ by a
decomposable $\land$-gate $(g_{1}\land d_{S_{2}})$, and gate $g_{2}$ by a
decomposable $\land$-gate $(g_{2}\land d_{S_{1}})$. Clearly, this does not
change the Boolean classifier computed, and $g$ is again deterministic because
$g_{1}$ and $(g_{1}\land d_{S_{2}})$ (resp., $g_{2}$ and $(g_{2}\land
d_{S_{1}})$) capture the same Boolean classifier. Moreover, since
$\mathsf{var}(g_{1}\land d_{S_{2}})=\mathsf{var}(g_{2}\land
d_{S_{1}})=\mathsf{var}(g_{1})\cup\mathsf{var}(g_{2})$, we have that $g$ is
now smooth. Therefore, the circuit that we obtain after this operation is
equivalent to the one we started from, is again deterministic and
decomposable, and contains one less non-smooth $\lor$-gate. Hence, by
repeating this operation for each non-smooth $\lor$-gate, which we can do in
polynomial time, we obtain an equivalent smooth deterministic and decomposable
circuit where each $\lor$\- and $\land$-gate has fan-in exactly $2$. Thus,
from now on we also assume that $C$ is smooth.

For a gate $g$ of $C$, let $R_{g}$ be the Boolean circuit over
$\mathsf{var}(g)$ that is defined by considering the subgraph of $C$ induced
by the set of gates $g^{\prime}$ in $C$ for which there exists a path from
$g^{\prime}$ to $g$ in $C$.444The only difference between $R_{g}$ and $C_{g}$
(defined in Section 2) is that we formally regard $R_{g}$ as a Boolean
classifier over $\mathsf{var}(g)$, while we formally regarded $C_{g}$ as a
Boolean classifier over $X$. Notice that $R_{g}$ is a deterministic and
decomposable Boolean circuit with output gate $g$. Moreover, for a gate $g$
and natural number $\ell\leq|\mathsf{var}(g)|$, define
$\alpha_{g}^{\ell}\coloneqq\mathsf{H}_{\Pi_{p_{|\mathsf{var}(g)}}}(R_{g},\mathbf{e}_{|\mathsf{var}(g)},\ell)$,
which we recall is equal, by definition of
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$, to

$\mathsf{H}_{\Pi_{p_{|\mathsf{var}(g)}}}(R_{g},\mathbf{e}_{|\mathsf{var}(g)},\ell)\
=\ \sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)].$

We will show how to compute all the values $\alpha_{g}^{\ell}$ for every gate
$g$ of $C$ and $\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ in polynomial time.
This will conclude the proof of Lemma 4 since, for the output gate
$g_{\mathsf{out}}$ of $C$, we have that
$\alpha_{g_{\mathsf{out}}}^{k}=\mathsf{H}_{\Pi_{p}}(C,\mathbf{e},k)$. Next we
explain how to compute these values by bottom-up induction on $C$.

Variable gate.

$g$ is a variable gate with label $y\in X$, so that $\mathsf{var}(g)=\\{y\\}$.
Then for $\mathbf{e}^{\prime}\in\mathsf{ent}(\\{y\\})$ we have
$R_{g}(\mathbf{e}^{\prime})=\mathbf{e}^{\prime}(y)$, therefore

$\displaystyle\alpha^{0}_{g}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\\{y\\}\\\
|S|=0\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\\{y\\}}}}[\mathbf{e}^{\prime}(y)\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\\{y\\}},S)]$
$\displaystyle=\
\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\\{y\\}}}}[\mathbf{e}^{\prime}(y)\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\\{y\\}},\emptyset)]$
$\displaystyle=\
\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\\{y\\}}}}[\mathbf{e}^{\prime}(y)]$
$\displaystyle=\ 1\cdot p(y)+0\cdot(1-p(y))$ $\displaystyle=\ p(y)$ (8)

and

$\displaystyle\alpha^{1}_{g}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\\{y\\}\\\
|S|=1\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\\{y\\}}}}[\mathbf{e}^{\prime}(y)\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\\{y\\}},S)]$
$\displaystyle=\
\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\\{y\\}}}}[\mathbf{e}^{\prime}(y)\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\\{y\\}},\\{y\\})]$
$\displaystyle=\ \mathbf{e}(y).$ (9)

Constant gate.

$g$ is a constant gate with label $a\in\\{0,1\\}$, and
$\mathsf{var}(g)=\emptyset$. We recall the mathematical convention that there
is a unique function with the empty domain and, hence, a unique entity over
$\emptyset$. But then

$\displaystyle\alpha_{g}^{0}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\emptyset\\\
|S|=0\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\emptyset}}}[a\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\emptyset},S)]$
$\displaystyle=\
\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\emptyset}}}[a\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\emptyset},\emptyset)]$
$\displaystyle=\ a.$ (10)

$\lnot$-gate.

$g$ is a $\lnot$-gate with input gate $g^{\prime}$. Notice that
$\mathsf{var}(g)=\mathsf{var}(g^{\prime})$. Then, since for
$\mathbf{e}^{\prime}\in\mathsf{ent}(\mathsf{var}(g))$ we have that
$R_{g}(\mathbf{e}^{\prime})=1-R_{g^{\prime}}(\mathbf{e}^{\prime})$, we have

$\displaystyle\alpha_{g}^{\ell}\ $ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[1-R_{g^{\prime}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)].$

By linearity of expectations we deduce that

$\displaystyle\alpha_{g}^{\ell}\ $ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[1\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle\hskip
60.0pt-\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g^{\prime}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle=\ \big{(}\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}1\big{)}-\alpha_{g^{\prime}}^{\ell}$ $\displaystyle=\
\binom{|\mathsf{var}(g)|}{\ell}-\alpha_{g^{\prime}}^{\ell}$ (11)

for every $\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$. By induction, the values
$\alpha_{g^{\prime}}^{\ell}$ for $\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$
have already been computed. Thus, we can compute all the values
$\alpha_{g}^{\ell}$ for $\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ in
polynomial time.

$\lor$-gate.

$g$ is an $\lor$-gate. By assumption, recall that $g$ is deterministic,
smooth, and has fan-in exactly $2$. Let $g_{1}$ and $g_{2}$ be the input gates
of $g$, and recall that
$\mathsf{var}(g_{1})=\mathsf{var}(g_{2})=\mathsf{var}(g)$, because $g$ is
smooth. Given that $g$ is deterministic, observe that for every
$\mathbf{e}^{\prime}\in\mathsf{ent}(\mathsf{var}(g))$ we have
$R_{g}(\mathbf{e}^{\prime})=R_{g_{1}}(\mathbf{e}^{\prime})+R_{g_{2}}(\mathbf{e}^{\prime})$.
But then for $\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ we have

$\displaystyle\alpha_{g}^{\ell}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime})+R_{g_{2}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle=\ \sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle\hskip
60.0pt+\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{2}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle=\ \alpha_{g_{1}}^{\ell}+\alpha_{g_{2}}^{\ell},$ (12)

where the second equality is by linearity of the expectation, and the last
equality is valid because $g$ is smooth (in particular, we have that
$\mathsf{var}(g_{1})=\mathsf{var}(g_{2})=\mathsf{var}(g)$). By induction, the
values $\alpha_{g_{1}}^{\ell}$ and $\alpha_{g_{2}}^{\ell}$, for each
$\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$, have already been computed.
Therefore, we can compute all the values $\alpha_{g}^{\ell}$ for
$\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ in polynomial time.

$\land$-gate.

$g$ is an $\land$-gate. By assumption, recall that $g$ is decomposable and has
fan-in exactly $2$. Let $g_{1}$ and $g_{2}$ be the input gates of $g$. For
$\mathbf{e}^{\prime}\in\mathsf{ent}(\mathsf{var}(g))$ we have that
$R_{g}(\mathbf{e}^{\prime})=R_{g_{1}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{1})})\cdot
R_{g_{2}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})})$. Moreover, since
$\mathsf{var}(g)=\mathsf{var}(g_{1})\cup\mathsf{var}(g_{2})$ and
$\mathsf{var}(g_{1})\cap\mathsf{var}(g_{2})=\emptyset$ (because $g$ is
decomposable), observe that every $S\subseteq\mathsf{var}(g)$ can be uniquely
decomposed into $S_{1}\subseteq\mathsf{var}(g_{1})$,
$S_{2}\subseteq\mathsf{var}(g_{2})$ such that $S=S_{1}\cup S_{2}$ and
$S_{1}\cap S_{2}=\emptyset$. Therefore, for
$\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ we have

$\displaystyle\alpha_{g}^{\ell}=\
\sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|\leq\ell\end{subarray}}\,\sum_{\begin{subarray}{c}S_{2}\subseteq\mathsf{var}(g_{2})\\\
|S_{2}|=\ell-|S_{1}|\end{subarray}}\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{1})})\cdot
R_{g_{2}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})})$ $\displaystyle\mid$
$\displaystyle\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S_{1}\cup
S_{2})].$

But, by definition of the product distribution $\Pi_{p_{|\mathsf{var}(g)}}$
and because $g$ is decomposable, we have that
$R_{g_{1}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{1})})$ and
$R_{g_{2}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})})$ are independent random
variables, hence we deduce

$\displaystyle\alpha_{g}^{\ell}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|\leq\ell\end{subarray}}\,\sum_{\begin{subarray}{c}S_{2}\subseteq\mathsf{var}(g_{2})\\\
|S_{2}|=\ell-|S_{1}|\end{subarray}}\,\bigg{(}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{1})})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S_{1}\cup
S_{2})]$ $\displaystyle\hskip
120.0pt\cdot\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{2}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S_{1}\cup
S_{2})]\bigg{)}.$ $\displaystyle=\
\sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|\leq\ell\end{subarray}}\,\sum_{\begin{subarray}{c}S_{2}\subseteq\mathsf{var}(g_{2})\\\
|S_{2}|=\ell-|S_{1}|\end{subarray}}\,\bigg{(}\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{1})}}}[R_{g_{1}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{1})},S_{1})]$
$\displaystyle\hskip
120.0pt\cdot\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{2})}}}[R_{g_{2}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{2})},S_{2})]\bigg{)},$

where the last equality is simply by definition of the product distributions,
and because $R_{g_{1}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{1})})$ is
independent of the value $\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})}$, and
similarly for $R_{g_{2}}(\mathbf{e}^{\prime}_{|\mathsf{var}(g_{2})})$. But
then, using the convention that $\alpha_{g_{i}}^{\ell_{i}}=0$ when
$\ell_{i}>|\mathsf{var}(g_{i})|$, for $i=1,2$, we obtain that

$\displaystyle\alpha_{g}^{\ell}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|\leq\ell\end{subarray}}\,\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{1})}}}[R_{g_{1}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{1})},S_{1})]\,\cdot$
$\displaystyle\hskip
85.35826pt\sum_{\begin{subarray}{c}S_{2}\subseteq\mathsf{var}(g_{2})\\\
|S_{2}|=\ell-|S_{1}|\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{2})}}}[R_{g_{2}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{2})},S_{2})]$
$\displaystyle=\ \sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|\leq\ell\end{subarray}}\,\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{1})}}}[R_{g_{1}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{1})},S_{1})]\cdot\alpha_{g_{2}}^{\ell-|S_{1}|}$
$\displaystyle=\sum_{\ell_{1}=0}^{\ell}\alpha_{g_{2}}^{\ell-\ell_{1}}\cdot\sum_{\begin{subarray}{c}S_{1}\subseteq\mathsf{var}(g_{1})\\\
|S_{1}|=\ell_{1}\end{subarray}}\,\mathbb{E}_{\mathbf{e}^{\prime\prime}\sim\Pi_{p_{|\mathsf{var}(g_{1})}}}[R_{g_{1}}(\mathbf{e}^{\prime\prime})\mid\mathbf{e}^{\prime\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g_{1})},S_{1})]$
$\displaystyle=\sum_{\ell_{1}=0}^{\ell}\alpha_{g_{2}}^{\ell-\ell_{1}}\cdot\alpha_{g_{1}}^{\ell_{1}}$
$\displaystyle=\sum_{\begin{subarray}{c}\ell_{1}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})|)\\}\\\
\ell_{2}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})|)\\}\\\
\ell_{1}+\ell_{2}=\ell\end{subarray}}\alpha_{g_{1}}^{\ell_{1}}\cdot\alpha_{g_{2}}^{\ell_{2}}.$
(13)

By induction, the values $\alpha_{g_{1}}^{\ell_{1}}$ and
$\alpha_{g_{2}}^{\ell_{2}}$, for each
$\ell_{1}\in\\{0,\ldots,|\mathsf{var}(g_{1})|\\}$ and
$\ell_{2}\in\\{0,\ldots,|\mathsf{var}(g_{2})|\\}$, have already been computed.
Therefore, we can compute all the values $\alpha_{g}^{\ell}$ for
$\ell\in\\{0,\ldots,|\mathsf{var}(g)|\\}$ in polynomial time.

This concludes the proof of Lemma 4 and, hence, the proof that
$\mathsf{SHAP}$-score can be computed in polynomial time for our circuits.

Input : Deterministic and decomposable Boolean circuit $C$ over features $X$
with output gate $g_{\mathsf{out}}$, rational probability values
$\mathrm{p}(x)$ for all $x\in X$, entity $\mathbf{e}\in\mathsf{ent}(X)$, and
feature $x\in X$.

Output : The value $\mathsf{SHAP}(C,\mathbf{e},x)$ under the probability
distribution $\Pi_{\mathrm{p}}$.

1 Transform $C$ into an equivalent smooth circuit $D$ where each $\lor$-gate
and $\land$-gate has fan-in exactly 2;

2 Compute the set $\mathsf{var}(g)$ for every gate $g$ in $D$;

3 Compute values $\gamma_{g}^{\ell}$ and $\delta_{g}^{\ell}$ for every gate
$g$ in $D$ and $\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$ by
bottom-up induction on $D$ as follows:

4 if  _$g$ is a constant gate with label $a\in\\{0,1\\}$_ then

5 $\gamma_{g}^{0},\,\delta_{g}^{0}\leftarrow a$;

6

7 else if  _$g$ is a variable gate with $\mathsf{var}(g)=\\{x\\}$_ then

8 $\gamma_{g}^{0}\leftarrow 1$;

9 $\delta_{g}^{0}\leftarrow 0$;

10

11 else if  _$g$ is a variable gate with $\mathsf{var}(g)=\\{y\\}$ and $y\neq
x$_ then

12 $\gamma_{g}^{0},\,\delta_{g}^{0}\leftarrow\mathrm{p}(y)$;

13 $\gamma_{g}^{1},\,\delta_{g}^{1}\leftarrow\mathbf{e}(y)$;

14

15 else if  _$g$ is a $\lnot$-gate with input gate $g^{\prime}$_ then

16 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

17
$\gamma_{g}^{\ell}\leftarrow\binom{|\mathsf{var}(g)\setminus\\{x\\}|}{\ell}-\gamma_{g^{\prime}}^{\ell}$;

18
$\delta_{g}^{\ell}\leftarrow\binom{|\mathsf{var}(g)\setminus\\{x\\}|}{\ell}-\delta_{g^{\prime}}^{\ell}$;

19

20 end for

21

22

23 else if  _$g$ is an $\lor$-gate with input gates $g_{1},g_{2}$_ then

24 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

25 $\gamma_{g}^{\ell}\leftarrow\gamma_{g_{1}}^{\ell}+\gamma_{g_{2}}^{\ell}$;

26 $\delta_{g}^{\ell}\leftarrow\delta_{g_{1}}^{\ell}+\delta_{g_{2}}^{\ell}$;

27

28 end for

29

30 else if  _$g$ is an $\land$-gate with input gates $g_{1},g_{2}$_ then

31 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

32
$\gamma_{g}^{\ell}\leftarrow\sum_{\begin{subarray}{c}\ell_{1}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}\\\
\ell_{2}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}\\\
\ell_{1}+\ell_{2}=\ell\end{subarray}}\gamma_{g_{1}}^{\ell_{1}}\cdot\gamma_{g_{2}}^{\ell_{2}}$;

33
$\delta_{g}^{\ell}\leftarrow\sum_{\begin{subarray}{c}\ell_{1}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}\\\
\ell_{2}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}\\\
\ell_{1}+\ell_{2}=\ell\end{subarray}}\delta_{g_{1}}^{\ell_{1}}\cdot\delta_{g_{2}}^{\ell_{2}}$;

34

35 end for

36

37

38 end

39

40return
${\displaystyle\sum_{k=0}^{|X|-1}\frac{k!\,(|X|-k-1)!}{|X|!}\cdot\big{[}(\mathbf{e}(x)-\mathrm{p}(x))(\gamma_{g_{\mathsf{out}}}^{k}-\delta_{g_{\mathsf{out}}}^{k})\big{]}}$;

Algorithm 1 $\mathsf{SHAP}$-scores for deterministic and decomposable Boolean
circuits (intermediate)

####  3.1.3 Extracting an algorithm from the proof

From the previous proof, it is possible to extract Algorithm 1, which is more
amenable to implementation. The main idea of this algorithm is that values
$\gamma_{g}^{\ell}$ correspond to values $\alpha^{g}_{\ell}$ of the proof for
the circuit $D_{+x}$, while values $\delta_{g}^{\ell}$ correspond to values
$\alpha_{g}^{\ell}$ of the proof for the circuit $D_{-x}$. In lines 1–1, these
values are computed by bottom-up induction over the circuit $D$, following the
relations that we obtained in Equations (8)–(13) (but specialized to the
circuits $D_{+x}$ and $D_{-x}$, as can be seen from lines 1–1, and by the fact
that indices are always in
$\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$). Hence, it only remains to
show that the returned value of the algorithm is correct. To see that, observe
that we can rewrite Equations (6) and (7) into

$L=\mathbf{e}(x)\cdot\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(D_{+x},\mathbf{e}_{|X\setminus\\{x\\}},k)+(1-\mathbf{e}(x))\cdot\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(D_{-x},\mathbf{e}_{|X\setminus\\{x\\}},k),$

which works no matter the value of $\mathbf{e}(x)\in\\{0,1\\}$. We can then
directly combine this expression for $L$ with Equation (4) and the expression
of $R$ from Equation (5) to obtain

$\displaystyle\mathsf{Diff}_{k}(D,\mathbf{e},x)\ $ $\displaystyle=\ L-R$
$\displaystyle=\
(\mathbf{e}(x)-\mathrm{p}(x))\big{[}\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(D_{+x},\mathbf{e}_{|X\setminus\\{x\\}},k)-\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(D_{-x},\mathbf{e}_{|X\setminus\\{x\\}},k)\big{]}.$

But the rightmost factor is precisely
$(\gamma_{g_{\mathsf{out}}}^{k}-\delta_{g_{\mathsf{out}}}^{k})$ in Algorithm
1, so that the returned value is indeed correct by Equation (3).

###### Example 2

We describe in this example a complete execution of Algorithm 1 over the
deterministic and decomposable Boolean circuit $C$ in depicted Figure 1 (see
Example 1). More precisely, we show in Figure 2 how
$\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize nf})$ is computed under the
uniform distribution (that is, $\mathrm{p}(\mbox{\bf\footnotesize
fg})=\mathrm{p}(\mbox{\bf\footnotesize dtr})=\mathrm{p}(\mbox{\bf\footnotesize
nf})=\mathrm{p}(\mbox{\bf\footnotesize na})=\nicefrac{{1}}{{2}}$), and
assuming that $\mathbf{e}(\mbox{\bf\footnotesize fg})=1$,
$\mathbf{e}(\mbox{\bf\footnotesize dtr})=0$,
$\mathbf{e}(\mbox{\bf\footnotesize nf})=1$, and
$\mathbf{e}(\mbox{\bf\footnotesize na})=1$. Notice that $C(\mathbf{e})=1$.

In the first step of the algorithm, the gate in gray in Figure 2 is added to
$C$ so that the fan-in of every $\lor$\- and $\land$-gate is exactly 2, and
the gates in blue in Figure 2 are added to obtain a deterministic,
decomposable and smooth circuit $D$ (in particular, for every $\lor$-gate $g$
of $D$ with input gates $g_{1}$ and $g_{2}$, it holds that
$\mathsf{var}(g_{1})=\mathsf{var}(g_{2})$). Then in the main loop of the
algorithm, the values of $\gamma_{g}^{i}$ and $\delta_{g}^{i}$ are computed in
a bottom-up fashion for every gate $g$ and
$i\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{\mbox{\bf\footnotesize
nf}\\}|\\}$. Finally, assuming that $g_{\mathsf{out}}$ is the top $\land$-gate
in $D$, the value $\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize nf})$ is
computed as follows:

$\displaystyle\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize nf})$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{3}\frac{k!\,(3-k)!}{4!}\cdot\big{[}(\mathbf{e}(\mbox{\bf\footnotesize
nf})-\mathrm{p}(\mbox{\bf\footnotesize
nf}))(\gamma_{g_{\mathsf{out}}}^{k}-\delta_{g_{\mathsf{out}}}^{k})\big{]}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\bigg{(}\frac{1}{4}\cdot\frac{1}{8}+\frac{1}{12}\cdot\frac{3}{4}+\frac{1}{12}\cdot\frac{3}{2}+\frac{1}{4}\cdot
1\bigg{)}$ $\displaystyle=$ $\displaystyle\frac{15}{64}.$

As a final comment, we notice that by following the same procedure it can be
shown that $\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize
fg})=\nicefrac{{23}}{{64}}$,
$\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize
dtr})=-\nicefrac{{9}}{{64}}$, and
$\mathsf{SHAP}(C,\mathbf{e},\mbox{\bf\footnotesize
na})=\nicefrac{{15}}{{64}}$.  $\square$

dtr $\gamma^{0}=\frac{1}{2}$ $\gamma^{1}=0$ $\delta^{0}=\frac{1}{2}$
$\delta^{1}=0$ $\land$ $\gamma^{0}=\frac{1}{2}$ $\delta^{0}=\frac{1}{2}$
$\gamma^{1}=\frac{1}{2}$ $\delta^{1}=\frac{1}{2}$ $\gamma^{2}=0$
$\delta^{2}=0$ $\land$ $\gamma^{0}=1$ $\delta^{0}=1$ $\gamma^{1}=1$
$\delta^{1}=1$ $\lor$ $\gamma^{0}=1$ $\delta^{0}=1$ $\gamma^{1}=1$
$\delta^{1}=1$ na $\gamma^{0}=\frac{1}{2}$ $\gamma^{1}=1$
$\delta^{0}=\frac{1}{2}$ $\delta^{1}=1$ $\neg$ $\gamma^{0}=\frac{1}{2}$
$\gamma^{1}=0$ $\delta^{0}=\frac{1}{2}$ $\delta^{1}=0$ na
$\gamma^{0}=\frac{1}{2}$ $\gamma^{1}=1$ $\delta^{0}=\frac{1}{2}$
$\delta^{1}=1$ $\lor$ $\gamma^{0}=1$ $\delta^{0}=1$ nf $\gamma^{0}=1$
$\delta^{0}=0$ $\neg$ $\gamma^{0}=0$ $\delta^{0}=1$ nf $\gamma^{0}=1$
$\delta^{0}=0$ fg $\gamma^{0}=\frac{1}{2}$ $\gamma^{1}=1$
$\delta^{0}=\frac{1}{2}$ $\delta^{1}=1$ $\land$ $\gamma^{0}=\frac{1}{2}$
$\gamma^{1}=1$ $\delta^{0}=0$ $\delta^{1}=0$ na $\gamma^{0}=\frac{1}{2}$
$\gamma^{1}=1$ $\delta^{0}=\frac{1}{2}$ $\delta^{1}=1$ nf $\gamma^{0}=1$
$\delta^{0}=0$ $\land$$\neg$ $\gamma^{0}=\frac{1}{2}$ $\gamma^{1}=1$
$\delta^{0}=\frac{1}{2}$ $\delta^{1}=1$ $\gamma^{0}=\frac{1}{4}$
$\delta^{0}=0$ $\gamma^{1}=1$ $\delta^{1}=0$ $\gamma^{2}=1$ $\delta^{2}=0$
$\lor$ $\gamma^{0}=\frac{3}{4}$ $\delta^{0}=\frac{1}{2}$
$\gamma^{1}=\frac{3}{2}$ $\delta^{1}=\frac{1}{2}$ $\gamma^{2}=1$
$\delta^{2}=0$ $\land$ $\gamma^{0}=\frac{3}{8}$ $\delta^{0}=\frac{1}{4}$
$\gamma^{1}=\frac{3}{2}$ $\delta^{1}=\frac{3}{4}$ $\gamma^{2}=2$
$\delta^{2}=\frac{1}{2}$ $\gamma^{3}=1$ $\delta^{3}=0$ Figure 2: Execution of
Algorithm 1 over the deterministic and decomposable Boolean circuit depicted
in Figure 1.

###  3.2 An optimized version of the algorithm

In this section, we present an optimized version of the algorithm to compute
the $\mathsf{SHAP}$-score. The observation behind this algorithm is that it is
possible to bypass the smoothing step and directly work on the input circuit
$C$.555We first presented a version that used smoothing because it made the
tractability proof easier to understand. Our procedure can be found in
Algorithm 2.

Observe that Algorithm 2 is identical to Algorithm 1, except that: (1) we do
not smooth the circuit on line 2; and (2) the expressions for $\lor$-gates on
lines 2 and 2 have changed. Before showing the correctness of Algorithm 2,
notice that the smoothing step on line 2 of Algorithm 1 takes time
$O(|C|\cdot|X|)$, as described in Section 3.1.2, and the resulting circuit,
called $D$, has size $O(|C|\cdot|X|)$. As Algorithm 2 does not execute such a
smoothing step, it works directly with a circuit of size $O(|C|)$, obtained
after preprocessing input circuit $C$ to ensure that all $\lor$\- and
$\land$-gate have fan-in $2$, and it has a lower complexity.

The only thing that changed between Algorithm 1 and 2 is how we treat an
$\lor$-gate, which can now be non-smoothed. Therefore, to show that Algorithm
2 is correct, we need to revisit Equation (12). The relation

$\displaystyle\alpha_{g}^{\ell}$ $\displaystyle=\
\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime})+R_{g_{2}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
$\displaystyle=\ \sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{1}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$
(14) $\displaystyle\hskip
60.0pt+\sum_{\begin{subarray}{c}S\subseteq\mathsf{var}(g)\\\
|S|=\ell\end{subarray}}\,\,\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|\mathsf{var}(g)}}}[R_{g_{2}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|\mathsf{var}(g)},S)]$

is still true for an arbitrary deterministic $\lor$-gate $g$ with children
$g_{1},g_{2}$, however this is not equal to
$\alpha_{g_{1}}^{\ell}+\alpha_{g_{2}}^{\ell}$ anymore when $g$ is not smooth.
This is because, in this case, one of $\mathsf{var}(g_{1})$ or
$\mathsf{var}(g_{2})$ (or both) is not equal to $\mathsf{var}(g)$. Assuming
without loss of generality that we have
$\mathsf{var}(g_{1})\neq\mathsf{var}(g)$, by induction hypothesis we have
$\alpha_{g_{1}}^{\ell}=\mathsf{H}_{\Pi_{p_{|\mathsf{var}(g_{1})}}}(R_{g_{1}},\mathbf{e}_{|\mathsf{var}(g_{1})},\ell)$,
which is not the expression (14) that we obtain above. To fix this, we will do
as if the gate had been smoothed, by considering the virtual circuits
$d_{S_{1}}$ and $d_{S_{2}}$ that we use in the smoothing process, but without
materializing them. We recall that
$S_{1}\coloneqq\mathsf{var}(g_{1})\setminus\mathsf{var}(g_{2})$ and
$S_{2}\coloneqq\mathsf{var}(g_{2})\setminus\mathsf{var}(g_{1})$, and that
$d_{S_{1}}$ and $d_{S_{2}}$ are Boolean circuits that always evaluate to $1$
over sets of variables $S_{1}$ and $S_{2}$, respectively. Let $g^{\prime}_{1}$
and $g^{\prime}_{2}$ be the output gate of those circuits. We will show how to
compute the values $\alpha_{g^{\prime}_{1}}^{\ell_{1}}$ and
$\alpha_{g^{\prime}_{2}}^{\ell_{2}}$, for $\ell_{1}\in\\{0,\ldots,|S_{1}|\\}$
and $\ell_{2}\in\\{0,\ldots,|S_{2}|\\}$, directly with a closed form
expression and use Equation (13) for $\land$-gates to fix the algorithm. We
have

$\alpha_{g^{\prime}_{1}}^{\ell_{1}}\ =\
\mathsf{H}_{\Pi_{p_{|\mathsf{var}(g^{\prime}_{1})}}}(R_{g^{\prime}_{1}},\mathbf{e}_{|\mathsf{var}(g^{\prime}_{1})},\ell)\
=\ \sum_{\begin{subarray}{c}S\subseteq S_{1}\\\
|S|=\ell_{1}\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|S_{1}}}}[R_{g^{\prime}_{1}}(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|S_{1}},S)]\
=\\\ \sum_{\begin{subarray}{c}S\subseteq S_{1}\\\
|S|=\ell_{1}\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p_{|S_{1}}}}[1\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e}_{|S_{1}},S)]\
=\ \sum_{\begin{subarray}{c}S\subseteq S_{1}\\\ |S|=\ell_{1}\end{subarray}}1\
=\ \binom{|S_{1}|}{\ell_{1}}.$

Hence, by virtually considering that the circuit has been smoothed (that is,
that we replaced gate $g_{1}$ with $(g_{1}\land d_{S_{2}})$ and gate $g_{2}$
with $(g_{2}\land d_{S_{1}})$), and by using the relation for $\land$-gates we
can correct Equation (12) as follows:

$\displaystyle\alpha_{g}^{\ell}\ =\ $
$\displaystyle\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})|)\\}}\alpha_{g_{1}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{2})\setminus\mathsf{var}(g_{1})|}{\ell-\ell^{\prime}}$
$\displaystyle+\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})|)\\}}\alpha_{g_{2}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{1})\setminus\mathsf{var}(g_{2})|}{\ell-\ell^{\prime}}.$

And this is precisely what we use in Algorithm 2 for $\lor$-gates, so this
concludes the proof.

We note that, if we ignore the complexity of arithmetic operations (that is,
if we consider that arithmetic operations over rationals take constant time
and that rationals can be stored in constant space), Algorithm 2 runs in time
$O(|C|\cdot|X|^{2})$.

Input : Deterministic and decomposable Boolean circuit $C$ over features $X$
with output gate $g_{\mathsf{out}}$, rational probability values
$\mathrm{p}(x)$ for all $x\in X$, entity $\mathbf{e}\in\mathsf{ent}(X)$, and
feature $x\in X$.

Output : The value $\mathsf{SHAP}(C,\mathbf{e},x)$ under the probability
distribution $\Pi_{\mathrm{p}}$.

1 Preprocess $C$ so that each $\lor$-gate and $\land$-gate has fan-in exactly
2;

2 Compute the set $\mathsf{var}(g)$ for every gate $g$ in $C$;

3 Compute values $\gamma_{g}^{\ell}$ and $\delta_{g}^{\ell}$ for every gate
$g$ in $C$ and $\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$ by
bottom-up induction on $C$ as follows:

4 if  _$g$ is a constant gate with label $a\in\\{0,1\\}$_ then

5 $\gamma_{g}^{0},\,\delta_{g}^{0}\leftarrow a$;

6

7 else if  _$g$ is a variable gate with $\mathsf{var}(g)=\\{x\\}$_ then

8 $\gamma_{g}^{0}\leftarrow 1$;

9 $\delta_{g}^{0}\leftarrow 0$;

10

11 else if  _$g$ is a variable gate with $\mathsf{var}(g)=\\{y\\}$ and $y\neq
x$_ then

12 $\gamma_{g}^{0},\,\delta_{g}^{0}\leftarrow\mathrm{p}(y)$;

13 $\gamma_{g}^{1},\,\delta_{g}^{1}\leftarrow\mathbf{e}(y)$;

14

15 else if  _$g$ is a $\lnot$-gate with input gate $g^{\prime}$_ then

16 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

17
$\gamma_{g}^{\ell}\leftarrow\binom{|\mathsf{var}(g)\setminus\\{x\\}|}{\ell}-\gamma_{g^{\prime}}^{\ell}$;

18
$\delta_{g}^{\ell}\leftarrow\binom{|\mathsf{var}(g)\setminus\\{x\\}|}{\ell}-\delta_{g^{\prime}}^{\ell}$;

19

20 end for

21

22

23 else if  _$g$ is an $\lor$-gate with input gates $g_{1},g_{2}$_ then

24 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

25
$\gamma_{g}^{\ell}\leftarrow\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}}\gamma_{g_{1}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{2})\setminus(\mathsf{var}(g_{1})\cup\\{x\\})|}{\ell-\ell^{\prime}}+\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}}\gamma_{g_{2}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{1})\setminus(\mathsf{var}(g_{2})\cup\\{x\\})|}{\ell-\ell^{\prime}}$
;

26
$\delta_{g}^{\ell}\leftarrow\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}}\delta_{g_{1}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{2})\setminus(\mathsf{var}(g_{1})\cup\\{x\\})|}{\ell-\ell^{\prime}}+\sum_{\ell^{\prime}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}}\delta_{g_{2}}^{\ell^{\prime}}\cdot\binom{|\mathsf{var}(g_{1})\setminus(\mathsf{var}(g_{2})\cup\\{x\\})|}{\ell-\ell^{\prime}}$;

27

28 end for

29

30 else if  _$g$ is an $\land$-gate with input gates $g_{1},g_{2}$_ then

31 for  _$\ell\in\\{0,\ldots,|\mathsf{var}(g)\setminus\\{x\\}|\\}$_ do

32
$\gamma_{g}^{\ell}\leftarrow\sum_{\begin{subarray}{c}\ell_{1}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}\\\
\ell_{2}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}\\\
\ell_{1}+\ell_{2}=\ell\end{subarray}}\gamma_{g_{1}}^{\ell_{1}}\cdot\gamma_{g_{2}}^{\ell_{2}}$;

33
$\delta_{g}^{\ell}\leftarrow\sum_{\begin{subarray}{c}\ell_{1}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{1})\setminus\\{x\\}|)\\}\\\
\ell_{2}\in\\{0,\ldots,\min(\ell,|\mathsf{var}(g_{2})\setminus\\{x\\}|)\\}\\\
\ell_{1}+\ell_{2}=\ell\end{subarray}}\delta_{g_{1}}^{\ell_{1}}\cdot\delta_{g_{2}}^{\ell_{2}}$;

34

35 end for

36

37

38 end

39

40return
${\displaystyle\sum_{k=0}^{|X|-1}\frac{k!\,(|X|-k-1)!}{|X|!}\cdot\big{[}(\mathbf{e}(x)-\mathrm{p}(x))(\gamma_{g_{\mathsf{out}}}^{k}-\delta_{g_{\mathsf{out}}}^{k})\big{]}}$;

Algorithm 2 $\mathsf{SHAP}$-scores for deterministic and decomposable Boolean
circuits

##  4 Extension to Non-Binary Deterministic and Decomposable Circuits

In this section, we show how to extend the result of the previous section to
non-binary classifiers. First, we need to redefine the notions of entities,
product distributions and $\mathsf{SHAP}$-score to account for non-binary
features. We point out that these new definitions are to be considered for
this section only, as in the rest of the paper we will again consider binary
classifiers. Let $X$ be a finite set of features, and $\mathsf{dom}$ be a
function that associates to every feature $x\in X$ a finite domain
$\mathsf{dom}(x)$. An entity over $(X,\mathsf{dom})$ is a function
$\mathbf{e}$ that associates to every feature an element
$\mathbf{e}(x)\in\mathsf{dom}(X)$. We denote by $\mathsf{ent}(X,\mathsf{dom})$
the set of all entities over $(X,\mathsf{dom})$. We then consider product
distributions on $\mathsf{ent}(X,\mathsf{dom})$ as follows. For every $x\in
X$, let $\mathrm{p}_{x}:\mathsf{dom}(X)\to[0,1]$ be such that
$\sum_{v\in\mathsf{dom}(X)}\mathrm{p}_{x}(v)=1$. Then the _product
distribution generated by $(\mathrm{p}_{x})_{x\in X}$_ is the probability
distribution $\Pi_{\mathrm{p}}$ over $\mathsf{ent}(X,\mathsf{dom})$ such that,
for every $\mathbf{e}\in\mathsf{ent}(X,\mathsf{dom})$ we have

$\Pi_{\mathrm{p}}(\mathbf{e})\ \ \coloneqq\ \ \prod_{x\in
X}\mathrm{p}_{x}(\mathbf{e}(x)).$

That is, again, $\Pi_{\mathrm{p}}$ is the product distribution that is
determined by pre-specified marginal distributions, and that makes the
features take values independently from each other. A _Boolean classifier_ $M$
over $X$ is a function $M:\mathsf{ent}(X,\mathsf{dom})\to\\{0,1\\}$ that maps
every entity over $X$ to $0$ or $1$. The $\mathsf{SHAP}$ score over such
classifiers is then defined just like in Section 2.2.

##### Non-binary Boolean circuits.

We now define a variant of deterministic and decomposable circuits for non-
binary variables, that we will call _deterministic and decomposable non-binary
Boolean circuits_. Just like a Boolean circuit captures a set of binary
entities (those that satisfy the circuit), a _non-binary Boolean circuit_ will
capture a set of entities over $(X,\mathsf{dom})$. We define a non-binary
Boolean circuit over $(X,\mathsf{dom})$ like a Boolean circuit (recall the
definition from Section 2.3), except that each variable gate is now labeled
with an equality of the form $x=v$, where $x\in X$ and $v\in\mathsf{dom}(X)$.
Such a circuit then maps every entity over $X$ to $0$ or $1$ in the expected
way, and can thus be seen as a Boolean classifier. Again, an $\land$-gate is
decomposable if for every pair $g_{1}$, $g_{2}$ of distinct input gates of
$g$, we have that $\mathsf{var}(g_{1})\cap\mathsf{var}(g_{2})=\emptyset$; an
$\lor$-gate is deterministic if for every pair $g_{1}$, $g_{2}$ of distinct
input gates of $g$ there is no entity that satisfies them both; and the
circuit is called deterministic and decomposable if all its $\land$-gates are
decomposable and all its $\lor$-gates are deterministic.

The main result of this section is that we can generalize Theorem 2 to these
kind of circuits (we presented the result for Boolean circuits over binary
variables first for clarity of presentation):

###### Theorem 5

Given as input a set of features $X$, finite domains $\mathsf{dom}(x)$ for
every $x\in X$, a deterministic and decomposable non-binary Boolean circuit
$C$ over $(X,\mathsf{dom})$, rational probability values $\mathrm{p}_{x}(v)$
for every $x\in X$ and $v\in\mathsf{dom}(x)$, an entity
$\mathbf{e}\in\mathsf{ent}(X,\mathsf{dom})$, and a feature $x\in X$, the value
$\mathsf{SHAP}_{\Pi_{\mathrm{p}}}(C,\mathbf{e},x)$ can be computed in
polynomial time.

Proof  First, notice that, since probability values $\mathrm{p}_{x}(v)$ for
every $x\in X$ and $v\in\mathsf{dom}(x)$ are anyway given as part of the
input, it can safely be considered that $\mathsf{dom}(x)$ is of linear size.
We then go through the proof of Theorem 2 and only explain what changes. For
$x\in X$ and $v\in\mathsf{dom}(x)$, we denote by $C_{x=v}$ the non-binary
Boolean circuit that is obtained from $C$ by replacing every variable gate
that is labeled with $x=v$ by a constant 1-gate, and every variable gate that
is labeled with $x=v^{\prime}$ for $v^{\prime}\neq v$ by a constant 0-gate (it
is clear that $C_{x=v}$ is again deterministic and decomposable if $C$
satisfies these properties). Then, the reduction from
$\mathsf{SHAP}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ to
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ from Section 3.1.1 still works,
for instance the term $R$ from Equation (4) becomes

$\displaystyle R\ =$ $\displaystyle\ \sum_{\begin{subarray}{c}S\subseteq
X\setminus\\{x\\}\\\
|S|=k\end{subarray}}\mathbb{E}_{\mathbf{e}^{\prime}\sim\Pi_{p}}[C(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}\in\mathsf{cw}(\mathbf{e},S)]$
$\displaystyle=$ $\displaystyle\
\,\sum_{v\in\mathsf{dom}(X)}\mathrm{p}_{x}(v)\cdot\mathsf{H}_{\Pi_{p_{|X\setminus\\{x\\}}}}(C_{x=v},\mathbf{e}_{|X\setminus\\{x\\}},k).$

We now look at the computation of
$\mathsf{H}_{\Pi_{\cdot}}(\cdot,\cdot,\cdot)$ and inspect what changes in
Lemma 4. We can rewrite to fan-in $2$ and smooth the circuit in the same
way,666For smoothing, we use the circuits $d_{S}\coloneqq\bigwedge_{x\in
S}(\bigvee_{v\in\mathsf{dom}(x)}x=v)$. and the quantities $\alpha^{\ell}_{g}$
are also defined in the same way. The relations that we used to compute the
values $\alpha^{\ell}_{g}$ do not change, except the ones for variable gates:
for a variable gate $g$ labeled with $x=v$, Equations (8) and (9) become,
respectively, $\alpha^{0}_{g}=\mathrm{p}_{x}(v)$ and

$\displaystyle\alpha^{1}_{g}$ $\displaystyle=$
$\displaystyle\begin{cases}1&\text{if }\mathbf{e}(x)=v\\\
0&\text{otherwise}\end{cases}.$

This in particular allows us to prove that the $\mathsf{SHAP}$-score can be
computed in polynomial time for (not necessarily binary) decision trees, or
for variants of OBDDs/FBDDs that use non-binary features, as deterministic and
decomposable non-binary Boolean circuits generalize them.

##  5 Limits on the Tractable Computation of the $\mathsf{SHAP}$-Score

We have shown in the previous sections that the $\mathsf{SHAP}$-score can be
computed in polynomial time for deterministic and decomposable circuits under
product distributions. A natural question, then, is whether both determinism
and decomposability are necessary for this positive result to hold. In this
section we show that this is the case, at least under standard complexity
assumptions, and even when we consider the uniform distribution. Recall that
we are now back to considering Boolean classifiers. Formally, we prove the
following:

###### Theorem 6

The following problems are $\\#\text{{P}}$-hard.

  1. 1.

Given as input a decomposable (but not necessarily deterministic) Boolean
circuit $C$ over a set of features $X$, an entity $\mathbf{e}:X\to\\{0,1\\}$,
and a feature $x\in X$, compute the value
$\mathsf{SHAP}_{\mathcal{U}}(C,\mathbf{e},x)$.

  2. 2.

Given as input a deterministic (but not necessarily decomposable) Boolean
circuit $C$ over a set of features $X$, an entity $\mathbf{e}:X\to\\{0,1\\}$,
and a feature $x\in X$, compute the value
$\mathsf{SHAP}_{\mathcal{U}}(C,\mathbf{e},x)$.

Intuitively, for the first item, this comes from the fact that an arbitrary
Boolean circuit can always be transformed in polynomial time (in fact in
linear time) into an equivalent decomposable (but not necessarily
deterministic) Boolean circuit, simply by applying De Morgan’s laws to
eliminate all $\land$-gates. Hence the problem on those circuits it at least
as hard as on unrestricted Boolean circuits; and the argument is similar for
the second item. Therefore, to show Theorem 6, it is good enough to prove that
the problem is indeed intractable over unrestricted Boolean circuits. We now
prove these claims formally.

We start by showing that there is a general polynomial-time reduction from the
problem of computing the number of entities that satisfy $M$, for $M$ an
arbitrary Boolean classifier, to the problem of computing the
$\mathsf{SHAP}$-score over $M$ under the uniform distribution. This holds
under the mild condition that $M(\mathbf{e})$ can be computed in polynomial
time for an input entity $\mathbf{e}$, which is satisfied for all the Boolean
circuits and binary decision diagrams classes considered in this paper. The
proof of this result follows from well-known properties of Shapley values, and
a closely related result can be found as Theorem 5.1 in (Bertossi et al.,
2020).

###### Lemma 7

Let $M$ be a Boolean classifier over a set of features $X$, and let
$\mathsf{\\#SAT}(M)\coloneqq|\\{\mathbf{e}\in\mathsf{ent}(X)\mid
M(\mathbf{e})=1\\}|$. Then for every $\mathbf{e}\in\mathsf{ent}(X)$ we have:

$\displaystyle\mathsf{\\#SAT}(M)\ =\ 2^{|X|}\bigg{(}M(\mathbf{e})-\sum_{x\in
X}\mathsf{SHAP}_{\mathcal{U}}(M,\mathbf{e},x)\bigg{)}.$

Proof  The validity of this equation will be a consequence of the following
property of the $\mathsf{SHAP}$-score: for every Boolean classifier $M$ over
$X$, entity $\mathbf{e}\in\mathsf{ent}(X)$ and feature $x\in X$, it holds that

$\displaystyle\sum_{x\in X}\mathsf{SHAP}_{\mathcal{U}}(M,\mathbf{e},x)\ =\
\phi_{\mathcal{U}}(M,\mathbf{e},X)-\phi_{\mathcal{U}}(M,\mathbf{e},\emptyset).$
(15)

This property is often called the _efficiency_ property of the Shapley value.
Although this is folklore, we prove Equation (15) here for the reader’s
convenience. Recall from Equation (2) that the $\mathsf{SHAP}$-score can be
written as

$\mathsf{SHAP}_{\mathcal{U}}(M,\mathbf{e},x)\
=\frac{1}{|X|!}\sum_{\pi\in\Pi(X)}\big{(}\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x}\cup\\{x\\})-\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x})\big{)}.$

Hence, we have that

$\displaystyle\sum_{x\in X}\mathsf{SHAP}_{\mathcal{U}}(M,\mathbf{e},x)\ $
$\displaystyle=\ \frac{1}{|X|!}\sum_{x\in X}\
\sum_{\pi\in\Pi(X)}\big{(}\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x}\cup\\{x\\})-\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x})\big{)}$
$\displaystyle=\ \frac{1}{|X|!}\sum_{\pi\in\Pi(X)}\ \sum_{x\in
X}\big{(}\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x}\cup\\{x\\})-\phi_{\mathcal{U}}(M,\mathbf{e},S_{\pi}^{x})\big{)}$
$\displaystyle=\
\frac{1}{|X|!}\sum_{\pi\in\Pi(X)}\big{(}\phi_{\mathcal{U}}(M,\mathbf{e},X)-\phi_{\mathcal{U}}(M,\mathbf{e},\emptyset)\big{)}$
$\displaystyle=\
\phi_{\mathcal{U}}(M,\mathbf{e},X)-\phi_{\mathcal{U}}(M,\mathbf{e},\emptyset),$

where the second to last equality is obtained by noticing that the inner sum
is a telescoping sum. This establishes Equation (15). Now, by definition of
$\phi_{\mathcal{U}}(\cdot,\cdot,\cdot)$ we have that
$\phi_{\mathcal{U}}(M,\mathbf{e},X)=M(\mathbf{e})$ and
$\phi_{\mathcal{U}}(M,\mathbf{e},\emptyset)=\frac{1}{2^{|X|}}\sum_{\mathbf{e}^{\prime}\in\mathsf{ent}(X)}M(\mathbf{e}^{\prime})$,
so we obtain

$\displaystyle\sum_{x\in X}\mathsf{SHAP}_{\mathcal{U}}(M,\mathbf{e},x)\ =\
M(\mathbf{e})-\frac{\mathsf{\\#SAT}(M)}{2^{|X|}},$

thus proving Lemma 7.

We stress out here that this result holds for _any_ Boolean classifier and is
not restricted to the classes of Boolean circuits that we consider in this
paper.

Theorem 6 can then easily be deduced from Lemma 7 and the following two facts:
(a) counting the number of satisfying assignments of an arbitrary Boolean
circuit is a $\\#\text{{P}}$-hard problem (Provan and Ball, 1983); and (b)
every Boolean circuit can be transformed in linear time into a Boolean circuit
that is deterministic (resp, decomposable), simply by using De Morgan’s laws
to get rid of the $\lor$-gates (resp., $\land$-gates). For instance, the
reduction to prove the first item of Theorem 6 is as follows: on input an
arbitrary Boolean circuit $C$, use De Morgan’s laws to remove all
$\land$-gates, thus obtaining an equivalent circuit $C^{\prime}$ which is
vacuously decomposable (since it does not have any $\land$-gates), and then
use the oracle to computing SHAP-scores together with Lemma 7 with an
arbitrary entity (for instance, the one that assigns zero to all features) in
order to compute $\mathsf{\\#SAT}(C)$.

##  6 Non-Approximability of the $\mathsf{SHAP}$-Score

We now study the approximability of the $\mathsf{SHAP}$-score. As we have
shown in the previous section with Lemma 7, computing the
$\mathsf{SHAP}$-score is generally intractable for classes of models for which
model counting is intractable. Yet, it could be the case that one can
efficiently approximate the $\mathsf{SHAP}$-score, just like in some cases one
can efficiently approximate the number of models of a formula even though
computing this quantity exactly is intractable. For instance, model counting
of DNF formulas is $\\#\text{{P}}$-hard (Provan and Ball, 1983) but admits a
_Fully Polynomial-time Randomized Approximation Scheme_ , or FPRAS (Karp et
al., 1989). Unfortunately, as we show next, intractability of computing the
$\mathsf{SHAP}$-score continues to hold when one considers approximability,
and this even for very restricted kinds of Boolean classifiers and under the
uniform probability distribution.

To simplify the notation in this section, we will drop the subscript
$\mathcal{U}$ for the uniform distribution, and write
$\mathsf{SHAP}(\cdot,\cdot,\cdot)$ instead of
$\mathsf{SHAP}_{\mathcal{U}}(\cdot,\cdot,\cdot)$, and
$\phi(\cdot,\cdot,\cdot)$ instead of $\phi_{\mathcal{U}}(\cdot,\cdot,\cdot)$.
Let $\mathcal{C}$ be a class of Boolean classifiers and $\varepsilon\in(0,1)$.
We say that the problem of computing the $\mathsf{SHAP}$ score for
$\mathcal{C}$ admits an $\varepsilon$ polynomial-time randomized approximation
($\varepsilon$-PRA), if there exists a randomized algorithm $\mathcal{A}$
satisfying the following conditions. For every Boolean classifier
$M\in\mathcal{C}$ over a set of features $X$, entity $\mathbf{e}$ over $X$,
and feature $x\in X$, it holds that:

$\displaystyle\Pr\big{(}|\mathcal{A}(M,\mathbf{e},x)-\mathsf{SHAP}(M,\mathbf{e},x)|\leq\varepsilon\cdot|\mathsf{SHAP}(M,\mathbf{e},x)|\big{)}$
$\displaystyle\geq$ $\displaystyle\frac{3}{4}.$

Moreover, there exists a polynomial $p(\cdot)$ such that
$\mathcal{A}(M,\mathbf{e},x)$ works in time $O(p(\|M\|+\|\mathbf{e}\|))$,
where $\|M\|$ and $\|\mathbf{e}\|$ are the sizes of $M$ and $\mathbf{e}$
represented as input strings, respectively. We recall that the notion of FPRAS
mentioned before is defined as the concept of PRA, but imposing the stronger
requirements that $\varepsilon$ is part of the input and the algorithm is
polynomial in $\frac{1}{\varepsilon}$ as well.

We start by presenting a simple proof that for every $\varepsilon\in(0,1)$,
the problem of computing the $\mathsf{SHAP}$ score for Boolean classifiers
given as DNF formulas does not admit an $\varepsilon$-PRA, unless $\text{\rm
NP}=\text{\rm RP}$.777Recall that it is widely believed that RP is properly
contained in NP, as mentioned in Section 2.

###### Proposition 8

For every $\varepsilon\in(0,1)$, the problem of computing the $\mathsf{SHAP}$
score for Boolean classifiers given as DNF formulas does not admit an
$\varepsilon$-PRA, unless $\text{\rm NP}=\text{\rm RP}$. This result holds
even if we restrict to the uniform distributions on the entities.

Proof  We first recall the following fact: if a function $f$ admits an
$\varepsilon$-PRA, then the problem of determining, given a string $x$,
whether $f(x)=0$ is in BPP (although this is folklore, we provide a proof in
Appendix B). We use this to prove that if we could approximate the
$\mathsf{SHAP}$-score over DNF formulas, then we could solve the validity
problem over DNF formulas in BPP. Recall that the validity problem over DNF
formulas is the decision problem that, given as input a DNF formula $\varphi$,
accepts if all valuations satisfy $\varphi$, and rejects otherwise (in other
words, it rejects if $\lnot\varphi$ is satisfiable and accepts otherwise).
Since this problem is coNP-complete and BPP is closed under complement, this
would imply that $\text{\rm NP}\subseteq\text{\rm BPP}$, and thus that
$\text{\rm NP}=\text{\rm RP}$ (Ko, 1982). Let $\varphi$ be a DNF formula over
a set of variables $X$. We consider the DNF formula
$\varphi^{\prime}\coloneqq\varphi\lor x$ with $x\notin X$, and the uniform
probability distribution over $\mathsf{ent}(X\cup\\{x\\})$. Let $\mathbf{e}$
be an arbitrary entity over $X\cup\\{x\\}$ such that $\mathbf{e}(x)=1$. We
show that $\varphi$ is valid if and only if
$\mathsf{SHAP}(\varphi^{\prime},\mathbf{e},x)=0$, which, by the previous
remarks, is good enough to conclude the proof. By definition we have

$\mathsf{SHAP}(\varphi^{\prime},\mathbf{e},x)\ =\ \sum_{S\subseteq
X}\frac{|S|!\,(|X|-|S|)!}{(|X|+1)!}\,\bigg{(}\phi(\varphi^{\prime},\mathbf{e},S\cup\\{x\\})-\phi(\varphi^{\prime},\mathbf{e},S)\bigg{)}.$

Observe that for each $S\subseteq X$, it holds that
$\phi(\varphi^{\prime},\mathbf{e},S\cup\\{x\\})=1$ (given the definition of
$\varphi^{\prime}$ and the fact that $\mathbf{e}(x)=1$), and that
$0\leq\phi(\varphi^{\prime},\mathbf{e},S)\leq 1$. Now, if $\varphi$ is valid,
then it is clear that $\phi(\varphi^{\prime},\mathbf{e},S)=1$ for every
$S\subseteq X$, so that indeed
$\mathsf{SHAP}(\varphi^{\prime},\mathbf{e},x)=0$. Assume now that $\varphi$ is
not valid. By what preceded, it is good enough to show that for some
$S\subseteq X$ we have $\phi(\varphi^{\prime},\mathbf{e},S)<1$. But this
clearly holds for $S=\emptyset$, because $\varphi$ is not valid and all
entities have the same probability (so that no entity has probability zero).

Hence, this result already establishes an important difference with model
counting: for the case of DNF formulas, the model counting problem admits an
FPRAS (Karp et al., 1989) and, thus, an $\varepsilon$-PRA for every
$\varepsilon\in(0,1)$.

It is important to mention that the proof of Proposition 8 uses, in a crucial
way, the fact that the validity problem for DNF formulas is intractable. We
prove next a strong negative result, which establishes that not even for
_positive_ DNF formulas – for which the validity problem is trivial – it is
possible to obtain an $\varepsilon$-PRA for computing the
$\mathsf{SHAP}$-score. Let $\varphi=D_{1}\vee D_{2}\vee\cdots\vee D_{k}$ be a
formula in DNF, that is, each formula $D_{i}$ is a conjunction of positive
literals (propositional variables) and negative literals (negations of
propositional variables). Then $\varphi$ is said to be in POS-DNF if each
formula $D_{i}$ is a conjunction of positive literals, (hence, $\varphi$ is a
monotone formula), and $\varphi$ is said to be in 2-POS-DNF if $\varphi$ is in
POS-DNF and each formula $D_{i}$ contains at most two (positive) literals. Our
main result of this section is the following.

###### Theorem 9

For every $\varepsilon\in(0,1)$, the problem of computing the $\mathsf{SHAP}$
score for Boolean classifiers given as 2-POS-DNF formulas does not admit an
$\varepsilon$-PRA, unless $\text{\rm NP}=\text{\rm RP}$. This result holds
even if we restrict to the uniform distributions on the entities.

Furthermore, we can show that the same intractability result also holds for
closely related classes of Boolean classifiers. As before, let
$\varphi=D_{1}\vee D_{2}\vee\cdots\vee D_{k}$ be a formula in DNF. Then
$\varphi$ is in NEG-DNF if each formula $D_{i}$ is a conjunction of negative
literals, and $\varphi$ is in 2-NEG-DNF if it is in NEG-DNF and each formula
$D_{i}$ is a conjunction of at most two (negative) literals. We define
similarly formulas in 2-POS-CNF and in 2-NEG-CNF. We then obtain the following
result.

###### Corollary 10

Let $\mathcal{C}\in\\{\text{2-POS-DNF},\text{2-NEG-DNF},\text{2-POS-
CNF},\text{2-NEG-CNF}\\}$. Then for every $\varepsilon\in(0,1)$, the problem
of computing the $\mathsf{SHAP}$ score for Boolean classifiers given as
formulas in $\mathcal{C}$ does not admit an $\varepsilon$-PRA, unless
$\text{\rm NP}=\text{\rm RP}$. This result holds even if we restrict to the
uniform distributions on the entities.

It should be noticed that 2-NEG-CNF formulas are special cases of HORN-SAT
formulas, so that the previous result also applies for HORN-SAT.

We prove Theorem 9 in Section 6.1, and then show how the proof can be adapted
to prove Corollary 10 in Section 6.2

###  6.1 Proof of Theorem 9

We will use some results and techniques related to approximating cliques in
graphs. More specifically, all graphs $G=(N,E)$ considered in this proof are
assumed to be undirected and loop-free (that is, edges of the form $(a,a)$ are
not allowed). Besides, we assume that each graph $G=(N,E)$ satisfies the
following condition:

  1. (A)

there exist at least two isolated nodes in $G$, that is, two distinct nodes
$a,b\in N$ such that $(a,c)\not\in E$ and $(b,c)\not\in E$ for every node
$c\in N$.

The assumption that condition (A) is satisfied will allow us to simplify some
calculations. Besides, it is clear that condition (A) can be checked in
polynomial time.

We define the problem $\mathsf{GapClique}$ as follows. The input of
$\mathsf{GapClique}$ is a graph $G=(N,E)$ and a number $m\leq|N|$, and its
output is:

  * •

yes if $G$ contains a clique with $m$ nodes,

  * •

no if every clique of $G$ contains at most $\lfloor\frac{m}{3}\rfloor$ nodes.

From the PCP theorem and its applications to hardness of approximation (Feige
et al., 1996; Arora and Safra, 1998; Arora et al., 1998), it is known that
$\mathsf{GapClique}$ is NP-hard (in fact even if $\frac{1}{3}$ is replaced by
any $\delta\in(0,1)$). In other words, there exists a polynomial-time
reduction that takes as input a Boolean formula $\varphi$ and that outputs a
graph $G$ and an integer $m$ such that (1) if $\varphi$ is satisfiable then
$G$ contains a clique with $m$ nodes; and (2) if $\varphi$ is not satisfiable
then every clique of $G$ contains at most $\lfloor\frac{m}{3}\rfloor$ nodes.

The idea of our proof of Theorem 9 is then to show that if the problem of
computing the $\mathsf{SHAP}$ score for Boolean classifiers given as 2-POS-DNF
formulas admits an $\varepsilon$-PRA, then there exists a BPP algorithm for
$\mathsf{GapClique}$. Hence, we would conclude that $\text{\rm
NP}\subseteq\text{\rm BPP}$, which in turn implies that $\text{\rm
NP}=\text{\rm RP}$ (Ko, 1982). The proof is technical, and it is divided into
five modular parts, highlighted in bold in the remaining of this section.

##### The $\mathsf{SHAP}$-score of a Boolean classifier of the form $M\lor x$.

Given a set of features $X$, a Boolean classifier $M$ over $X$, and an
$S\subseteq X$, define

$\mathsf{\\#SAT}(M,S)\ \coloneqq\ |\\{\mathbf{e}\in\mathsf{ent}(X)\mid
M(\mathbf{e})=1\text{ and }\mathbf{e}(y)=1\text{ for every }y\in S\\}|.$

We can relate the $\mathsf{SHAP}$-score of a Boolean classifier of the form
$M\lor x$ to the quantities $\mathsf{\\#SAT}(\lnot M,S)$ as follows:

###### Lemma 11

Let $X$ be a set of features, $n=|X|$, $x\in X$, $M$ be a Boolean classifier
over $X\setminus\\{x\\}$, and 1 be the entity over $X$ such that
$\text{\rm{\bf 1}}(y)=1$ for every $y\in X$. Then

$\displaystyle\mathsf{SHAP}(M\vee x,\text{\rm{\bf 1}},x)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}\frac{k!(n-k-1)!}{n!}\cdot\frac{1}{2^{n-k}}\sum_{S\subseteq
X\setminus\\{x\\}\,:\,|S|=k}\mathsf{\\#SAT}(\neg M,S).$

Proof  Let $M^{\prime}$ be a Boolean classifier over $X$. Given $S\subseteq
X\setminus\\{x\\}$, we have that:

$\displaystyle\phi(M^{\prime},\text{\rm{\bf 1}},S\cup\\{x\\})$
$\displaystyle=$ $\displaystyle\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}},S\cup\\{x\\})}\frac{1}{2^{|X\setminus(S\cup\\{x\\})|}}\cdot
M^{\prime}(\mathbf{e})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{|X\setminus(S\cup\\{x\\})|}}\sum_{\mathbf{e}^{\prime}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|{X\setminus\\{x\\}}},S)}M^{\prime}_{+x}(\mathbf{e}^{\prime})$
$\displaystyle=$ $\displaystyle\frac{2}{2^{|X\setminus
S|}}\sum_{\mathbf{e}^{\prime}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|{X\setminus\\{x\\}}},S)}M^{\prime}_{+x}(\mathbf{e}^{\prime}).$

Besides, we have that:

$\displaystyle\phi(M^{\prime},\text{\rm{\bf 1}},S)$ $\displaystyle=$
$\displaystyle\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}},S)}\frac{1}{2^{|X\setminus S|}}\cdot M^{\prime}(\mathbf{e})$
$\displaystyle=$ $\displaystyle\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}},S)\,:\,\mathbf{e}(x)=0}\frac{1}{2^{|X\setminus S|}}\cdot
M^{\prime}(\mathbf{e})\ +\ \sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}},S)\,:\,\mathbf{e}(x)=1}\frac{1}{2^{|X\setminus S|}}\cdot
M^{\prime}(\mathbf{e})$ $\displaystyle=$ $\displaystyle\frac{1}{2^{|X\setminus
S|}}\cdot\bigg{(}\sum_{\mathbf{e}^{\prime}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}M^{\prime}_{-x}(\mathbf{e}^{\prime})\ +\
\sum_{\mathbf{e}^{\prime}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}M^{\prime}_{+x}(\mathbf{e}^{\prime})\bigg{)}.$

Therefore, we conclude that:

$\displaystyle\phi(M^{\prime},\text{\rm{\bf
1}},S\cup\\{x\\})-\phi(M^{\prime},\text{\rm{\bf 1}},S)\ =\
\frac{1}{2^{|X\setminus
S|}}\cdot\bigg{(}\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}M^{\prime}_{+x}(\mathbf{e})-\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}M^{\prime}_{-x}(\mathbf{e})\bigg{)}.$

Considering this equation with $M^{\prime}\coloneqq M\vee x$, we deduce that:

$\displaystyle\phi(M\vee x$ $\displaystyle,\text{\rm{\bf
1}},S\cup\\{x\\})-\phi(M\vee x,\text{\rm{\bf 1}},S)\ =$
$\displaystyle\frac{1}{2^{|X\setminus
S|}}\cdot\bigg{(}\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}(M\vee
x)_{+x}(\mathbf{e})-\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}(M\vee x)_{-x}(\mathbf{e})\bigg{)}\ =$
$\displaystyle\frac{1}{2^{|X\setminus
S|}}\cdot\bigg{(}\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}1-\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}M(\mathbf{e})\bigg{)}\ =$
$\displaystyle\frac{1}{2^{|X\setminus
S|}}\cdot\bigg{(}\sum_{\mathbf{e}\in\mathsf{cw}(\text{\rm{\bf
1}}_{|X\setminus\\{x\\}},S)}(1-M(\mathbf{e}))\bigg{)}\ =$
$\displaystyle\frac{1}{2^{|X\setminus S|}}\cdot\mathsf{\\#SAT}(\neg M,S).$

By considering the definition of the $\mathsf{SHAP}$ score, we obtain that:

$\displaystyle\mathsf{SHAP}(M\vee x$ $\displaystyle,\text{\rm{\bf 1}},x)\ =$
$\displaystyle\sum_{S\subseteq
X\setminus\\{x\\}}\frac{|S|!(|X|-|S|-1)!}{|X|!}\cdot\bigg{(}\phi(M\vee
x,\text{\rm{\bf 1}},S\cup\\{x\\})-\phi(M\vee x,\text{\rm{\bf 1}},S)\bigg{)}\
=$ $\displaystyle\sum_{k=0}^{n-1}\,\sum_{S\subseteq
X\setminus\\{x\\}\,:\,|S|=k}\frac{|S|!(|X|-|S|-1)!}{|X|!}\cdot\frac{1}{2^{|X\setminus
S|}}\cdot\mathsf{\\#SAT}(\neg M,S)\ =$
$\displaystyle\sum_{k=0}^{n-1}\frac{k!(n-k-1)!}{n!}\cdot\frac{1}{2^{n-k}}\sum_{S\subseteq
X\setminus\\{x\\}\,:\,|S|=k}\mathsf{\\#SAT}(\neg M,S).$

This concludes the proof of Lemma 11.

##### A 2-POS-DNF formula for cliques.

Given a graph $G=(N,E)$ we define the formula $\theta(G)$ in 2-POS-DNF by

$\displaystyle\theta(G)\coloneqq\bigvee_{\begin{subarray}{c}(a,b)\in(N\times
N)\\\ a\neq b\text{ and }(a,b)\not\in E\end{subarray}}a\wedge b.$ (16)

Notice that the set of propositional variables occurring in $\theta(G)$ is the
same as the set $N$ of nodes of $G$, given that $G$ satisfies condition (A).
For $S\subseteq N$ we define

$\displaystyle\mathsf{\\#CLIQUE}(G,S)$ $\displaystyle\coloneqq$
$\displaystyle|\\{Y\mid Y\text{ is a clique of }G\text{ and }S\subseteq
Y\\}|.$

Using Lemma 11, we can relate the $\mathsf{SHAP}$-score of the 2-POS-DNF
formula $\theta(G)\lor x$ to the quantities $\mathsf{\\#CLIQUE}(G,S)$ for
$S\subseteq N$ as follows.

###### Lemma 12

For every graph $G=(N,E)$ and $x\notin N$, letting $n=|N|$ and 1 be the entity
over $N\cup\\{x\\}$ such that $\text{\rm{\bf 1}}(y)=1$ for every $y\in
N\cup\\{x\\}$, we have:

$\displaystyle\mathsf{SHAP}(\theta(G)\vee x,\text{\rm{\bf
1}},x)=\frac{1}{2(n+1)}\sum_{k=0}^{n}\frac{k!(n-k)!}{n!}\cdot\frac{1}{2^{n-k}}\sum_{S\subseteq
N\,:\,|S|=k}\mathsf{\\#CLIQUE}(G,S).$

Proof  The crucial observation is that the following relation holds for every
$S\subseteq N$:

$\displaystyle\mathsf{\\#CLIQUE}(G,S)$ $\displaystyle=$
$\displaystyle\mathsf{\\#SAT}(\neg\theta(G),S).$

Indeed, this can be seen by defining the bijection that to every subset $Y$ of
$N$ associates the valuation $\nu_{Y}$ of $\theta(G)$ such that $\nu_{Y}(x)=1$
if and only if $x\in Y$, and then checking that [$Y$ is a clique of $G$ with
$S\subseteq Y$] if and only if [$\nu_{Y}\models\neg\theta(G)$ and
$\nu_{Y}(x)=1$ for all $x\in S$]. Therefore, we have from Lemma 11 that

$\displaystyle\mathsf{SHAP}(\theta(G)\vee x,\text{\rm{\bf 1}},x)$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n}\frac{k!(n-k)!}{(n+1)!}\cdot\frac{1}{2^{n+1-k}}\sum_{S\subseteq
N\,:\,|S|=k}\mathsf{\\#SAT}(\neg\theta(G),S)$ $\displaystyle=$
$\displaystyle\frac{1}{2(n+1)}\sum_{k=0}^{n}\frac{k!(n-k)!}{n!}\cdot\frac{1}{2^{n-k}}\sum_{S\subseteq
N\,:\,|S|=k}\mathsf{\\#CLIQUE}(G,S).$

##### Working with amplified graphs.

In this proof, we consider an amplification technique from (Sinclair, 1993).
More precisely, given a graph $G=(N,E)$ and a natural number $r\geq 1$, define
the amplified graph $G^{r}=(N^{r},E^{r})$ of $G$ as follows. For each $a\in
N$, let $N^{a}\coloneqq\\{a_{1},\ldots,a_{r}\\}$ and
$N^{r}\coloneqq\bigcup_{a\in N}N^{a}$, and let $E^{r}$ be the following set of
edges:

$\displaystyle E^{r}$ $\displaystyle\coloneqq$
$\displaystyle\\{(a_{i},a_{j})\mid a_{i},a_{j}\in N^{a}\text{ and }i\neq
j\\}\cup\\{(a_{i},b_{j})\mid a_{i}\in N^{a},b_{j}\in N^{b}\text{ and }(a,b)\in
E\\}.$

Thus, the amplified graph $G^{r}$ is constructed by copying $r$ times each
node of $G$, by connecting for each node of $G$ all of its copies as a clique,
and finally by connecting copies $a_{i}$, $b_{j}$ of nodes $a$, $b$ of $G$,
respectively, whenever $a$ and $b$ are connected in $G$ by an edge. Notice in
particular that $G^{1}$ is simply $G$. An example of this construction for
$r=2$ is illustrated in Figure 3.

$a$$b$$c$$d$$a_{1}$$a_{2}$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$ Figure 3:
Illustration of the amplification construction for $r=2$. On the left a graph
$G$, on the right the corresponding graph $G^{2}$. We only illustrate the
construction for $r=2$, as for $r\geq 3$ this very quickly becomes unreadable.

Let then $T$ be a clique of $G^{r}$. We say that $T$ _is a witness_ of the
clique $\\{a\in N\mid N^{a}\cap T\neq\emptyset\\}$ of $G$. Observe that a
clique of $G^{r}$ witnesses a unique clique of $G$ by definition, but that a
clique of $G$ can have multiple witnessing cliques in $G^{r}$. Moreover,
letting $S$ be a clique of $G$, we write $\mathsf{Wit}(G^{r},S)$ for the set
of cliques of $G^{r}$ that are witnesses of $S$. We then show the following
three properties of $G^{r}$:

  1. (i)

if $S_{1}$, $S_{2}$ are distinct cliques of $G$, then
$\mathsf{Wit}(G^{r},S_{1})\cap\mathsf{Wit}(G^{r},S_{2})=\emptyset$. Indeed,
assuming without loss of generality that $S_{1}\not\subseteq S_{2}$ (the case
$S_{2}\not\subseteq S_{1}$ being symmetrical) and letting $a\in S_{1}\setminus
S_{2}$, it is clear by that, by definition of being a witness, for any
$T\in\mathsf{Wit}(G^{r},S_{1})$ we must have $N^{a}\cap T\neq\emptyset$,
whereas for any $T\in\mathsf{Wit}(G^{r},S_{2})$ we have $N^{a}\cap
T=\emptyset$.

  2. (ii)

if $S$ is a clique of $G$, then $|\mathsf{Wit}(G^{r},S)|=(2^{r}-1)^{|S|}$.
Indeed, let $T\in\mathsf{Wit}(G^{r},S)$. By definition of being a witness, $T$
cannot contain any node of the form $a_{i}$ for $a\notin S$. Moreover, for
every $a\in S$, by definition of being a witness again, the set $T\cap N^{a}$
must be a non-empty subset of $N^{a}$. Since for every $a\in N$ there are
exactly $(2^{r}-1)$ non-empty subsets of $N^{a}$, this shows that
$|\mathsf{Wit}(G^{r},S)|\leq(2^{r}-1)^{|S|}$. Additionally, any set of the
form $\bigcup_{a\in S}S_{a}$ where each $S_{a}$ is a non-empty subset of
$N^{a}$ is in fact in $\mathsf{Wit}(G^{r},S)$: this is simply because $S$
itself is a clique of $S$ and by definition of the graph $G^{r}$. This shows
that $|\mathsf{Wit}(G^{r},S)|\geq(2^{r}-1)^{|S|}$, hence
$|\mathsf{Wit}(G^{r},S)|=(2^{r}-1)^{|S|}$ indeed.

  3. (iii)

for every natural number $\ell$, if all cliques of $G$ have size at most
$\ell$, then all cliques of $G^{r}$ have size at most $\ell\cdot r$. Indeed,
for any clique $T$ of $G^{r}$, letting $S$ be the clique of $S$ that $T$
witnesses, it is clear that $|T|\leq r\cdot|S|$ (with the equality being
reached when $T\cap N^{a}=N^{a}$ for every $a\in S$).

We use these properties to prove our next lemma.

###### Lemma 13

Let $G=(N,E)$ be a graph, $x\notin N$, $n\coloneqq|N|$, and $m,r$ be natural
numbers such that $1\leq m\leq n$ and $r\geq 1$. Then:

  1. (a)

If every clique of $G$ contains at most $\lfloor\frac{m}{3}\rfloor$ nodes,
then

$\displaystyle\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf 1}},x)$
$\displaystyle\leq$ $\displaystyle\frac{2^{2\lfloor\frac{m}{3}\rfloor
r+n}}{2^{n\cdot r+1}}.$

  2. (b)

If $G$ contains a clique with $m$ nodes, then

$\displaystyle\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf 1}},x)$
$\displaystyle\geq$ $\displaystyle\frac{1}{(n\cdot
r+1)}\cdot\frac{2^{mr}}{2^{n\cdot r+1}}.$

Proof

  1. (a)

Given that $|N^{r}|=n\cdot r$, we have from Lemma 12 that:

$\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf 1}},x)\ =\ \frac{1}{2(n\cdot
r+1)}\sum_{k=0}^{n\cdot r}\frac{k!(n\cdot r-k)!}{(n\cdot r)!}\ \cdot\\\
\frac{1}{2^{n\cdot r-k}}\sum_{S\subseteq
N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S).$

Now, since every clique of $G$ contains at most $\lfloor\frac{m}{3}\rfloor$
nodes, we have by Item (iii) that all cliques of $G^{r}$ have size at most
$\lfloor\frac{m}{3}\rfloor\cdot r$. Hence when
$k>\lfloor\frac{m}{3}\rfloor\cdot r$ it holds that
$\mathsf{\\#CLIQUE}(G^{r},S)=0$ for any $S\subseteq N^{r}$ with $|S|=k$.
Therefore, we have that

$\displaystyle\mathsf{SHAP}(\theta($ $\displaystyle G^{r})\vee x,\text{\rm{\bf
1}},x)\ =$ $\displaystyle\frac{1}{2(n\cdot
r+1)}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot r}\frac{k!(n\cdot
r-k)!}{(n\cdot r)!}\cdot\frac{1}{2^{n\cdot r-k}}\sum_{S\subseteq
N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S)\ \leq$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\frac{k!(n\cdot r-k)!}{(n\cdot r)!}\sum_{S\subseteq
N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S)\ =$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\frac{1}{\binom{n\cdot r}{k}}\sum_{S\subseteq
N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S).$

Now, defining $\mathsf{\\#CLIQUE}(G,\ell)\coloneqq|\\{Y\mid Y\text{ is a
clique of }G\text{ and }|Y|=\ell\\}|$, observe that we have

$\displaystyle\sum_{S\subseteq N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S)$
$\displaystyle=$ $\displaystyle\sum_{S\subseteq N^{r}\,:\,|S|=k}\ \
\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\ S\subseteq
Y\end{subarray}}1$ $\displaystyle=$ $\displaystyle\sum_{S\subseteq
N^{r}\,:\,|S|=k}\ \ \sum_{\ell=k}^{|N^{r}|}\ \
\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\ |Y|=\ell\\\ S\subseteq
Y\end{subarray}}1$ $\displaystyle=$ $\displaystyle\sum_{S\subseteq
N^{r}\,:\,|S|=k}\ \ \sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot r}\ \
\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\ |Y|=\ell\\\ S\subseteq
Y\end{subarray}}1$ $\displaystyle=$
$\displaystyle\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot r}\ \
\sum_{S\subseteq N^{r}\,:\,|S|=k}\ \ \sum_{\begin{subarray}{c}Y\text{ clique
of }G^{r}\\\ |Y|=\ell\\\ S\subseteq Y\end{subarray}}1$ $\displaystyle=$
$\displaystyle\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot r}\ \
\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\ |Y|=\ell\end{subarray}}\
\ \sum_{S\subseteq Y\,:\,|S|=k}1$ $\displaystyle=$
$\displaystyle\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot r}\ \
\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\
|Y|=\ell\end{subarray}}\binom{|Y|}{k}$ $\displaystyle=$
$\displaystyle\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot r}\ \
\binom{\ell}{k}\sum_{\begin{subarray}{c}Y\text{ clique of }G^{r}\\\
|Y|=\ell\end{subarray}}1$ $\displaystyle=$
$\displaystyle\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\binom{\ell}{k}\mathsf{\\#CLIQUE}(G^{r},\ell),$

where the third equality is simply because all cliques of $G^{r}$ have size at
most $\lfloor\frac{m}{3}\rfloor\cdot r$, again by Item (iii). Hence, we have
that

$\displaystyle\mathsf{SHAP}(\theta($ $\displaystyle G^{r})\vee x,\text{\rm{\bf
1}},x)\ \leq$ $\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\frac{1}{\binom{n\cdot r}{k}}\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\binom{\ell}{k}\mathsf{\\#CLIQUE}(G^{r},\ell)\ \leq$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\frac{1}{\binom{n\cdot r}{k}}\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\binom{n\cdot r}{k}\mathsf{\\#CLIQUE}(G^{r},\ell)\ =$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\sum_{\ell=k}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)\ \leq$ $\displaystyle\frac{1}{2(n\cdot
r+1)}\cdot\frac{1}{2^{n\cdot r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{k=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)\ \leq$
$\displaystyle\frac{(\lfloor\frac{m}{3}\rfloor\cdot r+1)}{2(n\cdot
r+1)}\cdot\frac{1}{2^{n\cdot r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)\ \leq$ $\displaystyle\frac{n\cdot
r+1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)\ =$
$\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell).$

But notice that $\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)$ is simply the total number of cliques of
$G^{r}$. Given a clique $S$ of $G$ with $\ell$ elements, remember that by Item
(ii) we have that $|\mathsf{Wit}(G^{r},S)|=(2^{r}-1)^{\ell}$. Hence, given
that each clique of $G$ has at most $\lfloor\frac{m}{3}\rfloor$ nodes, that
$G$ has at most $\binom{n}{\ell}$ cliques with $\ell$ nodes, and that every
clique of $G^{r}$ witnesses a unique clique of $G$, we have that the total
number of cliques of $G^{r}$ is bounded as follows:

$\displaystyle\sum_{\ell=0}^{\lfloor\frac{m}{3}\rfloor\cdot
r}\mathsf{\\#CLIQUE}(G^{r},\ell)$ $\displaystyle\leq$
$\displaystyle\sum_{\ell^{\prime}=0}^{\lfloor\frac{m}{3}\rfloor}\binom{n}{\ell^{\prime}}(2^{r}-1)^{\ell^{\prime}}.$

Therefore, we conclude that:

$\displaystyle\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf 1}},x)$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{\ell^{\prime}=0}^{\lfloor\frac{m}{3}\rfloor}\binom{n}{\ell^{\prime}}(2^{r}-1)^{\ell^{\prime}}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor
r}}\sum_{\ell^{\prime}=0}^{\lfloor\frac{m}{3}\rfloor}\binom{n}{\ell^{\prime}}(2^{r}-1)^{\lfloor\frac{m}{3}\rfloor}$
$\displaystyle=$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor
r}}\cdot(2^{r}-1)^{\lfloor\frac{m}{3}\rfloor}\sum_{\ell^{\prime}=0}^{\lfloor\frac{m}{3}\rfloor}\binom{n}{\ell^{\prime}}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor
r}}\cdot(2^{r}-1)^{\lfloor\frac{m}{3}\rfloor}\sum_{\ell^{\prime}=0}^{n}\binom{n}{\ell^{\prime}}$
$\displaystyle=$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\cdot(2^{r}-1)^{\lfloor\frac{m}{3}\rfloor}\cdot
2^{n}$ $\displaystyle\leq$ $\displaystyle\frac{1}{2}\cdot\frac{1}{2^{n\cdot
r-\lfloor\frac{m}{3}\rfloor r}}\cdot 2^{\lfloor\frac{m}{3}\rfloor r}\cdot
2^{n}$ $\displaystyle=$ $\displaystyle\frac{2^{2\lfloor\frac{m}{3}\rfloor
r+n}}{2^{n\cdot r+1}}.$

  2. (b)

First, we claim that $G^{r}$ contains at least $2^{mr}$ cliques. Indeed, let
$S$ be a clique with $m$ nodes that $G$ contains (by hypothesis). Every subset
$S^{\prime}$ of $S$ is also a clique of $G$. Now, by Item (i) and Item (ii),
we have that the number of witnesses of all the subcliques of $S$ is equal to

$\displaystyle\bigg{|}\bigcup_{S^{\prime}\subseteq
S}\mathsf{Wit}(G^{r},S^{\prime})\bigg{|}\ $ $\displaystyle=\
\sum_{S^{\prime}\subseteq S}|\mathsf{Wit}(G^{r},S^{\prime})|$ $\displaystyle=\
\sum_{\ell=0}^{m}\binom{m}{\ell}(2^{r}-1)^{\ell}$ $\displaystyle=\
\sum_{\ell=0}^{m}\binom{m}{\ell}(2^{r}-1)^{\ell}1^{m-\ell}$ $\displaystyle=\
(2^{r}-1+1)^{m}$ $\displaystyle=\ 2^{mr}.$

All terms in the summation of $\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf
1}},x)$ are non-negative. Hence, we have that:

$\displaystyle\mathsf{SHAP}(\theta($ $\displaystyle G^{r})\vee x,\text{\rm{\bf
1}},x)\ =$ $\displaystyle\frac{1}{2(n\cdot r+1)}\sum_{k=0}^{n\cdot
r}\frac{k!(n\cdot r-k)!}{n\cdot r!}\cdot\frac{1}{2^{n\cdot
r-k}}\sum_{S\subseteq N^{r}\,:\,|S|=k}\mathsf{\\#CLIQUE}(G^{r},S)\ \geq$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{0!(n\cdot r)!}{(n\cdot
r)!}\cdot\frac{1}{2^{n\cdot r}}\sum_{S\subseteq
N^{r}\,:\,|S|=0}\mathsf{\\#CLIQUE}(G^{r},S)\ =$
$\displaystyle\frac{1}{2(n\cdot r+1)}\cdot\frac{1}{2^{n\cdot
r}}\cdot\mathsf{\\#CLIQUE}(G^{r},\emptyset).$

But $\mathsf{\\#CLIQUE}(G^{r},\emptyset)$ is the total number of cliques of
$G^{r}$, which we have just proved to be greater than or equal to $2^{mr}$.
Therefore

$\displaystyle\mathsf{SHAP}(\theta(G^{r})\vee x,\text{\rm{\bf 1}},x)$
$\displaystyle\geq$ $\displaystyle\frac{1}{(n\cdot
r+1)}\cdot\frac{2^{mr}}{2^{n\cdot r+1}},$

which concludes the proof of Lemma 13.

##### A technical lemma.

Last, we will need the following technical lemma.

###### Lemma 14

For every $\varepsilon\in(0,1)$, there exists $n_{\varepsilon}\in\mathbb{N}$
such that for every $n,m\in\mathbb{N}$ with $n\geq n_{\varepsilon}$ and $m\geq
1$, it holds that:

$\displaystyle(1+\varepsilon)\cdot 2^{2\lfloor\frac{m}{3}\rfloor n^{2}+n}$
$\displaystyle<$
$\displaystyle(1-\varepsilon)\cdot\frac{2^{mn^{2}}}{(n^{3}+1)}.$

The proof is straightforward and can be found in Appendix C.1.

##### Putting it all together.

We now have all the necessary ingredients to prove Theorem 9. Assume that the
problem of computing the $\mathsf{SHAP}$ score for Boolean classifiers given
as 2-POS-DNF formulas admits an $\varepsilon$-PRA, for some fixed
$\varepsilon\in(0,1)$, that we will denote by $\mathcal{A}$. By using
$\mathcal{A}$, we define the following BPP algorithm $\mathcal{B}$ for
$\mathsf{GapClique}$. Let $G=(N,E)$ be a graph with $n=|N|$ and
$m\in\\{0,\ldots,n\\}$. Then $\mathcal{B}(G,m)$ performs the following steps:

  1. 1.

If $m=0$, then return yes.

  2. 2.

Let $n_{\varepsilon}$ be the constant in Lemma 14. If $n\leq n_{\varepsilon}$,
then by performing an exhaustive search, check whether $G$ contains a clique
with $m$ nodes or if every clique of $G$ contains at most
$\lfloor\frac{m}{3}\rfloor$ nodes. In the former case return yes, in the
latter case return no.

  3. 3.

Construct the formula $\theta(G^{n^{2}})\vee x$, where $x$ is a fresh feature
(not occurring in $N^{n^{2}}$). Notice that $\theta(G^{n^{2}})\vee x$ is a
formula in 2-POS-DNF.

  4. 4.

Use algorithm $\mathcal{A}$ to compute
$s\coloneqq\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf 1}},x)$.

  5. 5.

If

$\displaystyle s$ $\displaystyle>$
$\displaystyle(1+\varepsilon)\cdot\frac{2^{2\lfloor\frac{m}{3}\rfloor
n^{2}+n}}{2^{n^{3}+1}},$

then return yes; otherwise return no.

Algorithm $\mathcal{B}$ works in polynomial time since $n_{\varepsilon}$ is a
fixed natural number (given that $\varepsilon$ is a fixed value in $(0,1)$),
amplified graph $G^{n^{2}}$ can be computed in polynomial time from $G$,
formula $\theta(G^{n^{2}})\vee x$ can be constructed in polynomial time from
$G^{n^{2}}$, algorithm $\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)$ works in time $p(\|\theta(G^{n^{2}})\vee x\|+\|\text{\rm{\bf 1}}\|)$
for a polynomial $p(\cdot)$, and bound
$(1+\varepsilon)\cdot\frac{2^{2\lfloor\frac{m}{3}\rfloor
n^{2}+n}}{2^{n^{3}+1}}$ can be computed in polynomial time in $n$. Therefore,
to conclude the proof we need to show that the error probability of algorithm
$\mathcal{B}$ is bounded by $\frac{1}{4}$.

  * •

Assume that every clique of $G$ contains at most $\lfloor\frac{m}{3}\rfloor$
nodes. Then the error probability of algorithm $\mathcal{B}$ is equal to
$\Pr(\mathcal{B}(G,m)$ returns yes$)$. By using the definition of
$\mathcal{B}$ and Lemma 13 (a) with $r=n^{2}$, we obtain that:

$\displaystyle\Pr($ $\displaystyle\mathcal{B}(G,m)\text{ returns {\bf yes}})\
=$ $\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)>(1+\varepsilon)\cdot\frac{2^{2\lfloor\frac{m}{3}\rfloor
n^{2}+n}}{2^{n^{3}+1}}\bigg{)}\ \leq$
$\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)>(1+\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\bigg{)}\ \leq$
$\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)>(1+\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\ \vee$
$\displaystyle\phantom{\Pr\bigg{(}}\mathcal{A}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)<(1-\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{)}\ =$ $\displaystyle
1-\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\leq(1+\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\ \wedge$
$\displaystyle\phantom{1-\Pr\bigg{(}}\mathcal{A}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf
1}},x)\geq(1-\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{)}\ =$ $\displaystyle
1-\Pr\bigg{(}\bigg{|}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)-\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf 1}},x)\bigg{|}\
\leq$ $\displaystyle\hskip
200.0pt\varepsilon\cdot\bigg{|}\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{|}\bigg{)}\ \leq$ $\displaystyle 1-\frac{3}{4}\ =\
\frac{1}{4},$

where in the last step we use the fact that $\mathcal{A}$ is an
$\varepsilon$-PRA for the problem of computing the $\mathsf{SHAP}$ score for
Boolean classifiers given as 2-POS-DNF formulas, and the fact that
$\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf 1}},x)\geq 0$ (as can be
seen from Lemma 12).

  * •

Assume now that $G$ contains a clique with $m$ nodes. We can assume that
$n>n_{\varepsilon}$, since otherwise we know that $\mathcal{B}$ returns the
correct answer in Step 2. Given that $n>n_{\varepsilon}$, we know from Lemma
14 that:

$\displaystyle(1+\varepsilon)\cdot\frac{2^{2\lfloor\frac{m}{3}\rfloor
n^{2}+n}}{2^{n^{3}+1}}$ $\displaystyle<$
$\displaystyle(1-\varepsilon)\cdot\frac{1}{(n^{3}+1)}\cdot\frac{2^{mn^{2}}}{2^{n^{3}+1}}.$
(17)

The error probability of algorithm $\mathcal{B}$ is equal to
$\Pr(\mathcal{B}(G,m)$ returns no$)$. By using the definition of
$\mathcal{B}$, Lemma 13 (b) with $r=n^{2}$, and inequality (17), we obtain
that:

$\displaystyle\Pr($ $\displaystyle\mathcal{B}(G,m)\text{ returns {\bf no}})\
=$ $\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\leq(1+\varepsilon)\cdot\frac{2^{2\lfloor\frac{m}{3}\rfloor
n^{2}+n}}{2^{n^{3}+1}}\bigg{)}\ \leq$
$\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)<(1-\varepsilon)\cdot\frac{1}{(n^{3}+1)}\cdot\frac{2^{mn^{2}}}{2^{n^{3}+1}}\bigg{)}\
\leq$ $\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)<(1-\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{)}\ \leq$
$\displaystyle\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)<(1-\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\ \vee$
$\displaystyle\phantom{\Pr\bigg{(}}\mathcal{A}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)>(1+\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{)}\ =$ $\displaystyle
1-\Pr\bigg{(}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)\geq(1-\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\ \wedge$
$\displaystyle\phantom{1-\Pr\bigg{(}}\mathcal{A}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf
1}},x)\leq(1+\varepsilon)\cdot\mathsf{SHAP}(\theta(G^{n^{2}})\vee
x,\text{\rm{\bf 1}},x)\bigg{)}\ =$ $\displaystyle
1-\Pr\bigg{(}\bigg{|}\mathcal{A}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf
1}},x)-\mathsf{SHAP}(\theta(G^{n^{2}})\vee x,\text{\rm{\bf 1}},x)\bigg{|}\
\leq$ $\displaystyle\hskip