A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

This paper introduces ESENSC_rev2, a computationally efficient, polynomial-time feature attribution rule grounded in cooperative game theory and a novel axiomatic framework that approximates SHAP accuracy while significantly improving scalability for high-dimensional explainability tasks.

The Gist

Imagine you have a team of 100 people working together to bake a giant, delicious cake. The cake turns out amazing, and it sells for \1,000. Now, the big question is: **How do you split that \1,000 fairly among the 100 people?**

Maybe one person brought the best flour, another had the perfect oven, and a third just showed up and stood there doing nothing. You want to know exactly how much credit (or blame) each person deserves for the final result.

In the world of Artificial Intelligence (AI), this is called Feature Attribution. The "cake" is the AI's prediction, the "people" are the data features (like income, age, or location), and the "split" is figuring out which features caused the AI to make a specific decision.

The Problem with the Current Gold Standard (SHAP)

For a long time, the most popular way to solve this cake-splitting problem has been a method called SHAP. It's based on a mathematical concept called the "Shapley Value."

Think of SHAP as the ultimate, fair judge. To figure out how much credit the "Flour Guy" deserves, SHAP doesn't just look at him once. It simulates thousands of different scenarios:

• What if we bake the cake with only flour?
• What if we bake it with flour and sugar, but no eggs?
• What if we bake it with flour, sugar, and eggs, but no oven?

It calculates the difference in the cake's quality for every single possible combination of ingredients. If you have 10 ingredients, that's easy. But if you have 100 ingredients (which is common in AI), the number of combinations becomes astronomical. It's like trying to taste every possible combination of ingredients in the universe.

The Result: SHAP is incredibly fair, but it takes forever to compute. It's so slow that for large AI models, it's practically impossible to use.

The Paper's Solution: A Faster, Smarter Alternative

The authors of this paper asked: "Can we find a rule that is almost as fair as SHAP, but doesn't take a million years to calculate?"

They looked at two older, simpler ways of splitting the cake:

1. The "Equal Surplus" Rule: Everyone gets their basic contribution first (e.g., the value of just the flour), and then any extra profit is split equally among everyone.
2. The "Reverse" Rule: Imagine starting with the full cake and removing one ingredient at a time. How much value did we lose? That's what the ingredient is worth.

The authors realized that if you just mix these two rules together, you get a fast method. However, there was a catch: sometimes these simple rules would give credit to the person who stood there doing nothing (the "Null Player"). In AI, if a feature has zero effect on the prediction, it should get zero credit. Giving it credit is like paying the guy who just stood in the corner for the whole baking session.

The Innovation: The authors tweaked the math to create a new rule called ESENSC_rev2.

• It combines the speed of the simple rules.
• It strictly ensures that if a feature does nothing, it gets zero credit.
• It avoids the "Order Reversal" trap (a weird glitch where a bad ingredient gets a huge positive score just because of how the math works).

The Results: Speed vs. Accuracy

The authors ran experiments comparing their new rule against the slow, perfect SHAP and other fast approximations.

• Speed: Their new rule is blazing fast. While SHAP's time explodes exponentially as you add more features (like a snowball rolling down a hill getting huge), their rule stays linear and manageable. It's like switching from a horse-drawn carriage to a sports car.
• Accuracy: Surprisingly, their fast rule is almost identical to the slow, perfect SHAP. The difference in the final "cake split" is tiny.
• The Competitors: Other fast methods they tested (like "Proportional Allocation") were fast but sometimes gave weird, unfair results, like giving a huge bonus to a feature that actually hurt the prediction.

The "Why" (The Axioms)

To prove their rule isn't just a lucky guess, the authors used a set of logical rules (called Axioms) to show that their method is the only one that fits a specific set of criteria:

1. Efficiency: The total credit must equal the total value of the cake.
2. No Free Riders: If you do nothing, you get nothing.
3. Simplicity: You don't need to check every single combination of ingredients; just the basics are enough.

They proved that if you want a method that is fast, fair, and respects these rules, ESENSC_rev2 is the unique solution.

The Takeaway

This paper offers a practical tool for the AI world. It says: "You don't need to wait forever to explain your AI. You can use this new, super-fast rule that is mathematically proven to be fair and nearly as accurate as the gold standard."

It's like realizing you don't need to taste every single possible cake combination to know who the best baker is; you just need a smart, quick recipe that gets you 99% of the way there in a fraction of the time.

Technical Summary

1. Problem Statement

Explainable AI (XAI) relies heavily on Additive Feature Attribution (AFA) methods to decompose a model's prediction into contributions from individual features. SHAP (SHapley Additive exPlanations), based on the Shapley value from cooperative game theory, is the industry standard due to its strong theoretical guarantees (efficiency, symmetry, null-player property, etc.).

However, SHAP faces two critical limitations:

1. Computational Infeasibility: Calculating the exact Shapley value requires evaluating $2^n$ coalitions, where $n$ is the number of features. This exponential complexity makes exact SHAP infeasible for high-dimensional datasets.
2. Approximation Instability: Existing approximation algorithms (e.g., Kernel SHAP, Permutation SHAP) reduce computational cost but often suffer from unstable accuracy, require tuning parameters (e.g., number of samples), and do not strictly satisfy the theoretical axioms of the Shapley value.

The paper seeks a computationally efficient (polynomial-time) alternative that maintains high approximation accuracy to exact SHAP while satisfying rigorous axiomatic properties tailored to the specific structure of XAI problems.

2. Methodology

2.1 Formulation: XAI–TU Games

The authors formalize feature attribution as a Transferable Utility (TU) cooperative game, termed an XAI–TU game.

• Players: The set of features $N = \{1, \dots, n\}$.
• Characteristic Function: For a specific observation $x$, the value of a coalition $S$ is defined as the expected model prediction when features in $S$ are fixed to their observed values, and features in $N \setminus S$ are drawn from the empirical distribution (interventional formulation):
  $$v(S) = \mathbb{E}[f(x_S, X_{N \setminus S})]$$
• Distinctive Features: Unlike classical TU games where $v(\emptyset)=0$, in XAI–TU games, $v(\emptyset)$ (the baseline prediction) is generally non-zero. Furthermore, coalition values can be positive or negative, and the sum of individual marginal contributions may not align with the total surplus, leading to potential "order-reversal" issues in standard allocation rules.

2.2 Proposed Solution: ESENSC_rev2

The authors investigate two classes of low-cost solution concepts from cooperative game theory: Equal Surplus (ES) and Proportional Allocation (PA).

• The ES-Type Approach:

  • They start with the Equal Surplus (ES) and Egalitarian Nonseparable Contribution (ENSC) solutions.
  • A simple 50-50 mixture of ES and ENSC ($\psi_{ESENSC}$) is computationally cheap ($O(n)$) but violates the null-player property (assigning non-zero values to features with no marginal impact).
  • Modification: To fix this, they propose $\psi_{ESENSC\_rev2}$. This rule:
    1. Calculates the average of the marginal contribution from the empty set ($v(i) - v(\emptyset)$) and the marginal contribution from the grand coalition ($v(N) - v(N \setminus i)$).
    2. Distributes the remaining surplus equally, but only among features that have non-zero marginal contributions in either direction.
    3. If a feature has zero marginal contribution in both directions, it is assigned a value of 0.

• The PA-Type Approach:

  • The authors also explore Proportional Allocation (PA) and a "Reverse PA" (RPA) to handle cases where total surplus and sum of marginal contributions have opposite signs (which causes order-reversal).
  • They propose a hybrid rule ($\psi_{PARPA}$) that switches between PA and RPA based on sign configurations.
  • Result: Empirical results show that while PA-type rules are efficient, they suffer from large deviations from exact SHAP and instability, making them less suitable than the ES-type approach.

2.3 Axiomatic Characterization

The paper provides a theoretical proof that $\psi_{ESENSC\_rev2}$ is the unique solution satisfying a specific set of axioms:

1. Efficiency: The sum of attributions equals the total prediction difference ($v(N) - v(\emptyset)$).
2. Null-Player Property: Features with no marginal impact receive zero attribution.
3. Restricted Differential Marginality: A weakened version of the standard differential marginality axiom, restricted to games where players have non-zero marginal effects.
4. Intermediate Inessential Game: In specific "inessential" games, the rule assigns the average of the optimistic and pessimistic marginal contributions.
5. Reduction in Computational Complexity: The solution depends only on coalition values of size 0, 1, $n-1$, and $n$ (ignoring intermediate coalition sizes), ensuring polynomial-time computation.

3. Key Contributions

1. Formalization of XAI–TU Games: The paper rigorously defines the structural properties of feature attribution games, highlighting how they differ from classical cooperative games (e.g., non-zero baselines, mixed signs).
2. Development of ESENSC_rev2: It introduces a novel, polynomial-time attribution rule that combines the computational efficiency of ES/ENSC with the null-player property required for interpretable AI.
3. Axiomatic Justification: It is the first study to provide an axiomatic characterization for a polynomial-time feature attribution rule that approximates SHAP. It clarifies the trade-off between the strong symmetry axioms of SHAP and the computational tractability required for high-dimensional data.
4. Empirical Validation: Extensive experiments on tabular data (California Housing) using XGBoost and Neural Networks demonstrate that the proposed method scales linearly with feature count, whereas exact SHAP scales exponentially.

4. Experimental Results

• Approximation Accuracy:
  • $\psi_{ESENSC\_rev2}$ closely approximates exact SHAP. Its deviation is comparable to Permutation SHAP and significantly better than Kernel SHAP.
  • PA-type rules (even the modified $\psi_{PARPA}$) showed large and unstable deviations from exact SHAP, particularly as the number of features increased.
• Computational Efficiency:
  • Exact SHAP: Exponential growth in computation time; becomes infeasible for $n > 16$.
  • Proposed AFA ($\psi_{ESENSC\_rev2}$): Linear growth in computation time. It is orders of magnitude faster than sampling-based approximations (Permutation/Kernel SHAP) and requires no tuning parameters (unlike sampling methods which trade accuracy for speed).
  • The method remains efficient even with up to 512 features.

5. Significance

• Practical Alternative to SHAP: The paper offers a theoretically grounded, parameter-free, and computationally efficient alternative to SHAP. It is particularly valuable for high-dimensional datasets where exact SHAP is impossible and sampling-based approximations are too slow or unstable.
• Theoretical Insight: By characterizing the rule via axioms, the authors clarify why this specific rule works: it balances fairness (via the intermediate inessential game axiom) with the practical necessity of ignoring computationally expensive coalition interactions.
• Robustness: The method avoids the "order-reversal" and instability issues found in proportional allocation methods, making it a more reliable tool for modern explainability pipelines.

In conclusion, ESENSC_rev2 represents a significant step forward in XAI, bridging the gap between the theoretical rigor of the Shapley value and the computational constraints of modern machine learning applications.