What is the Shapley Value in Cooperative Game Theory?

This article provides a comprehensive overview of the Shapley value, a fundamental concept in cooperative game theory. It explains how the Shapley value fairly distributes joint gains or costs among players in a coalition, details the core axioms that define it, and highlights its modern applications in economics and machine learning.

Understanding the Shapley Value

In cooperative game theory, players form coalitions to achieve a common goal that yields a certain payoff or savings. The central question is: how should this total payoff be divided among the participants in a way that is fair and reflective of each individual’s contribution?

Introduced by Lloyd Shapley in 1953, the Shapley value solves this problem by calculating the average marginal contribution of each player across all possible coalitions that could be formed. It ensures that every player receives a payout proportional to their importance to the group’s success.

How the Shapley Value is Calculated

To determine a player’s Shapley value, you must consider every possible order in which the players could join the coalition. The calculation follows these steps:

1. List all permutations: Determine all possible sequences in which players can enter the game.
2. Calculate marginal contributions: For each sequence, calculate how much value a specific player adds when they join the already existing subgroup of players.
3. Average the contributions: Sum these marginal contributions across all permutations and divide by the total number of permutations (which is \(N!\), where \(N\) is the number of players).

By averaging the marginal contributions over all possible orderings, the Shapley value accounts for the fact that a player’s contribution might depend on who is already in the coalition.

The Four Axioms of Fairness

The Shapley value is highly regarded because it is the only distribution method that satisfies four fundamental axioms of fairness:

• Efficiency: The sum of the Shapley values of all players equals the total value generated by the grand coalition. No resources are left over, and no extra resources are needed.
• Symmetry: If two players contribute exactly the same marginal value to any given coalition, they receive equal Shapley values.
• Dummy Player (Null Player): If a player contributes nothing to any coalition they join, their Shapley value is zero (or equal to the individual value they could generate alone).
• Additivity: If a group plays two independent games, a player’s total payoff from both games combined is the sum of their payoffs from each game played separately.

Real-World Applications

While initially a theoretical concept, the Shapley value is widely used today in several practical fields:

• Explainable Artificial Intelligence (XAI): In machine learning, the “SHAP” (SHapley Additive exPlanations) framework uses the Shapley value to explain individual predictions. Features of a model are treated as players in a game, and the Shapley value determines the impact of each feature on the final output.
• Cost Allocation: Businesses and governments use it to fairly distribute shared infrastructure costs—such as airport runways or municipal water systems—among different user groups.
• Political Power Indexes: In political science, the Shapley-Shubik power index applies this concept to voting bodies to measure the actual voting power of different political parties or coalition members.