# Shapley Value

The Shapley value is a game-theoretic solution concept that fairly distributes total gains or costs among cooperating players, based on average marginal contributions. It is widely used in machine learning for feature attribution and model interpretability.

The Shapley value is a solution concept in cooperative game theory that provides a method for fairly distributing the total gains or costs among a group of players who have collaborated. It was introduced by Lloyd Shapley in 1951 and has since become a fundamental tool in economics, political science, and more recently, in machine learning for interpreting model predictions. The value assigns each player a share of the total payoff based on their average marginal contribution across all possible coalitions of other players. It is the unique distribution that satisfies four key properties: efficiency, symmetry, additivity, and the dummy player property, making it a widely accepted standard for fair allocation.

In the context of machine learning, the Shapley value is used to explain individual predictions by attributing the contribution of each feature to the model's output. This approach, often referred to as SHAP (SHapley Additive exPlanations), provides a unified framework for feature importance that is both theoretically grounded and practically applicable. The computational complexity of calculating exact Shapley values grows exponentially with the number of features, leading to the development of various approximation methods.

## Definition and Formula

Formally, consider a cooperative game with a set of players \( N \) and a value function \( v \) that assigns a real number to each subset (coalition) \( S \subseteq N \). The Shapley value for player \( i \) is defined as:

\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) \]

where \( n = |N| \). This formula can be interpreted as the average marginal contribution of player \( i \) over all possible orders in which the coalition can be formed. An equivalent formulation sums over all \( n! \) permutations of players, where \( P_i^R \) is the set of players preceding \( i \) in order \( R \):

\[ \phi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right] \]

The value function \( v(S) \) represents the total payoff that coalition \( S \) can achieve by cooperating. The Shapley value distributes the total value \( v(N) \) among all players, ensuring that each player receives their average contribution to the overall outcome.

## Properties

The Shapley value is the only solution concept that satisfies the following four axioms, which are considered essential for a fair distribution:

- **Efficiency**: The sum of all Shapley values equals the total value of the grand coalition, \( \sum_{i \in N} \phi_i(v) = v(N) \). This ensures that the entire payoff is distributed.
- **Symmetry**: If two players \( i \) and \( j \) contribute equally to all coalitions (i.e., \( v(S \cup \{i\}) = v(S \cup \{j\}) \) for all \( S \subseteq N \setminus \{i,j\} \)), then they receive the same Shapley value. This guarantees fairness among identical contributors.
- **Additivity**: For any two games \( v \) and \( w \), the Shapley value of the combined game \( v + w \) is the sum of the Shapley values of the individual games, \( \phi_i(v + w) = \phi_i(v) + \phi_i(w) \). This property allows for decomposition of complex games.
- **Dummy player property**: If a player \( i \) adds no value to any coalition (i.e., \( v(S \cup \{i\}) = v(S) \) for all \( S \subseteq N \setminus \{i\} \)), then \( \phi_i(v) = 0 \). This ensures that players who do not contribute receive nothing.

These properties make the Shapley value a unique and principled method for allocating credit or cost among participants.

## Applications in Machine Learning

In machine learning, the Shapley value is applied to interpret model predictions by treating each feature as a player and the model's output as the value function. For a given prediction, the Shapley value of a feature quantifies its contribution to the difference between the model's output and the average prediction. This approach, known as SHAP, was popularized by Scott Lundberg and Su-In Lee in 2017. SHAP values provide a unified measure of feature importance that is consistent with the axioms of the Shapley value, making them a reliable tool for model interpretability.

The use of Shapley values in machine learning has grown significantly, particularly in fields where understanding model decisions is critical, such as finance, healthcare, and autonomous systems. For example, in credit scoring, SHAP values can reveal which factors most influence a loan approval decision, aiding in regulatory compliance and fairness audits. In medical diagnosis, they help clinicians understand why a model predicts a certain condition, increasing trust in AI-assisted decisions.

## Computational Challenges

Calculating exact Shapley values requires evaluating the value function for all \( 2^n \) possible coalitions, which is computationally infeasible for models with many features. For a model with \( n \) features, the complexity is \( O(2^n) \), making exact computation impractical beyond a few dozen features. To address this, several approximation methods have been developed:

- **Monte Carlo sampling**: Randomly sample permutations of features and average the marginal contributions, providing an unbiased estimate with a controllable variance.
- **TreeSHAP**: An algorithm specifically designed for tree-based models (e.g., random forests, gradient boosting) that computes exact Shapley values in polynomial time by exploiting the structure of decision trees.
- **KernelSHAP**: A model-agnostic method that uses a weighted linear regression to approximate Shapley values, suitable for any black-box model.
- **Gradient-based methods**: For neural networks, approximations using gradients or attention mechanisms can provide fast estimates, though they may not satisfy all Shapley axioms.

These approximations have made it feasible to apply Shapley values to large-scale machine learning models, including deep neural networks and large language models, where interpretability is increasingly important.

## Related Concepts and Extensions

The Shapley value has been extended and adapted in various ways to address different needs. In cooperative game theory, the Shapley-Shubik power index and the Banzhaf power index are specialized applications for voting games. In machine learning, SHAP has been extended to handle interactions between features, providing second-order attributions that capture synergistic effects. Additionally, the concept has been applied to explain the behavior of [large language models](https://www.wikiprompt.org/wiki/large-language-model), where it helps identify which parts of the input text most influence the generated output.

The Shapley value is also related to other attribution methods, such as LIME (Local Interpretable Model-agnostic Explanations), but it offers stronger theoretical guarantees due to its axiomatic foundation. While LIME focuses on local fidelity, SHAP ensures consistency and local accuracy, making it a preferred choice in many practical applications.

## Historical Context

Lloyd Shapley introduced the concept in his 1951 paper "A Value for n-Person Games," which laid the groundwork for cooperative game theory. His work earned him the Nobel Memorial Prize in Economic Sciences in 2012, shared with Alvin Roth, for contributions to the theory of stable allocations and the practice of market design. The Shapley value has since become a cornerstone of economic theory, influencing fields such as cost allocation, profit sharing, and network analysis.

In the 2010s, the rise of machine learning and the need for model interpretability brought the Shapley value into the spotlight. Researchers recognized that the axioms of fairness in cooperative games align with the requirements for explaining model predictions, leading to the development of SHAP and its widespread adoption. Today, the Shapley value is a standard tool in the toolkit of data scientists and AI researchers, bridging the gap between game theory and modern artificial intelligence.

## See Also

- [Machine Learning](https://www.wikiprompt.org/wiki/machine-learning)
- [Artificial Intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence)
- [Deep Learning](https://www.wikiprompt.org/wiki/deep-learning)
- [Neural Network](https://www.wikiprompt.org/wiki/neural-network)
- [Model Pruning](https://www.wikiprompt.org/wiki/model-pruning)
- [Data Augmentation](https://www.wikiprompt.org/wiki/data-augmentation)

## References

- Shapley, L. S. (1951). "A Value for n-Person Games." In Contributions to the Theory of Games, volume II.
- Lundberg, S. M., & Lee, S.-I. (2017). "A Unified Approach to Interpreting Model Predictions." Advances in Neural Information Processing Systems.
- Strumbelj, E., & Kononenko, I. (2014). "Explaining Prediction Models and Individual Predictions with Feature Contributions." Knowledge and Information Systems.

---
Source: https://www.wikiprompt.org/wiki/shapley-value
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-12T16:21:19.540944+00:00