Rethinking Shapley Value for Negative Interactions in Non-convex Games
Authors: Wonjoon Chang
Myeongjin Lee
Jaesik Choi
Venue: ICLR 2025 Poster (2025)
Keywords: Shapley value
Interaction
Feature Attribution
Interpretability
Primary area: interpretability and explainable AI

Abstract: We study causal interactions for payoff allocation in cooperative game theory, including quantifying feature attribution for deep learning models. Most feature attribution methods mainly stem from the criteria of the Shapley value, which assigns fair payoffs to players based on their expected contribution in a cooperative game. However, interactions between players in the game do not explicitly appear in the original formulation of the Shapley value. In this work, we reformulate the Shapley value to clarify the role of interactions and discuss implicit assumptions from a game-theoretical perspective. Our theoretical analysis demonstrates that when negative interactions exist—common in deep learning models—the efficiency axiom can lead to the undervaluation of attributions or payoffs. We suggest a new allocation rule that decomposes contributions into interactions and aggregates positive parts for non-convex games. Furthermore, we propose an approximation algorithm to reduce the cost of interaction computation which can be applied to differentiable functions such as deep learning models. Our approach mitigates counterintuitive attribution outcomes observed in existing methods, ensuring that features critical to a model’s decision receive appropriate attribution.

Published as a conference paper at ICLR 2025
RETHINKING SHAPLEY VALUE FOR NEGATIVE INTERACTIONS IN NON-CONVEX GAMES
Wonjoon Chang, Myeongjin Lee
Korea Advanced Institute of Science and Technology (KAIST) {one ji, 1m 1mjk11 ) istiistaa ac.kk
Jaesik Choi"
Korea Advanced Institute of Science and Technology (KAIST), INEEJI jaesik. shoi@kaistt kr
ABSTRACT
We study causal interactions for payoff allocation in cooperative game theory, in- cluding quantifying feature attribution for deep learning models. Most feature attribution methods mainly stem from the criteria of the Shapley value, which as- signs fair payoffs to players based on their expected contribution in cooperative game. However, interactions between players in the game do not explicitly appear in the original formulation of the Shapley value. In this work, reformulate the Shapley value to clarify the role of interactions and discuss implicit assump- tions from game-theoretical perspective. Our theoretical analysis demonstrates that when negative interactions exist-common in deep learning models-the ef- ficiency axiom can lead to the undervaluation of attributions or payoff'.. We sug- gest a new allocation rule that decomposes contributions into interactions and ag- gregates positive parts for non-convex games. Furthermore, we propose an ap- proximation algorithm to reduce the cost of interaction computation which can be applied to differentiable functions such as deep learning models. Our approach mitigates counterintuitive attribution outcomes observed in existing methods, en- suring that features critical a model's decision receive appropriate attribution.
INTRODUCTION
As black-box models like Deep Neural Networks (DNNs) become increasingly prevalent, providing the cause of their decision decision-making making process is crucial for model reliability and interpretation. One fundamental approach to understanding such prediction models is quantify the attributions of in- dividual input features to model decisions. Theoretically, feature attribution methods are usually grounded in the Shapley value (Shapley 1953), which provides a fair payoff allocation rule in coop- erative game theory. [Shapley (1953) introduced a set of axioms -linerity, dummy,, symmetry, and efficiency- that uniquely defines this payoff allocation. This axiomatic approach has been widely extended to machine learning research and attribution methods (Bach et al. 2015: Sundararajan al. 2017 Rozemberezki et al., (022).
Despite this game-the foundation, there has been limited exploration of interaction between features and the relationship with axioms in computing attributions. Causal interaction measures the discrepancy of a player's 's effect on the game output depending on whether another player par- ticipates not (VanderWeell) Weele, 2015 Keele Stevenson, (021). In complex games or functions, understanding the impact of interactions is crucial for assigning reasonable payoffs or attributions. However, the original formulation the Shapley value is based on expected contributions and does not explicitly account for interactions between players (Grabisch & Roubens 1999. Procaccia et al.) 2014 Kumar et al. 2021).
In this work, we reformulate the Shapley value in terms of interaction components to clarify its dependence on interactions. Our derivation shows that the Shapley value can interpreted as the
"Corresponding author

---

Published as a conference paper at ICLR 2025
sum of individual effect and its weighted interactions with other players. This reformulation demonstrates that the Shapley value implicitly assumes non-negative interactions, a property that holds when the game is convex. From game-theoretic perspective, this assumption aligns with the efficiency axiom and the rational behavior of players within the grand coalition (Von Neumann & Morgenstern] 1944 Roth 1988, Peters (013). Consequently, the Shapley value becomes reason- able and well-defined allocation when a game is convex, and we prove that convexity is equivalent non-negative interactions.
However, many real-world scenarios involve non-convex games, where negative interactions exist. In such cases, the Shapley value may not be reasonable allocation derived from players' efficient and rational behaviors. Most axiomatic approaches for feature attribution, including extensions of the Shapley value, conventionally adhere to the efficiency axiom, even though many black-box mod- els like DNNs do not satisfy the convexity. Enforcing the efficiency axiom for non-convex games leads to the undervaluation of payoffs caused by negative interactions even though the players have a potential role in improving the output. In the case study, we present illustrative examples demonstrat- ing their impact on non-convex functions, such as a max function and a sigmoid function, and their connection to deep learning models. Negative interactions can result in the undervaluation of attri- butions, where highly relevant features receive low attribution scores. We discuss that these negative interactions between players arise from role redundancy or output saturation in cooperative game tups. Conventional approaches attempt to mitigate this by applying heuristic post-pree post-processing, such as taking the absolute value of attributions, but these solutions lack theoretical justification.
Building on our theoretical analysis of interaction, we extend the Shapley value to non-convex games while keeping its philosophy that assigns payoff's by measuring synergistic interactions between players. We propose a new allocation rule that decomposes each contribution into interactions and aggregates the refined interactions for non-convex games. Aggregated Positive Interactions (API), which aggregates only positive interactions, effectively resolves the undervaluation issue and ensures that crucial features receive sufficiently large attributions in non-convex games while following the Shapley value properties in convex games. Furthermore, we provide unbiased estimation of API using a permutation sampling approach and introduce an approximation algorithm that can be applied to differentiable functions, making it computationally tractable. In practice, approach successfully addresses the undervaluation issue deep learning tasks.
PRELIMINARIES
2.1 COOPERATIVE GAME
cooperative game consists of a set of players == (1, (1.....,,) called the grand coalition, and a characteristic function : 2N IR, which maps coalition S C N to the utility v(S) players in S achieve. The goal is to determine the payoff vector d(v) E IR" where i-th element o; (v) indicates the payoff allocated to player from the total utility v(N). This game is sometimes called transferable utility game allowing the utility to be fully transferred to the players as their payoffs (Von Neumann & Morgenstern] 1944, Roth 1988 Peters, 2015). In classic literature, for convenience, the function itself is often referred to as the game, and the cardinality of each set of players (N, S, S......) is denoted by the corresponding lower-case letter s.,.,.....) We follow this convention this work.
A game is convex if
(SS + + ((UT AS T N.
Equation I holds under the more relaxed condition Sn7 0, then the game is super-additive. This indicates that convex game is special case of super-additive game.
Remark. The implicit assumption in cooperative game is that players strategically form the grand coalition to maximize their payoffs (Roth 1988 Fujimoto et al. 2006 Peters 2015). Convex games indicate that the benefits of joining coalition increase the coalition size grows, ensuring that cooperation always leads to higher utility and that forming the grand coalition N is an optimal stralegy (Shapley 1971).
2

---

Published as a conference paper at ICLR 2025
2.2 SHAPLEY VALUE
The Shapley value Shapley 1953) is the payoff vector <(v) E IR" that fairly distributes the total utility v(N) to each player E N:
6.(1) E
-1 (
1 n 8
(i)s
(2)
SENMO
It is a unique form that satisfies four axioms designed for fair allocation: linearity, dunmy, sym- metry, and efficiency (Weber 1988). The detailed explanations of the axioms are provided in Ap- pendix A Equation 22 can be interpreted as the weighted average of i's contribution when join- ing all possible coalitions. Furthermore, can be viewed as the expectation of the causal effects on the function output since it evaluates the expected output increase while putting or removing player (Janzing et al., 2020. Pearl 2022). From this perspective, A;r(S) = v(S {+]) - v(S) is referred to as (causal) effect or (marginal) contribution.
alternative formulation of the Shapley value is represented as the expected contribution over all possible random orderings. Let II(NV denote the set of all permutations of the player set N. For a given æ E [I(N), ). define x' as the set of players preceding player i in the ordering x. Then, the Shapley value be expressed as follows:
dc(v)
1
Σ TEI(NN)
(v(#² U -()))
(3)
2.3 EFFICIENCY IN COOPERATIVE GAMES
The Shapley value is a well-defined solution that belongs to the core (Shapley 1971 Dehez 2017 The core of game is set of payoff vectors E IR" that satisfy the following two conditions:
{a E T -a= v(N), Σa 2a VS
The core represents the socially stable outcomes where no partial coalition can achieve a better result than the grand coalition. The first equality condition states that the sum of individual payoffs should equal the total utility v(N). This equality condition is the same the efficiency axiom of the Shapley value. The second inequality condition, namely the coalitional rationality, implies that the sum of payoff' allocated to any subset coalition is least large as the utility vSS) the coalition S can achieve on its own.
The concept of efficiency originates from Pareto efficiency, which states that player's payoff can be improved without reducing another player's payoff (Peleg & Sudhölter 2007 Peters 2015). This implicitly assumes that all players prefer to maintain cooperation through their rational behaviors. In this background, it is natural to consider rationality, which is linked to the core, when impos- ing efficiency for payoff allocation in cooperative games. Notably, the Shapley value solution positioned at the center of the core when the core exists (Shapley 1971.
3 INTERACTIONS IN SHAPLEY VALUE
The Shapley value assesses player's payoff based on the average causal effect across all possible coalitions. However, when effects vary significantly depending on the context, the resulting payoff allocation may be distorted. This study highlights the impact of interactions inherently captured in computing the Shapley value and argues that its underlying assumptions may not be suitable for games with complex interactions.
3.1 REFORMULATION OF SHAPLEY VALUE
We first define interaction between two players in the cooperative game.
Definition (interaction). For cooperative game on a player set N, an interaction between two player i.j E N given subset of players T Ç N {i,j} is defined as follows:
(T) v(T (i.i)) o {i)) - vT +
(5)
= (T - (.)(7)
3

---

Published as a conference paper at ICLR 2025
This definition comes from the notion of causal interaction in the causal inference literature (Van-) derWeele, 2015; Keele & Stevenson, 2021). It quantifies the discrepancy of player i's effect on whether player participates not. In the absence of interactions among players, each player's s effect remains constant regardless of others' participation, making payoff allo- cation trivial. However, cooperative games typically assume synergistic interactions, where players cooperate to maximize their payoff's.
the output depending
Despite this, the original formulation of the Shapley value provides limited insight into how such interactions influence payoff allocation. To address this limitation, we reformulate the Shapley value explicitly incorporate interaction terms, leading to the following representation.
Theorem 1. The Shapley value is a weighted sum of interactions:
(
z-2
6,(0) = (0) +
+Σ
Σ (T(
(6)
TCMML)
JZ1 1T|=
Proof. See Appendix.
The theorem states that the Shapley value measures the sum of the individual effect and the average interactions resulting from cooperation.
3.2 RELATIONSHIP WITH CONVEXITY
In Section 2.1
introduce the concept of convex game, where the benefits of cooperation in- crease as the coalition size grows. The connection between convexity and interactions can be re- vealed from the following theorem, which states game is convex if and only if all interactions are non-negative.
Theorem 2. A game v is convex if and only Lg 2 O Vi,j E V (i.j).
Proof. See Appendix.
guarantees the existence of the core and ensures that it forms a polytope in the solution space, with its vertices corresponding to the marginal contribution vectors (Shapley 1971 Ichiishi Dehez, 2017). For given permutation
Convexity closely related the core described in Section
2.3
II(N), the marginal contribution vector is an n2-dimensional vector, where the i-th element is given by v(TT' U (i)) v(z') with Æ' representing the of players preceding player i in the ordering The alternative formulation in Equation (3) shows that the Shapley value is obtained as the average of these marginal contribution vectors. Theorem fooloows from decomposing marginal contributions into the sum of cumulative interactions (Appendix C.I). Therefore, in convex games, positive interactions arising from player cooperation enhance marginal contributions, leading to increasing the Shapley value.
3.3 PROBLEMS IN NON-CONVEX GAMES
Non-convex games imply the existence of negative interactions between players. In such cases, the core does not encompass all marginal contribution vectors, indicating that some marginal contribu- tions arise from non-rational behaviors. As result, players' payoffs can be underestimated, even when they have the potential to enhance the overall outcome. This raises the question of whether the Shapley value remains an appropriate allocation rule in non-convex settings. The efficiency (or completeness) axiom is conventionally applied in the applications of the Shapley value and attribu- tion methods for black-box models (Lundberg 2017 Sundararajan et al. 2017). This axiom ensures that the solution, including the Shapley value, is expressed as expectation of marginal contribu- tion vectors (Weber 1988). Enforcing the efficiency axiom for non-convex games can lead to the undervaluation of payoffs feature attributions caused by negative interactions even though the players have a potential role in improving the output. We can identify the issue of undervaluation that negative interactions explicitly diminish player's payoff in Equation (
4

---

Published as a conference paper at ICLR 2025
Negative interactions between players arise from various factors, such as personal emotional conflicts. However, in cooperative games, where the primary assumption is that players collabo- rate to maximize total utility and individual payoffs,, it is more reasonable to attribute such negative interactions to functional role redundancy. This concept extends to feature attribution in machine learning. Black-box models typically leverage all available features- make decisions without regard for their conflicts. However, high-capacity models like DNNs usually exhibit non-convexity, leading negative interactions among features. This has been linked to un- expected experimental results in Shapley-based feature attribution methods, where features crucial for secision-making may receive low attribution scores. To mitigate this, conventional approaches often apply heuristic post-processing adjustments, such as taking the absolute value of attributions.
a grand coalition- to
To better understand the implications of negative interactions, Section 4 presents illustrative exam- ples demonstrating their impact on non-convex functions, including deep learning models. Section 5 then introduces a principled game-theoretic approach address these challenges.
4
CASE STUDY
In this section, we will explore examples of non-convex games where negative interactions occur. The problem emerges when the grand coalition is no longer driven by rational behavior. If the grand coalition is inefficient-mcaning that some players can contribute significantly to the outcome but are not essential for maximizing the final output-they may experience negative interactions. In cooperative games, negative interactions between players can happen due to their role redundancy or output saturation rather than their personal conflicts, which we illustrate through examples such as a max function and sigmoid function. Furthermore, we discuss how negative interactions naturally arise in deep learning models that incorporate these functions.
Max function. The max function returns the highest value that the participating players can yield. A player's 's causal effect the max function output diminishes when another player with similar contribution joins. In this case, interaction becomes negative, and indeed the max function is non- convex. Furthermore, consider the following function
f(r1,-.- .s) max( (11, .2, Ir 4x4) + max(625, 6.r. 6X,,, 7
We set each variable x, to be binary (0 or 1) to represent the participation keeping the setup of cooperative game theory. We can generally expect that player may get a larger payoff than player 4. However, there are negative interactions in this function, for example, [1)( = - Iss -6, which lead to counterintuitive results. The Shapley value of player is 10/4 while that of player is 13/4. This phenomenon conceptually arises from redundancy in the roles of individual players. Even if some player has a large impact on the outcome, their interactions become negative when their roles overlap, leading to underrated payoffs. In Appendix D this issue is intuitively described in an image recognition scenario.
Sigmoid function. Another example of a non-convex function that yields problematic negative interactions is the sigmoid function that takes the sum of features as input. There exist negative interactions when the input becomes sufficiently large, pushing the function into its near-saturation region. Consider the following function
f Z2, F3, xT) = 10 (7x; + 6IZ) + 10 [223 + 0.1x4)
where denotes the sigmoid function 1/(1 + e-"). Similar to the max function case, players 1 and 2 exhibit a stronger negative interaction (4)2(0) (0z)(0) -0.15). Consequently, player I's Shapley value (2.51) is lower than player 3's (3.73). This phenomenon arises due to the presence of saturation. More generally, this issue extends to any squashing function with saturation or upper-bound, such as the softmax function.
-4.6) compared to players 3 and
Deep Learning model. A deep learning model a non-convex function, incorporating various non-convex components within its architecture. Consider max pooling in Convolutional Neural Net- works (CNNs) and attention mechanisms in Transformer models. CNN classifiers commonly utilize the max pooling fundamental operation and attention mechanisms in Transformers compute a weighted sum of values, where the weights are derived from the softmax scores of query-key similarities (Vaswani et al. 2017). Given these structural properties, similar issues arising from
5

---

Published as a conference paper at ICLR 2025
non-convexity can be expected in CNNs and Transformers. In Figures 1 and 3 show the counter- intuitive results of the Shapley value in such models, highlighting the impact of negative interactions on feature attributions.
AGGREGATED POSITIVE INTERACTIONS
We have discussed the issue of utilizing the Shapley value and its variants for non-convex games. To address this, we propose generalized solution that decomposes each contribution into interactions and aggregates them using refinement function RR R:
n )
(i(1) = (.) +
Σ JEN TEN) jup
E
(()((T))
=t
The function g represents how interactions are interpreted attributions to the output. When g an identity function, interactions are directly used as attributions in the calculation, regardless of their magnitude or sign, resulting the Shapley value.
To alleviate the undervaluation in non non-convex games, we suggest a solution with g(x) = max(æ, (z, 0), namely Aggregated Positive Interactions (API). It can be interpreted as the extension of the Shapley value to non-convex games. In convex games, API equals the Shapley value, as all interactions are preserved. non-convex games, API evaluates a player's potential contribution to improving the output by forming synergistic coalitions by filtering out problematic negative interactions. Since negative interactions are removed in aggregation, player's payoff is no longer underrated from irrational coalitions. API effectively addresses the undervaluation demonstrated in Section 4 For the max function case, API assigns values of 7 and to players 8 and 4, respectively, and for the sigmoid function case, it assigns values of 4.99 and 3.81 to players I and 3, respectively.
Axioms. non-convex games, a solution does not need to strictly adhere to the efficiency axiom due to the issues described in Sections 3.3 and 4 Enforcing efficiency ensures that the total sum of attributions remains fixed, which inevitably leads to lower attributions for some players. In this spirit, API relaxes the efficiency axiom in non-convex games to prevent undervaluation caused by negative interactions. The dummy axiom states that if a player has no causal effect on the function output then the corresponding attribution should be zero. Any solution based aggregated interactions with g 0 satisfies the dummy axiom. We further discuss the converse of this axiom: does zero attribution imply that the corresponding player has no meaningful contribution improving the output? In the Shapley value and its variants, which follow the form of expected contribution, players in non-convex games may receive zero attribution due to negative interactions canceling out their positive contributions. This can result in undervaluation, even when player has a potential role in improving the output. In contrast, API ensures that zero attribution genuinely reflects a player's inability enhance the output (strictly speaking, in O-normalized games). Consequently, players with higher attributions in API are those who significantly contribute to improving the output.
The choice of 9 depends how the user interprets interactions attributions in given task. In Appendix E.2 we additionally provide attribution results using different choices of g. specifically Leaky ReLU and Softplus. The solutions derived from these functions do not follow all the prop- erties that API upholds. However, in scenarios where a decrease in the function output carries meaningful implications, such as in regression problems, strietly eliminating all negative interac- tions could misrepresent the influence of certain variables, and they should be carefully handled. Therefore, the treatment of negative interactions should be determined based on the context of the application. Especially, API focuses on solving the undervaluation problems derived from role re- dundancy or output saturation described in Section 4 by removing unexpected negative interactions and preserving positive ones.
5.1 ESTIMATION THROUGH PERMUTATION SAMPLING
Since dealing with interaction terms requires high computational cost for applying complex black-
box models like DNNs, we first propose the estimation of Equations (6) and (7). Then, introduce
an approximation algorithm to reduce the computational cost for interaction terms using gradient information.

---

Published as a conference paper at ICLR 2025
We reformulate Equation 66 into the expectation form to enable sample estimation with vectorized representations. Let ~ (S) be the uniform distribution of player from set S, and uz S) be the uniform distribution of subset S with cardinality [T' t. Φ(t) and Ae(O) denote the Shapley value and the marginal contributions of all players at the empty set in a vector form, respectively. We define interaction vector (T) R where the i-th element is I (T) for given T N {j)- We set (T') = O when i = j or i E T, then (T") is well-defined for any I PCNN {j). Then, obtain the following vectorized form estimate the Shapley value with interaction vectors.
Theorem 3. The payoff vector of the Shapley value Φ(v) is represented as follows:
n-
Φlv) = Av(0)
(8)
Proof. See Appendix.
We can now apply an unbiased sample estimation for the expected interaction at each cardinality and sum over interactions. This estimation can be also conducted by permutation sampling. For each permutation, we sequentially add features, and compute interactions at each level of cardinality. In this setup, we need to reformulate Equation with the expectation under the uniform distribution of permutations.
Corollary 1. The payoff vector of the Shapley value @(v) is represented as follows:
Φ(v) = Av((0)
B ([T]e]]
where II(N) is collection of all possible permutations of players in N. represents the t-th element n,, and [r] represents the subset of players up to the 1-th player the ordering m.
It can be easily proved by Theorem From the result, we can apply permutation sampling to estimate the Shapley value with interactions. It can be interpreted as the extension permutation sampling the original Shapley value (Castro al. 2009). Simply, we obtain Aggregated Positive Interactions by maintaining only non-negative interactions during sampling.
5.2 APPROXIMATION ALGORITHM
The major computational burden comes from the interaction terms. Since the computational cost for interactions grows with the number of player combinations, it requires n-times more computations compared computing individual effects in the original Shapley value. We propose an algorithm to reduce the cost of interaction computation that can be applied to differentiable functions. In dif- ferentiable functions like DNNs, this approach leverages backpropagation reduce computational complexity effectively.
Notations. We first explain notations for our algorithm described Algorithm [ tiable function to assess attributions, such as deep learning predictor. is a target instance with features, and each feature is treated as player N. baseline value refers to the value assigned when feature does not participate in the game, and it is typically set to the mean value from the data or zero. Vv(S) denotes a gradient of u evaluated when features in S are set to values in and the others are set to values in T.
differen-
The original definition of interaction expressed as the difference between two contributions, rep- resented by discrete derivatives. We replace this discrete derivative with partial derivative using a first-order Taylor approximation. This allows us to compute interactions quickly by leveraging gradients obtained through backpropagation.
(T) (T (i)) A,(TT (
(x; (x,- 2.)
(10)
When calculating interactions for all features given set T", the original computation requires O(n²)
forward passes. However, with this approximation, all feature gradients can be computed simul- taneously with single backpropagation, reducing the computation to O(n) backward passes. By utilizing this approximation and permutation sampling, our algorithm computes API as described in Algorithm The practical runtime of our algorithms is further discussed in Appendix E.3
7

---

Published as a conference paper at ICLR 2025
Algorithm Approximation for Aggregated Positive Interactions
Input: Differentiable function v, Instance æ, Baseline Parameter: # of permutations k
Output: Attribution
Initialize Cnt < 0, Φ < Av(H), 91 + Vv(0)
while Cnt. < do
sample
Uni((TI(N))
for / = 0, D.... . do
92 - Vu([=]++1)
I max((g2 gi) (a B),
vi (T)e11
- + i/k:
91 92
Cut + Cut +
end for end while return
EVALUATION
In Section we introduced some simple non-convex examples to identify the impact of negative interactions on the Shapley value. this section, we identify such phenomenon in practical deep learning tasks and evaluate the results from Aggregated Positive Interactions (API). Our experiments are conducted on image classifiers (VGG19 (Simonyan & Zisserman, 2014), ResNet50 (He et al., 20166) trained on the ImageNet dataset (Deng et al. 20099,, and sentence classifier (BERT (Devlin 2018)) trained on the IMDB Review dataset (Maas et al. 2011]. In experimental results, Approxi- mated Shapley value (abbreviated Approx. SV) denotes the approximation of the Shapley value by sampling permutation and aggregating all interactions. We samples 100 permutations for the image classifiers and 300 permutations for the sentence classifier. In the case of ImageNet data, we convert images into 20 x 20 patches for feasible computation.
6.1 IMPACT OF POSITIVE INTERACTIONS ON IMAGE CLASSIFIER
We analyze the impact of positive interactions on VGG19. Figure D shows attribution results, pre- senting high-attribution regions, and low-attribution regions when aggregating all interactions versus only positive interactions. In the attribution map, red indicates positive attribution, white represents zero attribution, and blue denotes negative attribution.
When all interactions aggregated, attributions tend become more dispersed. This dispersion can be explained by negative interactions, as seen in max pooling, where nearby inputs are grouped together, creating negative interactions within the same pooling operator, The Shapley value strug- gles to pinpoint key contributing areas to the model decision. However, when we aggregate only positive interactions, key regions become more distinct, such the eyes, nose, and front paws of red panda or the wheels and windows of a sports car.
6.2 UNDERRATED ATTRIBUTIONS FROM EFFICIENCY AXIOM
To demonstrate the limitations of methods based on the efficiency axiom in non-convex games, we compare our approach to relevant attribution methods using ResNet50 in Figure For Ker- nelSHAP (Lundbergg 2017). we use 40,000 samples, as our method approximates using 100 permu- tations across 400 features. Integrated Gradients (IG) (Sundararajan et al. 2017) is computed with 100 steps, and the attributions are summed for all pixels within each patch. We evaluate performance using the Insertion and Deletion metrics. Insertion measures the logit value when the top 30% at- tribution patches are removed. Higher values for both metrics indicate better identification regions crucial for the model's 's decision.
added, while Deletion measures it when the bottom 30% attribution patches
8

---

Published as a conference paper at ICLR 2025
red ponda
violin
sport Car
Approemetec Shailey value
Aggregated Positve Interactions
Approximated Shapley value
Aggregated Postivee Interaciions
Approxiaatd Shapley value
Aggregated Postivve Interactions
Atribusiio Map
Relevant Parts
(log
Imclovant Parcs (bottom 50%
Figure I: Aggregated Positive Interactions on the ImageNet dataset. While the approximated Shap- ley Value produces dispersed attributions across relevant regions, API more effectively captures these regions.
bighorn sheep
KemnelSHAP
IG
Approx. SV
API
12
KerneiSHAP
1G
Approx SV
API
fountain pon
por
mhat
CEMOMA
KernelSHP
Approx.
crayfish
12
Insertion Deletion
KernelSHAP
Approx.
Figure 2: Comparison to other Attribution methods based on Efficiency axiom. Insertion measures the logit value when the top 30% attribution patches are added, while Deletion measures it with the bottom 30% removed. API achieves better results compared to the previous methods.
KernelSHAP and IG, constrained by the efficiency axiom, tend to disperse attributions across various regions, similar to the Approximated Shapley value. In contrast, API focuses attributions on key input features, avoiding unnecessary assignments to the background. In practice, absolute attribution values are often used heuristically for better interpretability. API addresses this issue with a more principled, game-the theoreetccreiccccc approach. While KemelSHAP sometimes performs better numerically, it still suffers from attribution dispersion irrelevant regions. This may stem from errors introduced by the first-order Taylor approximation used in API for interaction computation.

---

Published as a conference paper at ICLR 2025
For additional quantitative results, assess effective complexity (guyye & Martinez 2020 in Appendix E.1 A low effective complexity indicates that the attribution provides a more compact explanation by focusing smaller number of significant features. On average, API achieves 30% lower complexity than the other methods.
6.3 APPLICATION ON LANGUAGE MODEL
We demonstrate the application of API on language model, using a BERT (Devlin 2018 trained on the IMDB dataset for sentence prediction (Maas et al. (001)) This model takes movie review which is a sequence of tokens, and predicts whether is positive or negative. Figure shows a frac- tion of input texts where the top row is predicted as negative, while the bottom row is positive. For these texts, we compare the approximated Shapley value and API, estimated with 300 permutations, by highlighting the tokens with attribution in the top 20%.
In the negative review case, the approximated Shapley value only highlights 'hardly be" while API focuses the entire phrase 'can hardly be taken seriously any level'. This indicates that the portion from 'taken' to 'level' was underrated due to strong negative interactions. While 'hardly be' alone does not intuitively seem influential for the negative prediction, it conveys negative meaning when combined with the subsequent tokens from 'taken' to 'level'. These tokens have strong nega- tive interactions that obscure their contributions, which API correctly addresses by focusing the key phrase. A similar issue arises in the positive review case in the bottom row, where the Shapley value underrates tokens 'i', 'liked', and 'movic', while assigning higher attributions to other irrele- vant tokens. API effectively resolves this by properly attributing the entire phrase "i really liked this movie'.
Approximated Shapley value
Aggregated Positive Interactions
Negative Review
it doesn' | matter what one' political views are because this Dim can hardly be taken seriously on any Jevel.
doesn matter what one' political
views are because this film car hardly
taken seriously on any leve
really liked this movie. 1' ve read few of The other comments, and although pity those who did not understand ido agree with some of the criticisms.
really liked this movie. read few of
Positive Review
the other comments, and although pity
those who did not understand it, do agree with some the criticisms.
Figure 3: Application on a Language Model. While the approximated Shapley value assigns low attributions to the tokens that seem relevant due the negative interactions, API effectively results in more reasonable attributions by focusing only on the positive interactions.
7 CONCLUSION
This study has explored the impact of causal interactions payoff allocation in cooperative game theory, with a particular focus on feature attribution deep learning models. We reformulate the Shapley value to account for interactions between players, and demonstrate that these interactions explicitly influence payoff's in the Shapley value framework. From the game-theoretic perspective, highlight that this framework implicitly assumes players' rational and efficient behaviors to im- prove the total utility, which may conflict with the presence of negative interactions in non-convex games. such games, the efficiency axiom of the Shapley value can unintentionally lead to the undervaluation of payoffs or attributions. To extend the Shapley value to non-convex games while preserving its underlying philosophy, we propose a new allocation rule, namely Aggregated Pos- itive Interactions (API), which decomposes contributions into interactions and aggregates positive ones. Additionally, we introduce an approximation algorithm to enhance computational tractability in interaction computation for differentiable functions. Our experimental results show that API ef- fectively resolves the counterintuitive results of the Shapley value and feature attribution methods based the efficiency axiom. We expect that work will serve solid foundation for tending name-theoreee approaches to the attribution task, contributing to the interpretability of deep learning models.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by Hyundai Motor Company, which provided valuable guidance on the re- search direction, and by Institute for Information & communications Technology Planning & Eval- uation (IIP)) grant funded by the Korea government (MSIT) (No. RS-2019-11100075, Artificial Intelligence Graduate School Program (KAIST); No. RS-2022-11220982 Development of Artificial Intelligence Technology for Personalized Plug-and-Play Explanation and Verification Explana- tion; No. RS-2024-00457882, AI Research Hub Project).
REFERENCES
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Houus-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e01 301400 40, 2015.
John Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev, 19: 317. 1964.
Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. Computers & operations research, 36(5): 2009.
Pierre Dehez. On harsanyi dividends and usymmetric values. International Game Theory Review, 19503)) 750012, 2017.
Huiqi Deng, Qihan Ren, Hao Zhang, and Quanshi Zhang. Discovering and explaining the represen- tation bottleneck dnns. arXiv preprint arXiv:2111.062580 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 1810.04805 2018.
Katsushige Fujimoto, Ivan Kojadinovic, and Jean-Lue Marichal. Axiomatic characterizations of probabilistic and probabii-cooaaallittiic interaction indices. Games and Economic Behavior, 55 (1):72-99, 2006.
Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Ham- mer. Shap-iq: Unified approximation of any-order shapley interactions. Advances in Neural Information Processing Systems, 36, 2024.
Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of game theory, 28:547-565, 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pailern recognition, pp- 770-778, 2016.
Tatsuro Ichiishi. Super-modularity: applications convex games and the greedy algorithm for 1p. Journal of Economic Theory, 25(2):283-286, 1981.
Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in ex- plainable ai: A causal problem. In International Conference artificial intelligence and statis- fics, pp. 2907-2916. PMLR, 2020.
Giyoung Jeon, Haedong Jeong, and Jacsik Choi. Beyond single path integrated gradients for reliable input attribution via randomized path sampling. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pp. 2052-2061, 2023.
Andrei Kapishnikov, Subhashini Venugopalan, Besim Avci, Ben Wedin, Michael Temry and Tolga Bolukbasi. Guided integrated gradients: An adaptive path method for removing noise. In Proceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 5050-5058, 2021.
11

---

Published as a conference paper at ICLR 2025
Luke Keele and Randolph T Stevenson. Causal interaction and effect modification: same model, different concepts. Political Science Research and Methods, 93)::441-449 649, 2021.
Indra Kumar, Carlos Scheidegger, Suresh Yenkatasubramanian, and Sorelle Friedler. Shapley resid- uals: 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.
Mingjie Li and Quanshi Zhang. Does neural network really encode symbolic concepts? In International conference on machine learning, pp. 20452-20469. PMLR, 2023.
Scott Lundberg. A unified approach to interpreting model predictions. arXiv preprint
1xXiv:7005.08874. 2017.
Andrew Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Y Ng, and Christopher Potts.
Learning word vectors for sentiment analysis. In Proceedings of the 49th amnual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Dov Monderer and Dov Samet. Variations on the shapley value. Handbook of game theory with economic applications, 3:2055-2077 2002.
Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojeiech Samek, and Klaus-Robert Müller. Explaining nonlinear classification decisions with deep taylor decomposition. Pattern recognition, 65:211-221 2017.
Woo-Jeoung Nam, Shir Gur, Jaesik Choi, Lior Wolf, and Seong-Whan Lee. Relative attributing propagation: Interpreting the comparative contributions of individual units in deep neural net- works. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 2501- 2508, 2020.
An-phi Nguyen and María Rodríguez Martínez. On quantitative aspects of model interpretability. arXiv preprini arXiv:2007.07555 2020.
Judea Pearl. Direct and indirect effects. In Probabilistic and causal inference: the works of Judea Pearl, pp. 373-392. 2022.
Bezalel Peleg and Peter Sudhölter. Introduction to the theory of cooperative games, volume 34. Springer Science Business Media, 2007.
Hans Peters. Game theory: Multi-leveled approach. Springer. 2015.
Ariel Procaccia, Nisarg Shah, and Max Tucker. On the structure of synergies in cooperative games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Jie Ren, Mingjie Li, Qirui Chen, Huiqi Deng, and Quanshi Zhang. Defining and quantifying the emergence of sparse concepts in dnns. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 20280-20289, 2023.
Alvin E Roth. Introduction to the shapley value. The Shapley value, 1, 1988.
Benedek Rozemberczki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Olivér Kiss. Sebastian Nils- son, and Rik Sarkar. The shapley value in machine learning. In Lud De Raedt (ed.), Proceed- ingy of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 3572-5579 International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10.24963/ijcai.222 2022//77 URL httpp:://di...o http://...oogo.////oooooo 10. 24963/ 20222 Sur- vey Track.
M Scott, Lee Su-In, et al. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30:4765-4774 2017.
Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2, 1953.
Lloyd S Shapley. Cores of convex games. International journal of game theory, 1:11-26, 1971.
12

---

Published as a conference paper at ICLR 2025
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. International conference on machine learning, pp. 3145- 3153. PMIR, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1eXxvv:400.15355 1556, 2014.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In Inter- national conference on machine learning, pp. 9269-9278 PMLR, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference machine learning, pp. 3319-3328. PMLR, 2017.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International conference on machine learning, pp. 9259-9268. PMLR, 2020.
Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley interac- tion index. Journal of Machine Learning Reseurch, 24(94))1-42, 2023.
TJ VanderWeele. Explanation in causal inference: methods for mediation and interaction. Oxford University Press, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you (npss, 2017. arXiv preprint arXiv:1706.03760 03762, 10:501405255160018777 2017.
J Von Neumann and O Morgenstern. Theory of games and economic behavior Princeton University Press, 1944.
Robert J Weber. Probabilistic values for games. The Shapley Value. Essays in Honor of Lloyd S. Shapley, pp. 101-119, 1988.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
A AXIOMS FOR SHAPLEY VALUE
The Shapley value Shapley 1953) the payoff vector (bv) E IR that fairly distributes the total utility v(N) to each player i E N:
Σ | ("-1)) (i))
(1(1)
(11)
8
SCNMA
is a unique form that satisfies four axioms designed for a fair allocation:
efficiency, synmetrry
linearity, and dummy (Weber 1988: Peleg & Sudhölter 2007 Dehez 2017 2022).
Rozemberczki al.
Efficiency. The sum of all payoffs equals the total utility of the grand coalition:
Σ (
(12)
VEN
It is often called Pareto efficiency (or Pareto optimality), which assumes that players behave effi ciently: no partition of players can achieve a larger total utility than the grand coalition. Under this assumption, the grand coalition results from the players' optimal strategies. Therefore, it is reasonable to directly allocate the utility of the grand coalition to the players' payoffs.
Symmetry. Two players and j are symmetric (()) o(S for every $ CCNN(
If two players i and j are symmetric, their payoffs should be equal:
(x(v) (v( if i,j are symmetric.
(13)
The symmetry property ensures that players with identical contributions to the utility receive the same payoff.
Linearity. For any two games (N, v), (N, w) and a real number a, the payoff' vector holds that $(v + w) (vv) + ((w), x(av) = aι(v).
(14)
(15)
The first property is often called additivity. It scems reasonable that for the rescaled game av the allocation rule simply rescales a player's 's original payoff with the same amount.
Dummy. A player is dummy (or null) in if uSS U {i)) v(S) for every S C N (i). if dummy player, the payoff of should be zero:
(v( 0 if a dummy player.
It is natural to assign a zero payoff to player who does not affect the total utility in any situation.
B RELATED WORK
Shapley Value. The payoff allocation for the utility function has been studied with axiomatic ap- proaches in cooperative game theory literature (Roth) 1988 Fujimoto al. 2006 Peters 2015). The Shapley value (Shapley 1953) is the payoff al allocation that uniquely satisfies the lineardy, dummy, symmetry, and efficiency axioms (Weber, 1988). It can also be interpreted as the expectation of the causal effects since the contribution of a player is measured by do-operator (Janzing et al. 2020) Pearl 2022 Due to the well-defined axioms of the Shapley value, there have been a lot of ap- proaches to apply the Shapley value to deep learning literature, especially for measuring feature attribution (Scott et al. 2017 Sundararajan & Najmi 2020 Rozemberczki et al. (022). Despite the widespread use of the Shapley value, some studies have identified problems with the axioms it relies on. Kumar et al. highlighted the limitation of the Shapley value when the game is not inessen- tial and proposed Shapley Residuals to quantify the lost information when using the Shapley value. Kwon & Zou raised the inappropriateness of the efficiency axiom, pointing out the information gap depending the size of the feature sets.
14

---

Published as a conference paper at ICLR 2025
Game-theoretic Interaction. The concept of interaction firstly proposed to deal with the infor- mation cooperation existing among players (Grabisch Roubens 1999). which cannot be taken into account by the Shapley value (Shapley [953) and its variants (Banzhaf III. 1964. Monderer & Samet 2002). Since the natural extensions of the axioms of the Shapley value do not guarantee the uniqueness of interaction indices, previous studies have introduced additional axioms (Grabischi & Roubens 1999; Sundararajan et al. 20200] Tsai et al.) 2023). Fumagalli et al. proposed a gen- eral form of these interaction indices and efficient sampling-based estimator SHAP-IQ. Some approaches have attempted to explain the underlying reasoning of the inference of DNNs through
the game-theoretic interactions (Deng et al. 2021 Ren et al. 2023 Li & Zhang 2023).
Attribution Methods. Attribution methods aim to measure the contributions of input features to the model output. While LRP-based methods sequentially redistribute the model output across the layers in reverse order (Bach et al., 2015 Montavon et al. 2017; (Shriumar et al.] 2017 Nam et al.) 2020), IG and variants evaluate attributions by aggregating gradients along one or more paths in the input space (Sundararajan et al. 2017 Kapishnikov et al. [2021 Jeon et al. 2023). Additive feature attribution methods unity several existing methods, with SHAP uniquely satistying Shapley- based axioms (Lundberg 2017). These methods typically impose the efficiency axiom, requiring
attributions to sum to the model output.
C PROOF
For convenience, we represent the cardinality of S, as n, s,t, respectively. II) denotes the set of all permutations of the player set S. Given II(S) and e S, xf is the set of players preceding player in the ordering æ. [π] denotes the subset of players up to the k-th player in the ordering where [x]a- = 0 and [x]s == S.
C.1
PROOF OF THEOREM 1
Lemma 1. Given a player and S C N (i), for any permutation т E II(S) and k E {1, {1,
Σ T. (())e-1),
(16)
t=k
where æ ( ... ,,), [r]a represents the subset of players up to the k-th player in the ordering [T] = 0 and [m]] = S.
Proof. It can be simply proved by the definition interactions.
A,((S) A,)([T)))
= A + (A.(((T)s) - Av(((T)--1))
A,v([T]--1) L.n, ([T]--1)
(17)
= - +
Lim ([T]--1).
t=
Theorem 1. The Shapley value is weighted sum of interactions:
(s(e)= = (,0 + Σ n
)
Σ Σ IT)
(18)
JEN (E.) JA IT
Sketch of proof.
1. The Shaley value is the expectation of marginal contributions over all possible random orderings.
15

---

Published as a conference paper at ICLR 2025
2. Each contribution is decomposed into cumulative interactions.
3. The coefficients of individual interactions in the Shapley value equation are obtained by aggregating the results of the decomposition.
Proof. The Shapley value can be expressed as the expected marginal contribution over all possible random orderings:
(v)
1 Σ Ae((T)= n!
E TEI((N)
(v(r² U ( v(('))
(19)
TEH(N))
Each contribution (,)(=²) can decomposed into various combinations of interactions depending on the order of players in s'. Let == ( TT) be fixed ordering for set S. By Lemma | obtain
we
A,v(S) = ( = Σ Li, ([T))-1) + (,)(
(20)
By substitution, the Shapley value be represented the sum of an individual contribution term and the aggregated interactions between players, weighted over all possible subsets.
s = (0) + Σ E
w (TT
(21)
JEN TEN
The coefficient "I, is determined by counting the occurrences of w/, in A,0(x") in Equation 19
why
Σ
Σ
[[TT] = n, #c+1 =
nl!
*ETI(T)
=ET(NN
1
t! n!
(n t - 1)!
(22)
1 n - 1
The coefficient win only depends on the cardinality of T. Finally, the Shapley value represented as follows:
Σ Σ (T)(T)
di(v) (0) +
JEN TENN(E IT
C.2 PROOF OF THEOREM 2
Theorem 2. A game is convex if and only (R) 2
{i,s}.
Proof. (-+ Necessity.
We show Is(RR 2 0 for any i,j N and R S N (t.j). Define $ R RU(() and T RU RU (f).
By the convexity of v, we obtain
((RU(i)))) + v(R) 2 v(Ru( +((UU)))
(23)
A (5) > (,((R.
Thus, it follows that (1)( 2 0.
(+) Sufficiency.
16

---

Published as a conference paper at ICLR 2025
Given S, T S P = and R = SNT. p. 9 denote the cardinality of P. Q, respectively. Choose permutations E [I))), क E [I))). By Lemma I the following equations hold for all & (1....9)..
A * [=)--) (() A. u | 1) + Σ I Tk.m RU]T] ([T]=-))
(24)
DRU
Summing over all k obtain
A (SU A., ( (=)x)))) 20,
(25)
( - {u(RR ( (R) 2 0,
v(S vSS) - -((T (((TT) 2 0.
Therefore, the game v is convex.
C.3 PROOF OF THEOREM 3
Let i (I(S) be the uniform distribution of player i over the set S, and T ut, be the uniform distribution over subsets T S. S with cardinality [2'] = t. σ(v) and Av(0) denote the Shapley value and the discrete derivatives of all players in vector form, respectively. We define an interaction vector (T) E IR where the i-th element is [T) for given T S N {j}. We set (T) 0 when i = the following vectorized form to estimate the Shapley value with interaction vectors.
T, ensuring (T) well-defined for T N (i). Then, we obtain
Theorem 3. The vector of the Shapley value (0()) is represented follows:
Φ(v) = Av(O)
Proof. Since we set l,g (T) = when i = or E T, the following equality holds for all E N:
Σ Σ (T(T) Σ Σ IT(T)
JEN (CN) J/4 IT
JEN
CENTCNUU
[T1=
(26)
By combining Theorem | with Equation (26 and vectorizing the result, we obtain the conclusion:
Φ(v) = Av(O)
D AN ILLUSTRATIVE EXAMPLE OF UNDERVALUATION
In Figure we provide an example of undervaluation in an image recognition scenario. Pattern scores for image classification are computed within each region, followed by max pooling, and the results are summed to obtain the final output. In this example, the efficiency axiom constrains the total attributions in each region to and respectively. Although Region (the first max pooling) extracts features that significantly contribute to the output, the Shapley value assigns lower attribution to feature '7' compared to feature '4' in Region 2 (the second max pooling). This occurs due strong negative interactions within an inefficient coalition, discussed in Section 4 The proposed API effectively alleviates this undervaluation by eliminating problematic negative interactions, ensuring that feature '7' receives higher attribution (7) than feature '4' (4).
17

---

Published as a conference paper at ICLR 2025
oulpul max(6,7,6,6) + -nxx(,,,,,,)-7774
feature
Shapley value
6
7
Interaction -6
10/4
6
1
Interaction
13/4
Figure 4: An Example in Image Recognition. Due negative interactions, feature '7' receives lower Shapley value than feature '4', which a counterintuitive result.
E ADDITIONAL EXPERIMENTS
E.1
EXPERIMENT RESULTS FOR COMPLEXITY
Effective Complexity
KL divergence
350
KimelSHAP
0010
230
200
8:008
8.004
0.002
0.000
KarnelSHA
Approx.
200 features
250
400
(a)
(b)
tiger
KernelSHAP
IG
Approx. SV
API
(c)
Figure 5:
Experiment Results for Complexity. We measured the minimum number of features in- serted (in descending order of attribution scores) to achieve the KL divergence between the model output and the original model output below 0.001. API requires fewer features to reproduce the original model output compared to other methods.
We additionally conduct quantitative experiments. We insert the features (i.e., patches) in descend- ing order of attribution scores and compute the output class probability distribution to measure the KL divergence with the original distribution (which includes all features). Then, identified the minimum number of features required to reduce the KL divergence to below 0.001. Figure 5 (a) shows the average number of features required, with API achieving almost 30% reduction compared to other methods. More specifically, the average numbers are 272.34, 342.94, 281.59, and 203.32 3..3222 for KernelSHAP, IG, Approximated Shapley value, and API, respectively. This indicates API requires fewer features to reproduce the original model output, effectively capturing the relevant features for the model prediction.
Figure 5 (b) shows the KL divergence with respect to the number of features inserted for a specific image, as depicted Figure (c). We observe that API leads to more rapid decrease KL divergence with relatively fewer features inserted. Specifically. the number of features required to reach the KL divergence of 0.001 is 311, 339, 337, and 203 for KerneISHAP, IG, Approximated Shapley value, and API, respectively. Furthermore, 5 shows visualization of the features
18

---

Published as a conference paper at ICLR 2025
inserted to achieve the KL divergence of 0.001. With the proposed API, reproduce the original decision with fewer irrelevant features inserted compared to other methods.
E.2 ABLATION STUDY FOR FUNCTION CHOICE ON INTERACTIONS
Shapley (e 1)
LeakyfeLLU (a 0.5)
(PI(R)LU)
(a
Scftplus
red pandl
troffilligh
Figure 6: Attribution Results with Different Function Choices Interactions.
Assigning attributions in the form of interactions in Equation can be seen as decomposing the characteristic function into interaction terms and then transforming these through a function g (e.g. ReLU) to determine the attributions for each player. If is the identity function, the result is the Shapley value; if it the ReLU function, the result is API.
The choice of depends on how the user interprets interactions attributions in the given task. For instance, if smoother transition from interaction values attributions preferred, softplus function might be a suitable choice. Figure 6 shows the impact of different function choices in an ImageNet classifier. In this setting, due to the large proportion of negative interactions, even slight relaxation using the Leaky ReLU function yields results similar to those of the API (albeit with differences in scale). When applying the softplus function, negative interactions are mitigated; however, the differences in positive interactions are also slightly reduced, leading to lower contrast in the final attributions.
E.3 RUNTIME OF API
Att anriouttinn Map
Ralooans Parts top 20%6
permutations (runtiie)
(00:53)
(01:45)
(03:00)
(04:41)
(38:57)
Figure 7: Attribution Results and Runtime with respect to the number of Permutations. API takes around 55 seconds for every 10 permutation samples. Notably, stable results can be achieved with as few as 30 permutations.
Figure 7 shows the runtime of API for different numbers of permutation samples on an ImageNet classifier. We observed that stable results can be achieved with as few as 30 permutations, which
19

---

Published as a conference paper at ICLR 2025
took around minutes RTX 6000 GPU. While this is slower compared to IG, it remains com- parable to other permutation- based attribution methods grounded in game theory. Since handling interactions inherently involves significant computational costs, accelerating this process through path-based approximations is one of our future research directions.
20


Reviews:
[{"review_id": "g0dptn1ygn", "reviewer": "Reviewer_kE5C", "summary": "This paper extended Shapley Value from convex games into non-convex games. The paper argues that traditional Shapley Value is only a fair and reasonable allocation when then underlying game is balanced or in other words, convex. Therefore, it is not a well-defined concept when non-convexity is involved. To address this issue, the paper proposed a variation of traditional Shapley Value called Aggregated Positive Interaction (API) that decomposes the total utility into pairwise interactions between players. The authors then provided an approach to estimate API using permutation sampling, which proves to be an unbiased estimator. Furthermore, the authors provided approximated method to compute API more efficiently. Experiments demonstrated the effectiveness of the proposed approach.", "questions": "I am wondering why API has to be designed as in this paper? Does other design work like taking max with another number instead of 0?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper extended traditional Shapley Value to non-convex games, which provided a way for the community to attribute contributions of features in non-convex settings. Given that deep learning models are widely used so far, the method in this paper would of be great importance to general AI and ML community.\n\nThe paper provided theoretical justification of the proposed API attribution method, including proof of relationship between traditional Shapley Value and convexity, unbiasedness of API estimation etc. The theoretical contribution of this paper is novel.\n\nThe presentation of this paper is nice - easy to read and understand. The case study is interesting and really helps readers understand why traditional Shapley Value has certain limitations.", "weaknesses": "The major weakness of the paper is that I don't see a clear and strong justification for why the API is designed this way, specifically why we need to take max with 0. Does the number 0 really matter? Can we take other numbers here? Traditional Shapley Value is supported by those 4 axioms, and they serve as a strong justification for the design of Shapley Value. However, for API, the utility of each individual may not sum up to the total utility. In this case, I am wondering why API has to be designed as in this paper? Does other design work like taking max with another number?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5ieyuSpBmI", "reviewer": "Reviewer_ypS5", "summary": "The paper identifies negative interactions to be an issue for methods that quantify feature attribution by approximating the Shapley value. The paper establishes the equivalency between the convexity of the game and the absence of negative interactions between features, and that the Shapley value can only meaningfully represent the causal effect of a feature’s contribution for convex games. The paper proposes Aggregated Positive Interactions, an extension of the Shapley value to non-convex games that only accounts for positive interactions between features. The papers proposes to estimate Aggregated Positive Interactions using sampling interactions, and show empirical evidence on a few examples in image classification (VGG19 and ResNet50 trained on ImageNet) and sentence classification (BERT trained on the IMDB Review dataset).", "questions": "- In Algorithm 1, it’s not exactly uniform sampling all permutations $\\pi$, as each sample is reused for all $t$. How much of a computation burden is it to resample $\\pi$ in the inner loop? And how much effect does it have in the performance?\n- Could you discuss the computation cost & sample efficiency for the proposed approach? Since you are using gradient information to approximate the interaction, I would expect the estimator to be quite scalable. It’s odd that you have to convert the images to 20x20 patches for feasible computation.\n\nMinor comments:\n\n- Line 296: I think it’s inaccurate to call (7) an unbiased estimator of the Shapley value. The expectation represents the exact Shapley value. You might want to explicitly provide the Monte Carlo estimator in equation.\n- It will be helpful to briefly define what “feature” refers to in this paper. It seems to refer to components of the data in this paper, but in other literature feature often refers to learned representations.\n- Line 410: the reference to Figure 2 is not displayed properly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written. The problem with using Shapley value for deep learning is rigorously discussed, and the proposed approach is well-motivated.\n- A proposed method is simple and intuitive. An efficient estimator (using gradient) is presented to lower the computation cost.", "weaknesses": "- The experimental evidence for the effectiveness the proposed Aggregated Positive Interactions is not strong enough. For the image classifiers, only results on a few image examples are shown for two models.. In the language model experiment, only one positive and negative sentence examples are shown for one model. Although the examples are quite illustrative, it’s unclear if they are cherry-picked.\n- It’s unclear how scalable the approach is. See questions about its computation cost and sample efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ffBTCVgXJz", "reviewer": "Reviewer_ApX2", "summary": "This paper proposes a modification to the Shapley value for its use in measuring feature attribution of deep learning models. This modification is based on an equivalent reformulation of the Shapley value formula as a weighted sum of pairwise interactions between players (features). When pairwise interactions are non-negative (i.e., a convex game by Theorem 2), Shapley value gives intuitive results and also satisfies desireable conditions from a cooperative game theory perspective, i.e., it lies at the center of the core and satisfies coalitional rationality. However, when interactions are negative, results can be counterintuitive as the authors show through examples; in addition, this coincides with a loss of coalitional rationality. Naturally, the authors suggest clipping interactions to always be non-negative and report the value of this formula instead of the Shapley value. This formula reduces to the Shapley value when the underlying game is convex, but gives more intuitive results in their examples when the game is non-convex. The authors also propose a more tractable estimate using a Taylor approximation and show their approach is competitive with baselines on explainable AI tasks for image and text domains.", "questions": "- Which of the 4 axioms underpinning the Shapley value does your approach no longer satisfy? can you discuss this as a limitation?\n- Can applying a ReLU to the interactions also be interpreted as first projecting the game onto the set of convex games?\n- Relatedly, can the characteristic function be rebuilt from interaction terms, I(T)? The I(T) matrix appears to be a discrete hessian, so a characteristic function only exists iff I(T) is symmetric for every subset of players T. I(T) appears to be symmetric by definition. Applying ReLU to entries of it should not break symmetry. Therefore, a characteristic function should exist.\n- There is some loss of information when applying the ReLU. Do you foresee any limitations? Are there other approaches that might retain more information or have desireable tradeoffs, e.g., a leaky-ReLU?\n- line 452: “highlighting the tokens with attribution in the top 20%” - I was expecting to see the same number of tokens highlighted in Figure 3. Line 465 suggests tokens are word level. Why do I not see the same number of words highlighted. If tokens aren’t word level, can you underline the actual tokens?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think Theorems 1 and 2 that reformulate Shapley value in terms of interactions and relate non-negative interactions to convex games are very insightful. These form the core theoretical discovery that enables the rest of the work. In addition, the case study examples appealing to the reader’s intuition on how negative interactions result in counter-intuitive Shapley value are helpful. Lastly, the Taylor approximation of their approach is competitive with standard baselines and provides intuitive features attributions.", "weaknesses": "I see opportunities for improvement both in writing / motivation as well as experiments.\n\n**Writing / Motivation**:\n- The 4 axioms that uniquely lead to the Shapley value are mentioned several times but never defined. Any modification to the Shapley value necessarily leads to the loss of one of these axiomatic properties and it should be discussed how this manifests as a limitation of the proposed approach.\n- Generally, the paper attempts to argue that Shapley value implicitly assumes a convex game (or least the formation of the grand coalition). I wonder if there is a better argument for the proposed modification. While it is clear that the core makes the assumption of a grand coalition forming, all Shapley value assumes are the 4 axioms, none of which explicitly require any rationality or formation of the grand coalition. Note these axioms are always satisfied regardless of the convexity of the game, and so statements like “Shapley value becomes nothing but taking an expectation formula” on line 189 are hyperbole. In addition, the first remark on line 094 states that the formation of the grand coalition is implicit in cooperative game theory, which is also too strong a statement (for instance, the problem of coalition structure generation obviously does not assume this). It seems the authors are taking the existence of the core as an axiom (core existence <-> convexity <-> non-negative interactions), and that would better serve as the starting point for their argument. Deep learning models typically assume one would make use of all features (i.e., the grand coalition forms), and so it seems sensible to assume this. Continuing this line of thought, could you better argue that the natural characteristic function for DL is one that is convex (i.e., is consistent with the formation of the grand coalition) and your work can be used to implicitly define such an appropriate function via clipping interactions (see questions)?\n\n**Experiments**:\n- Given the discussion of the core and Shapley value’s relation to it, why not compare against least-core [1,2] which always exists?\n- I would have liked to see a systematic study comparing your exact definition in (6) to your Taylor approximation in (9). How does the approximation degrade? Can you sample a subset of coalitions (features) T and compare the two?\n- I would have also liked to see how results in one of the domains (image or text) changes as the number of permutations varies (not just 100 or 300 permutations). How did you select the number of samples?\n- Given that computational efficiency was a motivation for the Taylor approximation, can you please report runtimes for the different methods? For instance, IG seemed to perform relatively well yet its unclear if it is generating these results in a runtime that is comparable to your proposed approach.\n\n[1] Benmerzoug, Anes, and Miguel de Benito Delgado. \"If You Like Shapley Then You’ll Love the Core.\" ML Reproducibility Challenge 2022. 2023.\n\n[2] Gemp, Ian, et al. \"Approximating the Core via Iterative Coalition Sampling.\" Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. 2024.\n\nminor:\n- line 098: “forming the grand coalition N is **an** optimal strategy”, e.g., v(S) = 0 is convex yet any coalition is optimal.\n- line 112: “from **this** perspective”\n- line 175: “we introduce**d** the concept”\n- line 266: “It is **the** extension” is too strong. Given Shapley value is derived to be unique from axioms, that is your baseline for strong statements. You would need to prove that API is the only formula satisfying some set of conditions.\n- line 359: “we introduce**d** some”\n- line 410: “ResNet 50 in Figure ?” missing reference\n- Please include more informative captions: for example, lines 413 - 417 can be moved to the caption of Figure 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vXw7HBJoeU", "reviewer": "Reviewer_fJo6", "summary": "The paper reformulates the Shapley value as $\\Delta(\\emptyset)$  plus a sum of second-order derivatives, which are refered to as interactions in the paper, and argues that ignoring negative second-order derivatives in the summation can provide better feature attribution.", "questions": "My major concern is the motivation of filtering out negative second-order derivatives, which the authors refer to as interactions. I do not think that the two simple examples as well as a few experiment results are sufficient. For the Shapley value, it is deemed good because it uniquely satifies the axioms of linearity, null, symmetry and efficiency. For the proposed API, which properties make it desirable?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Overall, the writing is clear, and the reformulation of the Shapley value seems interesting.", "weaknesses": "- Theorem 2 is already a well-known result in the literature, e.g., proposition 2.1 in (Nemhauser et al., 1978).\n\n\n- In lines 176-177, the authors suggest that a game has a non-empty core if and only if the game is convex.  However, a balanced game is not necessarily convex, and thus this statement is false. A counterexample is $v(\\emptyset)=0, v(\\\\{1\\\\})=v(\\\\{2\\\\})=v(\\\\{3\\\\})=3, v(\\\\{1,2\\\\})=v(\\\\{1,3\\\\})=v(\\\\{2,3\\\\})=5$ and $v(\\\\{1,2,3\\\\})=10$; the game is not convex as $v(\\\\{1\\\\}) -v(\\emptyset) > v(\\\\{1,2\\\\}) - v(\\\\{2\\\\})$, and its core contains $(10/3, 10/3,10/3)$.\n\n- I did not find any *clear* evidence to support the claim that \"Our theoretical analysis demonstrates that classical payoff allocation in a cooperative game assumes the convexity of the game\" stated in the abstract, which seems to be an overstatment.\n\n- I did not feel that the motivation is compelling enough, please refer to my question.\n\nMinor:\n- In lines 133-134, the statement that ''the Shapley value is a solution positioned at the center of the core'' is not strictly correct, because the Shapley value of a game always exists while its core may not if the game is not convex. Besides, I would recommend that the authors include a reference for this statement for those who are not familiar. I know that for a convex game, the Shapley value is the average of $n!$ marginal vectors (though there may be duplicates)  that constitute all the extreme points of the corresponding core, which is convex.\n\n- I feel it may confuse researchers by referring to second-order derivatives as just interactions, because there are already several defined interactions in the literature (Tsai et al. 2023). To fit into the existing studies, I think it would be better to term them as *second-order* interactions.\n \n- The proof of Theorem 1 can be greatly simplified using $\\phi_i(v) = \\frac{1}{n!}\\sum_{\\pi} (v(\\pi\\^{i} \\cup \\\\{i\\\\}) - v(\\pi\\^{i}))$ where $\\pi^i$ contains all players preceding $i$ in the permutation $\\pi$. \n\n- I would recommend that the authors write down the proposed API results in the case study for clear comparison. \n\n- For the case study of sigmoid function, the Shapley values of player 1 and 3 are $2.51$ and $3.73$, respectively. \n\nNemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14, 265-294.\n\nTsai, C. P., Yeh, C. K., & Ravikumar, P. (2023). Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94), 1-42.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)