# From SHAP Scores to Feature Importance Scores

Olivier Létoffé1 Xuanxiang Huang2 Nicholas Asher3&Joao Marques-Silva4
1IRIT, University of Toulouse, France  2CNRS@CREATE, Singapore
3IRIT, CNRS, France  4ICREA, University of Lleida, Spain
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A central goal of eXplainable Artificial Intelligence (XAI) is to assign
relative importance to the features of a Machine Learning (ML) model given
some prediction. The importance of this task of explainability by feature
attribution is illustrated by the ubiquitous recent use of tools such as SHAP
and LIME. Unfortunately, the exact computation of feature attributions, using
the game-theoretical foundation underlying SHAP and LIME, can yield manifestly
unsatisfactory results, that tantamount to reporting misleading relative
feature importance. Recent work targeted rigorous feature attribution, by
studying axiomatic aggregations of features based on logic-based definitions
of explanations by feature selection. This paper shows that there is an
essential relationship between feature attribution and a priori voting power,
and that those recently proposed axiomatic aggregations represent a few
instantiations of the range of power indices studied in the past. Furthermore,
it remains unclear how some of the most widely used power indices might be
exploited as feature importance scores (FISs), i.e. the use of power indices
in XAI, and which of these indices would be the best suited for the purposes
of XAI by feature attribution, namely in terms of not producing results that
could be deemed as unsatisfactory. This paper proposes novel desirable
properties that FISs should exhibit. In addition, the paper also proposes
novel FISs exhibiting the proposed properties. Finally, the paper conducts a
rigorous analysis of the best-known power indices in terms of the proposed
properties.

##  1 Introduction

The requirement of delivering trustworthy systems of artificial intelligence
(AI) and machine learning (ML) is arguably one of the most consequential
challenges in current computing research and practice. A growing number of
governments have put forth proposals for regulating the use of systems of
AI/ML (US Government, 2023; European Union, 2024), some of which are in the
process of becoming enforced regulations. Many companies that are stakeholders
in AI/ML are actively involved in building trust into the operation of highly
complex systems of AI/ML. Furthermore, it is widely accepted that trustworthy
AI/ML can only be achieved through the comprehensive use of (trustable)
methods for explaining the operation of those complex systems of AI/ML (High-
Level Expert Group on AI, 2019). This critical importance of explainability
justifies in part the massive interest in eXplainable AI (XAI) in recent years
(Montavon, Samek, and Müller, 2018; Guidotti et al., 2019; Samek et al., 2019;
Samek et al., 2021). Furthermore, in domains where the uses of AI/ML are
deemed of high-risk or are safety-critical, XAI must ensure the rigor of
computed explanations. Unfortunately, the most widely-used methods of XAI
offer no guarantees of rigor. Unsurprisingly, several results in recent years
have unveiled critical misconceptions of informal XAI (Ignatiev, 2020;
Marques-Silva, 2023).

Motivated by this state of affairs, a formal XAI (Marques-Silva and Ignatiev,
2022; Marques-Silva, 2022; Darwiche, 2023) that builds on logic-based
definitions of explanations and that in turn is deployed using highly
efficient automated reasoners has emerged. However, formal XAI also exhibits
some drawbacks, including the complexity of automated reasoning, but also the
need to offer human decision-makers mechanisms for summarizing information
about explanations. While non-rigorous methods of XAI have used so-called SHAP
scores (Lundberg and Lee, 2017) as a mechanism to convey to human decision-
makers information about relative feature importance, formal XAI focused
instead on finding explanations based on feature selection, i.e. finding sets
of features, with no apparent solution for addressing relative feature
importance.

SHAP scores have become a highly popular method in XAI (Molnar, 2023; Mosca et
al., 2022; Mishra, 2023). Nevertheless, recent work has demonstrated that the
rigorous computation of SHAP scores can be thoroughly unsatisfactory (Huang
and Marques-Silva, 2023a; Huang and Marques-Silva, 2023b; Huang and Marques-
Silva, 2024; Marques-Silva and Huang, 2024). Indeed, it is now known that even
for very simple classifiers, the computed SHAP scores can bear little
relationship with self-evident notions of feature importance. An immediate
consequence is that computed SHAP scores can be misleading, i.e. they can
induce human decision-makers in error, by assigning more importance to the
wrong features. Motivated by these negative results, researchers have proposed
alternative solutions for assessing relative feature importance (Yu, Ignatiev,
and Stuckey, 2023; Biradar et al., 2023; Yu et al., 2023; Biradar et al.,
2024), all of which are based on logic-based definitions of explanations.
Furthermore, axiomatic aggregations (Biradar et al., 2024) also reveal that
feature importance can be naturally related with power indices, i.e. measures
of voter importance in a priori voting power (see (Felsenthal and Machover,
2015) for an overview), but also with payoff vectors, i.e. measures of player
rewards in characteristic function games (see (Chalkiadakis, Elkind, and
Wooldridge, 2012)).

It should be underscored that there is a crucial difference between the focus
of power indices for measuring a priori voting power (Felsenthal and Machover,
2015) and the focus of SHAP scores (Lundberg and Lee, 2017). In power indices,
voter importance measures how likely each voter is to be _critical_ for a set
of voters to represent a winning coalition (e.g. see (Shapley and Shubik,
1954)). In contrast, the existing definitions of SHAP scores _overlook_ the
criticality of features, and instead measure feature contributions starting
from the expected values of the ML model. As discussed in this paper, this
fundamental difference is at the core of why SHAP scores can yield
unsatisfactory results.

Furthermore, and although the connection between feature attribution and power
indices proposed in recent work (Biradar et al., 2024) is intuitive, it is
unclear which power indices are best suited for feature attribution, or even
which properties such indices should exhibit. Our paper addresses these
issues. In particular, our work extends recent work on axiomatic aggregations
(Biradar et al., 2024) and their relationship with formal explanations in
several ways. First, we uncover the tight connection between feature
attribution in XAI and power indices in a priori voting power. Second, we
argue that feature attribution in XAI requires a more general formalization
than power indices, and develop such a formalization, namely feature
importance scores (FISs). Third, we overview several properties of interest
for FISs, and propose novel properties. Fourth, and motivated by the results
in this paper, we propose novel FISs, which can also find application in other
domains. Fifth, and finally, we provide a detailed characterization of which
FISs exhibit which properties.

##  2 Preliminaries

#### Classification problems.

Let ${\mathcal{F}}=\\{1,\ldots,m\\}$ denote a set of features and
${\mathcal{K}}=\\{c_{1},c_{2},\ldots,c_{K}\\}$ denote a set of classes. Each
feature $i\in{\mathcal{F}}$ takes values from a domain $\mathbb{D}_{i}$ which
is either categorical or ordinal. If ordinal, a domains can be discrete or
real-valued. Classes can also be categorical or ordinal. Throughout the paper,
we assume that domains are discrete-valued and that, unless otherwise stated,
classes are ordinal.

A feature space is defined by
$\mathbb{F}=\mathbb{D}_{1}\times\mathbb{D}_{2}\times\ldots\times\mathbb{D}_{m}$.
The notation $\mathbf{x}=(x_{1},\ldots,x_{m})$ denotes an arbitrary point in
feature space, where each $x_{i}$ is a variable taking values from
$\mathbb{D}_{i}$. Moreover, the notation $\mathbf{v}=(v_{1},\ldots,v_{m})$
represents a specific point in feature space, where each $v_{i},i=1,\ldots,m$
is a constant representing one concrete value from $\mathbb{D}_{i}$. An
_instance_ denotes a pair $(\mathbf{v},c)$, where $\mathbf{v}\in\mathbb{F}$
and $c\in{\mathcal{K}}$, and such that $c=\kappa(\mathbf{v})$. An ML
classifier ${\mathcal{M}}$ is characterized by a non-constant _classification
function_ $\kappa$ that maps feature space $\mathbb{F}$ into the set of
classes ${\mathcal{K}}$, i.e. $\kappa:\mathbb{F}\to{\mathcal{K}}$. Given the
above, we associate with a classifier ${\mathcal{M}}$, a tuple
$({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$.111The paper considers only
classification problems. However, under a suitable formalization, the paper’s
results are also valid for regression problems.

#### Selection of sets of points.

Given $\mathbf{x}$ and $\mathbf{v}$, and a set
${\mathcal{S}}\subseteq{\mathcal{F}}$, we define the predicate
$\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}$ to represent the logic
statement $(\land_{i\in{\mathcal{S}}}x_{i}=v_{i})$. Furthermore
$\Upsilon:2^{{\mathcal{S}}}\to 2^{\mathbb{F}}$, is defined by
$\Upsilon({\mathcal{S}};\mathbf{v})=\\{\mathbf{x}\in\mathbb{F}\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}\\}$.
Thus, $\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}$ iff
$\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})$.

Similarly, given an instance $(\mathbf{v},c)$, and for
$\mathbf{x}\in\mathbb{F}$,
${\mathcal{I}}(\mathbf{x};\mathbf{v})=\\{i\in{\mathcal{F}}\,|\,x_{i}=v_{i}\\}$
denotes the features for which both $\mathbf{x}$ and $\mathbf{v}$ take the
same values.

#### Expected value.

The _expected value_ of a classification function $\kappa$ is denoted by
$\mathbf{E}[\kappa]$. Furthermore,
$\mathbf{E}[\kappa\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]$
represents the expected value of $\kappa$ over points in feature space
consistent with the coordinates of $\mathbf{v}$ dictated by ${\mathcal{S}}$,
which is defined as follows:

$\mathbf{E}[\kappa\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]:=\nicefrac{{1}}{{|\Upsilon({\mathcal{S}};\mathbf{v})|}}\sum\nolimits_{\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})}\kappa(\mathbf{x})$
(1)

#### Explanation problems.

Given a classification problem ${\mathcal{M}}$ and a concrete instance
$(\mathbf{v},c)$, an _explanation problem_ ${\mathcal{E}}$ is a tuple
$({\mathcal{M}},(\mathbf{v},c))$. When describing concepts in explainability,
we assume an underlying explanation problem ${\mathcal{E}}$, with all
definitions parameterized on ${\mathcal{E}}$.

#### Shapley values.

Shapley values were proposed in the context of game theory by L. S. Shapley
(Shapley, 1953). Shapley values are defined relative to a set ${\mathcal{R}}$,
and a _characteristic function_ , i.e. a real-valued function defined on the
subsets of ${\mathcal{R}}$, $\upsilon:2^{{\mathcal{R}}}\to\mathbb{R}$, such
that $\upsilon(\emptyset)=0$.222The original formulation also required super-
additivity of the characteristic function, but that condition has been relaxed
in more recent works (Dubey, 1975; Young, 1985). It is well-known that Shapley
values represent the _unique_ function that, given ${\mathcal{R}}$ and
$\upsilon$, respects a number of important axioms (or properties). More detail
about Shapley values is available in standard references (Shapley, 1953;
Dubey, 1975; Young, 1985; Roth, 1988; Chalkiadakis, Elkind, and Wooldridge,
2012).

#### SHAP scores.

In the context of explainability, Shapley values are most often referred to as
SHAP scores (Strumbelj and Kononenko, 2010; Strumbelj and Kononenko, 2014;
Lundberg and Lee, 2017; Arenas et al., 2021; Arenas et al., 2023), and
consider a specific characteristic function
$\upsilon_{e}:2^{{\mathcal{F}}}\to\mathbb{R}$, which is defined by,

$\upsilon_{e}({\mathcal{S}};{\mathcal{E}})\leavevmode\nobreak\
\leavevmode\nobreak\ :=\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{E}[\kappa\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]$
(2)

Thus, given a set ${\mathcal{S}}\subseteq{\mathcal{F}}$ of features,
$\upsilon_{e}({\mathcal{S}};{\mathcal{E}})$ represents the expected value of
the classifier over the points of feature space represented by
$\Upsilon({\mathcal{S}};\mathbf{v})$. The formulation presented in earlier
work (Arenas et al., 2021; Arenas et al., 2023) allows for different input
distributions when computing the average values. For the purposes of this
paper, it suffices to consider solely a uniform input distribution, and so the
dependency on the input distribution is not accounted for. Independently of
the distribution considered, it should be clear that in most cases
$\upsilon_{e}(\emptyset)\not=0$; this is the case for example with boolean
classifiers (Arenas et al., 2021; Arenas et al., 2023).

To simplify notation, we use the following definitions:

$\displaystyle\Delta_{i}({\mathcal{S}};{\mathcal{E}})$
$\displaystyle:=\left(\upsilon_{e}({\mathcal{S}};{\mathcal{E}})-\upsilon_{e}({\mathcal{S}}\setminus\\{i\\};{\mathcal{E}})\right)$
(3) $\displaystyle\varsigma(|{\mathcal{S}}|)$
$\displaystyle:=\nicefrac{{1}}{{\left(|{\mathcal{F}}|\times\binom{|{\mathcal{F}}|-1}{|{\mathcal{S}}|-1}\right)}}$
(4)

Finally, let $\mathsf{Sc}_{E}:{\mathcal{F}}\to\mathbb{R}$, i.e. the SHAP score
for feature $i$, be defined by,

$\displaystyle\mathsf{Sc}_{E}(i;{\mathcal{E}}):=\sum\nolimits_{{\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\}}\varsigma(|{\mathcal{S}}|)\times\Delta_{i}({\mathcal{S}};{\mathcal{E}})$
(5)

Given an instance $(\mathbf{v},c)$, the SHAP score assigned to each feature
measures the _contribution_ of that feature with respect to the prediction.
From earlier work, it is understood that a positive/negative value indicates
that the feature can contribute to changing the prediction, whereas a value of
0 indicates no contribution (Strumbelj and Kononenko, 2010).

#### Abductive and contrastive explanations.

Given an explanation problem ${\mathcal{E}}$, a _weak abductive explanation_
(WAXp) is a set of features ${\mathcal{S}}$ such that the prediction remains
unchanged when the features in ${\mathcal{S}}$ are assigned the values
dictated by $\mathbf{v}$:

$\forall(\mathbf{x}\in\mathbb{F}).\left(\land_{i\in{\mathcal{S}}}x_{i}=v_{i}\right)\operatorname*{\rightarrow}\left(\kappa(\mathbf{x})=\kappa(\mathbf{v})\right)$
(6)

(The fixed features in ${\mathcal{S}}$ are said to be _sufficient_ for the
given prediction.) Moreover, an _abductive explanation_ (AXp) is a subset-
minimal WAXp. Similarly to the case of AXps, a _weak contrastive explanation_
(WCXp) is a set of features ${\mathcal{S}}$ such that the prediction can
change when the features not in ${\mathcal{S}}$ are assigned the values
dictated by $\mathbf{v}$:

$\exists(\mathbf{x}\in\mathbb{F}).\left(\land_{i\in{\mathcal{F}}\setminus{\mathcal{S}}}x_{i}=v_{i}\right)\land\left(\kappa(\mathbf{x})\not=\kappa(\mathbf{v})\right)$
(7)

A _contrastive explanation_ (CXp) is a subset-minimal WCXp. (Weak)
(abductive/contrastive) explanations are associated with predicates
$\mathsf{WAXp},\mathsf{AXp},\mathsf{WCXp},\mathsf{CXp}:2^{{\mathcal{F}}}\to\\{0,1\\}$
that hold true when the respective condition is satisfied. Progress in formal
explainability is summarized in recent overviews (Marques-Silva and Ignatiev,
2022; Marques-Silva, 2022; Darwiche, 2023).

A set of features is an AXp iff it is a minimal-hitting set (MHSes) of the set
of CXps (Ignatiev et al., 2020). Similarly, a set of features is a CXp iff it
is an MHS of the set of AXps. This result is referred to as MHS-duality, and
builds on Reiter’s seminal work on model-based diagnosis (Reiter, 1987).

#### Feature (ir)relevancy.

The set of features that are included in at least one (abductive) explanation
are defined as follows:

$\mathfrak{F}({\mathcal{E}}):=\\{i\in{\mathcal{X}}\,|\,{\mathcal{X}}\in
2^{{\mathcal{F}}}\land\mathsf{AXp}({\mathcal{X}})\\}$ (8)

(It is known that $\mathfrak{F}({\mathcal{E}})$ remains unchanged if CXps are
used instead of AXps (Ignatiev et al., 2020).) Finally, a feature
$i\in{\mathcal{F}}$ is _irrelevant_ , i.e. predicate
$\textnormal{{{Irrelevant}}}(i)$ holds true, if
$i\not\in\mathfrak{F}({\mathcal{E}})$; otherwise feature $i$ is _relevant_ ,
and predicate $\textnormal{{{Relevant}}}(i)$ holds true. Clearly, given some
explanation problem ${\mathcal{E}}$,
$\forall(i\in{\mathcal{F}}).\textnormal{{{Irrelevant}}}(i)\leftrightarrow\neg\textnormal{{{Relevant}}}(i)\,$.

#### A priori voting power.

A priori voting power (Felsenthal and Machover, 2004; Felsenthal and Machover,
2015) measures how each voter, taken from some assembly of voters, has the
potential to impact the voting outcomes of coalitions made of voters from that
assembly. A _weighted voting game_ (WVG) is defined for an assembly of voters
${\mathcal{F}}=\\{1,\ldots,m\\}$, where each voter $i\in{\mathcal{F}}$ has
some voting power $w_{i}$ (which we assume to be a non-negative integer).
Furthermore, the game is characterized by a quota
$Q\leq\sum_{i\in{\mathcal{F}}}w_{i}$. A subset of the voters
${\mathcal{S}}\subseteq{\mathcal{F}}$ is a coalition voting the same way, i.e.
either in favor or against. A coalition is a _winning coalition_ if
$\sum_{i\in{\mathcal{S}}}w_{i}\geq{Q}$; otherwise it is a losing coalition. A
WVG ${\mathcal{W}}$ is represented by $[Q;w_{1},\ldots,w_{m}]$ (Felsenthal and
Machover, 2015). Given a WVG, a _power index_ (or just _index_),
$\mathsf{Idx}:{\mathcal{F}}\to\mathbb{R}$, maps each voter to a real number,
measuring the voter’s capacity to influence voting decisions relative to other
voters. In the more general setting of characteristic function games
(Chalkiadakis, Elkind, and Wooldridge, 2012), power indices are referred to as
_payoff vectors_.

##  3 Related Work

#### Power indices.

Work on a priori voting power traces back at least to the mid 1940s (Penrose,
1946). Over the years, different power indices have been proposed as
mechanisms for assigning relative importance to voting members of an assembly.
While comprehensive lists of power indices exist (Andjiga, Chantreuil, and
Lepelley, 2003; Felsenthal and Machover, 2004; Felsenthal and Machover, 2015),
in this paper we only consider some of the best-known power indices: Shapley-
Shubik (Shapley and Shubik, 1954), Banzhaf (Banzhaf III, 1965), Deegan-Packel
(Deegan and Packel, 1978), Johnston (Johnston, 1978), Holler-Packel (Holler
and Packel, 1983), Andjiga (Andjiga, Chantreuil, and Lepelley, 2003), and the
Responsibility index (Biradar et al., 2024) (which can be related with earlier
work (Chockler, Halpern, and Kupferman, 2008)). For more details on power
indices the reader is invited to look at the more general setting of
cooperative game theory (Chalkiadakis, Elkind, and Wooldridge, 2012).

#### Axiomatic aggregations.

Motivated by a growing number of examples where SHAP scores yield misleading
relative feature importance, prior work has proposed ways of computing
measures of relative feature importance that address the limitations of
existing SHAP scores, namely _formal feature attribution_ (Yu, Ignatiev, and
Stuckey, 2023; Yu et al., 2023), and selected _axiomatic aggregation schemes_
(Biradar et al., 2023; Biradar et al., 2024), all of which are based on
abductive explanations. Even more importantly, recent work has demonstrated
that formal feature attribution corresponds to some proposed axiomatic
aggregation schemes (Biradar et al., 2024), and that these correspond to a few
well-known power indices (Deegan and Packel, 1978; Holler and Packel, 1983;
Chockler, Halpern, and Kupferman, 2008).

#### Corrected SHAP scores.

Other recent work observes that the problems with existing SHAP scores result
from the characteristic function used (Létoffé, Huang, and Marques-Silva,
2024), and proposes alternative characteristic functions, which eliminate the
known limitations of SHAP scores.

##  4 Formalizations of FISs

This section formalizes the best-known power indices, but targets the context
of explainability by feature attribution. The proposed formalizations will be
referred to as _Feature Importance Scores_ (FISs).

#### Why power indices for feature attribution?

Most of the existing work on using Shapley values in explainability relates
with the original work of L. Shapley for assigning values to the players of an
$n$-player cooperative game. Furthermore, and as noted earlier in Section 2,
the characteristic function used in the case of explainability has been the
expected value of the ML model (Lundberg and Lee, 2017; Van den Broeck et al.,
2022; Arenas et al., 2023).333For classification problems with unordered
classes, the expected value would be ill-defined. Recent work demonstrated
that such characteristic function can produce unsatisfactory relative orders
of feature importance.444It should be unsurprising that not all characteristic
functions may be suitable for the purposes of explainability by feature
attribution using Shapley values. The question is then which characteristic
function(s) might be the most adequate. In fact, it is apparent that feature
importance is far more related with a priori voting power than with arbitrary
$n$-player games, which impose no restrictions on the characteristic function
used. This relationship is exploited for example in recent work (Biradar et
al., 2024). Moreover, early work on voting power was clear about how to
measure the importance of each voter in voting games. Indeed, and quoting from
(Shapley and Shubik, 1954): “ _Our definition of the power of an individual
member depends on the chance he has of being critical to the success of a
winning coalition_ ”. All of the power indices briefly summarized above
explicitly measure the importance of an individual member (in our case a
feature) at being _critical_. The same insight can be used in explainability
by feature attribution. We can view feature attribution as a voting game, as
follows. A set of fixed features represents a coalition. A set of fixed
features is a winning coalition if those features are sufficient for the given
prediction. Furthermore, and adapting the quote above (Shapley and Shubik,
1954): _the importance of a feature depends on the chance it has of being
critical for a set of fixed features to be sufficient for a given prediction._
Moreover, it is plain to conclude that power indices and their use in
explainability will yield fundamentally different measures of feature
importance than what earlier work on SHAP scores did (Lundberg and Lee, 2017).
Finally, one could argue that capturing feature attribution by mimicking power
indices should not be warranted. However, as the most widely used version of
SHAP scores confirms, by choosing a problematic characteristic function, one
may obtain unsatisfactory results.

#### Why FISs?

In cooperative game theory, each characteristic function defines a concrete
game. In this case, the Shapley values assign relative importance to each
player, for the given game (Shapley, 1953). In the case of a priori voting
power, the (usually implicit) characteristic function captures the notion of a
voter being critical for a winning coalition; this is often reflected in terms
of the winning coalitions that are accounted for. In the case of feature
attribution for XAI, the situation is somewhat more complex. We adopt the
approach used for power indices, namely we will look at the cases when a
feature is critical for a winning coalition (i.e. fixed features sufficient
for prediction), and such that such coalition may or may not be subset-
minimal. In addition, we will adapt the best-known power indices. However, we
associate a parameterizable characteristic function with each FIS, which may
or may not be left implicit. Then, each explanation problem is used to set the
characteristic function to consider, and as a result produce the FIS
associated with the different features.

In contrast with other work (Biradar et al., 2024), FISs will be parameterized
given an explanation problem and a chosen characteristic function. Afterwards,
we detail the assumptions that must be made to obtain the indices proposed
elsewhere (Yu, Ignatiev, and Stuckey, 2023; Biradar et al., 2023; Yu et al.,
2023; Biradar et al., 2024).

###  4.1 Formalizing Template Scores

We will use the following concepts. First,
$\upsilon:2^{{\mathcal{F}}}\to\mathbb{R}$ is a characteristic function.
Furthermore, we parameterize $\upsilon$ using the target explanation problem
${\mathcal{E}}$, i.e. when defining the characteristic function, we will use
the notation $\upsilon({\mathcal{S}};{\mathcal{E}})$, indicating that we are
computing the characteristic function for some set ${\mathcal{S}}$, and that
the characteristic function is parameterized on ${\mathcal{E}}$. Given
${\mathcal{S}}\subseteq{\mathcal{F}}$ and $i\in{\mathcal{S}}$, we
define,555With respect to (3), $\Delta_{i}$ is being redefined to allow for a
parameterization on the characteristic function $\upsilon$.

$\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)=\upsilon({\mathcal{S}};{\mathcal{E}})-\upsilon({\mathcal{S}}\setminus\\{i\\};{\mathcal{E}})$
(9)

$\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)$ denotes the influence of
${\mathcal{S}}$ due to feature $i$. Moreover,
$\Delta({\mathcal{S}};{\mathcal{E}},\upsilon)=\sum_{i\in{\mathcal{S}}}\left(\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)\right)$
denotes the _relative influence_ of ${\mathcal{S}}$. (Although the definition
of $\Delta_{i}$ may seem different from recent works on explainability
(Lundberg and Lee, 2017; Van den Broeck et al., 2022; Arenas et al., 2023) it
follows the original work in game theory (Shapley, 1953) and a priori voting
power (Shapley and Shubik, 1954). More importantly, it is plain to conclude
that either can be used.)

Furthermore, the following additional sets are defined:

$\displaystyle\mathbb{WA}_{i}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{S}}\subseteq{\mathcal{F}}\,|\,\mathsf{WAXp}({\mathcal{S}};{\mathcal{E}})\land{i\in{\mathcal{S}}}\\}$
$\displaystyle\mathbb{WC}_{i}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{S}}\subseteq{\mathcal{F}}\,|\,\mathsf{WCXp}({\mathcal{S}};{\mathcal{E}})\land{i\in{\mathcal{S}}}\\}$
$\displaystyle\mathbb{A}_{i}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{S}}\subseteq{\mathcal{F}}\,|\,\mathsf{AXp}({\mathcal{S}};{\mathcal{E}})\land{i\in{\mathcal{S}}}\\}$
$\displaystyle\mathbb{C}_{i}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{S}}\subseteq{\mathcal{F}}\,|\,\mathsf{CXp}({\mathcal{S}};{\mathcal{E}})\land{i\in{\mathcal{S}}}\\}$

The definitions of $\mathbb{WA}$, $\mathbb{WC}$, $\mathbb{A}$, and
$\mathbb{C}$ mimic the ones above, but without specifying any feature.

#### Defining template scores.

FISs will be represented with the notation $\operatorname*{\mathsf{Sc}}$,
standing for _score_. An FIS is a function mapping features to some real
value, $\operatorname*{\mathsf{Sc}}:{\mathcal{F}}\to\mathbb{R}$. Moreover,
each FISs $\operatorname*{\mathsf{Sc}}$ will be the result of instantiating
some _template score_ $\mathsf{TSc}$, by specifying a concrete characteristic
function. Furthermore, each template score will generalize a well-known power
index.666In cases where the characteristic function is not parameterized on
some explanation problem, then a template score denotes an index. The term
template score serves to highlight that such indices can be parameterized by
some explanation problem. Moreover, as shown in Section 6, our framework
enables the definition of FISs without starting from a template score.
However, we first show how we obtain FISs from template scores. Moreover, and
besides resulting from a specific instantiation of a template score, each FIS
is parameterized on the target explanation problem ${\mathcal{E}}$. Several
generalized template scores (from which we will later derive FISs) are
presented next.777This paper introduces generalized formalizations of the
best-known power indices, starting from existing definitions of power indices
(e.g. (Andjiga, Chantreuil, and Lepelley, 2003)). Later, the paper shows how
suitable characteristic functions can be used to exactly capture the original
power indices.

#### Template score using Shapley-Shubik’s index.

Following (Shapley and Shubik, 1954), the template Shapley-Shubik score is
defined as follows:

$\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon):=\sum_{{\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\}}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|{\mathcal{F}}|\times\binom{|{\mathcal{F}}|-1}{|{\mathcal{S}}|-1}}\right)$
(10)

#### Template score using Banzhaf’s index.

Following (Banzhaf III, 1965), the template Banzhaf score is defined as
follows:

$\mathsf{TSc}_{B}(i;{\mathcal{E}},\upsilon):=\sum_{{\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\}}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{2^{|{\mathcal{F}}|-1}}\right)$
(11)

#### Template score using Johnston’s index.

Following (Johnston, 1978), the template Johnston score is defined as follows:

$\mathsf{TSc}_{J}(i;{\mathcal{E}},\upsilon):=\sum_{\begin{subarray}{c}{\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\}\\\
\Delta({\mathcal{S}};{\mathcal{E}},\upsilon)\not=0\end{subarray}}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{\Delta({\mathcal{S}};{\mathcal{E}},\upsilon)}\right)$
(12)

#### Template score using Deeghan-Packel index.

Following (Deegan and Packel, 1978), the template Deegan-Packel score is
defined as follows:

$\mathsf{TSc}_{D}(i;{\mathcal{E}},\upsilon):=\sum_{{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|{\mathcal{S}}|\times|\mathbb{A}({\mathcal{E}})|}\right)$
(13)

#### Template score using Holler-Packel index.

Following (Holler and Packel, 1983), the template Holler-Packel score is
defined as follows:

$\mathsf{TSc}_{H}(i;{\mathcal{E}},\upsilon):=\sum_{{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|\mathbb{A}({\mathcal{E}})|}\right)$
(14)

#### Template score using the Responsibility index.

Following (Biradar et al., 2024), the template Responsibility score is defined
as follows:

$\mathsf{TSc}_{R}(i;{\mathcal{E}},\upsilon):=\max\left\\{\left.\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|{\mathcal{S}}|}\,\right|\,{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})\right\\}$
(15)

The Deegan-Packel, Holler-Packel and Responsibility scores have been recently
applied in the context of explainability (Biradar et al., 2024). However, as
shown below, our definitions generalize the ones in (Biradar et al., 2024).
Furthermore, the relationship between the Responsibility score and the
Chockler index (Chockler, Halpern, and Kupferman, 2008) will be analyzed later
in Section 6.

#### Template score using Andjiga’s index.

Following (Andjiga, Chantreuil, and Lepelley, 2003), the template Andjiga
score is defined as follows:

$\mathsf{TSc}_{A}(i;{\mathcal{E}},\upsilon):=\sum_{{\mathcal{S}}\in\mathbb{WA}_{i}}\left(\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|{\mathcal{S}}|\times|\mathbb{WA}({\mathcal{E}})|}\right)$
(16)

#### Other power indices.

The importance of power indices for a priori voting power (and also
characteristic function games) has motivated the proposal of additional
proposals over the years (Penrose, 1946; Coleman, 1971; Curiel, 1987; Colomer,
1996; Berg, 1999; Freixas and Molinero, 2010; Freixas and Kaniovski, 2014;
Felsenthal, 2016). Our assessment is that these do not offer additional
insights for explainability by feature attribution. Nevertheless, it would be
simple to devise generalized template scores using those additional power
indices.

#### From template to instantiated scores.

Given one of the template scores $\mathsf{TSc}$ detailed above, we can
instantiate a concrete score by specifying the characteristic function to use.
(Clearly, we could consider arbitrary many characteristic functions.) Finally,
we obtain an FIS by parameterizing the concrete score given a target
explanation problem.

Suppose we have a template score $\mathsf{TSc}_{T}$ parameterized on some
explanation problem ${\mathcal{E}}$ and (unspecified) characteristic function
$\upsilon_{\tau}$. Then, the instantiated score $\mathsf{Sc}_{I}$ will be
defined as follows:

$\mathsf{Sc}_{I}(i;{\mathcal{E}}):=\mathsf{TSc}_{T}(i;{\mathcal{E}},\upsilon_{\tau})$

###  4.2 Existing Scores as FISs

The most often studied feature importance score, also referred to as the
(original) SHAP score is given by (5), and represented by $\mathsf{Sc}_{E}$.
Clearly, $\mathsf{Sc}_{E}$ can be viewed as an instantiation of the template
score based on Shapley-Shubik index, $\mathsf{TSc}_{S}$, using $\upsilon_{e}$
(see (2)):
$\mathsf{Sc}_{E}(i;{\mathcal{E}}):=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{e})$.

Recent work proposed a workaround to address some of the limitations of
existing SHAP scores, by replacing the classification function with an
alternative similarity (or matching) function (Létoffé, Huang, and Marques-
Silva, 2024).

$\zeta(\mathbf{x};{\mathcal{E}})=\left\\{\begin{array}[]{lcl}1&&\textnormal{if
$(\kappa(\mathbf{x})=\kappa(\mathbf{v}))$}\\\\[2.0pt]
0&&\textnormal{otherwise}\\\ \end{array}\right.$

Given the similarity function, we introduce a new characteristic function,

$\upsilon_{m}({\mathcal{S}};{\mathcal{E}})\leavevmode\nobreak\
\leavevmode\nobreak\ :=\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{E}[\zeta(\mathbf{x})\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]$
(17)

And, finally, the FIS using the similarity (or matching) function becomes:

$\mathsf{Sc}_{M}(i;{\mathcal{E}}):=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{m})$

###  4.3 Axiomatic Aggregations as FISs

Recent work (Biradar et al., 2024) showed that two variants of formal feature
attribution (Yu, Ignatiev, and Stuckey, 2023; Yu et al., 2023) can be viewed
as instantiations of the Deegan-Packel and Holler-Packel scores. In addition,
a third power index was also studied, namely the so-called Responsibility
score. Although this earlier work might seem to involve simpler formalizations
than the ones used in (13), (14), (15), because no characteristic function was
explicitly considered, we now show that it suffices to pick the right
characteristic function to obtain the same scores.888Earlier work (Biradar et
al., 2024) refers to indices and not to scores. We will opt to use the term
scores, and more specifically FISs, in the case of feature attribution in XAI.

#### Choosing a characteristic function.

The recently proposed axiomatic aggregations based on AXps are special cases
of the power indices introduced above, in the case of the Deegan-Packel,
Holler-Packel and Responsibility indices, when a concrete characteristic
function is used. We show below that this is indeed the case.

Let us define the following characteristic function:
$\upsilon_{a}({\mathcal{S}};{\mathcal{E}}):=\textnormal{ITE}(\mathsf{AXp}({\mathcal{S}};{\mathcal{E}}),1,0)$.
As a result, the Deegan-Packel, Holler-Packel and Responsibility indices can
be reformulated as FISs, as follows:

$\displaystyle\mathsf{Sc}_{D}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{D}(i;{\mathcal{E}},\upsilon_{a})=\sum\nolimits_{{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})}\left(\nicefrac{{1}}{{(|{\mathcal{S}}|\times|\mathbb{A}({\mathcal{E}})|)}}\right)$
$\displaystyle\mathsf{Sc}_{H}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{H}(i;{\mathcal{E}},\upsilon_{a})=\sum\nolimits_{{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})}\left(\nicefrac{{1}}{{|\mathbb{A}({\mathcal{E}})|}}\right)$
$\displaystyle\mathsf{Sc}_{R}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{R}(i;{\mathcal{E}},\upsilon_{a})=\max\left\\{\left.\nicefrac{{1}}{{|{\mathcal{S}}|}}\,\right|\,{\mathcal{S}}\in\mathbb{A}_{i}({\mathcal{E}})\right\\}$

These modified definitions match exactly those used in recent work (Biradar et
al., 2024).

#### Examples of unsatisfactory attributions.

For some of the scores studied in recent work (Biradar et al., 2024), there
are simple examples that illustrate that the computed scores can be
unsatisfactory in terms of relative order of feature importance. We analyze
two examples.

######  Example 1 (Holler-Packel FIS, $\mathsf{Sc}_{H}$).

Let the set of AXps be
$\mathbb{A}=\\{\\{1\\},\\{2,3,4,5,6\\},\\{2,3,4,5,7\\}\\}$. It is the case
that
$\mathsf{Sc}_{H}(1)=\mathsf{Sc}_{H}(6)=\mathsf{Sc}_{H}(7)<\mathsf{Sc}_{H}(2)=\mathsf{Sc}_{H}(3)=\mathsf{Sc}_{H}(4)=\mathsf{Sc}_{H}(5)$,
but it is apparent that feature 1 should be deemed more important than any of
the other features.

######  Example 2 (Responsibility FIS, $\mathsf{Sc}_{R}$).

Let the set of AXps be,

$\begin{array}[]{lcl}\mathbb{A}&=&\\{\\{1,8\\},\\{2,3,4\\},\\{2,3,5\\},\\{2,3,6\\},\\\
&&\leavevmode\nobreak\ \leavevmode\nobreak\
\\{2,3,7\\},\\{2,4,5\\},\\{2,4,6\\},\\{2,4,7\\},\\\ &&\leavevmode\nobreak\
\leavevmode\nobreak\ \\{2,5,6\\},\\{2,5,7\\},\\{2,5,6\\}\\}\end{array}$

It is the case that
$\mathsf{Sc}_{R}(1)=\mathsf{Sc}_{R}(8)>\mathsf{Sc}_{R}(2)$. However, it is
apparent that feature 2 should be deemed more important than feature 1;
feature 2 occurs in ten size 3 AXps, and features 1 and 8 only occur in one
size 2 AXp.

For the Deegan-Packel FIS, it is more difficult to find simple explanation
problems for which clearly unsatisfactory results are obtained. Nevertheless,
the Deegan-Packel FIS does not respect a few relevant properties of FISs, as
shown in Section 7.

###  4.4 Well-Known Power Indices as FISs

We now show how FISs can be obtained from the Shapley-Shubik, Banzhaf,
Johnston, and Andjiga indices.

#### FISs based on abductive explanations.

The simple characteristic function proposed in Section 4.3 serves for
capturing both formal feature attribution (Yu, Ignatiev, and Stuckey, 2023; Yu
et al., 2023) and axiomatic aggregations (Biradar et al., 2023; Biradar et
al., 2024), all of which are based on AXps. However, the same characteristic
function _cannot_ be used to capture either the Shapley-Shubik or the Banzhaf
indices (and this may indirectly justify why these power indices have not been
related with AXps before).

As a result, we introduce a somewhat different characteristic function:
$\upsilon_{w}({\mathcal{S}};{\mathcal{E}}):=\textnormal{ITE}(\mathsf{WAXp}({\mathcal{S}};{\mathcal{E}}),1,0)$.
(As shown next, $\upsilon_{w}$ enables capturing both the Shapley-Shubik and
the Banzhaf FISs, among others.)

Given $\upsilon_{w}$, we will obtain $\Delta_{i}({\mathcal{S}})=1$ only for
sets ${\mathcal{S}}\subseteq{\mathcal{F}}$ such that,
$\mathsf{WAXp}({\mathcal{S}})\land\neg\mathsf{WAXp}({\mathcal{S}}\setminus\\{i\\})$.
(Evidently, we can restrict further those sets with additional constraints.)
Observe that this definition of the characteristic function captures the cases
where feature $i$ is _critical_ for making ${\mathcal{S}}$ a _winning
coalition_ , and so naturally relates with the intended goals of Shapley-
Shubik’s index (Shapley and Shubik, 1954). However, the modified definition
does not equate with ${\mathcal{S}}$ being an AXp. Indeed, feature $i$ may be
critical, but other features may not be critical, and so ${\mathcal{S}}$ might
not be an AXp.

Given a set of features ${\mathcal{S}}\subseteq{\mathcal{F}}$ and a feature
$i\in{\mathcal{F}}$, with $i\in{\mathcal{S}}$, define the predicate denoting
whether a feature $i$ is critical for ${\mathcal{S}}$,

$\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{E}}):=\mathsf{WAXp}({\mathcal{S}};{\mathcal{E}})\land\neg\mathsf{WAXp}({\mathcal{S}}\setminus\\{i\\};{\mathcal{E}})$
(18)

As a result, we can instantiate the Shapley-Shubik, Banzhaf, Johnston and
Andjiga template scores as follows:

$\displaystyle\mathsf{Sc}_{S}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{w})=$
$\displaystyle\sum\nolimits_{{\mathcal{S}}\subseteq{\mathcal{F}}\land\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{E}})}\left(\nicefrac{{1}}{{\left(|{\mathcal{F}}|\times\binom{|{\mathcal{F}}|-1}{|{\mathcal{S}}|-1}\right)}}\right)$
$\displaystyle\mathsf{Sc}_{B}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{B}(i;{\mathcal{E}},\upsilon_{w})=$
$\displaystyle\sum\nolimits_{{\mathcal{S}}\subseteq{\mathcal{F}}\land\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{E}})}\left(\nicefrac{{1}}{{2^{|{\mathcal{F}}|-1}}}\right)$
$\displaystyle\mathsf{Sc}_{J}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{J}(i;{\mathcal{E}},\upsilon_{w})=$
$\displaystyle\sum\nolimits_{{\mathcal{S}}\subseteq{\mathcal{F}}\land\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{E}})}\left(\nicefrac{{1}}{{\Delta({\mathcal{S}})}}\right)$
$\displaystyle\mathsf{Sc}_{A}(i;{\mathcal{E}})$
$\displaystyle:=\mathsf{TSc}_{A}(i;{\mathcal{E}},\upsilon_{w})=$
$\displaystyle\sum\nolimits_{{\mathcal{S}}\subseteq{\mathcal{F}}\land\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{E}})}\left(\nicefrac{{1}}{{\left(|{\mathcal{S}}|\times|\mathbb{WA}|\right)}}\right)$

As can be concluded, by selecting a suitable characteristic function, we are
able to define feature importance scores that mimic some of the best-known
indices in a priori voting power.999It should be noted that we could also use
$\upsilon_{w}$ to obtain $\mathsf{Sc}_{D}$ and $\mathsf{Sc}_{H}$, by also
requiring ${\mathcal{S}}$ to be subset-minimal. However, we opted to mimic the
definitions proposed in earlier work (Biradar et al., 2024), where the concept
of characteristic function is not used. Furthermore, we note that
$\mathsf{Sc}_{E}$, $\mathsf{Sc}_{M}$ and $\mathsf{Sc}_{S}$ are defined using
the same template score, which generalizes the Shapley-Shubik index. These
scores are distinguished by the characteristic function used for instantiating
each one, and so can be referred to as the (expected-value) SHAP score (with
$\mathsf{Sc}_{E}(i;{\mathcal{E}})=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{e})$),
the similarity (or matching) SHAP score (with
$\mathsf{Sc}_{E}(i;{\mathcal{E}})=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{m})$),
and the formal SHAP score (with
$\mathsf{Sc}_{S}(i;{\mathcal{E}})=\mathsf{TSc}_{S}(i;{\mathcal{E}},\upsilon_{w})$).
Finally, some of the characteristic functions studied earlier in this paper,
e.g. $\upsilon_{e}$ or $\upsilon_{m}$, could also be used for defining
alternative scores starting from the template scores proposed at the beginning
of this section, e.g. $\mathsf{Sc}_{D}$ or $\mathsf{Sc}_{A}$, among others.

##  5 Proposed Properties for FISs

As observed earlier, FISs raise a number of challenges not faced either by
cooperative games or by power indices. More concretely, in the case of FISs,
the selected characteristic function will depend on the target explanation
problem and so also on the ML model being explained. As a result, the goal of
faithfully capturing feature importance requires identifying additional
properties, in addition to those that Shapley values in cooperative games are
well-known for.101010Different FISs may yield different rankings of features,
similarly to what is observed with power indices (Freixas, 2010; Doignon,
Moretti, and Öztürk, 2022). This explains in part why recent work (Biradar et
al., 2024) also proposed additional properties in addition to those that
characterize Shapley values in cooperative game theory.

###  5.1 Properties Targeting Cooperative Games

The best-known properties for values assigned to players of cooperative games
are those proposed by L. Shapley (Shapley, 1953). We start by overviewing
well-known properties for indices (and so for template scores), which are
parameterized on the explanation problem and (every) characteristic function.
(We adopt the presentation from (Chalkiadakis, Elkind, and Wooldridge, 2012).)

#### P01: Efficiency.

A cooperative game is efficient if,

$\sum\nolimits_{i\in{\mathcal{F}}}\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}},\upsilon)=\upsilon({\mathcal{F}})-\upsilon(\emptyset)$

In game theory, it is often assumed that $\upsilon(\emptyset)=0$ (e.g.
(Shapley, 1953)). However, in the case of SHAP scores,
$\upsilon(\emptyset)\not=0$. As a result, claims of efficiency for SHAP scores
usually ignore the term $\upsilon(\emptyset)$.

#### P02: Symmetry.

Two elements $i,j\in{\mathcal{F}}$ are symmetric if
$\upsilon({\mathcal{S}}\cup\\{i\\})=\upsilon({\mathcal{S}}\cup\\{j\\})$ for
${\mathcal{S}}\subseteq{\mathcal{F}}\setminus\\{i,j\\}$. An index respects the
property of symmetry if, for any ${\mathcal{E}}$ and for any symmetric
elements $i,j\in{\mathcal{F}}$,
$\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}},\upsilon)=\operatorname*{\mathsf{Sc}}(j;{\mathcal{E}},\upsilon)$.

#### P03: Additivity.

Let $\upsilon_{1}$ and $\upsilon_{2}$ represent two characteristic functions.
Furthermore, for any ${\mathcal{S}}\subseteq{\mathcal{F}}$, let
$\upsilon_{1{+}2}({\mathcal{S}})=\upsilon_{1}({\mathcal{S}})+\upsilon_{2}({\mathcal{S}})$.
An index respects the property of additivity if for $i\in{\mathcal{F}}$,
$\mathsf{Sc}_{1{+}2}(i;{\mathcal{E}},\upsilon_{1{+}2})=\mathsf{Sc}_{1}(i;{\mathcal{E}},\upsilon_{1})+\mathsf{Sc}_{2}(i;{\mathcal{E}},\upsilon_{2})$.

#### P04: Dummy player.

For any element $i\in{\mathcal{F}}$, if
$\upsilon({\mathcal{S}})=\upsilon({\mathcal{S}}\cup\\{i\\})$ for any
${\mathcal{S}}\subseteq{\mathcal{F}}$, then $i$ is a _dummy player_ (or
element). An index respects the dummy player property if for any dummy element
$i\in{\mathcal{F}}$, $\operatorname*{\mathsf{Sc}}(i)=0$.

###  5.2 Properties Devised for Axiomatic Aggregations

Work on axiomatic aggregations (Biradar et al., 2024) proposed a number of
properties that scores should respect. The properties described below are of
interest to the purposes of our work, and apply to FISs.

#### P05: Minimal monotonicity.

Another property proposed for axiomatic aggregations (Biradar et al., 2024)
requires that, given any classifier, whenever the set of AXps for feature $i$
is included in the set of AXps for feature $j$, then the score for $i$ should
be no greater than the score for $j$,

$\forall(i,j\in{\mathcal{F}}).(\mathbb{A}_{i}\subseteq\mathbb{A}_{j})\operatorname*{\rightarrow}\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}},\upsilon)\leq\operatorname*{\mathsf{Sc}}(j;{\mathcal{E}},\upsilon)$

#### P06: $\gamma$-efficiency.

A final property used for axiomatic aggregations generalizes the notion of
efficiency. Let $\gamma(;{\mathcal{E}})\in\mathbb{R}$. A score is
$\gamma$-efficient if,

$\sum\nolimits_{i\in{\mathcal{F}}}(\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}},\kappa))=\gamma(;{\mathcal{E}})$

$\gamma$-efficiency can be viewed as a mechanism of relaxing the property of
efficiency (see P01 above), and has been the subject of past research (Dubey,
Neyman, and Weber, 1981).

#### Other properties.

We will not adopt other properties discussed in (Biradar et al., 2024). Some
of the remaining properties, e.g.  _null feature_ , are special cases of the
properties discussed in the remainder of this section.

###  5.3 Novel Properties Targeting Scores

As noted earlier in the paper, FISs can be viewed as a generalization of power
indices. Whereas the ML model can be viewed as representing the weighted
voting game, for each ML model there are many different instances that need to
be explained.

#### P07: Independence from class labeling.

Given a classifier
${\mathcal{M}}=({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$, a class
relabeling consists in defining a new classifier
${\mathcal{M}}=({\mathcal{F}},\mathbb{F},{\mathcal{K}}^{\prime},\kappa^{\prime})$,
where the elements of ${\mathcal{K}}^{\prime}$ are related with the elements
of ${\mathcal{K}}$ by a bijection
$\sigma:{\mathcal{K}}\to{\mathcal{K}}^{\prime}$, such that
$\forall(\mathbf{x}\in\mathbb{F}).(\kappa^{\prime}(\mathbf{x})=\sigma(\kappa(\mathbf{x})))$.
For ${\mathcal{M}}$ and ${\mathcal{M}}^{\prime}$, the respective explanation
problems are ${\mathcal{E}}$ and ${\mathcal{E}}^{\prime}$.

Let $\operatorname*{\mathsf{Sc}}$ and $\operatorname*{\mathsf{Sc}}^{\prime}$
represent two FISs defined, respectively, on ${\mathcal{E}}$ and
${\mathcal{E}}^{\prime}$. Then, $\operatorname*{\mathsf{Sc}}$ respects
independence from class labeling if
$\forall(i\in{\mathcal{F}}).(\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}})=\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}}^{\prime}))$.

#### P08: Consistency with relevancy.

An FIS is consistent with relevancy if, for any explanation problem
${\mathcal{E}}$,
$\forall(i\in{\mathcal{F}}).(\textnormal{{{Relevant}}}(i)\operatorname*{\leftrightarrow}\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}})\not=0$,
i.e. a feature takes a non-zero FIS iff it is relevant. One can readily
conclude that property P08 generalizes the _null feature_ property proposed in
(Biradar et al., 2024).

We underline that properties P07 and P08 should both be deemed _mandatory_.
Otherwise, as shown in recent work (Huang and Marques-Silva, 2024; Marques-
Silva and Huang, 2024), one can construct examples where relative feature
importance is misleading.

#### P09: Consistency with duality.

MHS duality plays a key role in the enumeration of AXps and CXps. Furthermore,
it is known that CXps can be easier to enumerate than AXps (Huang et al.,
2021). As a result, it is of interest to know whether using (W)CXps instead of
(W)AXps changes the computed FISs. A dual characteristic function is obtained
by replacing the references to (W)AXps by references to (W)CXps. Similarly, a
dual template score is obtained by replacing the references to (W)AXps by
references to (W)CXps. Moreover, a dual FIS is obtained by replacing the
template score with its dual template score, and using a dual characteristic
function.

Given the above-defined characteristic function $\upsilon_{w}$, the resulting
dual characteristic function $\upsilon^{d}_{w}$ is:
$\upsilon^{d}_{w}({\mathcal{S}};{\mathcal{E}}):=\textnormal{ITE}(\mathsf{WCXp}({\mathcal{S}};{\mathcal{E}}),1,0)$.
Furthermore, for defining the dual template scores, sets defined using AXps
will be replaced by sets defined using CXps. As an example, the dual predicate
for a critical feature becomes,

$\mathsf{Crit}_{d}(i,{\mathcal{S}};{\mathcal{E}}):=\mathsf{WCXp}({\mathcal{S}};{\mathcal{E}})\land\neg\mathsf{WCXp}({\mathcal{S}}\setminus\\{i\\};{\mathcal{E}})$
(19)

When addressing duality, different forms of equivalence may or may not be
obtained. Two FISs $\operatorname*{\mathsf{Sc}}$ and
$\operatorname*{\mathsf{Sc}}^{\prime}$ are _equivalent_ if they do not differ
by more than a strictly positive multiplicative constant. Formally,
$\exists(\alpha>0)\forall({\mathcal{E}})\forall(i\in{\mathcal{F}}).\operatorname*{\mathsf{Sc}}^{\prime}(i;{\mathcal{E}})=\alpha\times\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}})$.
Two FISs $\operatorname*{\mathsf{Sc}}$ and
$\operatorname*{\mathsf{Sc}}^{\prime}$ are _weakly equivalent_ if they rank
features in the same order. Formally,
$\forall({\mathcal{E}})\forall(i,j\in{\mathcal{F}}).\operatorname*{\mathsf{Sc}}(i;{\mathcal{E}})\geq\operatorname*{\mathsf{Sc}}(j;{\mathcal{E}})\operatorname*{\leftrightarrow}\operatorname*{\mathsf{Sc}}^{\prime}(i;{\mathcal{E}})\geq\operatorname*{\mathsf{Sc}}^{\prime}(j;{\mathcal{E}})$.

An FIS $\operatorname*{\mathsf{Sc}}$ is _consistent_ with strict duality if
$\operatorname*{\mathsf{Sc}}$ is equivalent to its dual. An FIS
$\operatorname*{\mathsf{Sc}}$ is _weakly consistent_ with strict duality if
$\operatorname*{\mathsf{Sc}}$ is weakly equivalent to its dual. Finally, an
FIS $\operatorname*{\mathsf{Sc}}$ is _strongly consistent_ with strict duality
if $\operatorname*{\mathsf{Sc}}$ is _equal_ to its dual.

##  6 Novel FISs

As noted in Section 4, in the case of FISs there exists an underlying
explanation problem and a chosen characteristic function, and the optional
definition of a chosen power index. In turn, this enables envisioning
additional novel FISs. This section investigates two examples of novel FISs;
others can be envisioned.

#### FISs based on duality.

For each score that is defined using AXps or WAXps, a dual score can be
defined. Evidently, for scores that respect the duality property, the
resulting scores will be the same. However, for others this may not be the
case. To obtain dual FISs, we start by creating new (dual) template scores,
based on existing template scores, but where the dependency on (W)AXps is
replaced by dependency on (W)CXps. Afterwards, we instantiate the dual FIS by
specifying a dual characteristic function. As an example, we consider the
responsibility score. The dual template responsibility score is obtained from
the template responsibility score (see (15)). Hence, we obtain,

$\mathsf{TSc}_{R^{d}}(i;{\mathcal{E}},\upsilon):=\max\left\\{\left.\frac{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon)}{|{\mathcal{S}}|}\,\right|\,{\mathcal{S}}\in\mathbb{C}_{i}({\mathcal{E}})\right\\}$

Now, the resulting FIS is,

$\displaystyle\mathsf{Sc}_{C}(i;{\mathcal{E}})\leavevmode\nobreak\
\leavevmode\nobreak\ :=\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle\mathsf{TSc}_{R^{d}}(i;{\mathcal{E}},\upsilon^{d}_{w})=$
$\displaystyle\max\left\\{\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon^{d}_{w})|{\mathcal{S}}\in\mathbb{C}_{i}\right\\}$

This FIS corresponds to the index proposed in earlier work (Chockler, Halpern,
and Kupferman, 2008).

#### A coverage-based FIS.

We illustrate the flexibility of the proposed framework by developing a new
score, which is not derived from an existing power index, and so not derived
from one of the proposed template scores. Let
${\mathcal{V}}(i;{\mathcal{E}})=\\{\mathbf{x}\in\mathbb{F}\,|\,\exists({\mathcal{S}}\in\mathbb{A}_{i}).{\mathcal{S}}\subseteq{\mathcal{I}}(\mathbf{x};\mathbf{v})\\}$.
Clearly, ${\mathcal{V}}$ denotes the points in feature space co _v_ ered by
some AXp containing feature $i$. Given ${\mathcal{V}}$, the resulting
_coverage_ score is defined as follows,

$\mathsf{Sc}_{V}(i;{\mathcal{E}}):=\nicefrac{{|{\mathcal{V}}(i;{\mathcal{E}})|}}{{2^{|{\mathcal{F}}|}}}$

FIS | New? | Proposal | Properties
---|---|---|---
As score |  As index | On indices | On scores
|  |  P01 |  P02 |  P03 |  P04 |  P05 |  P06 |  P07 |  P08 |  P09
$\mathsf{Sc}_{E}$ | ✗ |  (Lundberg and Lee, 2017) |  (Shapley and Shubik, 1954) |  ✓ |  ✓ |  ✓ |  ✓ |  ✗ |  ✗$\,;\>$E |  ✗ |  ✗ |  —
$\mathsf{Sc}_{D}$ | ✗ |  (Biradar et al., 2024) |  (Deegan and Packel, 1978) |  ✗ |  ✗ |  ✓ |  ✓ |  ✓ |  ✓$\,;\>$1 |  ✓ |  ✓ |  ✗
$\mathsf{Sc}_{H}$ | ✗ |  (Biradar et al., 2024) |  (Holler and Packel, 1983) |  ✗ |  ✗ |  ✓ |  ✓ |  ✓ |  ✓$\,;\>$M |  ✓ |  ✓ |  ✗
$\mathsf{Sc}_{R}$ | ✗ |  (Biradar et al., 2024) |  Dual of (Chockler, Halpern, and Kupferman, 2008) |  ✗ |  ✗ |  ✗ |  ✓ |  ✓ |  ✓$\,;\>$H |  ✓ |  ✓ |  ✗
$\mathsf{Sc}_{M}$ | ✓ |  — |  (Shapley and Shubik, 1954) |  ✓ |  ✓ |  ✓ |  ✓ |  ✗ |  ✓$\,;\>$E |  ✓ |  ✗ |  —
$\mathsf{Sc}_{S}$ | ✓ |  — |  (Shapley and Shubik, 1954) |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓$\,;\>$1 |  ✓ |  ✓ |  S
$\mathsf{Sc}_{B}$ | ✓ |  — |  (Banzhaf III, 1965) |  ✗ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓$\,;\>$M |  ✓ |  ✓ |  S
$\mathsf{Sc}_{J}$ | ✓ |  — |  (Johnston, 1978) |  ✗ |  ✓ |  ✗ |  ✓ |  ✓ |  ✓$\,;\>$E |  ✓ |  ✓ |  W?
$\mathsf{Sc}_{A}$ | ✓ |  — |  (Andjiga, Chantreuil, and Lepelley, 2003) |  ✗ |  ✗ |  ✓ |  ✓ |  ✓ |  ✓$\,;\>$1 |  ✓ |  ✓ |  W?
$\mathsf{Sc}_{C}$ | ✓ |  — |  (Chockler, Halpern, and Kupferman, 2008) |  ✗ |  ✗ |  ✗ |  ✓ |  ✓ |  ✓$\,;\>$H |  ✓ |  ✓ |  ✗
$\mathsf{Sc}_{V}$ | ✓ |  — |  NA | No associated index |  ✓ |  ✓$\,;\>$H |  ✓ |  ✓ |  W?
Table 1: Characterization of FISs. The properties represent: efficiency (P01),
symmetry (P02), additivity (P03), dummy player (P04), minimal monotonicity
(P05), $\gamma$-efficiency (P06, where is is shown whether the value of
$\gamma$ is guaranteed not to be 0, and how difficult it is to compute the
value of $\gamma$: Easy, Medium, Hard, or its fixed value). independence from
class labeling (P07), consistency with relevancy (P08), and consistency with
duality (P09, Plain, Weak or Strong). Regarding duality, W? signifies
guaranteed not to be strong nor plain, but that it could be weak.

##  7 Characterization of FISs

Given the basic FISs studied in Section 4, the novel FISs proposed in Section
6, and the properties proposed in Section 5, this section characterizes each
of the FISs in terms of those properties.111111$\mathsf{Sc}_{S}$ and
$\mathsf{Sc}_{M}$ have also been studied in recent work (Létoffé, Huang, and
Marques-Silva, 2024). However, these were not obtained with the generalized
formalization this paper proposes. Also, while the scores $\mathsf{Sc}_{S}$
and $\mathsf{Sc}_{M}$ relate with Shapley values, the relationship with the
Shapley-Shubik index was not discussed.

Table 1 summarizes the assessment of the FISs studied in this paper in terms
of existing properties, or the ones also proposed in this paper. Some of the
results are proved in Appendix B; the remaining non-trivial results are proved
in the supplemental materials.) From the table it is apparent that the most
interesting FISs are Shapley-Shubik and Banzhaf, because of the properties
that these scores exhibit. However, the Shapley-Shubik and Banzhaf scores may
require analyzing exponentially many WAXps, whereas other scores, e.g.
Deeghan-Packel or Holler-Packel, only require analyzing all the sets of AXps.
The coverage score, proposed in this paper, represents a possible middle
ground, since it is based on AXps, and it is believed to exhibit some sort of
duality.

##  8 Conclusions

Despite their widespread use, SHAP scores (Lundberg and Lee, 2017) can produce
inadequate measures of relative feature importance in XAI by feature
attribution (Marques-Silva and Huang, 2024). This is explained by the
characteristic function used for computing SHAP scores.

#### Contributions.

Motivated by recent work, this paper: i) develops an in-depth analysis of
applying power indices in XAI by feature attribution; ii) proposes a novel
framework for creating new scores measuring feature importance in XAI; iii)
proposes properties that such scores should exhibit; iv) develops novel
scores; and v) characterizes the different scores in terms of the properties
they exhibit. Furthermore, the paper reveals novel connections between: i)
automated reasoning and its uses in logic-based abduction; ii) game theory and
its applications in a priori voting power and more generally in characteristic
function games; and iii) logic-based explainability and its usage in machine
learning.

#### Research directions.

Several topics of research can be envisioned. First, address the complexity of
computing the FISs studied in the paper and other recent work (Biradar et al.,
2024). This may enable choosing the most adequate FIS, given the properties it
exhibits and the computational complexity for its computation. Second, analyze
the many possible FISs that can be envisioned, either by devising novel
characteristic functions, and relating them with the template scores proposed
in this paper, or by proposing new template scores. Third, devise new
properties, aiming at developing a fine-grained axiomatic but rigorous
characterization of relative feature importance in explainability. Fourth, and
finally, propose ways for the rigorous approximation of FISs, namely when
analyzing complex ML models.

##  Appendix A From FISs back to Power Indices

The derivation of FISs in the case of XAI can be replicated in the case of
power indices for a priori voting power. Instead of using WAXps, we consider
_winning coalitions_ (WCs) of some weighted voting game ${\mathcal{W}}$. A
voter $i$ is critical for a winning coalition (i.e. set of voters voting the
same way) ${\mathcal{S}}$ if,

$\mathsf{Crit}(i,{\mathcal{S}};{\mathcal{W}}):=\mathsf{WC}({\mathcal{S}};{\mathcal{W}})\land\neg\mathsf{WC}({\mathcal{S}}\setminus\\{i\\};{\mathcal{W}})$

(Observe that $\mathsf{WC}$ is a predicate deciding whether the argument is a
winning coalition.) As a result, we can obtain FISs $\mathsf{Sc}_{S}$,
$\mathsf{Sc}_{B}$, $\mathsf{Sc}_{J}$, $\mathsf{Sc}_{A}$, and also
$\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$, and $\mathsf{Sc}_{R}$, from the
respective template scores. (For the last three FISs above, i.e.
$\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$, and $\mathsf{Sc}_{R}$, $\mathbb{A}$ and
$\mathbb{A}_{i}$ represent sets of _minimal_ winning coalitions, either all or
just the ones containing voter $i$.) Also, since there is no associated
explanation problem, the FISs in this concrete setting represent power
indices.121212The analysis of power indices also serves to illustrate the
flexibility of the generalized formalization proposed in this paper.

##  Appendix B Proofs for Table 1

######  Proposition 1.

The indices $\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$, $\mathsf{TSc}_{R}$ and
$\mathsf{TSc}_{A}$ do not respect symmetry (see P02).

###### Proof.

The proof uses the following definitions. A set of features
${\mathcal{S}}\subseteq{\mathcal{F}}$ is a _generator_ if
$\forall(i\in{\mathcal{F}}\setminus{\mathcal{S}}).\mathsf{WAXp}({\mathcal{S}}\cup\\{i\\})$.
The predicate $\mathsf{Gen}({\mathcal{S}})$ is true iff ${\mathcal{S}}$ is a
generator. The assumed characteristic function is:
$\upsilon_{G}({\mathcal{S}})=\textnormal{ITE}(\mathsf{Gen}({\mathcal{S}}),1,0)$.
Finally, we consider a boolean classifier ${\mathcal{M}}_{1}$ defined on two
boolean features ${\mathcal{F}}=\\{1,2\\}$, such that
$\kappa_{1}(x_{1},x_{2})=x_{1}$.
From P02, an index $\mathsf{Idx}$ is symmetric if, for any ${\mathcal{E}}$ and
symmetric elements $i,j\in{\mathcal{F}}$, then
$\mathsf{Idx}(i)=\mathsf{Idx}(j)$. In particular, if the condition is false
for $\upsilon_{G}$ and $\kappa_{1}$, then the index is not symmetric.
For the chosen example, ther are only 2 features, and so if
$\upsilon_{G}(1)=\upsilon_{G}(2)$, then
$\mathsf{Idx}(1;{\mathcal{E}},\upsilon_{G})=\mathsf{Idx}(2;{\mathcal{E}},\upsilon_{G})$.
Since by construction, $\upsilon_{G}(1)=\upsilon_{G}(2)$, then it must be the
case that
$\mathsf{Idx}(1;{\mathcal{E}},\upsilon_{G})=\mathsf{Idx}(2;{\mathcal{E}},\upsilon_{G})$.
We now consider the template scores (which correspond to indices)
$\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$, $\mathsf{TSc}_{R}$ and
$\mathsf{TSc}_{A}$. It is plain to compute
$\mathsf{TSc}_{D}(1;{\mathcal{E}},\upsilon_{G})=\mathsf{TSc}_{H}(1;{\mathcal{E}},\upsilon_{G})=\mathsf{TSc}_{R}(1;{\mathcal{E}},\upsilon_{G})=1$,
$\mathsf{TSc}_{A}(1;{\mathcal{E}},\upsilon_{G})=\nicefrac{{1}}{{2}}$, whereas
$\mathsf{TSc}_{D}(2;{\mathcal{E}},\upsilon_{G})=\mathsf{TSc}_{H}(2;{\mathcal{E}},\upsilon_{G})=\mathsf{TSc}_{R}(2;{\mathcal{E}},\upsilon_{G})=\mathsf{TSc}_{A}(2;{\mathcal{E}},\upsilon_{G})=0$.
This proves the result. ∎

######  Proposition 2.

$\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$ and $\mathsf{Sc}_{R}$ do not respect weak
duality (see P09), and so do not respect neither plain nor strong duality.
Furthermore, $\mathsf{Sc}_{J}$, $\mathsf{Sc}_{A}$ and $\mathsf{Sc}_{V}$ do not
respect neither plain nor strong duality.

###### Proof.

Let
$\kappa(x_{1},x_{2},x_{3},x_{4})=x_{1}\land(x_{2}\lor{x_{3}}\land{x_{4}})$,
with $\mathbb{A}=\\{\\{1,2\\},\\{1,3,4\\}\\}$ and
$\mathbb{C}=\\{\\{1\\},\\{2,3\\},\\{2,4\\}\\}$. We consider the dual FISs
obtained from $\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$, and $\mathsf{Sc}_{R}$, by
replacing AXps with CXps. Let $\mathsf{Sc}^{d}_{D}$, $\mathsf{Sc}^{d}_{H}$,
and $\mathsf{Sc}^{d}_{R}$ be the resulting dual FISes. Thus, for
$\mathsf{Sc}_{D}$, we compute,

$\displaystyle\mathsf{Sc}_{D}(1)=\nicefrac{{5}}{{12}},\mathsf{Sc}_{D}(2)=\nicefrac{{1}}{{4}},\mathsf{Sc}_{D}(3)=\nicefrac{{1}}{{6}},\mathsf{Sc}_{D}(4)=\nicefrac{{1}}{{6}}$
$\displaystyle\mathsf{Sc}^{d}_{D}(1)=\nicefrac{{1}}{{3}},\mathsf{Sc}^{d}_{D}(2)=\nicefrac{{1}}{{3}},\mathsf{Sc}^{d}_{D}(3)=\nicefrac{{1}}{{6}},\mathsf{Sc}^{d}_{D}(4)=\nicefrac{{1}}{{6}}$

which proves that $\mathsf{Sc}_{D}$ does not respect weak duality. Similarly,
for $\mathsf{Sc}_{H}$ we compute,

$\displaystyle\mathsf{Sc}_{H}(1)=1,\mathsf{Sc}_{H}(2)=\nicefrac{{1}}{{2}},\mathsf{Sc}_{H}(3)=\nicefrac{{1}}{{2}},\mathsf{Sc}_{H}(4)=\nicefrac{{1}}{{2}}$
$\displaystyle\mathsf{Sc}^{d}_{H}(1)=\nicefrac{{1}}{{3}},\mathsf{Sc}^{d}_{H}(2)=\nicefrac{{2}}{{3}},\mathsf{Sc}^{d}_{H}(3)=\nicefrac{{1}}{{3}},\mathsf{Sc}^{d}_{H}(4)=\nicefrac{{1}}{{3}}$

which proves that $\mathsf{Sc}_{H}$ does not respect weak duality. Moreover,
for $\mathsf{Sc}_{R}$, we compute,

$\displaystyle\mathsf{Sc}_{R}(1)=\nicefrac{{1}}{{4}},\mathsf{Sc}_{R}(2)=\nicefrac{{1}}{{4}},\mathsf{Sc}_{R}(3)=\nicefrac{{1}}{{6}},\mathsf{Sc}_{R}(4)=\nicefrac{{1}}{{6}}$
$\displaystyle\mathsf{Sc}^{d}_{R}(1)=\nicefrac{{1}}{{3}},\mathsf{Sc}^{d}_{R}(2)=\nicefrac{{1}}{{6}},\mathsf{Sc}^{d}_{R}(3)=\nicefrac{{1}}{{6}},\mathsf{Sc}^{d}_{R}(4)=\nicefrac{{1}}{{6}}$

which proves that $\mathsf{Sc}_{R}$ does not respect weak duality.
The proof regarding $\mathsf{Sc}_{J}$, $\mathsf{Sc}_{A}$ and $\mathsf{Sc}_{V}$
is included in the supplemental materials. ∎

######  Proposition 3.

$\mathsf{Sc}_{S}$ and $\mathsf{Sc}_{B}$ respect strong duality (see P09).

###### Proof.

We consider first the strong duality of $\mathsf{Sc}_{S}$. By definition, it
is the case that
$\forall({\mathcal{S}}\subseteq{\mathcal{F}}).\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})\leftrightarrow\neg\mathsf{WAXp}({\mathcal{S}})$.
Also, recall that
$\upsilon_{w}({\mathcal{S}};{\mathcal{E}}):=\mathsf{WAXp}({\mathcal{S}};{\mathcal{E}})$.
Thus,
$\forall(i\in{\mathcal{F}}),\forall({\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\})$
we have,

$\displaystyle\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon_{w})=1$
$\displaystyle\Leftrightarrow\>$
$\displaystyle\neg\mathsf{WAXp}({\mathcal{S}}\setminus\\{i\\};{\mathcal{E}})\land\mathsf{WAXp}({\mathcal{S}};{\mathcal{E}})$
$\displaystyle\Leftrightarrow\>$
$\displaystyle\mathsf{WCXp}({\mathcal{F}}\setminus({\mathcal{S}}\setminus\\{i\\}))\land\neg\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})$
$\displaystyle\Leftrightarrow\>$
$\displaystyle\mathsf{WCXp}(({\mathcal{F}}\setminus{\mathcal{S}})\cup\\{i\\}\land\neg\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})$
$\displaystyle\Leftrightarrow\>$
$\displaystyle\Delta_{i}(({\mathcal{F}}\setminus{\mathcal{S}})\cup\\{i\\};{\mathcal{E}},\upsilon^{d}_{w})=1$

Now, let
$\Phi(i):=\\{{\mathcal{S}}\in\\{{\mathcal{T}}\subseteq{\mathcal{F}}\,|\,i\in{\mathcal{T}}\\}\,|\,\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon_{w})=1\\}$.
Then, by construction,
$\mathsf{Sc}_{S}(i)=\sum_{{\mathcal{S}}\in\Phi(i)}\varsigma(|{\mathcal{S}}|)$
(because $\Delta_{i}({\mathcal{S}};{\mathcal{E}},\upsilon_{w})=0$ otherwise)
and, by the equivalence above,
$\mathsf{Sc}^{d}_{S}(i)=\sum_{{\mathcal{S}}\in\Phi(i)}\varsigma(|({\mathcal{F}}\setminus{\mathcal{S}})\cup\\{i\\}|)$.
However, it is immediate to prove that
$\varsigma(|{\mathcal{S}}|)=\varsigma(|({\mathcal{F}}\setminus{\mathcal{S}})\cup\\{i\\}|)$,
and so the two sums are also equal, i.e.
$\mathsf{Sc}_{S}(i;{\mathcal{E}},\upsilon_{w})=\mathsf{Sc}^{d}_{S}(i;{\mathcal{E}},\upsilon^{d}_{w})$.
For $\mathsf{Sc}_{B}$, a similar argument is used. This concludes the proof. ∎

######  Proposition 4.

For $\mathsf{Sc}_{J}$, $\mathsf{Sc}_{A}$ and $\mathsf{Sc}_{V}$, and for
propoerty P09, neither plain nor strong duality hold.

###### Proof.

The counterexample used in the proof of Proposition 2 (see paper) can also be
used for the claims above. Concretely, for $\mathsf{Sc}_{J}$ we get,

$\displaystyle\mathsf{Sc}_{J}(1)=\nicefrac{{17}}{{6}},\mathsf{Sc}_{J}(2)=\nicefrac{{3}}{{2}},\mathsf{Sc}_{J}(3)=\mathsf{Sc}_{J}(4)=\nicefrac{{1}}{{3}}$
$\displaystyle\mathsf{Sc}^{d}_{J}(1)=5,\mathsf{Sc}^{d}_{J}(2)=2,\mathsf{Sc}^{d}_{J}(3)=\mathsf{Sc}^{d}_{J}(4)=\nicefrac{{1}}{{2}}$

For $\mathsf{Sc}_{A}$ we get,

$\displaystyle\mathsf{Sc}_{A}(1)=\nicefrac{{7}}{{20}},\mathsf{Sc}_{A}(2)=\nicefrac{{7}}{{30}},\mathsf{Sc}_{A}(3)=\mathsf{Sc}_{A}(4)=\nicefrac{{1}}{{15}}$
$\displaystyle\mathsf{Sc}^{d}_{A}(1)=\nicefrac{{17}}{{66}},\mathsf{Sc}^{d}_{A}(2)=\nicefrac{{4}}{{33}},\mathsf{Sc}^{d}_{A}(3)=\mathsf{Sc}^{d}_{A}(4)=\nicefrac{{1}}{{22}}$

Finally, for $\mathsf{Sc}_{V}$ we get,

$\displaystyle\mathsf{Sc}_{V}(1)=\nicefrac{{5}}{{16}},\mathsf{Sc}_{V}(2)=\nicefrac{{1}}{{4}},\mathsf{Sc}_{V}(3)=\mathsf{Sc}_{V}(4)=\nicefrac{{1}}{{8}}$
$\displaystyle\mathsf{Sc}^{d}_{V}(1)=\nicefrac{{1}}{{2}},\mathsf{Sc}^{d}_{V}(2)=\nicefrac{{3}}{{8}},\mathsf{Sc}^{d}_{V}(3)=\mathsf{Sc}^{d}_{V}(4)=\nicefrac{{1}}{{4}}$

Which proves the result.
Unlike $\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$, $\mathsf{Sc}_{R}$, the order
remains unchanged and so this does not allow discarding Weak duality. ∎

######  Proposition 5.

P01, P02, P03 and P04 hold for $\mathsf{TSc}_{S}$.

###### Proof.

This is a consequence of the uniqueness of the Shapley value Shapley (1953). ∎

######  Proposition 6.

For the proposed FISs, and for P07 and P08 the properties that hold (resp. not
hold) are as shown in Table 1.

###### Proof.

The entries for $\mathsf{Sc}_{E}$, $\mathsf{Sc}_{M}$ and $\mathsf{Sc}_{S}$
result from the results in (Létoffé, Huang, and Marques-Silva, 2024).
Furthermore, the proofs from (Létoffé, Huang, and Marques-Silva, 2024) (see
propositions 5.2 and 5.3) also generalize for $\mathsf{Sc}_{D}$,
$\mathsf{Sc}_{H}$, $\mathsf{Sc}_{R}$, $\mathsf{Sc}_{B}$, $\mathsf{Sc}_{J}$,
$\mathsf{Sc}_{A}$, since the proofs only depend on the characteristic
functions used, and the same characteristic function can be used for all these
FISs.
For $\mathsf{Sc}_{V}$, it is immediate that a definition based on AXps does
not depend on the values taken by the classifier. Also, if a feature does not
occur in AXps, then its score will be 0. ∎

######  Proposition 7.

P01 does not hold for $\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$,
$\mathsf{TSc}_{R}$, $\mathsf{TSc}_{B}$, $\mathsf{TSc}_{J}$, and
$\mathsf{TSc}_{A}$.

###### Proof.

For $\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$, and $\mathsf{TSc}_{R}$, the value
of efficiency is computed in (Yu, Ignatiev, and Stuckey, 2023), and it is
different from what P01 would imply.
For $\mathsf{TSc}_{B}$, $\mathsf{TSc}_{J}$, and $\mathsf{TSc}_{A}$, if P01
would hold, then that would falsify Shapley’s theorem (Shapley, 1953). ∎

######  Proposition 8.

P02 holds for $\mathsf{TSc}_{B}$ and $\mathsf{TSc}_{J}$.

###### Proof.

The sums for two symmetric features $i$ and $j$ both use all sets (so the same
sets), have $\Delta_{i}=\Delta_{j}$ (due to symmetry) and the same coefficient
and so are equal. ∎

######  Proposition 9.

P03 holds for $\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$, $\mathsf{TSc}_{B}$ and
$\mathsf{TSc}_{A}$.

###### Proof.

By construction, the sum operator and the $\Delta_{i}$ are linear. As the
multiplicative constants do not depend on the characteristic function, the
score is linear. ∎

######  Proposition 10.

P03 does not hold for $\mathsf{TSc}_{J}$.

###### Proof.

For $\mathsf{TSc}_{J}$, and unlike the previous proof, the multiplicative
constant depends on the characteristic function and so break linearity. ∎

######  Proposition 11.

P03 does not hold for $\mathsf{TSc}_{R}$.

###### Proof.

The $\max$ operator is not linear; it is easy to break the linearity by taking
$\kappa(x_{1})=x_{1}$ with $\upsilon_{1}=\upsilon_{2}$ as the characteristic
function used to $\mathsf{TSc}_{R}$. Hence, lack of linearity becomes
apparent. ∎

######  Proposition 12.

P04 holds for $\mathsf{TSc}_{D}$, $\mathsf{TSc}_{H}$, $\mathsf{TSc}_{R}$,
$\mathsf{TSc}_{B}$, $\mathsf{TSc}_{J}$ and $\mathsf{TSc}_{A}$.

###### Proof.

The summations are trivially 0 by construction when
$\Delta_{i}({\mathcal{S}})=0$ for every set
${\mathcal{S}}\subseteq{\mathcal{F}}$. ∎

######  Proposition 13.

P05 holds for $\mathsf{Sc}_{D}$, $\mathsf{Sc}_{H}$, $\mathsf{Sc}_{R}$,
$\mathsf{Sc}_{S}$, $\mathsf{Sc}_{B}$, $\mathsf{Sc}_{J}$, $\mathsf{Sc}_{A}$,
$\mathsf{Sc}_{C}$, and $\mathsf{Sc}_{V}$, but not for $\mathsf{Sc}_{E}$ and
$\mathsf{Sc}_{M}$.

###### Proof.

(Sketch) The proof for each FIS is straightforward and only requires comparing
the terms for each set ${\mathcal{S}}$ and apply the axiom. What remains
becomes fairly similar to the arguments used in the case of P08. ∎

######  Proposition 14.

For P06, the results in Table 1 hold.

###### Proof.

(Sketch) The formula comes from P01 and so is easy to compute. For
$\mathsf{Sc}_{S}$, the simple valued is proved in (Létoffé, Huang, and
Marques-Silva, 2024).
For the remaining FISs, it suffices to manipulate the sum that defines
$\gamma$, aggregating the two sums and simplifying as much as possible. ∎

## References

  * Andjiga, Chantreuil, and Lepelley (2003) Andjiga, N.-G.; Chantreuil, F.; and Lepelley, D.  2003\.  La mesure du pouvoir de vote.  Mathématiques et sciences humaines. Mathematics and social sciences (163).
  * Arenas et al. (2021) Arenas, M.; Barceló, P.; Bertossi, L. E.; and Monet, M.  2021\.  The tractability of SHAP-score-based explanations for classification over deterministic and decomposable boolean circuits.  In AAAI, 6670–6678.
  * Arenas et al. (2023) Arenas, M.; Barceló, P.; Bertossi, L. E.; and Monet, M.  2023\.  On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results.  J. Mach. Learn. Res. 24:63:1–63:58.
  * Banzhaf III (1965) Banzhaf III, J. F.  1965\.  Weighted voting doesn’t work: A mathematical analysis.  Rutgers L. Rev. 19:317.
  * Berg (1999) Berg, S.  1999\.  On voting power indices and a class of probability distributions: With applications to EU data.  Group Decision and Negotiation 8:17–31.
  * Biradar et al. (2023) Biradar, G.; Izza, Y.; Lobo, E.; Viswanathan, V.; and Zick, Y.  2023\.  Axiomatic aggregations of abductive explanations.  CoRR abs/2310.03131.
  * Biradar et al. (2024) Biradar, G.; Izza, Y.; Lobo, E.; Viswanathan, V.; and Zick, Y.  2024\.  Axiomatic aggregations of abductive explanations.  In AAAI, 11096–11104.
  * Chalkiadakis, Elkind, and Wooldridge (2012) Chalkiadakis, G.; Elkind, E.; and Wooldridge, M.  2012\.  Computational aspects of cooperative game theory.
  * Chockler, Halpern, and Kupferman (2008) Chockler, H.; Halpern, J. Y.; and Kupferman, O.  2008\.  What causes a system to satisfy a specification?  ACM Transactions on Computational Logic (TOCL) 9(3):1–26.
  * Coleman (1971) Coleman, J. S.  1971\.  Control of collectivities and the power of a collectivity to act.  In Lieberman, B., ed., Social choice. Gordon and Breach, New York.  chapter 2.10.
  * Colomer (1996) Colomer, J. M.  1996\.  Measuring parliamentary deviation.  European Journal of Political Research 30(1):87–101.
  * Curiel (1987) Curiel, I. J.  1987\.  A class of non-normalized power indices for simple games.  Mathematical Social Sciences 13(2):141–152.
  * Darwiche (2023) Darwiche, A.  2023\.  Logic for explainable AI.  In LICS, 1–11.
  * Deegan and Packel (1978) Deegan, J., and Packel, E. W.  1978\.  A new index of power for simple $n$-person games.  International Journal of Game Theory 7:113–123.
  * Doignon, Moretti, and Öztürk (2022) Doignon, J.; Moretti, S.; and Öztürk, M.  2022\.  On the ordinal invariance of power indices on coalitional games.  In IJCAI, 258–264.
  * Dubey, Neyman, and Weber (1981) Dubey, P.; Neyman, A.; and Weber, R. J.  1981\.  Value theory without efficiency.  Math. Oper. Res. 6(1):122–128.
  * Dubey (1975) Dubey, P.  1975\.  On the uniqueness of the Shapley value.  International Journal of Game Theory 4:131–139.
  * European Union (2024) European Union.  2024\.  Artificial intelligence act.  https://tinyurl.com/yj2zv67w.
  * Felsenthal and Machover (2004) Felsenthal, D. S., and Machover, M.  2004\.  A priori voting power: what is it all about?  Political Studies Review 2(1):1–23.
  * Felsenthal and Machover (2015) Felsenthal, D. S., and Machover, M.  2015\.  The measurement of a priori voting power.  In Heckelman, J. C., and Miller, N. R., eds., Handbook of Social Choice and Voting. Edward Elgar Publishing.  chapter 08, 117–139.
  * Felsenthal (2016) Felsenthal, D. S.  2016\.  A well-behaved index of a priori P-power for simple $n$-person games.  Homo Oeconomicus 33:367–381.
  * Freixas and Kaniovski (2014) Freixas, J., and Kaniovski, S.  2014\.  The minimum sum representation as an index of voting power.  European Journal of Operational Research 233(3):739–748.
  * Freixas and Molinero (2010) Freixas, J., and Molinero, X.  2010\.  Detection of paradoxes of power indices for simple games.  Contributions to Game Theory and Management 3:82–90.
  * Freixas (2010) Freixas, J.  2010\.  On ordinal equivalence of the Shapley and Banzhaf values for cooperative games.  Int. J. Game Theory 39(4):513–527.
  * Guidotti et al. (2019) Guidotti, R.; Monreale, A.; Ruggieri, S.; Turini, F.; Giannotti, F.; and Pedreschi, D.  2019\.  A survey of methods for explaining black box models.  ACM Comput. Surv. 51(5):93:1–93:42.
  * High-Level Expert Group on AI (2019) High-Level Expert Group on AI.  2019\.  Ethics guidelines for trustworthy AI.  https://tinyurl.com/yyzwmm79.
  * Holler and Packel (1983) Holler, M. J., and Packel, E. W.  1983\.  Power, luck and the right index.  Journal of Economics 43(1):21–29.
  * Huang and Marques-Silva (2023a) Huang, X., and Marques-Silva, J.  2023a.  The inadequacy of Shapley values for explainability.  CoRR abs/2302.08160.
  * Huang and Marques-Silva (2023b) Huang, X., and Marques-Silva, J.  2023b.  Refutation of Shapley values for XAI – additional evidence.  CoRR abs/2310.00416.
  * Huang and Marques-Silva (2024) Huang, X., and Marques-Silva, J.  2024\.  On the failings of Shapley values for explainability.  International Journal of Approximate Reasoning 109112\.
  * Huang et al. (2021) Huang, X.; Izza, Y.; Ignatiev, A.; and Marques-Silva, J.  2021\.  On efficiently explaining graph-based classifiers.  In KR, 356–367.
  * Ignatiev et al. (2020) Ignatiev, A.; Narodytska, N.; Asher, N.; and Marques-Silva, J.  2020\.  From contrastive to abductive explanations and back again.  In AIxIA, 335–355.
  * Ignatiev (2020) Ignatiev, A.  2020\.  Towards trustable explainable AI.  In IJCAI, 5154–5158.
  * Johnston (1978) Johnston, R. J.  1978\.  On the measurement of power: Some reactions to Laver.  Environment and Planning A 10(8):907–914.
  * Létoffé, Huang, and Marques-Silva (2024) Létoffé, O.; Huang, X.; and Marques-Silva, J.  2024\.  On correcting SHAP scores.  CoRR abs/2405.00076.
  * Lundberg and Lee (2017) Lundberg, S. M., and Lee, S.  2017\.  A unified approach to interpreting model predictions.  In NeurIPS, 4765–4774.
  * Marques-Silva and Huang (2024) Marques-Silva, J., and Huang, X.  2024\.  Explainability is NOT a game.  Commun. ACM.  In Press.
  * Marques-Silva and Ignatiev (2022) Marques-Silva, J., and Ignatiev, A.  2022\.  Delivering trustworthy AI through formal XAI.  In AAAI, 12342–12350.
  * Marques-Silva (2022) Marques-Silva, J.  2022\.  Logic-based explainability in machine learning.  In Reasoning Web, 24–104.
  * Marques-Silva (2023) Marques-Silva, J.  2023\.  Disproving XAI myths with formal methods - initial results.  In ICECCS, 12–21.
  * Mishra (2023) Mishra, P.  2023\.  Explainable AI Recipes.  Apress.
  * Molnar (2023) Molnar, C.  2023\.  Interpreting Machine Learning Models With SHAP.  Lulu.com.
  * Montavon, Samek, and Müller (2018) Montavon, G.; Samek, W.; and Müller, K.  2018\.  Methods for interpreting and understanding deep neural networks.  Digit. Signal Process. 73:1–15.
  * Mosca et al. (2022) Mosca, E.; Szigeti, F.; Tragianni, S.; Gallagher, D.; and Groh, G.  2022\.  Shap-based explanation methods: A review for NLP interpretability.  In COLING, 4593–4603.
  * Penrose (1946) Penrose, L. S.  1946\.  The elementary statistics of majority voting.  Journal of the Royal Statistical Society 109(1):53–57.
  * Reiter (1987) Reiter, R.  1987\.  A theory of diagnosis from first principles.  Artif. Intell. 32(1):57–95.
  * Roth (1988) Roth, A. E.  1988\.  The Shapley value: essays in honor of Lloyd S. Shapley.  Cambridge University Press.
  * Samek et al. (2019) Samek, W.; Montavon, G.; Vedaldi, A.; Hansen, L. K.; and Müller, K., eds.  2019\.  Explainable AI: Interpreting, Explaining and Visualizing Deep Learning.  Springer.
  * Samek et al. (2021) Samek, W.; Montavon, G.; Lapuschkin, S.; Anders, C. J.; and Müller, K.  2021\.  Explaining deep neural networks and beyond: A review of methods and applications.  Proc. IEEE 109(3):247–278.
  * Shapley and Shubik (1954) Shapley, L. S., and Shubik, M.  1954\.  A method for evaluating the distribution of power in a committee system.  American political science review 48(3):787–792.
  * Shapley (1953) Shapley, L. S.  1953\.  A value for $n$-person games.  Contributions to the Theory of Games 2(28):307–317.
  * Strumbelj and Kononenko (2010) Strumbelj, E., and Kononenko, I.  2010\.  An efficient explanation of individual classifications using game theory.  J. Mach. Learn. Res. 11:1–18.
  * Strumbelj and Kononenko (2014) Strumbelj, E., and Kononenko, I.  2014\.  Explaining prediction models and individual predictions with feature contributions.  Knowl. Inf. Syst. 41(3):647–665.
  * US Government (2023) US Government.  2023\.  Executive order on the safe, secure, and trustworthy development and use of artificial intelligence.  https://tinyurl.com/yb7wcmen.
  * Van den Broeck et al. (2022) Van den Broeck, G.; Lykov, A.; Schleich, M.; and Suciu, D.  2022\.  On the tractability of SHAP explanations.  J. Artif. Intell. Res. 74:851–886.
  * Young (1985) Young, H. P.  1985\.  Monotonic solutions of cooperative games.  International Journal of Game Theory 14:65–72.
  * Yu et al. (2023) Yu, J.; Farr, G.; Ignatiev, A.; and Stuckey, P. J.  2023\.  Anytime approximate formal feature attribution.  CoRR abs/2312.06973.
  * Yu, Ignatiev, and Stuckey (2023) Yu, J.; Ignatiev, A.; and Stuckey, P. J.  2023\.  On formal feature attribution and its approximation.  CoRR abs/2307.03380.