A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Kazuhiro Hiraki Shinichi Ishihara Takumi Kongo Junnosuke Shino · 2026

Read A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution by Kazuhiro Hiraki Shinichi Ishihara Takumi Kongo Junnosuke Shino (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00496.txt.

Introduction

Hiraki and three colleagues offer a fast axiomatic rival to SHAP for explaining which input features drive a prediction. Framing attribution as a cooperative game, they combine two polynomial time closed form rules into ESENSC_rev2, preserving the null player property. Tests on tabular prediction show it tracks exact SHAP closely while scaling far better as feature counts grow. Theory proves the rule is uniquely fixed by efficiency, null player, restricted marginality, inessential game, and cost cutting axioms.

Catalog record

CREATORKazuhiro Hiraki Shinichi Ishihara Takumi Kongo Junnosuke Shino
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79540
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.00496

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution Thanks: This work was supported by the Japan Society for the Promotion of Science [KAKENHI, grant nos. 25K05176] and Nomura Foundation. The views expressed in this paper are those of the authors and do not represent the views of the IMF, its Executive Board, or IMF management. Kazuhiro Hiraki Shinichi Ishihara Takumi Kongo Junnosuke Shino Abstract In this paper, we provide a theoretically grounded and computationally efficient alternative to SHAP. To this end, we study feature attribution through the lens of cooperative game theory by formulating a class of XAI–TU games. Building on this formulation, we investigate equal-surplus-type and proportional-allocation-type attribution rules and propose a low-cost attribution rule, ESENSC ​ _ ​ rev2 \mathrm{ESENSC\_rev2} , constructed by combining two polynomial-time closed-form rules while ensuring the null-player property in the XAI–TU domain. Extensive experiments on tabular prediction tasks demonstrate that ESENSC ​ _ ​ rev2 \mathrm{ESENSC\_rev2} closely approximates exact SHAP while substantially improving scalability as the number of features increases. These empirical results indicate that equal-surplus-type attribution rules can achieve favorable trade-offs between computational cost and approximation accuracy in high-dimensional explainability settings. To provide theoretical foundations for these findings, we establish an axiomatic characterization showing that ESENSC ​ _ ​ rev2 \mathrm{ESENSC\_rev2} is uniquely determined by efficiency, the null-player axiom, a restricted differential marginality principle, an intermediate inessential-game property, and axioms that reduce computational requirements. Our results suggest that axiomatically justified and computationally efficient attribution rules can serve as practical and theoretically principled substitutes for SHAP-based approximations in modern explainability pipelines. Keywords: Explainable AI (XAI); Feature attribution; SHAP; Shapley value; Cooperative game theory; Axiomatization; Computational efficiency; Exact SHAP approximation JEL classification: C45, C71, C63 1 Introduction Additive feature attribution (AFA) methods in explainable artificial intelligence (XAI) decompose a model’s prediction into feature-level contributions. Among these methods, SHAP, which is based on the Shapley value from cooperative game theory (Shapley [ 18 ] ), is the most widely used approach in practice (Lundberg and Lee [ 13 ] ). More formally, let f denote a trained prediction model, such as a neural network or XGBoost model. Consider the k -th observation x_{k}=(x_{k1},\ldots,x_{kn})\in X , consisting of n features, and let the model prediction be y_{k}=f(x_{k}) . An AFA method provides a rule that allocates the difference between the prediction under full information, f(x_{k}) , and the baseline prediction E[f(X)] , that is, f(x_{k})-E[f(X)] , to each feature according to its contribution. For example, suppose that the trained model f predicts the probability of default based on a loan applicant’s profile. If the j -th feature represents occupation and revealing the occupation of applicant k substantially changes the predicted default probability, then feature j should receive a larger contribution in explaining y_{k} . This illustrates the basic idea of AFA. When applying SHAP, one can construct a transferable utility (TU) cooperative game from the trained model f and dataset X by defining a coalitional value for each subset of features, corresponding to the expected prediction when only those features are known. In this paper, we refer to this game as a XAI–TU game. In a XAI-TU game, intriguing situations may arise—for example, positive and negative coalition values can coexist—phenomena that have not been fully explored in the traditional cooperative game theory literature. SHAP is obtained by applying the Shapley value to this XAI–TU game. However, it is well known that the computational costs of the Shapley value and SHAP are substantial, making it infeasible to compute exact values in many applications. Approximation algorithms for SHAP have already been developed and implemented; however, their accuracy can be unstable and they typically require tuning parameters. Moreover, they do not necessarily satisfy the theoretical properties that SHAP is designed to fulfill. This study investigates existing solution concepts from classical cooperative game theory that have low computational costs and desirable properties, and proposes additive feature attributions (AFAs) based on these solution concepts. Specifically, we first focus on two existing cooperative game–theoretic solution concepts with relatively low computational cost: Equal Surplus (ES)–type solutions and Proportional Allocation (PA)–type solutions. As for ES-type solutions, we first consider the solution defined as the equal-weight average (the so-called “50–50 mixture”) of ES and the Egalitarian Nonseparable Contribution (ENSC), which were intensively studied in the 1990s in works such as Dragan et al. [ 4 ] and Driessen and Funaki [ 5 ] . However, the simple equal-weight average of ES and ENSC does not satisfy the null-player property, as is well known for ES-type solutions. In classical cooperative game theory, where players represent human agents, such a violation may occasionally be considered acceptable. For example, when the value generated by the grand coalition is sufficiently large relative to individual coalition values, one might accept allocating a small share of the surplus even to agents who make no marginal contribution (i.e., null players), reflecting a form of generosity in surplus division. In contrast, such generosity should not be incorporated into the solution of XAI–TU games, where features play the role of players. From the perspective of model explanation, assigning a nonzero attribution to a feature that has no effect on the prediction is undesirable. Therefore, in this paper, we modify the equal-weight average of ES and ENSC so that the resulting solution satisfies the null-player property, and we formulate the modified rule as an additive feature attribution (AFA) method. As for PA-type solutions, we introduce new solution concepts that preserve the ordering of players even in games where positive and negative coalition values coexist. As noted above, in XAI–TU games it is common for positive and negative coalition values to appear within a single game. In such situations, a product between the total surplus to be distributed and the sum of player weights can be negative. When this product is then multiplied by a given player’s weight (which in classical TU games corresponds to v(i) ), proportional allocation rules can lead to situations in which, for example, v(i)>v(j) but player i receives a smaller allocation than player j . As will be discussed in subsequent sections, we refer to this phenomenon as the order-reversal problem . An allocation rule is said to satisfy the order preservation property if the resulting allocation maintains the ranking implied by v(i) even in the presence of such sign conflicts. In this paper, we develop proportional-allocation–type AFAs that satisfy this order-preservation property. Next, we apply the ES-type and PA-type solution concepts, as well as SHAP and its existing approximation algorithms, to actual datasets and conduct a comparative performance analysis. The ES-type AFA introduced above is not only substantially less computationally demanding than Exact SHAP but also requires less computation than existing SHAP approximation methods, such as Permutation SHAP and Kernel SHAP. Moreover, the computational advantage of the ES-type AFA becomes increasingly pronounced as the number of features grows, with the gap expanding exponentially. In terms of approximation accuracy, the ES-type AFA exhibits only small deviations from SHAP and achieves at least comparable approximation quality to existing SHAP approximation methods. In contrast, although PA-type solution concepts are computationally efficient, their deviations from SHAP can be large depending on the model and the number of features. These results strongly suggest that

Read the complete text