# A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

arXiv: https://arxiv.org/abs/2603.00496 · HTML: https://mlsanity.com/paper/2603.00496/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 23 references that are in the map.
- First posted on arXiv 28 Feb 2026.

## Builds on (most cited first, 4 of 4)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [On the Robustness of Interpretability Methods](https://mlsanity.com/paper/1806.08049/) (2018)
- [Alternative Methods to SHAP Derived from Properties of Kernels: A Note on Theoretical Analysis](https://mlsanity.com/paper/2406.00371/) (2024)
- [Construction of Compromise Values for Cooperative Games](https://mlsanity.com/paper/2503.05381/) (2025)

## Abstract (arXiv)

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.