cs.LGFeb 28, 2026

A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Authors: Kazuhiro Hiraki, Shinichi Ishihara, Takumi Kongo, Junnosuke Shino

Organizations: International Monetary Fund · Independent Researcher · Fukuoka University · Waseda University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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, 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 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 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.

Figures & tables

Table 1: PA and RPA: cases where the order-reversal problem does not arise (“OK”)
AFAEquationLiterature / Description
ψjSHAP\psi_{j}^{SHAP}( 2 )Formulated in Lundberg and Lee [ 13 ] . Based on the Shapley value [ 18 ] .
ψjES\psi_{j}^{ES}( 3 )Proposed in Condevaux et al. [ 3 ] . Based on Equal Surplus (ES).
ψjENSC\psi_{j}^{ENSC}( 4 )Based on Egalitarian Non-Separable Contribution (ENSC) [ 4 , 5 ] .
ψjESENSC_rev2\psi_{j}^{ESENSC\_rev2}( 9 )50–50 mixture of ES and ENSC, modified to satisfy the null-player property.
ψjPAROP\psi_{j}^{PAROP}( 12 )50–50 mixture of proportional rules based on v(i)−v(∅)v(i)-v(\emptyset) and v(N)−v(N∖i)v(N)-v(N\setminus i) .
ψjPARPA\psi_{j}^{PARPA}( 15 )A proportional-allocation–type solution adjusted to avoid the “order-reversal problem.”
Table 2: Summary of AFAs Used in the Experiments
Figure 1: Deviation from SHAP (1) neural net model
Figure 2: Deviation from SHAP (2) XGBoost model
Figure 3: Computation time (1) Neural net model
Figure 4: Computation time (2) XGBoost model
More in this topic

Feature Attribution

Feature attribution estimates which input features or internal components contribute to a model’s predictions.

See all 225 papers

Explore similar work

CardsList
Jun 23, 2026

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is #P\#P-hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.

Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Departamento de Computación, Facultad de Ciencias Exactas y Naturales, UBA · Instituto de Ciencias de la Computación (ICC), CONICET

Cooperative Game TheoryFeature AttributionCausal AttributionShapley Value AttributionCausal Interpretability
AskPDF
Feb 26, 2026

Fair feature attribution for multi-output prediction: a Shapley-based perspective

In this article, we provide an axiomatic characterization of feature attribution for multi-output predictors within the Shapley framework. While SHAP explanations are routinely computed independently for each output coordinate, the theoretical necessity of this practice has remained unclear. By extending the classical Shapley axioms to vector-valued cooperative games, we establish a rigidity theorem showing that any attribution rule satisfying efficiency, symmetry, dummy player, and additivity must necessarily decompose component-wise across outputs. Consequently, any joint-output attribution rule must relax at least one of the classical Shapley axioms. This result identifies a previously unformalized structural constraint in Shapley-based interpretability, clarifying the precise scope of fairness-consistent explanations in multi-output learning. Numerical experiments on a biomedical benchmark illustrate that multi-output models can yield computational savings in training and deployment, while producing SHAP explanations that remain fully consistent with the component-wise structure imposed by the Shapley axioms.

Umberto Biccari, Alain Ibáñez de Opakua, José María Mato +3

Feature AttributionShapley Value AttributionCooperative Game Theory
AskPDF
Aug 11, 2026

RelShap: Relationally Consistent Shapley Explanations

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not. Our code is available at: https://github.com/duneag2/relshap.

Seungeun Lee, Joao Fonseca, Julia Stoyanovich

New York University, New York, USA · INESC-ID, Lisbon, Portugal

Feature AttributionShapley Value Attribution
AskPDF