Shapley Value
Introduction
The Shapley Value is a solution concept in cooperative game theory named after Lloyd Shapley. It represents a method for distributing the total gains (or costs) among the players based on their individual contributions to the total payoff. The Shapley Value is widely used in economics, political science, and various fields of engineering, particularly in situations where the contribution of each participant to the collective outcome needs to be fairly assessed.
Definition and Mathematical Formulation
The Shapley Value is defined for a cooperative game with a set of players \( N \) and a characteristic function \( v \) that assigns a value to every coalition of players. Formally, the Shapley Value for a player \( i \) in a game \( (N, v) \) is given by:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (|N| - |S| - 1)!}{|N|!} [v(S \cup \{i\}) - v(S)] \]
where: - \( S \) is a subset of players not including \( i \), - \( |S| \) is the number of players in \( S \), - \( v(S) \) is the value of coalition \( S \), - \( |N| \) is the total number of players.
This formula ensures that the value assigned to each player reflects their marginal contribution to every possible coalition.
Properties of the Shapley Value
The Shapley Value has several important properties that make it a desirable solution concept in cooperative game theory:
Efficiency
The total value distributed among all players equals the value of the grand coalition \( N \): \[ \sum_{i \in N} \phi_i(v) = v(N) \]
Symmetry
If two players contribute equally to all coalitions, they receive the same value: If \( v(S \cup \{i\}) = v(S \cup \{j\}) \) for all \( S \subseteq N \setminus \{i, j\} \), then \( \phi_i(v) = \phi_j(v) \).
Linearity
The Shapley Value is linear with respect to the characteristic function: \[ \phi_i(v + w) = \phi_i(v) + \phi_i(w) \] for any two games \( v \) and \( w \).
Null Player
A player who does not contribute to any coalition receives a value of zero: If \( v(S \cup \{i\}) = v(S) \) for all \( S \subseteq N \), then \( \phi_i(v) = 0 \).
Applications
The Shapley Value has a wide range of applications across different fields:
Economics
In economics, the Shapley Value is used to allocate costs or benefits among participants in joint ventures, public goods provision, and cost-sharing problems. For example, in cost allocation problems, the Shapley Value provides a fair distribution of costs among users based on their usage.
Political Science
In political science, the Shapley Value is applied to measure the power of different players in voting games. It helps in understanding the influence of individual voters or parties in a voting system.
Network Analysis
In network analysis, the Shapley Value is used to determine the importance of nodes in a network. It helps in identifying key nodes that contribute significantly to the connectivity or functionality of the network.
Machine Learning
In machine learning, the Shapley Value is used to interpret the contribution of individual features to the prediction of a model. This is particularly useful in explainable AI to understand the importance of different features in a predictive model.
Calculation Methods
Calculating the Shapley Value can be computationally intensive, especially for large games with many players. Several methods have been developed to approximate the Shapley Value efficiently:
Exact Calculation
The exact calculation involves evaluating the marginal contribution of each player to all possible coalitions, which can be computationally expensive for large \( N \).
Monte Carlo Simulation
Monte Carlo simulation is a popular method for approximating the Shapley Value. It involves randomly sampling coalitions and averaging the marginal contributions of players across these samples.
Approximation Algorithms
Various approximation algorithms have been developed to estimate the Shapley Value with reduced computational complexity. These algorithms leverage properties of the game or specific structures within the characteristic function to provide efficient approximations.
Extensions and Variants
Several extensions and variants of the Shapley Value have been proposed to address specific scenarios or to relax some of its assumptions:
Weighted Shapley Value
The weighted Shapley Value assigns different weights to players, reflecting their relative importance or bargaining power. The formula is adjusted to account for these weights, providing a more tailored distribution of value.
Aumann-Shapley Value
The Aumann-Shapley Value extends the Shapley Value to situations with a continuum of players. It is used in contexts where the set of players is not finite, such as in public goods provision with a large population.
Shapley-Shubik Power Index
The Shapley-Shubik Power Index is a variant of the Shapley Value used specifically in voting games. It measures the power of players (voters) in terms of their ability to influence the outcome of a vote.
Criticisms and Limitations
While the Shapley Value is a powerful and widely used concept, it is not without criticisms and limitations:
Computational Complexity
The exact calculation of the Shapley Value can be computationally prohibitive for large games, limiting its practical applicability in some scenarios.
Assumptions of Rationality
The Shapley Value assumes that players are rational and will cooperate to maximize their collective payoff. In real-world scenarios, players may not always behave rationally or cooperatively.
Sensitivity to Characteristic Function
The Shapley Value is highly sensitive to the specification of the characteristic function. Small changes in the function can lead to significant changes in the value distribution, which may not always be desirable.
Conclusion
The Shapley Value remains a fundamental concept in cooperative game theory, offering a fair and systematic method for distributing value among players based on their contributions. Despite its computational challenges and assumptions, it continues to be a valuable tool in economics, political science, network analysis, and machine learning.