Rethinking Shapley Value for Negative Interactions in Non-convex Games

Q1. Motivation of filtering out negative interactions (second-order derivatives).

A1. Please refer to the general response provided above for the details.

In summary, the proposed method satisfies the four axioms for convex games, but it no longer satisfies efficiency for non-convex games. If we maintain efficiency in non-convex games, the sum of attributions remains fixed, preventing the compensation for undervaluation from negative interactions—some players will inevitably receive lower attributions. We believe that a reasonable solution need not satisfy efficiency in non-convex games, as the presence of negative interactions implies that the players' coalition is not a fully efficient strategy. To alleviate the undervaluation, our goal is to evaluate each feature/player based on its potential effect to increase the output value by avoiding inefficient scenarios. In this spirit, API was designed to evaluate a player’s causal effect (output changes) from only cooperative behaviors between players.

As explained in General Response, computing API can be interpreted as a two-step process: (1) approximating an original non-convex game with a convex game, and (2) computing the Shapley value on the projected convex game. In choosing a convexified game, our current solution design was guided by two key criteria: (1) positive interactions must be preserved, and (2) the approximated characteristic function should remain as close as possible to the original function. That is why we take max with zero for interaction terms.

In addition, API satisfies two properties

• The efficiency holds for the revised (convexified) function.
• Zero attribution guarantees that the corresponding feature cannot improve the output in any case, which does not hold in other attribution methods for non-convex games.

Response to Comments in Theoretical Parts

• Related to Theorem 2, we checked the proposition 2.1 in Nemhauser et al.’s work [1] and we will cite it in our manuscript.
• In the second weakness you pointed out, we acknowledge that we misunderstood the connection between core existence and convexity, and we will revise the corresponding statement accordingly. We assumed that a solution represented by the weighted sum of marginal vectors, including the Shapley value, must always belong to the core since it can be interpreted as the combination of outputs from rational strategies. Initially, we believed that this statement was equivalent to the core existence; however, we later realized this was incorrect. It corresponds to the condition under which the core and the Weber set are equivalent—that is, convexity. We would appreciate it if you could note that this correction does not critically impact our main argument on the issue of negative interactions or our proposed solution to address it. Nonetheless, your feedback has been truly helpful in clarifying and improving our manuscript.

Response to other comments

• Thank you for your valuable feedback. It must be helpful to improve the details of our work. We will incorporate it into the revised manuscript. We will revise some overstated parts and mis-calculated values, and clarify the meaning of interaction which was designed as a second-order derivative in the literature about causal effect [2].

[1] Nemhauser, George L., Laurence A. Wolsey, and Marshall L. Fisher. "An analysis of approximations for maximizing submodular set functions—I." (1978)

[2] Egami, Naoki, and Kosuke Imai. "Causal interaction in factorial experiments: Application to conjoint analysis."  (2019)

Personally, I think that the starting point of this work might be promising and I have been trying to figure out how to make this work more complete in theory. In my view, the proposed method is not well justified theoretically. I already noticed that the proposed API might be interpreted by convexification while reviewing, but it is not a concrete concept because there is no theoretical justification provided in eithier the submission or reponses.

For deriving the convexification, my understanding is that it concerns with the bijective conversion between games and their first- and second-order derivatives. Precisely, assuming $v(\emptyset)=0$, there are $n + n(n-1) 2\^{n-3}$ variables standing for all first- and second-order derivatives, but the freedom of variables for games is $2\^{n} - 1$. That being said, one conversion is overdetermined and the other is underdetermined. Given this, I am not sure if the interpretation using convexification is possible.

I would be happy to raise my score if the authors can step further in theory for interpreting the proposed API. So far, I did not see anything new in theory compared with the initial submission. This lack of theoretical interpretation makes me feel that the good performance of the proposed API is more of a magic.

Why convexification is good

This section is intended purely for discussion. Personally, I think Eq. (1) is not a proper perspective for domenstrating why convexification is good. Despite that, I noticed that the authors have discussed its equivalent definition in the remark right below Eq. (1), which states that $\Delta\_{i}v(S) \leq \Delta\_{i}v(T)$ for every $i \in N$ and $S \subseteq T \subseteq N \backslash \\{ i\\}$. I think this one is more convenient for interpreting why convexification is good. In my own understanding, I think it suggests that it is probably better to fous on the approximate game (best in some sense) where the marginal contribution of one specific feature should not decrease while introduing more other features.

I have read through the authors' responses, including the global one, and I confirm that the second weakness was not considered in my initial score. I noticed that the authors provide three additional properties for the proposed API, but I could not find any detailed justification for them.

• If I understand correctly, the authors seem to suggest that the proposed API is equal to calculating the Shapley value of

$

v(S)=v(\emptyset)+\sum_{i\in S}\Delta_iv(\emptyset)+\sum_{\substack{i,j\in S, \ i\neq j}} \sum_{T\subseteq S\setminus{i,j}} \frac{1}{s}\binom{s-1}{t}^{-1}\max(I_{ij}(T), 0) .

$

Although I did not mention it in my initial review, my first impression is that the proposed API seems to first convexify games and then calculate the Shapley value of the convexified games. However, the submission and the responses do not provide any detailed discussion on this. The above equation seems to refer to this possibility. Could the authors elaborate on this aspect theoretically?

• In addition, in the global response, the authors write "applying ReLU achieves the closest approximation to the original game under these constraints." I find this vague, as "closest" is not rigorously defined. A better choice is to prove that the convexified game $\hat{v}$ is an optimal solution to, e.g., $\min\_{u \in \mathcal{U}} \\|u - v\\|$ where $\mathcal{U}$ contains all the games that satisfy the specified constraints.

• Finally, there is an issue with the claim provided in the global response that if the proposed API assigns $0$ to the $i$-th player, then $\Delta_iv(S)\leq0$ for all $S\subseteq N\setminus {i}$. A counterexample is as follows: let $N = \\{1,2,3\\}$ with $v(\emptyset)=v(\\{1, 3\\})=v(\\{2, 3\\})=0$, $v(\\{2\\})=1$, $v(\\{1\\})=-1$, $v(\\{1,2\\})=3$, $v(\\{3\\})=10$ and $v(\\{1,2,3\\})=-20$. In this case, the proposed API assigns $0$ to player $1$, but $\Delta\_{1}v(\\{2\\}) = v(\\{1,2\\}) - v(\\{2\\}) = 2 > 0$.

Properties of the proposed API

Discarding the axiom of efficiency is not a novel idea. For example, the Beta Shapley values proposed by Kwon and Zou (2022a) consider this, and their effectiveness is demonstrated by Kwon and Zou (2022b). That being said, the proposed API is not unique in ignoring the axiom of efficiency. Plus, using the terminology of (Weber, 1988), it is straightforward to verfiy that the proposed API satisfies the axioms of dummy, symmetry and monotonicity. However, all the probabilistic values mentioned by Weber (1998) satisfy these three axioms. Perhaps, there is something else that makes the proposed API unique or desirable?

Kwon, Y., & Zou, J. (2022a). Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning. In International Conference on Artificial Intelligence and Statistics (pp. 8780-8802). PMLR.

Kwon, Y., & Zou, J. Y. (2022b). Weightedshap: analyzing and improving shapley based feature attributions. Advances in Neural Information Processing Systems, 35, 34363-34376.

Weber, R. J. (1988). Probabilistic values for games. In A. E. Roth (Ed.), The Shapley Value: Essays in Honor of Lloyd S. Shapley (pp. 101–120). chapter, Cambridge: Cambridge University Press.

Q1. Axioms that our approach no longer satisfies.

A1. Please refer to the general response provided above for the details.

In summary, the proposed method satisfies the four axioms for convex games, but it no longer satisfies efficiency for non-convex games. If we maintain efficiency in non-convex games, the sum of attributions remains fixed, preventing the compensation for undervaluation from negative interactions—some players will inevitably receive lower attributions. We believe that a reasonable solution need not satisfy efficiency in non-convex games, as the presence of negative interactions implies that the players' coalition is not a fully efficient strategy. To alleviate the undervaluation, our goal is to evaluate each feature/player based on its potential effect to increase the output value by avoiding inefficient scenarios. There may be concerns regarding the lack of adherence to the efficiency axiom. However, as discussed in the response to the next question, our method can be interpreted as satisfying efficiency within the context of a convexified characteristic function.

Q2. Can applying ReLU to the interactions also be interpreted as first projecting the game onto the set of convex games? Can the characteristic function be rebuilt from interaction terms?

A2. Please refer to the general response provided above for the details.

In summary, computing API can be interpreted as a two-step process: (1) approximating an original non-convex game with a convex game, and (2) computing the Shapley value on the projected convex game. Applying ReLU (max with zero) to interaction terms means that attributions are computed by evaluating output changes from only cooperative behaviors between players in the original characteristic function (game), which is equivalent to projecting to convex games. In choosing a convexified game, our current solution design was guided by two key criteria: (1) positive interactions must be preserved, and (2) the approximated characteristic function should remain as close as possible to the original function. Applying ReLU achieves the closest approximation to the original function while preserving positive interactions, leading to its adoption as our design choice. We can explicitly represent the revised characteristic function in interaction terms as follows. API satisfies efficiency in this revised characteristic function.

$$v(S)=v(\emptyset)+\sum_{i\in S}\Delta_iv(\emptyset)+\sum_{\substack{i,j\in S, i\neq j}} \sum_{T\subseteq S\setminus\{i,j\}} \frac{1}{s}\binom{s-1}{t}^{-1}\max(I_{ij}(T),0)$$

Q3. Limitation from loss of information when applying the ReLU.

A3. Removing negative interactions using ReLU is not intended to result in information loss but rather to prevent undervaluation. This approach is appropriate under the assumption that players cooperate to increase the output. For instance, in deep learning classification models, input variables are used to extract evidence that increases the logit probability. However, in scenarios where a decrease in the function's output serves a meaningful result, such as regression problems, eliminating negative interactions could misrepresent the influence of certain variables and they should be carefully handled. Thus, the appropriateness of removing negative interactions depends on the specific context and objectives of the application.

Q4. The number of highlighted tokens is different.

A4. In Figure 3, we showed only a portion of the original text input since the entire text is too long considering page limit.

Q5. How results change as the number of permutations varies. Computational efficiency & Runtimes.

A5. We have added an example in the Appendix illustrating the changes in API results and runtime with respect to the number of permutations, using an ImageNet classifier. Empirically, we observed that stable results can be achieved with as few as 30 permutations. On an RTX 6000 GPU, this process took approximately 3 minutes. While this is slower compared to IG, it is comparable to other permutation-based methods grounded in game theory. Handling interactions inherently involves significant computational costs. Accelerating this process through path-based approximations is one of our future research directions.

Response to other comments

• Thank you for your valuable feedback including various suggestions to clarify our work. It must be helpful to improve the details of our work. We will incorporate it into the revised manuscript.

Q1. It’s not exactly uniform sampling all permutations $\pi$. How much of a computation burden is it to resample $\pi$ in the inner loop?

A1. In Algorithm 1, the probability of constructing $[\pi]\_{t+1}, [\pi]\_{t}$ by resampling a new permutation $\pi$ at each time step $t$ is equivalent to sampling a permutation beforehand and using $[\pi]\_{t+1}, [\pi]\_{t}$ at each $t$. The latter approach is more efficient as it eliminates the need to resample a permutation for every $t$. Additionally, backpropagation is implemented once at each $t$, whereas the former approach requires it twice. This technique is similarly employed in Castro et al.'s work [1] for efficiently approximating the Shapley value using permutation sampling.

[1] Castro, Javier, Daniel Gómez, and Juan Tejada. "Polynomial calculation of the Shapley value based on sampling." (2009)

Q2. Computational cost & sample efficiency for the proposed method.

A2. Our algorithm requires $O(n)$ backpropagations per permutation to compute the gradients. This is a significant improvement over directly calculating interactions, which would require $O(n^2)$ forward passes, making such computations prohibitively expensive. The proposed approximation method addresses this computational challenge.

However, permutation-based methods inherently involve high computational costs despite providing robust game-theoretic justification. This is because inserting players (or elements) sequentially necessitates $N$ evaluations. In our study, we achieve computational efficiency comparable to conventional permutation-based methodologies, even while incorporating interactions. For the individual pixel-level application, a path-based approach would likely be suggested, which we consider as our future work.

Q3. Few experimental results.

A3. To demonstrate the generality of our results, we conducted additional quantitative experiments inspired by the effective complexity metric proposed by Nguyen et al. [2]. Specifically, we evaluated the change in output probability for an ImageNet classifier as features (patches) were added in descending order of attribution scores. If the attributions accurately identify information critical to the model's decision-making, a small number of features should suffice to reproduce the output probability observed with all features included.

In this context, we measured the number of features required for the KL divergence between the original and reconstructed probabilities to drop below 0.001. The average complexity is summarized as follows. Our method achieves almost 30% reduction in the number of features required to reproduce the original decision output compared to alternative methods. We will include this evaluation in the Appendix of the revised paper.

• KernelSHAP : 272.34
• Integrated Gradients : 342.94
• Approximated Shapley value : 281.59
• Aggergated Positive Interactions : 203.32

[2] Nguyen, An-phi, and María Rodríguez Martínez. "On quantitative aspects of model interpretability." (2020).

Response to other comments

• Thank you for your valuable feedback. It must be helpful to improve the details of our work. We will incorporate it into the revised manuscript.

Q1. The utility of each individual may not sum up to the total utility. Why is API designed as in this paper? Does other design work like taking max with another number instead of zero?

A1. Please refer to the general response provided above for the details.

In summary, if we maintain efficiency in non-convex games, the sum of attributions remains fixed, preventing the compensation for undervaluation from negative interactions—some players will inevitably receive lower attributions. To alleviate the undervaluation, our goal is to evaluate each feature/player based on its potential effect to increase the output value by avoiding inefficient scenarios. In this spirit, API was designed to evaluate a player’s causal effect (output changes) from only cooperative behaviors between players.

As explained in General Response, computing API can be interpreted as a two-step process: (1) approximating an original non-convex game with a convex game, and (2) computing the Shapley value on the projected convex game. In choosing a convexified game, our current solution design was guided by two key criteria: (1) positive interactions must be preserved, and (2) the approximated characteristic function should remain as close as possible to the original function. That is why we take max with zero for interaction terms.

In addition, API satisfies two properties

• The efficiency holds for the revised (convexified) function.
• Zero attribution guarantees that the corresponding feature cannot improve the output in any case, which does not hold in other attribution methods for non-convex games.