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.

Group of individuals discussing around a table with charts and documents.

Group of individuals discussing around a table with charts and documents.

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.

See Also

• Cooperative Game Theory
• Cost Allocation
• Voting System
• Explainable AI
• Public Goods