Shapley Value Approximation Based on k-Additive Games Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier Abstract The Shapley value is the prevalent solution for fair division problems in which a payout is to be divided among multiple agents. By adopting a game-theoretic view, the idea of fair division and the Shapley value can also be used in machine learning to quantify the individual contribution of features or data points to the performance of a predictive model. Despite its popularity and axiomatic justification, the Shapley value suffers from a computational complexity that scales exponentially with the number of entities involved, and hence requires approximation methods for its reliable estimation. We propose SVA k ADD k_{\text{ADD}} , a novel approximation method that fits a k k -additive surrogate game. By taking advantage of k k -additivity, we are able to elicit the exact Shapley values of the surrogate game and then use these values as estimates for the original fair division problem. The efficacy of our method is evaluated empirically and compared to competing methods. 1 Engineering School - Mackenzie Presbyterian University 2 LMU Munich 3 Munich Center for Machine Learning (MCML) 4 German Research Center for Artificial Intelligence (DFKI, DSA) guilherme.pelegrina@mackenzie.br, patrick.kolpaczki@lmu.de, eyke@lmu.de Code — https://github.com/GuilhermePelegrina/Shapley˙Value˙Approximation˙Based˙on˙k-Additive˙Games.git 1 Introduction The complexity of machine learning models experienced a rapid and certainly significant increase over the last decade. This development comes with an ever-rising burden to understand a model’s decision-making, reaching a point beyond human comprehension. Meanwhile, societal and political influences led to a growing demand for trustworthy AI ( Li et al. 2023 ) . The field of Explainable AI (XAI) emerges to counteract these consequences, aiming to bring back understanding to the human user. Among various explanation types ( Molnar 2021 ) , post-hoc additive explanations convince with an intuitive appeal: an observed numerical effect caused by the behavior of the black box model is divided among participating entities. Additive feature explanations decompose a predicted value ( Lundberg and Lee 2017 ) or generalization performance ( Covert et al. 2020 ) among the involved features, enabling feature importance scores. Beyond explainability, this allows in feature engineering to conduct feature selection by removing features with irrelevant or even harmful contributions ( Cohen et al. 2005 ; Marcílio and Eler 2020 ) . Treating this decomposition as a fair division problem opens the door to game theory which views the features as cooperating agents, forming groups called coalitions to achieve a task and collect a common reward that is to be shared. Such scenarios are captured by the widely applicable notion of cooperative games, modeling the agents as a set of players N and assuming that a real-valued worth \nu(A) can be assigned to each coalition A\subseteq N by a value function \nu . Among multiple propositions the Shapley value ( Shapley 1953 ) prevailed as the most favored solution to the fair division problem. It assigns to each player a share of the collective benefit, more precisely a weighted average of all its marginal contributions, i.e., the increase in collective benefit a player causes when joining a coalition. Its popularity is rooted in the fact that it is provably the only solution to fulfill certain desirable axioms ( Shapley 1953 ) which arguably capture a widespread understanding of fairness. For example, in supply chain cooperation ( Fiestras-Janeiro et al. 2011 ) , the cost reduction when joining a coalition may be shared among companies based on the Shapley value. The greater a company’s marginal contributions to the cost reduction, the greater its received payoff. The applicability of the Shapley value exceeds economics as its utility has been recognized within various disciplines. Most prominently, it has found its way into the field of machine learning, especially as a model-agnostic approach, quantifying the importance of entities such as features or datapoints (see ( Rozemberczki et al. 2022 ) for an overview). Adopting the game-theoretic view, these entities are understood as players which cause a certain numerical outcome. Shaping the measure of a coalition’s worth adequately is pivotal to the informativeness of the importance scores obtained by the Shapley values. For example, considering a model’s generalization performance on a test dataset restricted to the feature subset given by a coalition yields global feature importance scores ( Pfannschmidt et al. 2016 ; Covert et al. 2020 ) . Conversely, local feature attribution scores are obtained by splitting the model’s prediction value for a fixed datapoint ( Lundberg and Lee 2017 ) . The Shapley value is not limited to provide additive explanations since it has also been proposed to perform data valuation ( Ghorbani and Zou 2019 ) , feature selection ( Cohen et al. 2007 ) by removing features with low relevance towards the model’s performance ( Pelegrina and Siraj 2024 ) , ensemble construction ( Rozemberczki and Sarkar 2021 ) , and the pruning of neural networks ( Ghorbani and Zou 2020 ) . Further practical applications include its usage to quantify each feature’s impact in predicting the risk degree in managing industrial machine maintenance ( Nimmy et al. 2023 ) , Pelegrina et al. (2023b) apply it to evaluate the influence of each electrode on the quality of recovered fetal electrocardiograms, and Brusa et al. (2023) measure the features’ importance towards machinery fault detection. Worth mentioning, each application requires an appropriate modeling in terms of player set and value function in order to obtain meaningful scores. The uniqueness of the Shapley value comes at a price that poses an inherent drawback to practitioners: its computation scales exponentially with the number of players taking part in the cooperative game. Consequently, it becomes quickly infeasible for increasing feature numbers or even a few datapoints, especially when complex models are in use whose evaluation is highly resource consuming. As a viable remedy, it is common practice to approximate the Shapley value while providing reliably precise estimates is crucial to obtain meaningful importance scores. On this background, the recent interest in assigning scores to features, datapoints, or even model components, has fueled the research on approximation algorithms, leading to a diverse landscape of approaches (see ( Chen et al. 2023 ) for an overview). Contribution. We propose with SVA k_{\text{ADD}} (Shapley Value Approximation under k -additivity) a novel approximation method for the Shapley value based on the concept of k -additive games whose structure elicits a denser parameterizable value function. Fitting a k -additive surrogate game to randomly sampled coalition-value pairs comes with a twofold benefit. First, it reduces flexibility, promising faster convergence and second, the Shapley values of the k -additive surrogate game are obtained immediately from its representation. In summary, our contributions are: • SVA k_{\text{ADD}} fits a k -additive surrogate game to sampled coalitions, mimicking the given game by a simpler structure with parameterizable degree of freedom while maintaining low representation error. The surrogate game’s own Shapley values are obtained immediately and yield precise estimates for the given game if the representation exhibits a good fit. • SVA k_{\text{ADD}} does not require any structural properties of the value function. Thus, it is domain-independent and can be applied to any cooperative game oblivious to what players and payoffs represent. Specifically in the field of explainability, it is model-agnostic and can approximate local as well as global explanations. • We prove the theoretical soundness of SVA k_{\text{ADD}} by showing analytically that its underlying optimization problem yields the Shapley value. • We empirically compare SVA k_{\text{ADD}} to competitive baselines at the hand of various explanation tasks, and shed light onto the best fitting degree of k -additivity. 2 Related Work The problem of approximating the Shapley value, tackled by various communities, lead to a multitude of approaches to overcome its complexity. First to mention among the class of methods that can handle arbitrary games, without further assumptions on the value function, are those which construct mean estimates via random sampling. Fittingly, the Shapley value of a player can be interpreted as its expected marginal contribution to a specific probability distribution over coalitions. Castro et al. (2009) propose with ApproShapley the sampling of permutations from which marginal contributions are extracted. Further works employ stratification by coalition size ( Maleki et al. 2013 ; Castro et al. 2017 ; van Campen et al. 2018 ; Okhrati and Lipani 2020 ; Zhang et al. 2023 ) , or utilize reproducing kernel Hilbert spaces ( Mitchell et al. 2022 ) . Departing from marginal contributions, Stratified SVARM ( Kolpaczki et al. 2024a ) splits the Shapley value into multiple means of coalition values being further refined by Adaptive SVARM ( Kolpaczki et al. 2024b ) . Guided by a different representation of the Shapley value, KernelSHAP ( Lundberg and Lee 2017 ) solves an approximated weighted least squares problem, to which the Shapley value is its solution. Fumagalli et al. (2023) prove its variant Unbiased KernelSHAP ( Covert and Lee 2021 ) to be equivalent to importance sampling of single coalitions. Joining this family, Pelegrina et al. (2023a) propose k_{ADD} -SHAP, which formulates the surrogate model assuming a k -additive game 1 1 1 Note that k_{ADD} -SHAP is limited to local explanations. In contrast, our proposed method SVA k_{\text{ADD}} differs by its applicability to any formulation of a cooperative game. Moreover, in the context of explainable AI, it is capable of providing global explanations. . It locally adopts the Choquet integral as the interpretable model, whose parameters have a straightforward connection with the Shapley value. Similar to us, Yan et al. (2020) apply surrogate games of parameterizable structure that sum up unanimity games to calculate Shapley values, however, under the assumption that the given game possesses this structure from which we refrain. On the contrary, tailoring the approximation to a specific application by leveraging structural properties promises faster converging estimates. In data valuation, including knowledge of how datapoints tend to contribute to a learning algorithm’s performance resulted in multiple tailored methods ( Ghorbani and Zou 2019 ; Jia et al. 2019b ; Jia et al. 2019a ) . In similar fashion Liben-Nowell et al. (2012) leverage supermodularity in cooperative games. Even further, value functions of certain parameterized shapes facilitate closed-form polynomial solutions of the Shapley value w.r.t. the number of players. Examples include the voting game ( Bilbao et al. 2000 ) and the minimum cost spanning tree games ( Granot et al. 2002 ) used in operations research. 3 The Shapley Value and k -Additivity We formally introduce cooperative games and the Shapley value in Section 3.1 . Next, we present in Section 3.2 the concept of k -additivity, constituting the core of our approach. 3.1 Cooperative Games and the Shapley Value A cooperative game is formally described by n players, captured by the set N=\{1,\ldots,n\} , and an associated payoff function \nu:\mathcal{P}(N)\to\mathbb{R} , where \mathcal{P}(N) represents the power set of N . This simple but expressive formalism may for example represent a shipment coordination where companies form a coalition in order to save costs when delivering their products. In this case, the companies can be modeled as players and \nu(A) represents the benefit achieved by the group of companies A\subseteq N . Clearly, \nu(N) is the total benefit when all companies (players) form the grand coalition N . Commonly, one normalizes the game by defining \nu(\emptyset)=0 , i.e., the worth of the empty set. However, in explainability, \nu(\emptyset) may take nonzero values, e.g., with no features available one may obtain a classification accuracy of 50%. In this case, one can normalize \nu by simply subtracting the worth of the empty set from all game payoffs, i.e., \nu^{\prime}(A)\leftarrow\nu(A)-\nu(\emptyset) for all A\subseteq N . A central question arising from a cooperative game is how to fairly share the worth \nu(N) of the grand coalition N among all participating players. The Shapley value ( Shapley 1953 ) emerges as the prevalent solution concept since it uniquely satisfies axioms that intuitively capture fairness ( Shapley 1953 ) . Given the game (N,\nu) , the Shapley value of each player i is defined as \phi_{i}=\sum\limits_{A\subseteq N\setminus\{i\}}\frac{\left(n-\left|A\right|-1\right)!\left|A\right|!}{n!}[\nu(A\cup\{i\})-\nu(A)]\,, (1) where \left|A\right| represents the cardinality of coalition A . It can be interpreted as a player’s weighted average of marginal contributions to the payoff. Among the fulfilled axioms such as null player, symmetry, and additivity (see ( Young 1985 ) for more details and other properties), in explainability the most useful is efficiency. It demands that the sum of all players’ Shapley values is equal to the difference between \nu(N) and \nu(\emptyset) . Formally, efficiency means \sum\nolimits_{i=1}^{n}\phi_{i}=\nu(N)-\nu(\emptyset) . Or, in the game theory framework where \nu(\emptyset)=0 , one obtains \sum_{i=1}^{n}\phi_{i}=\nu(N) . In explainability, efficiency can be used to decompose a measure of interest among the set of features. As a result, one can interpret the importance of each feature to that measure. Unfortunately, satisfying the desired axioms in the form of the Shapley value comes at a price. According to Equation 1 , the calculation requires the evaluation of all 2^{n} coalitions within the exponentially growing power set of N . In fact, the exact computation of the Shapley value is known to be NP-hard ( Deng and Papadimitriou 1994 ) . Hence, its exact computation does not only become practically infeasible for growing player numbers but it is also of interest that the evaluation of only a few coalitions suffices to retrieve precise estimates. For instance, a model has to be costly re-trained and re-evaluated on a test dataset for each coalition if one is interested in the features’ impact on the generalization performance. Therefore, a common goal is to approximate all Shapley values \phi=(\phi_{1},\ldots,\phi_{n}) of a given game (N,\nu) by observing only a subset of evaluated coalitions \mathcal{M}\subseteq\mathcal{P}(N) . We denote the size of \mathcal{M} by T\in\mathbb{N} and refer to it as the available budget representing the number of samples an approximation algorithm is allowed to draw. The mean squared error (MSE) serves as a popular measure to quantify the quality of the obtained estimates \hat{\phi}=(\hat{\phi}_{1},\ldots,\hat{\phi}_{n}) and is to be minimized: \frac{1}{n}\sum\nolimits_{i=1}^{n}\mathbb{E}[(\hat{\phi}_{i}-\phi_{i})^{2}] , where the expectation is taken w.r.t. the (potential) randomness of the approximation strategy. 3.2 Interaction Indices and k -Additivity The underlying idea of measuring the impact (or share) of a single player i by means of its marginal contributions finds its natural extension to sets of players S in the Shapley interaction index ( Murofushi and Soneda 1993 ; Grabisch 1997 ) by generalizing from marginal contributions to discrete derivatives. For any S\subseteq N its Shapley interaction I(S) is given by I(S)=\sum_{A\subseteq N\backslash S}w_{A,S}\left(\sum_{A^{\prime}\subseteq S}\left(-1\right)^{\left|S\right|-|A^{\prime}|}\nu(A\cup A^{\prime})\right) (2) with weights w_{A,S}=\frac{\left(n-\left|A\right|-\left|S\right|\right)!\left|A\right|!}{\left(n-\left|S\right|+1\right)!} . For convenience, we will write I_{i}:=I(\{i\}) and I_{i,j}:=I(\{i,j\}) . Instead of individual importance, I(S) indicates the synergy between players in S . Although this interpretation is not straightforward for coalitions of three or more entities, it has a clear meaning for pairs. For two players i and j , the Shapley interaction index I_{i,j} quantifies how the presence of i impacts the marginal contributions of j and vice versa. Especially in explainable AI, where players represent features, it can be interpreted as follows: (i) if I_{i,j}<0 , there is a negative interaction (redundant effect) between features i,j ; (ii) if I_{i,j}>0 , there is a positive interaction (complementary effect) between features i,j ; (iii) if I_{i,j}=0 , there is no interaction between i,j (independence) on average. Note that the Shapley interaction index reduces to the Shapley value for a singleton, i.e., I_{i}=\phi_{i} . Moreover, there is a linear relation between the interactions and the game payoffs ( Grabisch 1997 ) . Indeed, from the interactions one may easily retrieve the game payoffs by the following expression: \nu(A)=\sum_{B\subseteq N}\gamma^{\left|B\right|}_{\left|A\cap B\right|}I(B)\,, (3) where \gamma^{\left|B\right|}_{\left|A\cap B\right|} is defined as follows with the Bernoulli numbers starting at \eta_{0}=1 : \gamma_{r}^{s}=\sum_{l=0}^{r}\binom{r}{l}\eta_{s-l}\hskip 14.22636pt\text{and}\hskip 14.22636pt\eta_{r}=-\sum_{l=0}^{r-1}\frac{\eta_{l}}{r-l+1}\binom{r}{l}\,. This linear transformation recovers any coalition value \nu(A) by using the Shapley interactions of all 2^{n} coalitions, thus including the Shapley values. Therefore, 2^{n} parameters are to be defined if the whole game is to be expressed by Shapley interactions. However, in some situations one may assume that interactions only exist for coalitions up to k many players. This assumption leads to the concept known as k -additive games. A k -additive game is such that I(S)=0 for all S with \left|S\right|>k . Obviously, this restricts the flexibility of the game but depending on k , this may significantly decrease the number of parameters to be defined such that for low k it increases only polynomially with the number of players. For instance, in 2 -additive and 3 -additive games, there are only n(n+1)/2 , and n(n^{2}+5)/6 respectively, many interactions indices as the remaining parameters are equal to zero. One may argue that within Shapley-based feature explanations, the neglect of higher order interactions, by setting them to zero per default, comes naturally. For instance, ( Bordt and von Luxburg 2023 ) show that these interactions barely exist in the context of post-hoc local explanations. 4 k -Additive Approximation Approach In this section, we present our method SVA k_{\text{ADD}} to approximate Shapley values. It builds upon the idea of adjusting a k -additive surrogate game (N,\nu_{k}) to randomly sampled and evaluated coalitions. Having fit the surrogate game to represent the observed coalition values with minimal error, its own Shapley values \phi^{k} can be interpreted as estimates \hat{\phi} for \phi of (N,\nu) since the fitting promises \nu_{k} to be close to \nu . See Figure 1 for an illustration of the approach. The framework of fitting a surrogate game encompasses other methods such as KernelSHAP ( Lundberg and Lee 2017 ) and k_{ADD} -SHAP ( Pelegrina et al. 2023a ) . See Appendix C for a conceptual comparison with our proposal. 4.1 The k -Additive Optimization Problem We leverage the representation of \nu_{k} by means of interactions as given in Equation 3 . In particular, since \nu_{k} is supposed to be k -additive, we specify \nu_{k} as a linear transformation of interactions I^{k}(B) for all B\subseteq N of size |B|\leq k , allowing us to truncate interactions of higher order than k : \nu_{k}(A)=\sum_{B\subseteq N,|B|\leq k}\gamma^{\left|B\right|}_{\left|A\cap B\right|}I^{k}(B)\,. (4) Within this representation, the Shapley values \phi^{k} of the resulting game (N,\nu_{k}) are obtained immediately by the interactions I_{i}^{k}=\phi_{i}^{k} , which will serve as estimates for the Shapley values \phi of the game (N,\nu) , i.e. I_{i}^{k}\approx\phi_{i} . The k -additive representation of \nu_{k} comes with the advantage that the number of parameters I^{k}(B) needed to define the surrogate game is reduced (as several parameters are set to zero). The drawback of this strategy is the reduction in flexibility left to model the observed game (N,\nu) according to the obtained evaluations. However, we can still model interactions for coalitions up to k players. Empirically, works in the literature ( Grabisch et al. 2002 ; Grabisch et al. 2006 ; Pelegrina et al. 2020 ; Pelegrina et al. 2023a ) have been using 2 -additive or even 3 -additive games and obtained satisfactory results for modeling interactions. Our goal is to fit \nu_{k} as closely as possible to \nu and therefore minimize the deviation of \nu_{k} from \nu captured by \sum_{A\in\mathcal{P}(N)\setminus\{\emptyset,N\}}w_{A}\left(\nu(A)-\nu_{k}(A)\right)^{2}\,, (5) where w_{A} is an importance weight associated to each coalition A . We are eager to meet the desirable efficiency axiom such that the difference between and \nu(N) and \nu(\emptyset) is decomposed among the players within our approximated values \phi^{k} . This is ensured by imposing the constraint \nu(N)-\nu(\emptyset)=\nu_{k}(N)-\nu_{k}(\emptyset) . Hence, we arrive at the following optimization problem. Definition 4.1 . Given a cooperative game (N,\nu) , a degree of k -additivity k\in\mathbb{N} with k\leq n , and weights w_{A}\in\mathbb{R} associated with each coalition A\subseteq N , the k -additive optimization problem is given by the following constrained weighted least square optimization problem: \begin{array}[]{rl}\displaystyle\min_{I^{k}}&\hskip-8.5359pt\sum\limits_{A\in\mathcal{P}(N)\setminus\left\{\emptyset,N\right\}}\hskip-2.84544ptw_{A}\left(\hskip-1.42271pt\nu(A)-\hskip-2.84544pt\sum\limits_{B\subseteq N,|B|\leq k}\hskip-2.84544pt\gamma^{\left|B\right|}_{\left|A\cap B\right|}I^{k}(B)\hskip-1.42271pt\right)^{2}\\ \text{s.t.}&\nu(N)-\nu(\emptyset)\ =\sum\limits_{B\subseteq N,|B|\leq k}\left(\gamma^{\left|B\right|}_{\left|B\right|}-\gamma^{\left|B\right|}_{0}\right)I^{k}(B)\end{array} Solving the k -additive optimization is at the core of our approach. In the remainder we describe how to overcome two key challenges. First, we address in Section 4.2 how to choose the weights w_{A} such that \phi^{k} comes close to \phi . Second, as the objective function sums up over exponential many coalitions, we present in Section 4.3 our algorithm SVA k_{\text{ADD}} that constructs an approximative objective function by sampling coalitions and adding their error terms. Figure 1: The sampled coalition values \nu(A_{1}),\ldots,\nu(A_{T}) from the game (N,\nu) are used to fit a k -additive surrogate game (N,\nu_{k}) in polynomial time w.r.t. n . The Shapley values \phi_{1}^{k},\ldots,\phi_{n}^{k} of (N,\nu_{k}) are obtained immediately from its k -additive representation. As \nu_{k} approximates \nu , these serve as estimates of the true Shapley values \phi_{1},\ldots,\phi_{n} of (N,\nu) . 4.2 Theoretical Soundness Through Choice of Weights Seeking precise estimates \phi^{k}\approx\phi , one may even raise the question if it is feasible to retrieve the exact Shapley values \phi from the solution I^{k} and how the weights w_{A} have to be set to achieve this. We analytically derive the correct weights and positively answer this question. Theorem 4.2 . The solution to the k -additive optimization problem of any cooperative game (N,\nu) for the cases of k=1 , k=2 , and k=3 with weights w_{A}^{*}=\binom{n-2}{|A|-1}^{-1} yields the Shapley value, i.e. I_{i}^{k}=\phi_{i}\,. See Appendix A for the proof of Theorem 4.2 . Note that the weights coincide with those derived by ( Charnes et al. 1988 ) used in ( Lundberg and Lee 2017 ) for a different optimization problem. The result implies that after observing all coalitions of the cooperative game (N,\nu) our approach yields the exact Shapley values with no approximation error. We interpret this as evidence for the soundness and theoretical foundation of our method. Moreover, since the result holds irregardless of the shape of \nu , the game can even highly deviate from being k -additive and our estimates will still converge to \phi . Hence, k -additivity is not an assumption that our method requires but rather a tool to be leveraged. We conjecture that Theorem 4.2 holds also true for arbitrary degrees of k -additivity and leave the proof for future work due to the analytical challenges. Worth mentioning is that the hardness of incorporating Shapley interactions of higher degree into weighted least squares optimizations has been acknowledged by ( Fumagalli et al. 2024 ) . 4.3 Approximating the k -Additive Optimization Problem via Sampling Computing the solution to the k -additive optimization problem (see Definition 4.1 ) is practically infeasible since the objective compromises exponential many error terms w.r.t. n . As a remedy we follow the same strategy as adopted in ( Lundberg and Lee 2017 ; Pelegrina et al. 2023a ) and approximate the objective function by sampling coalitions without replacement. Let \mathcal{M}=\{A_{1},\ldots,A_{T}\} be the set of sampled coalitions with A_{i}\neq A_{j} for all i\neq j and the sequence \nu_{\mathcal{M}}=(\nu(A_{1}),\ldots,\nu(A_{T})) representing its evaluated coalition values. Thus, we solve the following optimization problem after sampling: \begin{array}[]{rl}\displaystyle\min_{I^{k}}&\hskip-8.5359pt\sum\limits_{A\in\mathcal{M}\backslash\left\{\emptyset,N\right\}}w_{A}\left(\nu(A)-\sum\limits_{B\subseteq N,|B|\leq k}\gamma^{\left|B\right|}_{\left|A\cap B\right|}I^{k}(B)\right)^{2}\\ \text{s.t.}&\nu(N)-\nu(\emptyset)=\sum\limits_{B\subseteq N,|B|\leq k}\left(\gamma^{\left|B\right|}_{\left|B\right|}-\gamma^{\left|B\right|}_{0}\right)I^{k}(B)\end{array} (6) To ensure the efficiency constraint, we force the evaluation of \nu(\emptyset) and \nu(N) . Each coalition A\in\mathcal{P}(N)\setminus\{\emptyset,N\} is drawn according to an initial probability distribution p defined by p_{A}=\frac{w_{A}^{*}}{\sum\nolimits_{B\in\mathcal{P}(N)\setminus\{\emptyset,N\}}w_{B}^{*}} (see Appendix B.2 for a practical realization of the sampling). After drawing a coalition A , we set p_{A} to zero and normalize the remaining probabilities. This procedure is repeated until \left|\mathcal{M}\right|=T . Algorithm 1 presents the pseudo-code of SVA k_{\text{ADD}} . The algorithm requires the game (N,\nu) , the additivity degree k , and the budget T . It starts by evaluating \nu(\emptyset) and \nu(N) . Thereafter, based on the (normalized) distribution p , it samples T-2 coalitions from \mathcal{P}(N)\setminus\{\emptyset,N\} , evaluates each, and extends \mathcal{M} as well as \nu_{\mathcal{M}} . Finally, it solves the optimization problem in Equation 6 with weights w_{A}^{*} given by Theorem 4.2 (see Appendix B.1 for an analytical solution). The extracted Shapley values \phi^{k} of \nu_{k} are returned as estimates \hat{\phi} for the Shapley values \phi of (N,\nu) . Algorithm 1 SVA k_{\text{ADD}} 1: Input: (N,\nu) , k , T 2: \mathcal{M}\leftarrow\{\emptyset,N\} 3: \nu_{\mathcal{M}}\leftarrow(\nu(\emptyset),\nu(N)) 4: while \left|\mathcal{M}\right|k ). By assuming k -additivity, one reduces the number of parameters while keeping enough flexibility to adjust the function even with lower k ( e.g. , k=2 or k=3 ). This leads to the following optimization problem: \begin{array}[]{rl}\displaystyle\min_{I(B)\forall B\subseteq N,|B|\leq k}&\sum\limits_{A\in\mathcal{M}}\pi_{A}^{{}^{\prime}}\left(f(h(z^{A}))-\sum\limits_{\begin{subarray}{c}B\subseteq N\\ |B|\leq k\end{subarray}}\gamma^{\left|B\right|}_{\left|A\cap B\right|}I(B)\right)^{2}\,.\end{array} (29) Note that both KernelSHAP and k_{ADD} -SHAP method were conceived for local interpretability in machine learning. Surely, they can be extended to estimate global interpretability, for instance, by taking the average Shapley values over a set of local instances. Differently from these methods, in this paper, the proposed SVAk_{\text{ADD}} can be used in any problem formulated as a game-theory scenario whose Shapley values must be estimated. As in ( Pelegrina et al. 2023a ) , we also adopted the concept of k -additive games, however, we provide a general formulation to estimate the Shapley values. Moreover, we proved that by solving the proposed optimization problem \begin{array}[]{rl}\displaystyle\min_{I^{k}}&\sum\limits_{A\in\mathcal{M}}w_{A}\left(\nu(A)-\sum\limits_{\begin{subarray}{c}B\subseteq N\\ |B|\leq k\end{subarray}}\gamma^{\left|B\right|}_{\left|A\cap B\right|}I^{k}(B)\right)^{2}\,,\end{array} (30) for the cases of k=1 , k=2 , and k=3 , with weights w_{A}^{*}=\binom{n-2}{|A|-1}^{-1} , one obtains the Shapley values. Appendix D Cooperative Games Details The cooperative games used within our conducted experiments are based on explanation examples for real world data. This section completes their brief description given in Section 5 similar to ( Kolpaczki et al. 2024b ) . Across all cooperative games the players represent a fixed set of features given by a particular dataset. D.1 Global Feature Importance Seeking to quantify each feature’s individual importance to a model’s predictive performance, the value function is based on the model’s performance of a hold out test set. This necessitates to split the dataset at hand into training and test set. Features outside of an inspected coalition S are removed by retraining the model on the training set and measuring its performance on the test set. For all games we a applied train-test split of 70% to 30% and a random forest consisting of 20 trees. For classification the value function maps each coalition to the model’s resulting accuracy on the test set minus the accuracy of the mode within the data such that the empty coalition has a value of zero. For regression tasks the worth of a coalition is the reduction of the model’s mean squared error compared to the empty set which is given by the mean prediction. Again, the empty coalition has a value of zero. D.2 Local Feature Attribution Instead of assessing each feature’s contribution to the predictive performance, its influence on a model’s prediction for a fixed datapoint can also be investigated. Hence, the value function is based on the model’s predicted value in comparison to the predicted value for the empty coalition. For regression the model’s predicted value is taken and for classification the assigned class probability of the predicted class in presence of the grand coalition. Numerical features are removed by imputing their mean value and categorical features by imputing their mode. Adult Classification A sklearn gradient-boosted tree classifies whether a person’s annual salary exceeds 50,000 in the Adult ( Kohavi 1996 ) tabular dataset containing 14 features. The predicted class probability of the true class is taken as the worth of a coalition S . In order to render features outside of S absent, these are imputed by their mean value such that the datapoint is compatible to the model’s expected feature number. Image Classification A ResNet18 ( He et al. 2016 ) model is used to classify images from ImageNet ( Deng et al. 2009 ) . Since the for error tracking necessary exact computation of Shapley values is infeasible for the given number of pixels, 14 semantic segments are formed after applying SLIC ( Achanta et al. 2012 ) . These super-pixels form the player set. Given that the model predicts class c using the full image, the value function assigns to each coalition S the predicted class probability of c resulting from only including those super-pixels in S . The other super-pixels are removed by mean imputation, setting them grey. IMDB Sentiment Analysis A DistilBERT ( Sanh et al. 2019 ) transformer fine-tuned on the IMDB ( Maas et al. 2011 ) dataset predicts the sentiment of a natural language sentence between -1 and 1. The sentence is transformed into a sequence of tokens. The input sentences are restricted to sentences that result in 14 tokens being represented by players of the cooperative game. This allows to remove players in the tokenized representation of the transformer. The predicted sentiment is taken as the worth of a coalition. D.3 Unsupervised Feature Importance In contrast to the previous settings, there is no available predictive model to investigate unlabeled data. Still, each feature’s contribution to the shared information within the data can be quantified and assigned as a score. ( Balestra et al. 2022 ) proposed to view the features 1,\ldots,n as random variables X_{1},\ldots,X_{n} such that the datapoints are realizations of their joint distribution. Next, the worth of a coalition S is given by their total correlation \nu(S)=\sum\limits_{i\in S}H(X_{i})-H(S) where H(X_{i}) denotes the Shannon entropy of X_{i} and H(S) the contained random variables joint Shannon entropy. The utilized datasets are reduced in the number of features and datapoints to ease computation. The Breast cancer dataset contains 9 features and 286 datapoints. The class label indicating the diagnosis is removed. From the Big five and FIFA 21 dataset 12 random features are selected out of the first 50 and the datapoints are reduced to the first 10,000. This processing is carried out as done by ( Balestra et al. 2022 ) . Appendix E Further Empirical Results E.1 Impact of the Additivity Degree k In this section, we present the obtained results for other datasets. As mentioned in Section 5.2 , the 1-additive model has less flexibility and, therefore, its error decreases more slowly in comparison to other additivity degrees for most datasets. Looking at the existing approaches, the proposed SVA k_{\text{ADD}} appears competitive, specially with Stratified SVARM , and achieves similar performance with the KernelSHAP for the Breast Cancer dataset. (a) Diabetes ( n=10 ) (b) Diabetes ( n=10 ) (c) IMDB ( n=14 ) (d) IMDB ( n=14 ) (e) FIFA 21 ( n=12 ) (f) FIFA 21 ( n=12 ) Figure 4: MSE of SVA k_{\text{ADD}} and competing methods, averaged over 50 runs except for (c)-(f) with 10 runs, in dependence of available sample budget T . Datasets stem from various explanation types (i) global (first row), (ii) local (second row), and unsupervised (third row) with differing player numbers n . E.2 Comparison with Existing Approximation Methods Aiming at further illustrating the performance of our proposal in comparison with existing approximation methods, in this section, we extend the results presented in Section 5.3 by including another approach, called ApproShapley (given here as Permutation sampling ) ( Castro et al. 2009 ) , and our proposal for k=2 . We show this comparison in Figure 5 . Note that, with the exception of the Wine dataset, the Permutation sampling leads to the worst results. (a) Diabetes ( n=10 ) (b) Titanic ( n=11 ) (c) Wine ( n=13 ) (d) Adult ( n=14 ) (e) ImageNet ( n=14 ) (f) IMDB ( n=14 ) (g) Breast Cancer ( n=9 ) (h) Big Five ( n=12 ) (i) FIFA 21 ( n=12 ) Figure 5: MSE of SVA k_{\text{ADD}} and competing methods, averaged over 50 runs except for (d), (e), (f) and (i) with 10 runs, in dependence of available sample budget T . Datasets stem from various explanation types (i) global (first row), (ii) local (second row), and unsupervised (third row) with differing player numbers n .