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. Named after Lloyd Shapley, who introduced it in 1951, it answers the question of how much credit or blame each participant deserves when a collective outcome is produced. The method calculates each player's average marginal contribution across all possible coalitions, ensuring a distribution that satisfies four fundamental properties: efficiency, symmetry, additivity, and the dummy player property. Beyond its origins in economics, the Shapley value has become a cornerstone of interpretable Machine learning, where it is used to attribute the predictions of complex models to individual input features.
The core idea is to evaluate how the overall outcome changes when a player joins each possible subset of other players, then average these changes over all subsets and all possible joining orders. This approach accounts for interactions between players, recognizing that a contribution may depend on who else is already in the coalition. Because it is the only distribution rule that simultaneously satisfies the four axiomatic properties, it is often described as the unique fair way to divide cooperative gains.
Definition
In a coalitional game, a set of players \(N\) can form coalitions \(S \subseteq N\), and a value function \(v(S)\) assigns the total payoff that members of \(S\) can obtain by cooperating. The Shapley value for player \(i\) is given by the formula:
\[\varphi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))\]
where \(n\) is the total number of players. The term \(v(S \cup \{i\}) - v(S)\) is the marginal contribution of player \(i\) to coalition \(S\). The combinatorial weight \(\frac{|S|! (n - |S| - 1)!}{n!}\) accounts for the number of permutations in which the players in \(S\) precede \(i\) and the remaining players follow. An equivalent formulation averages the marginal contribution over all \(n!\) possible orders of the players, where \(P_i^R\) denotes the set of players preceding \(i\) in order \(R\):
\[\varphi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right]\]
This interpretation imagines the coalition being formed one player at a time, with each player receiving their marginal contribution as compensation, and then averaging over all possible formation sequences.
Axiomatic Properties
The Shapley value is uniquely characterized by four axioms, which are widely accepted as defining a fair distribution:
- Efficiency: The sum of all players' Shapley values equals the total value of the grand coalition, \(\sum_{i \in N} \varphi_i(v) = v(N)\). This ensures no value is lost or created.
- Symmetry: If two players \(i\) and \(j\) contribute identically to every coalition (i.e., \(v(S \cup \{i\}) = v(S \cup \{j\})\) for all \(S\) not containing either), they receive equal shares.
- Additivity: For two games \(v\) and \(w\), the Shapley value of the combined game \(v+w\) is the sum of the individual Shapley values, \(\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)\). This property supports decomposition of complex problems.
- Dummy player: If a player \(i\) adds no value to any coalition (i.e., \(v(S \cup \{i\}) = v(S)\) for all \(S\)), their Shapley value is zero.
These axioms were formalized in Shapley's 1951 paper and later refined in his 1953 publication. They ensure that the value is not arbitrary but follows from reasonable fairness criteria.
Applications in Economics and Business
In cooperative game theory, the Shapley value has been used to allocate costs and benefits in various economic settings. For example, in a business partnership, partners can use it to divide profits based on their marginal contributions to different project combinations. It has been applied to cost allocation in joint ventures, such as sharing the cost of a shared infrastructure among multiple users. In supply chain management, it helps determine fair prices for components when firms collaborate to produce a final product. The method is also used in voting power analysis, where it measures the influence of each voter in a weighted voting system, though the closely related Banzhaf power index is sometimes preferred in that context.
Shapley Values in Machine Learning
In Machine learning, the Shapley value has been adapted to explain individual predictions of models, a field known as feature attribution. The players are the input features, and the value function \(v(S)\) is the model's prediction when only the features in subset \(S\) are known, typically by marginalizing out the other features. The Shapley value of a feature measures its average contribution to the prediction, accounting for interactions with all other features. This approach is model-agnostic, meaning it can be applied to any predictive model, including Deep learning networks, Neural network ensembles, and Large language model systems.
A key practical implementation is SHAP (SHapley Additive exPlanations), introduced by Scott Lundberg and Su-In Lee in 2017. SHAP provides efficient algorithms to approximate Shapley values for complex models, as exact computation is exponential in the number of features. The method has become a standard tool for model interpretability, helping data scientists and regulators understand why a model made a particular decision.
Computational Challenges and Approximations
The exact Shapley value requires summing over \(2^n\) subsets, which is computationally infeasible for models with many features. For a model with 30 features, there are over a billion possible coalitions. Several approximation techniques have been developed:
- Monte Carlo sampling: Randomly sample permutations or subsets and average the marginal contributions. This provides an unbiased estimate with a controllable variance.
- SHAP with TreeSHAP: For tree-based models like random forests and gradient boosting, TreeSHAP computes exact Shapley values in polynomial time by exploiting the tree structure.
- KernelSHAP: A model-agnostic method that uses a weighted linear regression to approximate Shapley values, often used for black-box models.
- Gradient-based methods: For differentiable models, approximations can be computed using gradients, though these may not satisfy all axioms exactly.
These approximations have made Shapley values practical for real-world applications, including credit scoring, medical diagnosis, and natural language processing.
Relationship to Other Attribution Methods
The Shapley value is often compared to other feature attribution techniques. Unlike simple methods such as permutation importance or gradient-based saliency maps, Shapley values account for feature interactions and satisfy the efficiency property, ensuring that attributions sum to the model's output. However, it assumes that features are independent when marginalizing, which can lead to unrealistic samples if features are highly correlated. Alternatives like LIME (Local Interpretable Model-agnostic Explanations) are faster but do not guarantee the same axiomatic properties. In cooperative game theory, the Shapley value is one of several solution concepts, including the nucleolus and the core, but it is the only one satisfying all four axioms simultaneously.
Extensions and Variants
Several extensions of the Shapley value have been proposed for different contexts. The weighted Shapley value allows players to have different weights, reflecting unequal bargaining power. The Shapley-Shubik power index applies the value to voting games, measuring the probability that a player is pivotal. In machine learning, variants like Shapley interaction indices decompose the total attribution into main effects and interaction effects between features. For time series data, dynamic Shapley values account for temporal dependencies. These extensions preserve the core idea of fair marginal contribution averaging while adapting to specific problem structures.
Limitations and Criticisms
Despite its theoretical appeal, the Shapley value has limitations. The assumption of feature independence in machine learning applications can produce misleading attributions when features are correlated. The exponential computational cost, even with approximations, can be prohibitive for very high-dimensional data. Additionally, the value function in predictive models is not always well-defined, as marginalizing out features requires a distribution over the feature space, which may not be known. Critics argue that the axiomatic properties, while elegant, may not always align with human notions of fairness in practical scenarios. Nevertheless, the Shapley value remains a foundational concept in both game theory and interpretable AI, with active research addressing these challenges.
Historical Context
Lloyd Shapley introduced the value in 1951 while at the RAND Corporation, and it was formally published in 1953. His work built on earlier ideas in cooperative game theory, particularly the work of John von Neumann and Oskar Morgenstern. Shapley later received the Nobel Memorial Prize in Economic Sciences in 2012, jointly with Alvin Roth, for his contributions to game theory. The Shapley value's adoption in machine learning began in the 2010s, driven by the need for model interpretability as AI systems became more complex. Today, it is a standard tool in the toolkit of data scientists and is implemented in major libraries such as SHAP and scikit-learn.