Shapley value

The Shapley value is a rule from cooperative game theory for dividing the payoff of a group among its members. Given a set of players and a function stating what payoff each possible subset of them could earn on its own, the rule gives every player the average of the extra payoff that player brings when joining a coalition, averaged over all the orders in which the full group could have been assembled ^[1][2]. Lloyd Shapley introduced it in a 1953 paper, "A Value for n-Person Games," and it has been the reference solution concept for splitting credit on a jointly produced result ever since ^[1][3].

The construction matters to machine learning because a model prediction has the same shape as a coalition payoff. Treat the input features as players and the model output as the payoff, and the Shapley value becomes an attribution scheme that says how much each feature moved the prediction. That is the basis of SHAP, introduced by Scott Lundberg and Su-In Lee at NeurIPS 2017, which is among the most heavily cited feature attribution methods in machine learning ^[4][19]. The same substitution works with training examples as players (data valuation), clients as players (federated learning contribution measurement), and agents as players (credit assignment in multi-agent systems).

The catch is cost. An exact Shapley value requires evaluating the payoff function on every subset of players, so the work grows as 2 to the power of the number of players ^[6]. Almost every deployment in machine learning is therefore an approximation, a model-specific exact algorithm, or both, and much of the research literature since 2017 has been about closing that gap.

Origins

Lloyd Stowell Shapley was born on 2 June 1923 in Cambridge, Massachusetts, took a mathematics degree at Harvard in 1948, and completed a Princeton PhD in 1953 with a dissertation on additive and non-additive set functions ^[3]. He worked at the RAND Corporation from 1954 to 1981, then moved to UCLA, where he held appointments in both mathematics and economics until his death on 12 March 2016 ^[3].

The value appeared in "A Value for n-Person Games," published in Contributions to the Theory of Games, Volume II, edited by Harold Kuhn and Albert Tucker as number 28 in the Annals of Mathematics Studies series (Princeton University Press, 1953), as chapter 17 beginning at page 307 ^[1][2]. Shapley's framing was axiomatic: rather than proposing a formula and defending it, he wrote down properties any reasonable division rule should have and showed that exactly one rule satisfies all of them.

Shapley shared the 2012 Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel with Alvin E. Roth, announced on 15 October 2012, with the motivation "for the theory of stable allocations and the practice of market design" ^[7]. The cited work is the matching theory behind the Gale-Shapley deferred acceptance algorithm, not the Shapley value itself, a distinction often blurred in secondary accounts ^[7].

Definition

A cooperative game with transferable utility is a pair consisting of a player set N of size n and a characteristic function v that maps every subset (coalition) S of N to a real number, with the empty coalition worth zero. The Shapley value of player i is a weighted sum of that player's marginal contributions:

phi_i(v) = sum over every coalition S that excludes player i of
             [ s! * (n - s - 1)! / n! ] * ( v(S with i added) - v(S) )

where s is the number of players in S and n is the total number of players

An equivalent and more intuitive form averages over orderings. Imagine the players arriving one at a time in a random order; each player is credited with whatever they add to the coalition already present when they walk in. Averaging that credit over all n! orderings gives the same number ^[2]:

phi_i(v) = (1/n!) * sum over all n! orderings R of
             ( v(Pred_i(R) with i added) - v(Pred_i(R)) )

where Pred_i(R) is the set of players that precede i in ordering R

The combinatorial weights in the first expression are simply the fraction of orderings that produce each coalition S immediately before player i arrives.

Axioms and uniqueness

Shapley's theorem is that the value is the unique function satisfying four conditions ^[2].

Scroll sideways for more →

Additivity is the axiom that draws the most objection, since it is a mathematical convenience rather than a statement about fairness. H. Peyton Young showed in 1985 that it can be dropped: efficiency, symmetry, and a monotonicity requirement (a player whose contribution to every coalition rises should not see their allocation fall) also single out the Shapley value, without assuming additivity or the dummy condition ^[8]. Young's characterization is what the SHAP authors invoke when they argue that their consistency property forces a unique attribution ^[5].

Computational cost

Exact evaluation touches all 2^n coalitions, and each evaluation may itself be expensive. A survey of the value's machine learning uses puts the general case at "an exponential number of characteristic function evaluations" ^[6]. When the players are training examples, a single characteristic function evaluation means retraining a model, which makes brute force hopeless beyond a very small number of players.

The complexity picture depends on the class of game. Xiaotie Deng and Christos Papadimitriou showed in 1994 that for games defined on a weighted graph, where a coalition is worth the total weight of the edges inside it, the Shapley value is always easy to compute, while the core, kernel, nucleolus, and bargaining set are intractable outside special cases such as convex games ^[9]. For weighted majority voting games the picture is worse: Yasuko Matsui and Tomomi Matsui proved in 2001 that calculating power indices for such games is NP-complete ^[10]. In the machine learning setting, the authors of the tree-based SHAP algorithm write that computing Shapley values exactly is NP-hard, "requiring a summation over all feature subsets" ^[11][16].

Practical work therefore relies on approximation or on structure in the model.

Scroll sideways for more →

For the tree case, T is the number of trees, L the maximum number of leaves in any tree, D the maximum depth, and M the number of features; memory use is O(D^2 + M) ^[13]. The paper reports that an XGBoost model with 1,000 depth-10 trees over 100 input features can be explained in 0.08 seconds under this algorithm ^[13].

SHAP and feature attribution

Erik Strumbelj and Igor Kononenko had already proposed sampling-based Shapley explanations for individual classifications, in the Journal of Machine Learning Research in 2010 and again in Knowledge and Information Systems in 2014 ^[14][15]. The method that made the idea ubiquitous was SHAP (SHapley Additive exPlanations), published by Lundberg and Lee as arXiv preprint 1705.07874 on 22 May 2017 and presented at NeurIPS 2017 ^[4][5].

The paper's argument is a unification. It defines a class of additive feature attribution methods, shows that six existing techniques belong to it, and proves that only one member of the class satisfies three properties simultaneously ^[5]. The three are local accuracy (the attributions add up to the model output for the instance being explained), missingness (a feature absent from the input gets no attribution), and consistency (if a model changes so that a feature's contribution never decreases, its attribution must not decrease either) ^[5]. The six unified methods are LIME, DeepLIFT, layer-wise relevance propagation, Shapley regression values, Shapley sampling values, and quantitative input influence ^[5].

Kernel SHAP is the model-agnostic estimator: it runs a weighted linear regression over sampled coalitions of present and absent features, using a specific weighting kernel chosen so the regression coefficients coincide with Shapley values ^[5]. Tree SHAP is the model-specific one, first described in a 2018 preprint and then developed in Nature Machine Intelligence in 2020 as TreeExplainer, which computes exact Shapley values for tree ensembles in low-order polynomial time ^[11][13][16]. The 2018 preprint also extended SHAP values to interaction effects, defining SHAP interaction values ^[13]. The Nature Machine Intelligence paper (volume 2, issue 1, pages 56 to 67, published 17 January 2020) applied the method to three medical problems, identifying high magnitude but low frequency non-linear mortality risk factors in the general US population, surfacing interaction effects among risk factors for chronic kidney disease, and monitoring a model deployed in a hospital ^[16].

The reference implementation is the shap Python package, created in November 2016 and MIT licensed. As of July 2026 the repository had roughly 25,600 stars and 3,700 forks, and the current release, v0.52.0, shipped on 28 May 2026 with native bindings rewritten in nanobind ^[17][18]. It ships explainers specialized for trees, linear models, and deep networks alongside the model-agnostic kernel method ^[17]. Semantic Scholar's index recorded more than 38,000 citations for the original SHAP paper as of July 2026 ^[19]. Attribution libraries outside the SHAP project carry the method too: Captum, the PyTorch attribution library, ships Shapley value sampling alongside gradient methods such as integrated gradients and saliency ^[36].

SHAP is also used as an inferential tool rather than a purely descriptive one. Work by Andreas Joseph, circulated as Bank of England Staff Working Paper 784, builds an estimation and inference framework for universal function approximators by decomposing predictions into Shapley components, an approach it calls Shapley regressions ^[20].

Data valuation

Swapping features for training examples turns the same machinery into a way of pricing data. Amirata Ghorbani and James Zou introduced "data Shapley" at ICML 2019, defining each training point's value as its Shapley value in a game whose payoff is model performance ^[21]. They reported that it outperforms leave-one-out and leverage scores at identifying valuable points, flags outliers and corrupted labels, and can guide decisions about which additional data to acquire ^[21]. Ruoxi Jia and co-authors published a parallel line of work at AISTATS the same year, focused on approximation algorithms that make the computation affordable ^[22].

The obvious problem is that every characteristic function evaluation is a retraining run. In-Run Data Shapley, presented at ICLR 2025 by Jiachen T. Wang, Prateek Mittal, Dawn Song, and Ruoxi Jia, sidesteps this by computing attributions during a single training run at negligible additional runtime, which the authors report as the first time data attribution has been feasible at foundation model pretraining scale ^[23]. The paper frames the result partly around copyright questions in generative AI, where the practical question is which training sources a given model behavior traces back to ^[23].

Federated learning and multi-agent credit

In federated learning a central server aggregates updates from clients that never share raw data, so paying or ranking those clients requires measuring contribution without inspecting their datasets. GTG-Shapley, described by Zelei Liu and colleagues in 2021, reconstructs candidate federated models from stored gradient updates instead of retraining from scratch, then uses guided Monte Carlo sampling with truncation to cut the number of evaluations ^[24]. Ripple Shapley, presented at AAAI 2026, decomposes each sample's contribution into an immediate performance drop and a recursive term tracking how that influence propagates through later rounds, reporting speedups of up to 62 times over prior Shapley-based federated methods while attributing within a single training run ^[25].

Cooperative credit assignment in reinforcement learning uses the value the same way. Shapley Q-value, presented at AAAI 2020, decomposes a shared global reward into per-agent marginal contributions and uses those as critics, which the authors report improves convergence rates over MADDPG and COMA baselines ^[26].

The pattern has carried into large language model systems. TokenSHAP applies Monte Carlo Shapley estimation to tokens and substrings in a prompt to measure how each part of the input shaped the output ^[27]. RepoShapley, accepted to ACL 2026 Findings, computes exact Shapley values over small sets of retrieved code chunks to decide which context to keep for repository-level code completion, on the grounds that some retrieved snippets help only in combination and others actively interfere ^[28]. SHARP, a 2026 preprint on multi-agent LLM systems, adds a Shapley-based marginal-credit term to the reward so that individual agents in a pipeline are scored by their own contribution rather than by the outcome of the whole trajectory ^[29].

Criticism and known failure modes

The uniqueness theorem is often read as proof that Shapley attributions are the correct explanation of a model. Several lines of work push back on that reading, and they do not all point the same way.

Mukund Sundararajan and Amir Najmi argued in 2020 that there is no single Shapley value for model explanation, because the value depends on how you define "absent" for a feature, and the available choices (marginalizing over the data distribution, conditioning on the remaining features, using a fixed baseline) yield materially different numbers ^[30]. Some formulations even assign non-zero attributions to features the model never reads ^[30]. Hugh Chen, Joseph Janizek, Lundberg, and Lee framed the same choice as being true to the model versus true to the data: interventional conditioning respects what the model actually computes, observational conditioning respects the correlations in the dataset, and the right pick depends on whether you are auditing a credit model or looking for biological signal ^[31].

I. Elizabeth Kumar and co-authors, also at ICML 2020, argued that mathematical problems arise when Shapley values are used as feature importance measures, that fixing them requires causal machinery the standard implementations lack, and that the resulting numbers do not answer the questions human users actually ask ^[32]. Blair Bilodeau, Natasha Jaques, Pang Wei Koh, and Been Kim went further in a 2024 Proceedings of the National Academy of Sciences paper: for model classes as rich as ordinary neural networks, any complete and linear feature attribution method, a description that covers SHAP and integrated gradients, can provably fail to beat random guessing at tasks such as identifying spurious features or providing algorithmic recourse ^[33]. Their recommendation is to define the downstream task first, because repeated direct model evaluation often outperforms attribution for a specific question ^[33].

None of this has displaced SHAP in deployment, and the usual rejoinder is that a clearly stated conditioning scheme plus an honest account of what the numbers do and do not mean is enough for most audit and debugging work. The criticism does establish that the axioms guarantee less about real explanations than the phrase "the unique fair attribution" suggests.

Recent work

Research since 2024 has concentrated on interactions, estimators, and scale. The shapiq package, presented at NeurIPS 2024, extends the SHAP toolkit to Shapley interactions of any order and bundles fourteen approximation algorithms, seven for Shapley values (including KernelSHAP, unbiased KernelSHAP, SVARM, Owen sampling, and stratified sampling) and seven for Shapley interactions, alongside a benchmark suite of eleven applications with pre-computed games and ground-truth values ^[34]. Estimator theory continues to move too: a 2026 preprint by Fabian Fumagalli and co-authors shows that the Shapley value depends only on the odd component of the set function, which explains why paired sampling works and suggests how to filter out the components that do not matter ^[35].

Applied use has spread well beyond feature attribution. ShapLoRA, a January 2026 preprint, treats LoRA ranks as players in a cooperative game and uses the resulting importance scores to decide how much rank to allocate to each layer of a language model backbone ^[37]. Outside machine learning research proper, SHAP has become a routine reporting convention in applied modeling papers, with 2026 examples spanning metro ridership regression, lithium-ion battery state-of-health estimation, and wildfire susceptibility mapping ^[38].

See also

• SHAP
• Explainable AI
• Interpretability
• Feature importance
• Game theory
• Federated learning

References

1. ^Shapley, L. S. "A Value for n-Person Games." In H. W. Kuhn and A. W. Tucker (eds.), *Contributions to the Theory of Games (AM-28), Volume II*, Annals of Mathematics Studies 28, Princeton University Press, 1953, chapter 17, from p. 307. press.princeton.edu/...ry-of-games-am-28-volume-ii
2. ^Wikipedia, "Shapley value." en.wikipedia.org/...Shapley_value
3. ^Wikipedia, "Lloyd Shapley." en.wikipedia.org/...Lloyd_Shapley
4. ^Lundberg, S. M. and Lee, S.-I. "A Unified Approach to Interpreting Model Predictions." *Advances in Neural Information Processing Systems 30* (NIPS 2017). proceedings.neurips.cc/...6c43dfd28b67767-Abstract
5. ^Lundberg, S. and Lee, S.-I. "A Unified Approach to Interpreting Model Predictions." arXiv:1705.07874, submitted 22 May 2017. arxiv.org/...1705.07874
6. ^Rozemberczki, B., Watson, L., Bayer, P., Yang, H.-T., Kiss, O., Nilsson, S. and Sarkar, R. "The Shapley Value in Machine Learning." arXiv:2202.05594, 2022. arxiv.org/...2202.05594
7. ^The Royal Swedish Academy of Sciences, press release for the 2012 Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel, 15 October 2012. nobelprize.org/...press-release
8. ^Young, H. P. "Monotonic solutions of cooperative games." *International Journal of Game Theory* 14 (1985), pp. 65-72. doi.org/...BF01769885
9. ^Deng, X. and Papadimitriou, C. H. "On the Complexity of Cooperative Solution Concepts." *Mathematics of Operations Research* 19(2), 1994, pp. 257-266. pubsonline.informs.org/...moor.19.2.257
10. ^Matsui, Y. and Matsui, T. "NP-completeness for calculating power indices of weighted majority games." *Theoretical Computer Science* 263(1-2), 2001, pp. 305-310. doi.org/...S0304-3975(00)00251-6
11. ^Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N. and Lee, S.-I. "Explainable AI for Trees: From Local Explanations to Global Understanding." arXiv:1905.04610, 2019. arxiv.org/...1905.04610
12. ^Castro, J., Gomez, D. and Tejada, J. "Polynomial calculation of the Shapley value based on sampling." *Computers and Operations Research* 36(5), 2009, pp. 1726-1730. doi.org/...j.cor.2008.04.004
13. ^Lundberg, S. M., Erion, G. G. and Lee, S.-I. "Consistent Individualized Feature Attribution for Tree Ensembles." arXiv:1802.03888, 2018. arxiv.org/...1802.03888
14. ^Strumbelj, E. and Kononenko, I. "An Efficient Explanation of Individual Classifications using Game Theory." *Journal of Machine Learning Research* 11 (2010), pp. 1-18. jmlr.org/...strumbelj10a
15. ^Strumbelj, E. and Kononenko, I. "Explaining prediction models and individual predictions with feature contributions." *Knowledge and Information Systems* 41(3), 2014, pp. 647-665. doi.org/...s10115-013-0679-x
16. ^Lundberg, S. M. et al. "From Local Explanations to Global Understanding with Explainable AI for Trees." *Nature Machine Intelligence* 2 (2020), pp. 56-67. doi.org/...s42256-019-0138-9
17. ^shap/shap repository, GitHub. github.com/...shap
18. ^shap release history (v0.52.0, published 28 May 2026). github.com/...releases
19. ^Semantic Scholar record for "A Unified Approach to Interpreting Model Predictions" (citation count 38,065, retrieved July 2026). api.semanticscholar.org/...arXiv:1705.07874
20. ^Joseph, A. "From interpretability to inference: an estimation framework for universal approximators." arXiv:1903.04209, submitted 11 March 2019, last revised 5 December 2024; circulated as Bank of England Staff Working Paper No. 784. arxiv.org/...1903.04209
21. ^Ghorbani, A. and Zou, J. "Data Shapley: Equitable Valuation of Data for Machine Learning." *Proceedings of the 36th International Conference on Machine Learning*, PMLR 97, 2019, pp. 2242-2251. proceedings.mlr.press/...ghorbani19c
22. ^Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gurel, N. M., Li, B., Zhang, C., Song, D. and Spanos, C. J. "Towards Efficient Data Valuation Based on the Shapley Value." *AISTATS*, PMLR 89, 2019, pp. 1167-1176. proceedings.mlr.press/...jia19a
23. ^Wang, J. T., Mittal, P., Song, D. and Jia, R. "Data Shapley in One Training Run." arXiv:2406.11011; ICLR 2025. arxiv.org/...2406.11011
24. ^Liu, Z., Chen, Y., Yu, H., Liu, Y. and Cui, L. "GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning." arXiv:2109.02053, 2021. arxiv.org/...2109.02053
25. ^Zeng, D., Tian, W., Wang, H., Lu, J., Xiao, W. and Xu, Z. "Ripple Shapley: Data Influence Attribution in One Federated Training Run." *Proceedings of the AAAI Conference on Artificial Intelligence*, Vol. 40 No. 33 (AAAI-26), 2026. ojs.aaai.org/...40034
26. ^Wang, J., Zhang, Y., Kim, T.-K. and Gu, Y. "Shapley Q-value: A Local Reward Approach to Solve Global Reward Games." arXiv:1907.05707; AAAI 2020. arxiv.org/...1907.05707
27. ^Goldshmidt, R. and Horovicz, M. "TokenSHAP: Interpreting Large Language Models with Monte Carlo Shapley Value Estimation." arXiv:2407.10114, 2024. arxiv.org/...2407.10114
28. ^Huo, Y., Zeng, K., Zhang, S., Lu, Y., Yang, C., Guo, Y. and Tang, X. "RepoShapley: Shapley-Enhanced Context Filtering for Repository-Level Code Completion." arXiv:2601.03378; ACL 2026 Findings. arxiv.org/...2601.03378
29. ^Li, Y. et al. "Who Deserves the Reward? SHARP: Shapley Credit-based Optimization for Multi-Agent System." arXiv:2602.08335, 2026. arxiv.org/...2602.08335
30. ^Sundararajan, M. and Najmi, A. "The many Shapley values for model explanation." arXiv:1908.08474, 2019-2020. arxiv.org/...1908.08474
31. ^Chen, H., Janizek, J. D., Lundberg, S. and Lee, S.-I. "True to the Model or True to the Data?" arXiv:2006.16234, 2020. arxiv.org/...2006.16234
32. ^Kumar, I. E., Venkatasubramanian, S., Scheidegger, C. and Friedler, S. "Problems with Shapley-value-based explanations as feature importance measures." arXiv:2002.11097; ICML 2020. arxiv.org/...2002.11097
33. ^Bilodeau, B., Jaques, N., Koh, P. W. and Kim, B. "Impossibility Theorems for Feature Attribution." *Proceedings of the National Academy of Sciences* 121(2), 2024; arXiv:2212.11870. arxiv.org/...2212.11870
34. ^Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Hammer, B. and Hullermeier, E. "shapiq: Shapley Interactions for Machine Learning." arXiv:2410.01649; NeurIPS 2024. arxiv.org/...2410.01649
35. ^Fumagalli, F., Butler, L., Kang, J. S., Ramchandran, K. and Witter, R. T. "An Odd Estimator for Shapley Values." arXiv:2602.01399, 2026. arxiv.org/...2602.01399
36. ^pytorch/captum repository, GitHub (attribution algorithm list). github.com/...captum
37. ^Zhao, Y., Yao, Q., Song, X. and Zhu, W. "ShapLoRA: Allocation of Low-rank Adaption on Large Language Models via Shapley Value Inspired Importance Estimation." arXiv:2601.17921, 25 January 2026. arxiv.org/...2601.17921
38. ^Semantic Scholar, paper search for "SHAP Shapley" restricted to publication year 2026 (retrieved July 2026). api.semanticscholar.org/...search