# Stratum by Stratum: Building Stable SHAP Explanations through Layered Approximations

Gwladys Kelodjou, Laurence Rozé, Véronique Masson, Romaric Gaudel, Luis Galárraga, Alexandre Termier

► To cite this version:

Gwladys Kelodjou, Laurence Rozé, Véronique Masson, Romaric Gaudel, Luis Galárraga, et al. Stratum by Stratum: Building Stable SHAP Explanations through Layered Approximations. 2025. hal-04962944

HAL Id: hal-04962944

https://hal.science/hal-04962944v1

Preprint submitted on 23 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stratum by Stratum: Building Stable SHAP Explanations through Layered Approximations

**Gwladys Kelodjou**

Univ Rennes, Inria, CNRS, IRISA
UMR 6074, F35000 Rennes, France

GWLADYS.KELODJOU@IRISA.FR

**Laurence Rozé**

Univ Rennes, INSA Rennes, CNRS, Inria, IRISA
UMR 6074, F35000 Rennes, France

LAURENCE.ROZE@IRISA.FR

**Véronique Masson**

Univ Rennes, Inria, CNRS, IRISA
UMR 6074, F35000 Rennes, France

VERONIQUE.MASSON@IRISA.FR

**Romaric Gaudel**

Univ Rennes, Inria, CNRS, IRISA
UMR 6074, F35000 Rennes, France

ROMARIC.GAUDEL@IRISA.FR

**Luis Galárraga**

Univ Rennes, Inria, CNRS, IRISA
UMR 6074, F35000 Rennes, France

LUIS.GALARRAGA@INRIA.FR

**Alexandre Termier**

Univ Rennes, Inria, CNRS, IRISA
UMR 6074, F35000 Rennes, France

ALEXANDRE.TERMIER@IRISA.FR

## Abstract

SHAP is a popular post-hoc explainability method that assigns feature attribution scores based on the Shapley value from cooperative game theory. Since computing the exact SHAP values is intractable for large feature sets, several sampling-based approximation methods, such as KernelSHAP, have been proposed in the literature. These methods overcome intractability but suffer from stability issues. To address this instability, we propose the StratoSHAP family of stable SHAP approximations based on feature coalitions organized into strata. We provide formal analytical formulations for these approximations and demonstrate that they respect important properties of attribution values, such as stability, linearity, efficiency, symmetry, and fair treatment. A series of comparative experiments reveal that our stratum-based approach offers an interesting trade-off between computational complexity and approximation quality while remaining fully stable.

## 1 Introduction

The challenge of making machine learning (ML) models transparent and understandable has emerged as an active research area. This problem is particularly crucial in high-stakes domains such as healthcare where the opacity of decision models can raise concerns. Having explicit interpretations of the rationale of AI-based predictions is vital to guarantee transparent AI systems and elicit trust in such solutions (Lipton, 2016; Ribeiro et al., 2016; Ghorbani et al., 2019a). One approach to achieve such transparency is by providing explanations for
the decisions made by black-box models (Molnar, 2022; Wachter et al., 2017; Shrikumar et al., 2017; Ribeiro et al., 2016, 2018; Ghorbani et al., 2019b; Rudin, 2019). A prevalent type of explanation is feature attribution, which aims to quantify the contribution of input features to the outputs made by these black-box ML models. Explanation methods based on this principle are called **attribution methods**. SHAP (SHapley Additive exPlanations) (Lundberg and Lee, 2017) is a prominent post-hoc local explainer that computes feature attribution for individual predictions based on the Shapley value (Shapley et al., 1953). The Shapley value is a solution to the problem of distributing the gains of a *transferable utility* cooperative game (Neumann et al., 1953) among players in a fair way. The Shapley values enjoy several desirable theoretical properties that have made them a widely used method for distributing collective value equitably among multiple agents (Chalkiadakis et al., 2022). Computing the Shapley value requires aggregating the rewards that all possible sets of players, called coalitions, would receive; these are $2^n$ for $n$ players.

The SHAP values (Lundberg and Lee, 2017) are the adaptation of the Shapley values to ML models. Input features act as players, and the reward is the model's output. The SHAP values, therefore, tell us how much each feature contributed to the model's decision. Calculating decisions for all $2^n$ coalitions (assuming $n$ input features) is computationally prohibitive for datasets with many features. SHAP thus proposes several approximations that sample a limited number of feature coalitions to estimate the Shapley values, the most general of which is KernelSHAP (Lundberg and Lee, 2017). However, recent findings (Covert and Lee, 2021; Agarwal et al., 2022; Kelodjou et al., 2024) show that KernelSHAP's approximations are not *stable*: different runs of the algorithm on the same input can lead to significantly different explanations, i.e., explanations for which the attribution values of a given input feature can vary drastically across executions. This happens because KernelSHAP produces a different sample of coalitions every time. We believe that such instability can harm users' trust in the explanations.

In this paper, we present three key contributions aimed at addressing the stability and computational challenges of SHAP explanations. For this, we introduce StratoSHAP, the first family of SHAP approximations by sampling that has solid theoretical guarantees on the attribution values (LES properties), and that is completely stable.

1. Our first contribution is the StratoSHAP sampling scheme for coalitions, which is based on an organization of coalitions into strata. We also provide a formal analytical expression for the attribution method associated with each stratum. This approach gives stable and accurate approximations of the SHAP values, with the exact result being reached at the final stratum.

2. We demonstrate that the attribution values found by StratoSHAP retain most of the axiomatic properties of the SHAP values (linearity, efficiency, symmetry, fair treatment).

3. We conduct an extensive experimental evaluation on both real and synthetic datasets to investigate the ability of these approximations to capture complex feature interactions. Our findings suggest that users can achieve stable explanations while tailoring the computational effort to their specific needs.
## 2 Related Work

The straightforward computation of the SHAP values has exponential complexity in the number of features, prompting the development of acceleration techniques. These include sampling-based approximations (Strumbelj and Kononenko, 2010; Castro et al., 2009; Illés and Kerényi, 2019; Maleki et al., 2013), model-specific approximations (Chau et al., 2022; Lundberg and Lee, 2017; Lundberg et al., 2020; Lemaire et al., 2023; Chen et al., 2020), and linear-regression-based approximations (Lundberg and Lee, 2017). While model-specific techniques often offer faster computation, sampling- and regression-based approaches have the advantage of being model-agnostic, providing greater flexibility. Consequently, we prioritize these model-agnostic methods.

Sampling-based approximations typically involve sampling permutations to compute marginal contributions<fnref n="1" />. The approximate Shapley value is then calculated as the average of these marginal contributions across different sampled permutations. This is the approach used by ApproShapley (Castro et al., 2009), which samples permutations uniformly at random from all possible permutations. Building on this idea, other approaches aim to develop more efficient sampling strategies that reduce variance in the estimates, such as antithetic sampling (Mitchell et al., 2022; Okhrati and Lipani, 2021), ergodic sampling (Illés and Kerényi, 2019), stratified sampling (Maleki et al., 2013; Castro et al., 2017), orthogonal spherical codes (Mitchell et al., 2022), and more (Strumbelj and Kononenko, 2010; Kolpaczki et al., 2024). SHAP values can also be computed via a constrained weighted least squares problem (Charnes et al., 1988), but this approach requires considering all possible coalitions, making it computationally infeasible for large feature sets. Some recent methods approximate SHAP values along these lines. KernelSHAP, for example, solves a weighted least squares problem using a sample of coalitions. However, Merrick and Taly (2020) questioned the unbiasedness of KernelSHAP, noting its lack of uncertainty estimates and guidelines on the required number of coalitions. Covert and Lee (2021) introduced an unbiased KernelSHAP and a method to detect its convergence. Despite these advances, stability guarantees for the resulting explanations remain a challenge. To address stability issues, Kelodjou et al. (2024) proposed ST-SHAP, which adjusts KernelSHAP’s sampling strategy, providing some control over the variance depending on the number of sampled coalitions. They show that using only extreme coalitions (those containing only one feature or all but one feature) allows for fully stable and fast approximations. Their approach, though, may yield poor approximations of the SHAP value when dealing with a target model exhibiting complex non-linear relationships between features.

A limitation of the SHAP value is its treatment of features as independent, assigning scores to individual features without accounting for correlations and interactions between them. This limitation has been explored (Kumar et al., 2021), leading to variants that quantify feature interactions by attributing scores to groups of features rather than single features when appropriate (Fumagalli et al., 2024a,b; Tsai et al., 2023; Bordt and von Luxburg, 2023).

In this paper, we focus on explaining model predictions by assigning individual scores to features using an approximation of SHAP values. Our stratum-based method, similar to

<footnote n="1">1. The marginal contribution of a player to a coalition is the change in the worth observed when the player is added to the coalition if they were not already included, or removed if they were already a member.</footnote>
KernelSHAP, relies on linear regression and can deal with feature interactions in the target model by considering more strata. This offers a series of trade-offs between runtime and explanation quality.

# 3 Preliminaries

In this section, we present the functioning of KernelSHAP, a method that approximates the SHAP values in a local and model-agnostic way (Lundberg and Lee, 2017). We first introduce the notions of game theory necessary to understand Shapley's values.

## 3.1 Coalitional Game Theory

A coalitional game is defined by the tuple $(N, v)$ where $N = \{1, 2, \dots, n\}$ denotes a set of $n$ players and $v: 2^N \to \mathbb{R}$ is a characteristic function that maps subsets of $N$ to real values. These subsets are called coalitions, and $N$ itself is referred to as the grand coalition. The value $v(S)$, for any coalition $S \subseteq N$, represents the total payoff that coalition $S$ can secure for its members and is referred to as the worth of $S$. In cooperative game theory it is typically assumed that the players form the grand coalition and the goal is to distribute the total worth, $v(N)$, among the players. A solution concept, or value, is represented by an operator $\phi$ that assigns to the game $(N, v)$ a vector of payoffs $\phi(v) = (\phi_1, \dots, \phi_n) \in \mathbb{R}^n$ such that $\phi_i$ is player $i$'s share of the total payoff $v(N)$ (Strumbelj and Kononenko, 2010). Different solution concepts offer various guarantees. The following four statements are attempts at axiomatizing the notion of fairness of a solution $\phi$ (Chalkiadakis et al., 2022; Strumbelj and Kononenko, 2010):

* **Efficiency:** The gain is completely distributed, i.e., $\sum_{j=1}^n \phi_j(v) = v(N)$. This axiom requires that the sum of everyone's payoffs should be equal to the worth of the grand coalition.

* **Symmetry:** If $i$ and $j$ are two players that contribute equally to all possible coalitions, i.e., $v(S \cup \{i\}) = v(S \cup \{j\})$ for every subset $S$ which contains neither $i$ nor $j$, then they should be assigned equal payoffs $\phi_i(v) = \phi_j(v)$.

* **Linearity:** For any games $v$ and $w$, $\phi_j(v+w) = \phi_j(v) + \phi_j(w)$. This states that the payoff vector for the sum of two games should be the sum of the payoff vectors of each of the games. Also, for any real number $\alpha$, we have that $\phi_j(\alpha v) = \alpha \phi_j(v)$.

* **Null effects:** If $v(S \cup \{j\}) = v(S)$ holds for every $S \subseteq N \setminus \{j\}$, then $\phi_j(v) = 0$. This states that if all of a player's contributions are equal to 0, the player should receive that amount.

Solutions that satisfy the first three properties belong to the **ESL family of values** (representing Efficiency, Symmetry, and Linearity) (Radzik and Driessen, 2013). Including the null effects property leads to the Shapley value (Shapley et al., 1953), making it the only ESL-value that meets the null effects property.
## 3.2 SHAP Method and KernelSHAP

In the context of Machine Learning, given a predictive model $f$ trained on a set $N = \{1, 2 \dots n\}$ of $n$ features, an instance $x = [x_1, \dots, x_n]$ and its prediction $f(x) \in \mathbb{R}$, the objective of feature attribution is to assign an importance score to each feature to quantify its contribution to a prediction $f(x)$. SHAP leverages coalitional game theory and the Shapley value to obtain those attribution scores. Features in $N$ are treated as players, and $f(x)$ is the worth to distribute among them. It is assumed that $f$ maps a subset $S \subseteq N$ to a real-value number $f(x_S)$ with $x_S = [x_i : i \in S]$ representing the vector $x$ restricted to the features present in $S$. The value $f(x_S)$ assigned to a coalition $S$ is its worth, i.e. the value predicted by $f$ when only the features in $S$ are considered. So SHAP assigns each feature a share of the grand coalition's worth $f(x_N) = f(x)$. The SHAP value of a feature $j \in N$ for the explanation of a prediction $f(x)$ is defined as (Lundberg and Lee, 2017; Shapley et al., 1953):

$$ \phi_j(f, x) = \frac{1}{n} \sum_{S \subseteq N, j \in S} \binom{n-1}{|S|-1}^{-1} f(x_S) - \frac{1}{n} \sum_{S \subseteq N, j \notin S} \binom{n-1}{|S|}^{-1} f(x_S). \quad (1) $$

In the following, we denote by $f(S)$ the value of $f(x_S)$, and $\phi_i(f, x)$ is written $\phi_i(f)$ or $\phi_i$ when $x$ and $f$ are clear from the context.

SHAP values are the only solution concepts that satisfy the properties mentioned in Section 3.1. However they have one major drawback: their computational complexity increase exponentially with the number of features $n$. For this reason, various approaches to approximating the exact SHAP values have been proposed (Lundberg and Lee, 2017; Lundberg et al., 2020; Kwon and Zou, 2022; Chen et al., 2023; Kelodjou et al., 2024). We focus here on KernelSHAP (Lundberg and Lee, 2017).

KernelSHAP (Lundberg and Lee, 2017) views the SHAP values as the solution to a weighted linear regression problem (Charnes et al., 1988). A prediction's explanation is modeled as a linear function of the form $g(S) = \phi_0 + \sum_{i \in S} \phi_i$. Attributions are the coefficients $\phi$ that minimize the following objective:

$$ \phi(f) = \arg \min_{\phi_0, \dots, \phi_n} \sum_{S \subseteq N} w(S) (f(S) - g(S))^2. \quad (2) $$

With the SHAP weighting kernel $w(S)$ given by:

$$ w(S) = \frac{n-1}{\binom{n}{|S|} |S|(n-|S|)}, $$

where the values $w(\emptyset) = w(N) = \infty$ enforce constraints $\phi_0 = f(\emptyset)$ for the intercept, and $\sum_{i \in N} \phi_i = f(N) - f(\emptyset)$ for the sum of the coefficients $^2$. It has been proved that when all possible coalitions are present, the solutions to this optimization problem are the SHAP values. Due to the exponential number of coalitions, KernelSHAP solves this optimization problem on a sample.

<footnote n="2">2. In ML, unlike traditional game theory, $f(\emptyset)$ is the baseline prediction, when all features are absent and may not be zero. The total payoff to distribute is then $f(N) - f(\emptyset)$.</footnote>
A fixed **budget** $\mathcal{B} \in \mathbb{N}$ dictates the number of coalitions in the sample. Coalitions can be structured into **layers**, where a layer $l$ comprises coalitions $S$ of size $|S| = l$ features or $|S| = n - l$ features. A layer is considered *complete* once all its constituent coalitions have been selected to solve the problem stated in (2); otherwise we say the layer is *incomplete*. Since the SHAP kernel assigns higher weights to lower layers, KernelSHAP completes the layers progressively, only filling a layer when two conditions are met: (a) the remaining budget is sufficient to complete the layer, and (b) the layer carries significant weight to justify its complete exploration. If these conditions are not met, the selection process is carried out randomly on all the remaining incomplete layers. Kelodjou et al. (2024) found that in practice, KernelSHAP only manages to complete the earliest layers (or lower layers). Hence, a significant part of its coalitions are selected at random, making SHAP unstable – the same prediction may obtain different explanations across different runs (Zhou et al., 2021; Saarela and Geogieva, 2022; Visani et al., 2020). To tackle this instability, Kelodjou et al. (2024) propose to remove condition (b) and to fix $\mathcal{B}$ so that it yields only complete layers. This approach eliminates variability in the set of coalitions used to derive the explanation $g$, resulting in stable explanations.

# 4 Stratum-based Attribution Scores

This section presents our main contributions: the StratoSHAP family of stable attribution values, and the proof of the properties of this family.

## 4.1 StratoSHAP

We refer to a **stratum** as a cumulative set of *complete* layers, starting from layer 1. In other words, stratum $k$ encompasses all layers up to layer $k$, expressed as $\text{strat}(k) = \bigcup_{i=1}^{k} \text{lay}(i)$ where $\text{lay}(i)$ is the complete set of coalitions in layer $i$, alternatively defined as:

$$ \text{strat}(k) = \{S \in \mathcal{P}(N) \mid 1 \le |S| \le k \lor n - k \le |S| \le n - 1\}. $$

For example, stratum 3 comprises all the coalitions from layers 1, 2 and 3. The budget, i.e., number of coalitions of a stratum $k$, required to guarantee fully stable explanations, is $\mathcal{B}_k = \sum_{l=1}^{k} 2 \times \binom{n}{l}^3$, except for the case where $k$ is strictly equals to $\frac{n}{2}$. In such a case $\mathcal{B}_k = \mathcal{B}_{k-1} + \binom{k}{n}^4$.

Our approximation StratoSHAP builds upon the weighted linear formulation proposed in KernelSHAP and obtains the attribution values $\phi_1(f) \cdots \phi_n(f)$ by solving the optimization problem (Lundberg and Lee, 2017):

$$ \begin{array}{ll} \min_{\phi_0, \dots, \phi_n} & \displaystyle \sum_{S \in \text{strat}(k)} w(S) \left( \phi_0 + \sum_{i \in S} \phi_i - f(S) \right)^2 \\ \text{s.t.} & \displaystyle \phi_0 = f(\emptyset), \quad \sum_{i=1}^{n} \phi_i = f(N) - f(\emptyset), \qquad (3) \end{array} $$

<footnote n="3">3. Layer $i$ comprises coalitions of size $i$ and $n - i$ with a total of $\binom{n}{i} + \binom{n}{n-i} = 2 \times \binom{n}{i}$ coalitions – since $\binom{n}{i} = \binom{n}{n-i}$.</footnote>

<footnote n="4">4. When $n$ is even, $i = n - i$ in the last layer, which has $\binom{n}{2}$ coalitions.</footnote>
By using the coalitions of a specific stratum k and paying attention to the constraints<fnref n="5" />, we obtain a family of attribution values introduced in the following theorem.

**Theorem 1** (Attribution values with strat(k)). For any feature j ∈ N, the attribution value $\phi_j^k$ computed when using the coalitions of stratum k is:

$$ \phi_j^k(f) = \bar{\phi} + \sum_{S \in \text{strat}(k)} \frac{\lambda_k}{n} \binom{n-1}{|S|-1}^{-1} f(S) - \sum_{S \in \text{strat}(k)} \frac{\lambda_k}{n} \binom{n-1}{|S|}^{-1} f(S), \quad (4) $$

with $\bar{\phi} = \frac{f(N)-f(\emptyset)}{n}$ representing the trivial attribution, $1 \le k \le \lfloor \frac{n}{2} \rfloor$, and $\lambda_k = \begin{cases} 1 & \text{if } k = \frac{n}{2}, \\ \frac{n-1}{2k} & \text{otherwise.} \end{cases}$

The proof of Theorem 1 is shown in Appendix A.

Note that this is a generalization to any $k \in [1, \lfloor \frac{n}{2} \rfloor]$ of the analytical formulation presented in Kelodjou et al. (2024) for $k = 1$.

## 4.2 Theoretical Analysis

StratoSHAP's family of attribution values ensures completely stable explanations, as the set D of coalitions used to solve Equation (3) is deterministic. In line with Theorem 1, we establish that:

**Theorem 2** (Properties of strat(k)). Let N be a set of n features, and k ∈ N such that $1 \le k \le \lfloor \frac{n}{2} \rfloor$. The solution $\phi^k$ computed when using the coalitions of stratum k satisfies the Efficiency, Symmetry, and Linearity (ESL) properties.

The proof can be found in Apppendix B. It is based by establishing an equivalence between equation 4 and formal expression of attribution values from Theorem 3 of Driessen and Radzik (2003), especially the existence of a unique sequence of constants {$b_s | s = 1, \dots, n$} with $b_n = 1$ such that:

$$ \phi_j(f) = \frac{f(N)}{n} + \sum_{\substack{S \subseteq N \\ j \in S}} \frac{b_s}{n} \binom{n-1}{|S|-1}^{-1} f(S) - \sum_{\substack{S \subseteq N \\ j \notin S}} \frac{b_s}{n} \binom{n-1}{|S|}^{-1} f(S), \quad (5) $$

In addition to these properties, the $\phi^k$ values verify the fair treatment property.

**Definition 3** (Fair treatment). Let j, l ∈ N be two features and f be a model.

$$ \text{If } f(S \cup \{j\}) \ge f(S \cup \{l\}) \quad \forall S \subseteq N \setminus \{j, l\}, \text{ then } \phi_j(f) \ge \phi_l(f). $$

<footnote n="5">5. Note that $|S| = 0$ and $|S| = n$ are excluded from the sampling procedure in favor of the constraints $\phi_0 = f(\emptyset)$ and $\sum_{i=1}^n \phi_i = f(N) - f(\emptyset)$.</footnote>
As established in (Radzik and Driessen, 2013), an ESL-value $\phi$ verifies fair treatment if and only if the constants $b_s$ in its representation in Equation (5) satisfy:

$$b_n = 1 \text{ and } b_l \ge 0 \text{ for } l = 1, 2, \dots, n-1.$$

Hence, the attribution values computed using the coalitions of a stratum $k$ adhere to the fair treatment principle since $b_s = \lambda_k$ is always positive. This property guarantees that if two features are such that one always contributes more than the other across all coalitions, the attribution value of the first will be higher than that of the second – ensuring a proper ranking based on contribution.

Besides adhering to the aforementioned properties, these attribution scores correspond to the exact SHAP values when $k = \lfloor \frac{n}{2} \rfloor$. Specifically, in the last stratum, $k$ is either $\frac{n}{2}$ (when $n$ is even) or $\frac{n-1}{2}$ (when $n$ is odd) resulting in $\lambda_k = 1$ for both cases. When $\lambda_k = 1$, Equation (4) boils down to Equation (1). It also follows that only the stratum $\lfloor \frac{n}{2} \rfloor$, i.e., the stratum that leads to the exact SHAP value, verifies the **null effects** axiom (see details in Appendix C).

Finally, we highlight that the time complexity for computing the attribution values within a stratum $k$ is on the order of $O(\frac{n^k}{k!})$.

# 5 Experiments

We conduct experiments to assess the approximation quality of the explanations derived from stratum $k$ w.r.t. the exact SHAP values, and compare our algorithm with other approximation methods.

## 5.1 Empirical Analysis of StratoSHAP

The following hypotheses guide our experiments:

**Hypothesis 1.** For any $k$ such that $1 \le k \le \lfloor \frac{n}{2} \rfloor$, the attribution values $\phi_j^k$ become closer to the exact SHAP values as $k$ increases.

**Hypothesis 2.** We argue that stratum 1 is adequate for explaining predictions of models that do not rely on higher-degree feature interactions. All other effects can be captured by higher strata.

Our evaluations use tabular datasets, both real and synthetic. The real-world datasets were chosen to provide a mixture of classification and regression problems with varying dimensionality as well as to cover a variety of problem domains (see Section 5.1.1). Synthetic data experiments provide control over data and models (See Section 5.1.2).

**Metrics.** We assess the approximation quality of StratoSHAP explanations by comparing them to the exact SHAP values. These explanations are computed for a random sample of instances. We quantify the approximation quality using the following metrics: (a) the **coefficient of determination** $R^2$, which compares an *expected* explanation (e.g., the exact SHAP values) and an *observed* explanation (e.g., stratum-$k$ approximation) to evaluate how well the observed explanation captures the variance of the expected one; higher scores (closer to 1) indicate better agreement; (b) the **mean squared error (MSE)**, which measures the average squared difference between *expected* and *observed* explanations, with lower scores reflecting higher accuracy; (c) the **cosine similarity**, which measures the angular similarity
between the explanations, producing a score in the range [-1, 1], where values closer to 1 indicate stronger agreement; and the (d) **Kendall-τ correlation** (Kendall, 1938), which assesses the consistency of feature rankings, with values ranging from -1 to 1, where higher values indicate better concordance.

### 5.1.1 EVALUATION ON REAL-WORLD DATASETS

**Data.** The following table describes the datasets used (C: classification, R: regression): For

<table><thead><tr><td>Name</td><td>#features</td><td>Size</td><td>Task</td></tr></thead><tbody><tr><td>German Credit (Hofmann, 1994)</td><td>20</td><td>1000</td><td>C</td></tr><tr><td>Dry bean (Dry Bean [Dataset], 2020)</td><td>16</td><td>13611</td><td>C</td></tr><tr><td>Adult (Becker and Kohavi, 1996)</td><td>12</td><td>32561</td><td>C</td></tr><tr><td>Credit Card (Yeh, 2016)</td><td>23</td><td>30000</td><td>C</td></tr><tr><td>Boston (Harrison Jr and Rubinfeld, 1978)</td><td>13</td><td>506</td><td>R</td></tr><tr><td>Movie</td><td>19</td><td>505</td><td>R</td></tr><tr><td>HELOC (FICO, 2018)</td><td>23</td><td>10459</td><td>C</td></tr></tbody></table>

each dataset, the explanations were computed on all strata and 100 random instances from the test set. For each tested instance, we invoke a black-box model for prediction and explain this prediction using our stratum-wise approach. Subsequently, we assess the explanation quality, w.r.t. the exact SHAP values using the aforementioned metrics, and report the average explanation quality across all instances. The complete experiments on all datasets and models are available in Appendix D.

**Black-box models.** We experiment with different ML models such as Random Forest (RF), Multi-layer Perceptron (MLP), Logistic Regression (LR - for classification), Support Vector Machines (SVM), and XGBoost (XGB). The models were trained on 80% of the data, and their accuracy was tested on the remaining 20%. We use the scikit-learn implementations, except for XGB, which was trained using its official library 6. The accuracy ranges between 0.65 to 0.99.

**Results.** Figure 1 illustrates the approximation quality of StratoSHAP on the Adult and Boston datasets, each containing a total of 6 strata. Each point indicates the approximation quality (y-axis) achieved using stratum *k* to compute explanations (x-axis). Across different black-box models, the approximation quality generally improves with increasing *k*, reaching the exact SHAP value at the optimum. However, with the XGB model, we occasionally observe a different pattern for the Kendall metric (e.g., on Adult and German Credit datasets), in which the increase is not monotonic. Yet the metric still reflects a good level of approximation quality, even in these cases.

The same phenomenon can be observed in all the other datasets and black-box models (details in Appendix D). This trend supports our first hypothesis: augmenting the number of strata results in a closer approximation of the exact SHAP value. Additionally, we highlight that in the Adult dataset, all stratum-based explanations perfectly agree with the exact SHAP

<footnote n="6">6. https://github.com/dmlc/xgboost</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Different agreement metrics between the exact SHAP values and the attribution values computed on the coalitions of the *k*-th stratum on two datasets.</figcaption></figure>

values for the LR and SVM classifiers. This can be attributed to the fact that these models do not rely on feature interactions to make predictions. Hence, the coalitions of stratum 1 are sufficient to capture the average marginal contribution of the features. Conversely, the MLP model appears to be more challenging to explain. These results suggest that when a model includes feature effects that are difficult to capture, using more strata can yield better explanations, supporting our second hypothesis. Further analyses of the differences in approximation quality observed between two strata can be found in the Appendix D. We also note that in the studied models, most information is captured when reaching strata 5.

### 5.1.2 SYNTHETIC DATA AND MODELS

This section presents some experiments performed on synthetic data and models aimed at testing our hypotheses in fully controlled settings.

**Polynomial Function as Black-Box Model.** We start by studying the behavior of StratoSHAP explanations on multivariate polynomial black-box models. The idea is to construct increasingly complex functions and evaluate whether our hypotheses 1 and 2 remain valid. We focus on feature interactions. If $f$ is a function on $n$ features ($x_1, \dots, x_n$), we define it as a sum of higher degree monomials of the form $\prod_{l \in S' \subset N} x_l$, e.g., $x_1x_3$, that capture interactions between subsets of the input features. The order (or level) of an interaction is the number of features multiplied in a monomial, whereas the degree of the polynomial is the highest degree of all its monomials. For example, the function $f(x) = 7x_1x_3x_4 + x_2x_5$ has two monomials of order 3 and 2, and thus its order is 3.

We build functions defined on $n = 15$ features. We randomly build 45 functions of orders ranging from 1 to 8. Each function contains 15 monomials, and each variable occurs in at
least one monomial. In addition to the interactions, we also allow for non-linear effects in
the monomials: powers $x_j^{\beta_j}$ with $\beta_j \le 5$. Next, we randomly generate 1000 input instances
$x \in \mathbb{R}^{15}$ and evaluate them on the functions to simulate a prediction scenario. We then
compute StratoSHAP explanations for $1 \le k \le 7$ and present the average explanation quality
across the 45 functions and the 1000 instances.

Figure 2(a) and (b) show the obtained results for the $R^2$-score and cosine similarity $^7$. The plots tell us that the attribution values based on lower strata can be very bad approximations of the exact SHAP values when the degree of feature interaction in the black-box model is high. In those cases, the upper strata contribute with valuable and novel information about the actual attribution of the features. For instance, going from stratum 3 to 4 makes the $R^2$-score jump from negative values to around 0.5 for order-8 functions. These observations stand in line with both our first and second hypotheses.

**Black-Box Models on Synthetic Data.** We now shift our attention to scenarios where feature interactions are embedded in the training data. We therefore generate datasets $\mathcal{D} = \{(x^{(i)}, f(x^{(i)}))\}_{i=1}^m$, where $f(x)$ is a multivariate polynomial function designed according to the protocol of the previous section, and $x^{(i)} \sim \mathcal{N}(0, 1)$. We train black-box models on these datasets to compute predictions.

We generate datasets of 1000 instances in $\mathbb{R}^{15}$ for each interaction order between 1 and 8 leading to 8 datasets. We then build 10 polynomial functions (such that the interaction variables can have powers greater than 1) and use them to label the instances of our 8 datasets yielding 10 × 8 learning problems. We then train a Random Forest (RF), a Multilayer Perceptron (MLP), and an XGBoost (XGB) on those datasets and explain the predictions of these models for all the 1000 instances. Finally, we assess the quality of the explanations by comparing them to the exact SHAP values and then report the average results across all instances.

Figure 2(c) and (d) depicts our findings. We expect the black-box to be a complex function given the interactions in the data. However, the excellent $R^2$ scores obtained from stratum 1 for XGB show that this approach has learnt a very simple model. Here, increasing the strata level hardly changes the computed attribution values, indicating early convergence and no need to increase strata level. On the other hand, even for order-1 polynomials, attribution values for MLP cannot be fully captured by stratum 1 and require to go up to strata 3-4: this indicates that MLP is likely to have built a model with higher level interactions than the original data. Conversely, for interactions of order 7-8 in the data, MLP yields a good performance at strata 5-6. This suggests that the MLP is likely to have built a model that captures interactions of order 5-6 (lower than the data). In all these cases StratoSHAP requires the use of higher strata for more accurate explanations.

## 5.2 StratoSHAP vs. Competitors

We now compare StratoSHAP’s performance against several state-of-the-art sampling-based approximations of the SHAP value in traditional synthetic coalition games and for providing local explanations of ML model predictions. The methods considered in this comparison include KernelSHAP (Lundberg and Lee, 2017), SVARM (Kolpaczki et al., 2024), Owen

<footnote n="7">7. The results for the other metrics are available in Appendix D.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: (a) and (b): explanation quality of synthetic functions; (c) and (d): explanation quality of black-box models trained on synthetic data.</figcaption></figure>

Sampling (Okhrati and Lipani, 2021), Sobol (Mitchell et al., 2022), ApproShapley (Castro et al., 2009), and Unbiased KernelSHAP (Covert and Lee, 2021). Each algorithm was executed 30 times per coalition budget (to evaluate the variance), and the results are reported using the metrics described previously. The algorithm's runtime is also assessed.

The algorithms were executed with comparable budgets corresponding to the number of coalitions in the specified stratum. For example, in the Shoes game (more details below), stratum 2 consists of 2550 coalitions. Both KernelSHAP and StratoSHAP were allotted this budget. Since KernelSHAP and StratoSHAP add two additional coalitions to handle constraints (coalitions with all features and no features), ApproShapley, SVARM, Owen Sampling, and Unbiased KernelSHAP used a budget of 2552 coalitions. For Sobol, its budget must satisfy the condition $B \mod (n+1) = 0$. Thus, the closest integer to 2552 that meets this requirement is 2550, which is used as its budget.
<figure><img src="image_4.png" /><figcaption>Figure 3: StratoSHAP and selected competitors on synthetic and explainable AI games.</figcaption></figure>

**Environment.** These experiments were conducted on a dedicated server equipped with dual Intel Xeon Gold 5220 CPU @ 2.20 GHz, consisting of 36 cores (2 sockets, each with 18 cores).

**Synthetic Coalitional Games.** As done for other methods (Kolpaczki et al., 2024), we evaluate the approximation quality of StratoSHAP and the competitors on synthetic coalitional games where the exact Shapley values are available. These synthetic games, with known Shapley values, enable us to evaluate the approximation quality in situations involving a large number of features — which is often a challenge in explainable AI due to the complexity of computing the exact Shapley value. Specifically, we consider the Airport Game (Castro et al., 2009) (with $n = 100$ players), the Shoes Game (Castro et al., 2009) (with $n = 50$ players), and the Sum Of Unanimity Game (van Campen et al., 2018) (with $n = 20$ players). More details about these games are left in the supplementary material.

**Explainability Games.** We used the Boston and Adult datasets as before and computed explanations for 10 randomly chosen instances from each dataset. To handle missing features, a fixed background dataset consisting of 50 randomly selected instances was employed in this experiment.

The results are presented in Figure 3, featuring the games Shoes (a), SOUG (b), and the local explainability of XGBoost's predictions for Boston (c) and Adult (d). For Shoes, only the first 5 strata were used, as the number of coalitions becomes excessively large beyond that point, while all strata were applied in the other cases. Firstly, note that in (a.1), StratoSHAP is not displayed because it consistently finds the exact Shapley values, resulting in an MSE of 0, which is not visible on the logarithmic scale. Similarly, in (b.1), (c.1) and (d.1), StratoSHAP and KernelSHAP accurately determine the exact SHAP values for the final stratum, resulting the plunge on the log-scale graph. One can also observe that all the approaches have a similar behavior across all experiments. StratoSHAP exhibits at first modest improvements of the MSE when the stratum index increases, however when
getting to a number of strata tackling the level of interactions present in the actual model (hypothesis 2), StratoSHAP improves exponentially and is guaranteed to get the exact results at worst in the last stratum. KernelSHAP enjoys the same property for the final stratum, however with the lowest budgets, it tends to choose coalitions from many different layers, leading to a poorer approximation than StratoSHAP. The other sampling approaches also tend to have worse approximation than StratoSHAP for the lowest budget, but then improve these approximations faster as the budget grows. However they don't benefit from the same theoretical properties as StratoSHAP, and their approximation quality reaches a plateau for the highest budgets, without getting to the exact SHAP values. StratoSHAP is also the only sampling approach that is completely stable. The other sampling approaches are especially unstable for the lowest budget (ex: for SOUG, up to stratum 3's budget, both SVARM and KernelSHAP have a mean standard deviation above 30%), getting more stable as the budget increases. The detailed results are in the supplementary materials.

# 6 Conclusion

We have proposed the StratoSHAP family of attribution values computed from strata of feature coalitions. Those attribution values not only deliver fully stable explanations, but also enjoy most of SHAP's theoretical properties. In a complementary empirical evaluation we show that these attribution values strike a series of trade-offs between computational complexity and agreement with the exact SHAP values. While in many cases explanations based on low strata approximate the SHAP values very efficiently, the presence of complex interactions tilts the balance towards higher computational complexity. This is so because SHAP needs the feature coalitions from higher strata to assign attribution in a fair way. We believe these are all good news for the users of SHAP, who can now count on a framework to trade runtime for explanation quality – with full stability guarantees. That said, finding the right stratum level still requires users to compute different attribution scores. We believe that automating such a process remains an interesting research avenue.

# References

Chirag Agarwal, Nari Johnson, Martin Pawelczyk, Satyapriya Krishna, Eshika Saxena, Marinka Zitnik, and Himabindu Lakkaraju. Rethinking stability for attribution-based explanations. In *ICLR Workshop on PAIR 2Struct: Privacy, Accountability, Interpretability, Robustness, Reasoning on Structured Data*, 2022.

Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5XW20, 1996. Accessed: 2024-10-15.

Sebastian Bordt and Ulrike von Luxburg. From shapley values to generalized additive models and back. In *International Conference on Artificial Intelligence and Statistics*, pages 709–745. PMLR, 2023.

Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. *Computers & Operations Research*, 36(5):1726–1730, 2009.
Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada. Improving polynomial estimation of the shapley value by stratified random sampling with optimum allocation. *Computers & Operations Research*, 82:180-188, 2017.

Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. *Computational aspects of cooperative game theory*. Springer Nature, 2022.

A Charnes, B Golany, M Keane, and J Rousseau. Extremal principle solutions of games in characteristic function form: core, chebychev and shapley value generalizations. *Econometrics of planning and efficiency*, pages 123-133, 1988.

Siu Lun Chau, Robert Hu, Javier Gonzalez, and Dino Sejdinovic. Rkhs-shap: Shapley values for kernel methods. *Advances in neural information processing systems*, 35:13050-13063, 2022.

Hugh Chen, Joseph D Janizek, Scott Lundberg, and Su-In Lee. True to the model or true to the data? *arXiv preprint arXiv:2006.16234*, 2020.

Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate shapley value feature attributions. *Nature Machine Intelligence*, 5(6):590-601, 2023.

Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation using linear regression. In Arindam Banerjee and Kenji Fukumizu, editors, *Proceedings of The 24th International Conference on Artificial Intelligence and Statistics*, volume 130 of *Proceedings of Machine Learning Research*, pages 3457-3465. PMLR, 13-15 Apr 2021.

Theo Driessen and Tadeusz Radzik. Extensions of hart and mas-colell's consistency to efficient, linear, and symmetric values for tu-games. In *ICM millennium lectures on games*, pages 147-165. Springer, 2003.

Dry Bean [Dataset]. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/CS0S4B, 2020. Accessed: 2024-10-15.

FICO. Explainable machine learning challenge, 2018. https://community.fico.com/s/explainable-machine-learning-challenge, 2018. Accessed: 2024-10-15.

Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. Kernelshap-iq: Weighted least-square optimization for shapley interactions. *arXiv preprint arXiv:2405.10852*, 2024a.

Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. Shap-iq: Unified approximation of any-order shapley interactions. *Advances in Neural Information Processing Systems*, 36, 2024b.

Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile. In *Proceedings of the AAAI conference on artificial intelligence*, volume 33, pages 3681-3688, 2019a.

Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim. Towards automatic concept-based explanations. *Advances in neural information processing systems*, 32, 2019b.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. *Journal of environmental economics and management*, 5(1):81-102, 1978.

Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5NC77, 1994. Accessed: 2024-10-15.

Ferenc Illés and Péter Kerényi. Estimation of the shapley value by ergodic sampling. *arXiv preprint arXiv:1906.05224*, 2019.

Gwladys Kelodjou, Laurence Rozé, Véronique Masson, Luis Galárraga, Romaric Gaudel, Maurice Tchuente, and Alexandre Termier. Shaping up shap: Enhancing stability through layer-wise neighbor selection. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 13094-13103, 2024.

Maurice G Kendall. A new measure of rank correlation. *Biometrika*, 30(1/2):81-93, 1938.

Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the shapley value without marginal contributions. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 13246-13255, 2024.

Indra Kumar, Carlos Scheidegger, Suresh Venkatasubramanian, and Sorelle Friedler. Shapley residuals: Quantifying the limits of the shapley value for explanations. *Advances in Neural Information Processing Systems*, 34:26598-26608, 2021.

Yongchan Kwon and James Y Zou. Weightedshap: analyzing and improving shapley based feature attributions. *Advances in Neural Information Processing Systems*, 35:34363-34376, 2022.

Vincent Lemaire, Fabrice Clérot, and Marc Boullé. An Efficient Shapley Value Computation for the Naive Bayes Classifier. In *Proceedings of the Workshop on Advances in Interpretable Machine Learning and Artificial Intelligence*, 2023.

Zachary Chase Lipton. The mythos of model interpretability (2016). *arXiv preprint arXiv:1606.03490*, pages 14-18, 2016.

Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. *Advances in neural information processing systems*, 30, 2017.

Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. *Nature machine intelligence*, 2(1): 56-67, 2020.

Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the estimation error of sampling-based shapley value approximation. *arXiv preprint arXiv:1306.4265*, 2013.

Luke Merrick and Ankur Taly. The explanation game: Explaining machine learning models using shapley values. In *Machine Learning and Knowledge Extraction: 4th IFIP TC 5, TC 12, WG 8.4, WG 8.9, WG 12.9 International Cross-Domain Conference, CD-MAKE 2020, Dublin, Ireland, August 25-28, 2020, Proceedings 4*, pages 17-38. Springer, 2020.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation. *Journal of Machine Learning Research*, 23(43):1–46, 2022.

Christoph Molnar. *Interpretable Machine Learning*. https://christophm.github.io/interpretable-ml-book, 2022.

J von Neumann, Oskar Morgenstern, et al. Theory of games and economic behavior. *Princeton*, 1953.

Ramin Okhrati and Aldo Lipani. A multilinear sampling algorithm to estimate shapley values. In *2020 25th International Conference on Pattern Recognition (ICPR)*, pages 7992–7999. IEEE, 2021.

Tadeusz Radzik and Theo Driessen. On a family of values for tu-games generalizing the shapley value. *Mathematical Social Sciences*, 65(2):105–111, 2013.

Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " why should i trust you?" explaining the predictions of any classifier. In *Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining*, pages 1135–1144, 2016.

Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In *Proceedings of the AAAI conference on artificial intelligence*, volume 32, 2018.

Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. *Nature machine intelligence*, 1(5):206–215, 2019.

Mirka Saarela and Lilia Geogieva. Robustness, stability, and fidelity of explanations for a deep skin cancer classification model. *Applied Sciences*, 12(19):9545, 2022.

Lloyd S Shapley et al. A value for n-person games. In Harold William Kuhn and Albert William Tucker, editors, *Contributions to the Theory of Games (AM-28), Volume II*, pages 307–318. Princeton University Press, Princeton, 1953. ISBN 978-1-4008-8197-0.

Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In *International conference on machine learning*, pages 3145–3153. PMLR, 2017.

Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. *The Journal of Machine Learning Research*, 11:1–18, 2010.

Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley interaction index. *Journal of Machine Learning Research*, 24(94):1–42, 2023.

Tjeerd van Campen, Herbert Hamers, Bart Husslage, and Roy Lindelauf. A new approximation method for the shapley value applied to the wtc 9/11 terrorist attack. *Social Network Analysis and Mining*, 8:1–12, 2018.

Giorgio Visani, Enrico Bagli, and Federico Chesani. Optilime: Optimized lime explanations for diagnostic computer algorithms. *arXiv preprint arXiv:2006.05714*, 2020.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. *Harv. JL & Tech.*, 31:841, 2017.

I-Cheng Yeh. Default of credit card clients. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C55S3H, 2016. Accessed: 2024-10-15.

Zhengze Zhou, Giles Hooker, and Fei Wang. S-lime: Stabilized-lime for model explanation. In *Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining*, pages 2429–2438, 2021.
Appendix A. Proof of Theorem 1 (See page 7)

**Theorem 1** (Attribution values with strat(k)). For any feature j ∈ N, the attribution value
$\phi_j^k$ computed when using the coalitions of stratum k is:

$$
\phi_j^k(f) = \bar{\phi} + \sum_{S \in \text{strat}(k)} \frac{\lambda_k}{n} \binom{n-1}{|S|-1}^{-1} f(S) - \sum_{S \in \text{strat}(k)} \frac{\lambda_k}{n} \binom{n-1}{|S|}^{-1} f(S), \quad (4)
$$

with $\bar{\phi} = \frac{f(N)-f(0)}{n}$ representing the trivial attribution,
$1 \le k \le \lfloor \frac{n}{2} \rfloor$, and $\lambda_k = \begin{cases} 1 & \text{if } k = \frac{n}{2}, \\ \frac{n-1}{2k} & \text{otherwise.} \end{cases}$
Appendix B. Proof of Theorem 2 (See page 7)

**Theorem 2** (Properties of strat($k$)). Let $N$ be a set of $n$ features, and $k \in \mathbb{N}$ such that $1 \le k \le \lfloor \frac{n}{2} \rfloor$. The solution $\phi^k$ computed when using the coalitions of stratum $k$ satisfies the *Efficiency, Symmetry, and Linearity (ESL) properties*.
Appendix C. Proof of the Null Effects Property and the Last Stratum

We aim to demonstrate that, with the attribution values defined by the following equation:

$\forall j \in N = \{1, \dots, n\}$

$$
\phi_j^k(f) = \frac{f(N) - f(\emptyset)}{n} + \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \lambda_k \frac{(|S| - 1)!(n - |S|)!}{n!} f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \lambda_k \frac{|S|!(n - |S| - 1)!}{n!} f(S),
$$

$$
\text{with } \text{strat}(k) = \{S \in \mathcal{P}(N) \mid \begin{array}{l} 1 \le |S| \le k \quad \lor \quad n-k \le |S| \le n-1 \end{array}, |N| = n, 1 \le k \le \lfloor \frac{n}{2} \rfloor\}, \text{ and } \lambda_k = \begin{cases} 1 & \text{if } k = \frac{n}{2} \\ \frac{n-1}{2k} & \text{otherwise,} \end{cases}
$$

only the stratum ⌊n/2⌋, i.e., the stratum that leads to the exact SHAP value, satisfies the **null effects** property.

**Proof** Assume that a feature *j* is entirely disregarded by model *f* when computing the prediction to be explained. This means that

$$
f(S \cup \{j\}) = f(S) \quad \forall S \in \text{strat}(k) \quad \text{with} \quad j \notin S. \tag{6}
$$

Our goal is to prove that $\phi_j^k = 0$ when $k = \lfloor \frac{n}{2} \rfloor$, and that $\phi_j^k \neq 0$ otherwise.

Introducing the quantities $\gamma_{1,n}(s) = \frac{(s-1)!(n-s)!}{n!}$, and $\gamma_{2,n}(s) = \frac{s!(n-s-1)!}{n!}$ with $s = |S|$, we get

$$
\phi_j^k = \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s) f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s) f(S) \right) - \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) \right) \tag{7}
$$

Noting that $\sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s)f(S) = \frac{f(\{j\})}{n}$ and $\sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) = \frac{f(N \setminus \{j\})}{n}$, the
expression follows as

$$
= \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \frac{f(\{j\})}{n} + \sum_{\substack{S \in \text{strat}(k) \\ 2 \le s \le k}} \gamma_{1,n}(s) f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s) f(S) + \sum_{\substack{S \in \text{strat}(k) \\ n-k+1 \le s \le n-1}} \gamma_{1,n}(s) f(S) \right) - \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ 1 \le s \le k-1}} \gamma_{2,n}(s) f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) + \sum_{\substack{S \in \text{strat}(k) \\ n-k \le s \le n-2}} \gamma_{2,n}(s) f(S) + \frac{f(N \setminus \{j\})}{n} \right) \tag{8}
$$

$$
= \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \frac{f(\{j\})}{n} - \frac{f(N \setminus \{j\})}{n} \right) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ 2 \le s \le k}} \gamma_{1,n}(s) f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) \right) \\
+ \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s) f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) \right) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \in S}} \gamma_{1,n}(s) f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s) f(S) \right)
$$
Observe that considering all sets $S \in \text{strat}(k)$ where $j \in S$ and $s \in [2..k]$ is equivalent to considering all sets $S \cup \{j\}$ where $S \in (\text{strat}(k) \setminus \{j\})$ and $s \in [1..k-1]$. Therefore, it follows that

$$ \phi_j^k = \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \frac{f(\{j\})}{n} - \frac{f(N \setminus \{j\})}{n} \right) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{1,n}(s+1)f(S \cup \{j\}) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right. \\ \left. + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{1,n}(s+1)f(S \cup \{j\}) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{1,n}(s+1)f(S \cup \{j\}) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) \right) $$

Noting that $\gamma_{1,n}(s+1) = \gamma_{2,n}(s)$ and using the relation from Equation (6), we arrive at the following

$$ \phi_j^k = \frac{f(N \setminus \{j\})}{n} (1 - \lambda_k) - \frac{f(\emptyset)}{n} (1 - \lambda_k) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) \\ + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) $$

This leads to the following expression

$$ \phi_j^k = \frac{f(N \setminus \{j\})}{n} (1 - \lambda_k) - \frac{f(\emptyset)}{n} (1 - \lambda_k) + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \right) \quad (9) $$

For $1 \le k < \lfloor \frac{n}{2} \rfloor$, $\phi_j^k$ corresponds to Equation (9), which is non-zero for any function $f$.

However, if $k = \lfloor \frac{n}{2} \rfloor$, we have $\lambda_k = 1$, simplifying the expression to:

$$ \phi_j^k = \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S}} \gamma_{2,n}(s)f(S) \quad (10) $$

Next, we consider two scenarios: $k = \frac{n-1}{2}$ and $k = \frac{n}{2}$.
**Case 1:** If $k = \frac{n-1}{2}$, then for both the left and right sums in Equation (10), $s = \frac{n-1}{2}$. Therefore, $\phi_j^k = 0$.

**Case 2:** If $k = \frac{n}{2}$, we have $k = n - k$, and $\text{strat}(k)$ can be expressed as:

$$ \text{strat}(k) = \{S \in \mathcal{P}(N) \mid 1 \le |S| \le k \ \lor \ n-k+1 \le |S| \le n-1\}. $$

Subsequently, the expressions (7) and (8) become:

$$ \phi_j^k = \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \in S \\ 1 \le s \le k}} \gamma_{1,n}(s)f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \in S \\ n-k+1 \le s \le n-1}} \gamma_{1,n}(s)f(S) \right) - \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ 1 \le s \le k}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ n-k+1 \le s \le n-1}} \gamma_{2,n}(s)f(S) \right) \quad (11) $$

$$ = \frac{f(N) - f(\emptyset)}{n} + \lambda_k \left( \frac{f(\{j\})}{n} + \sum_{\substack{S \in \text{strat}(k) \\ j \in S \\ 2 \le s \le k}} \gamma_{1,n}(s)f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \in S \\ s=n-k+1}} \gamma_{1,n}(s)f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \in S \\ n-k+2 \le s \le n-1}} \gamma_{1,n}(s)f(S) \right) \\ - \lambda_k \left( \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ 1 \le s \le k-1}} \gamma_{2,n}(s)f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ s=k}} \gamma_{2,n}(s)f(S) + \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ n-k+1 \le s \le n-2}} \gamma_{2,n}(s)f(S) + \frac{f(N \setminus \{j\})}{n} \right), (12) $$

which simplifies further in:

$$ \phi_j^k = \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ s=n-k}} \gamma_{2,n}(s)f(S) - \sum_{\substack{S \in \text{strat}(k) \\ j \notin S \\ s=k}} \gamma_{2,n}(s)f(S). \quad (13) $$

This confirms $\phi_j^k = 0$ as both sides of the equation involve $s = \frac{n}{2}$. ■
# Appendix D. Experiments: Empirical Analysis of StratoSHAP

Here, we present the results of the empirical analysis of StratoSHAP, evaluated on both real-world tabular datasets and synthetic data.

## D.1 Evaluation on Real-World Datasets

<table><caption>Table 1: Real-world datasets</caption><thead><tr><td>Name</td><td>#features</td><td>Size</td><td>Task</td></tr></thead><tbody><tr><td>German Credit (Hofmann, 1994)</td><td>20</td><td>1000</td><td>Classification</td></tr><tr><td>Adult (Becker and Kohavi, 1996)</td><td>12</td><td>32561</td><td>Classification</td></tr><tr><td>Boston (Harrison Jr and Rubinfeld, 1978)</td><td>13</td><td>506</td><td>Regression</td></tr><tr><td>Dry bean (Dry Bean [Dataset], 2020)</td><td>16</td><td>13611</td><td>Classification</td></tr><tr><td>Credit Card (Yeh, 2016)</td><td>23</td><td>30000</td><td>Classification</td></tr><tr><td>Movie</td><td>19</td><td>505</td><td>Regression</td></tr><tr><td>HELOC (FICO, 2018)</td><td>23</td><td>10459</td><td>Classification</td></tr></tbody></table>

Table 1 summarizes the datasets utilized in this evaluation. The approximation quality was assessed using the following metrics: coefficient of determination $R^2$, the mean squared error (MSE), the cosine similarity, and the Kendall-$\tau$ correlation. The black-box models considered included Random Forest (RF), Multi-layer Perceptron (MLP), Logistic Regression (LR – for classification), Support Vector Machines (SVM), and XGBoost (XGB). For each dataset, 100 instances were randomly selected from the test set$^8$. Missing features were managed using a baseline approach, representing the average instance from the training data of the corresponding dataset. For each instance, predictions are made using a black-box model, and our stratum-wise approach is applied to explain these predictions. The quality of the explanations is then evaluated against the exact SHAP values using the specified metrics, with the average quality reported across all instances.

The following presents two types of visualizations for each dataset:

1. The progression of approximation quality as a function of the strata used for computation. Each point represents the approximation quality (y-axis) achieved using stratum $k$ to compute explanations (x-axis).

2. A more detailed breakdown of the approximation quality for each individual stratum. This enables the assessment of the improvement from a stratum $k$ to a stratum $k + 1$. Specifically, it compares the explanations derived from stratum $k$ with those based on strata $k' > k$. This comparison highlights the incremental informational value provided by each additional layer of coalitions. For instance, stratum 3 encompasses all layers from stratum 2, along with layer 3. That means that if the explanation computed from stratum 3 shows a significant difference compared to that from stratum 2, that difference is attributable to the coalitions in layer 3 (coalitions of size 3 or $n-3$). Since the $R^2$-score is not symmetric, we calculate it such that the coefficients obtained from stratum $k' > k$ serve as the “expected” values (x-axis), which are then “predicted” using

<footnote n="8">8. Each dataset is split into 80% training and 20% testing sets to train and evaluate the models.</footnote>
the coefficients from stratum *k*. The charts also display the loss in agreement as the number of layers between strata *k* and *k'* increases (shown in parentheses).

<figure><img src="image_5.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the LR model.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(f) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the LR model.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_25.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the LR model.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-Stratum coalitions.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_36.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the LR model.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the XGB model.</figcaption></figure>
<figure><img src="image_39.png" /><figcaption>(a) Exact SHAP vs. Attribution Values computed on the *k*-th stratum coalitions⁹.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(b) Evolution of the quality of explanations across the different strata on the MLP model.</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>(c) Evolution of the quality of explanations across the different strata on the SVM model.</figcaption></figure>
<figure><img src="image_42.png" /><figcaption>(d) Evolution of the quality of explanations across the different strata on the RF model.</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>(e) Evolution of the quality of explanations across the different strata on the LR model.</figcaption></figure>
## D.2 Synthetic Data and Models

We provide a comprehensive outline of the experimental protocol using polynomial functions, along with the results across all metrics.

### D.2.1 POLYNOMIAL FUNCTION AS BLACK-BOX MODEL

#### Detailed Experimental Protocol:

1. **Features:** The experiments are conducted with 15 features.

2. **Interaction levels:**

* The interaction levels vary from 1 to 8.

* An interaction level $p$ indicates that the monomials in the polynomial functions will involve up to $p$ features multiplied together.

3. **Polynomial functions:**

* For each interaction level $p$, we construct 45 distinct polynomial functions.

* Each polynomial function consists of 15 monomials.

* Monomials can include terms where features are raised to powers greater than 1, with the highest allowed power being $x_j^{\beta_j}$ where $\beta_j \le 5$.

* Each monomial is assigned a coefficient, randomly drawn from a uniform distribution within the range $(-30, 30)$, excluding 0.

* Each of the 15 features appears in at least one monomial of each polynomial function.

4. **Instances:**

* We generate 1000 input instances to evaluate each polynomial function.

* These instances are sampled from a standard normal distribution with mean = 0 and standard deviation = 1.

5. **Evaluation:**

* For each of the 45 polynomial functions and across the 7 strata, explanations are generated using the 1000 input instances. Missing features were managed using a baseline approach, representing the average instance from the data.

* The quality of these explanations is assessed by comparing the exact SHAP values with the explanations provided by each stratum.

* The average explanation quality is computed across all explanations, except for the MSE, where the median is used due to the considerable influence of outliers on the mean.

**Complete Results:** Figure 11 shows the results.
<figure><img src="image_44.png" /><figcaption>Figure 11: Polynomial function as black-box models.</figcaption></figure>

**Discussion:** We observe that for certain interaction orders, the cosine similarity plot does not reach its maximum value, even at the final stratum (stratum 7). This occurs because some predictions $f(x)$ equal 0, leading to exact SHAP values of 0 for each feature. In such cases, explanations (represented as an $n$-dimensional vector) result in a zero vector. When this happens, the cosine similarity is returned as 0, according to the scikit-learn implementation<fnref n="10" />. As these zero values are averaged with instances where the cosine similarity equals 1, the overall average deviates from 1. Similarly, the occurrence of this type of vector prevents the calculation of the Kendall coefficient, resulting in a ‘NaN’ value, as per the scipy implementation of this metric<fnref n="11" />. After excluding such cases, the adjusted results are shown in Figure 12. A total of 73,045 explanations out of 2,520,000 were excluded, representing approximately 2.9% of the total.

## D.2.2 BLACK-BOX MODELS ON SYNTHETIC DATA

**Detailed Experimental Protocol:** In this experiment, the feature interactions are embedded in the training data, and we train black-box models using these data. The datasets are generated as $\mathcal{D} = \{(x^{(i)}, f(x^{(i)}))\}_{i=1}^m$, where $f(x)$ is a multivariate polynomial constructed based on the previously presented protocol. The dataset construction follows these steps:

1. **Features:** We again use 15 features in the datasets.

<footnote n="10">10. https://scikit-learn.org/stable/modules/generated/sklearn.metrics pairwise.cosine similarity.html</footnote>

<footnote n="11">11. https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.kendalltau.html</footnote>
<figure><img src="image_45.png" /><figcaption>Figure 12: Polynomial function as black-box models: adjusted results.</figcaption></figure>

2. **Interaction levels:** As before, interaction levels range from 1 to 8.

3. **Instances:**

• We generate 1000 input instances.

• These instances, denoted as $x^{(i)}$, are sampled from a standard normal distribution: $x^{(i)} \sim N(0, 1)$.

4. **Polynomial functions:**

• For each interaction level, we build 10 polynomial functions as presented previously.

• Each polynomial function is used to label the instances, resulting in 10 datasets for each interaction level.

5. **Black-Box Models:**

• The black-box models utilized are Random Forest (RF), Multilayer Perceptron (MLP), and XGBoost (XGB). These models are chosen for their ability to capture complex, non-linear relationships between features.

• Each model is trained on the 10 datasets per interaction level.

6. **Evaluation:**
* For each black-box model, we compute explanations for predictions made on all 1000 instances, and across the 7 strata. Missing features were managed using a baseline approach, representing the average instance from the data.

* The quality of these explanations is assessed by comparing the exact SHAP values with the explanations provided by each stratum.

* The average explanation quality is computed for each stratum across all explanations and models, except for the MSE, where the median is used due to the considerable influence of outliers on the mean.

**Complete Results:** The results for the various metrics (where calculable) are shown in Figure 13 for the MLP model, Figure 15 for the XGB model and Figure 17 for the RF model.

<figure><img src="image_46.png" /><figcaption>Figure 13: Explanation quality of black-box models trained on synthetic data: **MLP**.</figcaption></figure>

**Discussion:** As in the previous experiment, we encounter instances where the prediction $f(x)$ equals 0, leading to exact SHAP values of 0 for each feature. Consequently, the explanations are zero vectors, which prevents the accurate calculation of cosine similarity and the Kendall coefficient, as previously noted. This behavior was observed with both MLP and XGB models. After filtering out these cases, the adjusted results are shown in Figure 14 for MLP and Figure 16 for XGB. For the XGB model, 147 explanations out of a total of 56,000 were excluded, representing approximately 0.26% of the total. In the case of the MLP model, 1,743 explanations were removed out of 56,000, accounting for about 3.11%.
<figure><img src="image_47.png" /><figcaption>Figure 14: Explanation quality of black-box models trained on synthetic data: MLP - adjusted results.</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>Figure 15: Explanation quality of black-box models trained on synthetic data: XGB.</figcaption></figure>
<figure><img src="image_49.png" /><figcaption>Figure 16: Explanation quality of black-box models trained on synthetic data: **XGB** - adjusted results.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>Figure 17: Explanation quality of black-box models trained on synthetic data: **RF**.</figcaption></figure>
# Appendix E. Experiments: StratoSHAP versus Competitors

## E.1 Synthetic Coalitional Games

In this section, we provide detailed information about the synthetic coalitional games used in our experiments.

* Shoes Game (Castro et al., 2009; Kolpaczki et al., 2024). This game requires an even number of players. The Shapley value for each player is given by $\phi_j = \frac{1}{2}, \forall j \in N$, where $N$ represents the set of players. In our experiment, we consider $n = 50$ players, resulting in a Shapley value vector of length 50, where each entry is equal to 0.5. For each of the algorithms evaluated, we calculate the approximation of the Shapley value across a set of budgets corresponding to specific strata. We use the first 5 strata in this game. The results are shown in Figure 18. The Kendall metric and $R^2$-score are not provided because they are not appropriate in this context. The Kendall metric fails when the compared values form a vector where all elements are identical, resulting in a ‘NaN’ value due to the lack of rank variation. Similarly, the $R^2$-score is unsuitable when the target values contain identical elements. In such cases, the variance to be explained is zero, which leads to an undefined $R^2$-score.

* Sum of Unanimity (SOUG) Game (van Campen et al., 2018; Kolpaczki et al., 2024). In this game, we consider $n = 20$ players. For each of the algorithms evaluated, we compute the approximation of the Shapley value over a set of comparable budgets, corresponding to distinct strata. In this case, we use all strata. The results are depicted in Figure 19.

* Airport Game: We consider 100 players in this game, following the setup described in Castro et al. (2009); Kolpaczki et al. (2024). For each evaluated algorithm, we calculate the approximation of the Shapley value over a set of budgets, corresponding to a precise stratum. We use the first 4 strata in this game. The results are shown in Figure 20. Contrary to the other two games, this one is not discussed in the paper: we give here a brief analysis of the results. On this game, StratoSHAP does not exhibit a good MSE or $R^2$, and has an average cosine value. Nevertheless even if the attribution values are different from the perfect SHAP values, StratoSHAP manages to get the order correctly even with a very low budget, which its competitors cannot do. Our hypothesis is that Airport, which has 100 players, exhibits complex dependencies with multiple players. These cannot be captured with low strata count. However, due to the sheer combinatorial size of the problem, we could not compute the results for higher strata level. Indeed, the Airport game has a structured scheme for assigning values to players and coalitions of players (see Section 4.3 of Castro et al. (2009)): this structure is antagonistic to the way StratoSHAP samples coalitions. In the Airport game, StratoSHAP, for small strata value, will sample coalitions with too little or too big value according to the valuation scheme of Airport. While more random approaches will be able to get coalitions of average value, that lead them to better results. However they remain unstable, while StratoSHAP is deterministic.

Each algorithm was executed 30 times per coalition budget, and the average results are reported using the metrics described previously. The algorithm's runtime is also assessed.
<figure><img src="image_51.png" /><figcaption>Figure 18: StratoSHAP and selected competitors on Shoes game.</figcaption></figure>

S

## E.2 Explainability Games

We used Adult and Boston datasets and computed explanations for 10 randomly chosen instances from each dataset. To handle missing features, a fixed background dataset consisting of 50 randomly selected instances was employed in this experiment. Here, we present the results for all the metrics discussed in the paper.
<figure><img src="image_52.png" /><figcaption>Figure 19: StratoSHAP and selected competitors on SOUG game.</figcaption></figure>
<figure><img src="image_53.png" /><figcaption>Figure 20: StratoSHAP and selected competitors on Airport game.</figcaption></figure>
<figure><img src="image_54.png" /><figcaption>Figure 21: StratoSHAP and selected competitors on Boston dataset: XGB model.</figcaption></figure>
<figure><img src="image_55.png" /><figcaption>Figure 22: StratoSHAP and selected competitors on Boston dataset: MLP model.</figcaption></figure>
<figure><img src="image_56.png" /><figcaption>Figure 23: StratoSHAP and selected competitors on Boston dataset: RF model.</figcaption></figure>
<figure><img src="image_57.png" /><figcaption>Figure 24: StratoSHAP and selected competitors on Boston dataset: SVM model.</figcaption></figure>
<figure><img src="image_58.png" /><figcaption>Figure 25: StratoSHAP and selected competitors on Adult dataset: XGB model.</figcaption></figure>
<figure><img src="image_59.png" /><figcaption>Figure 26: StratoSHAP and selected competitors on Adult dataset: MLP model.</figcaption></figure>
<figure><img src="image_60.png" /><figcaption>Figure 27: StratoSHAP and selected competitors on Adult dataset: RF model.</figcaption></figure>
<figure><img src="image_61.png" /><figcaption>Figure 28: StratoSHAP and selected competitors on Adult dataset: SVM model.</figcaption></figure>
<figure><img src="image_62.png" /><figcaption>Figure 29: StratoSHAP and selected competitors on Adult dataset: LR model.</figcaption></figure>