Shapley Value in Game Theory: Definition, Application, and Example

Table of Contents#

• What is the Shapley Value?
• Game Theory Context: Coalitions and Payoffs
• How Shapley Value Works: Mathematical Framework
• Key Properties of Shapley Value
• Example: Applying Shapley Value in a Coalition Game
• Real-World Applications of Shapley Value
• Conclusion

What is the Shapley Value?#

The Shapley Value is a solution concept for cooperative games (where players form coalitions to maximize joint payoffs). It answers: How should the total payoff of a coalition be divided among its members, considering their unique contributions?

• Cooperative Games: Players work together (rather than competing) to achieve a shared goal (e.g., building a product, delivering a service).
• Unequal Contributions: Players’ individual contributions to subsets of the coalition (not just the “grand coalition” of all players) determine their fair share.

Game Theory Context: Coalitions and Payoffs#

In game theory, a “coalition” is any subset of players. A characteristic function $v(S)$ defines the total payoff (or cost) a coalition $S$ can generate independently. The Shapley Value focuses on the grand coalition (all players, $S = N$) and distributes $v(N)$ fairly by analyzing:

• Marginal contributions: How much a player adds to a coalition when joining (compared to the coalition’s value without them).
• All permutations of coalition formation: Every possible order of players joining the coalition is considered to average out biases (e.g., who joins first/last).

How Shapley Value Works: Mathematical Framework#

For a game with $n$ players, the Shapley Value $\phi_i$ for player $i$ is calculated as:

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

Breakdown of the Formula:#

1. $S$: All subsets of players excluding $i$ (i.e., coalitions $S$ that exist before $i$ joins).
2. $v(S \cup \{i\}) - v(S)$: The marginal contribution of $i$ to coalition $S$ (value added when $i$ joins $S$).
3. $\frac{|S|! \cdot (n - |S| - 1)!}{n!}$: The probability (or weight) of coalition $S$ forming before $i$ (derived from all permutations of $n$ players).

Key Properties of Shapley Value#

The Shapley Value satisfies four critical properties, ensuring fairness:

1. Efficiency: The sum of all Shapley Values equals the total payoff of the grand coalition: $\sum_{i=1}^n \phi_i = v(N)$.
2. Symmetry: Players with identical marginal contributions across all subsets receive the same value.
3. Dummy Player: A player who never contributes ( $v(S \cup \{i\}) = v(S)$ for all $S$) receives $\phi_i = 0$.
4. Additivity: If two games are combined, the Shapley Value of the combined game is the sum of the values from each game.

Example: Applying Shapley Value in a Coalition Game#

Let’s analyze a simple coalition game with three players (A, B, C) collaborating on a project. The characteristic function $v(S)$ (value created by coalition $S$) is:

Step 1: Enumerate All Permutations of Players#

There are $3! = 6$ permutations (orders of joining the coalition):

1. $A \rightarrow B \rightarrow C$
2. $A \rightarrow C \rightarrow B$
3. $B \rightarrow A \rightarrow C$
4. $B \rightarrow C \rightarrow A$
5. $C \rightarrow A \rightarrow B$
6. $C \rightarrow B \rightarrow A$

Step 2: Calculate Marginal Contributions for Each Player#

For each permutation, compute the value added by each player when they join the coalition:

Step 3: Average Marginal Contributions#

Sum the marginal contributions for each player and divide by $6$ (number of permutations):

• A’s Shapley Value: \frac{20 + 20 + 40 + 80 + 35 + 80}{6} = \frac{275}{6} \approx \45.83$
• B’s Shapley Value: \frac{30 + 60 + 10 + 10 + 60 + 15}{6} = \frac{185}{6} \approx \30.83$
• C’s Shapley Value: \frac{50 + 20 + 50 + 10 + 5 + 5}{6} = \frac{140}{6} \approx \23.33$

This example shows how the Shapley Value accounts for every possible coalition formation, ensuring each player’s “average” contribution is rewarded fairly.

Real-World Applications of Shapley Value#

The Shapley Value is widely used across industries:

1. Cost Allocation: Fairly distributing costs in shared projects (e.g., building a bridge, developing software) based on each party’s contribution.
2. Revenue Sharing: Allocating profits in partnerships (e.g., music royalties, joint ventures) or platforms (e.g., app stores, streaming services).
3. Explainable AI (SHAP Values): In machine learning, Shapley Additive Explanations (SHAP) use Shapley Values to attribute prediction importance to features, improving model interpretability.
4. Multi-Agent Systems: Allocating resources or rewards in teams (e.g., autonomous vehicles, robotics) where agents collaborate to achieve goals.

Conclusion#

The Shapley Value is a powerful tool for fair distribution in cooperative games, balancing individual contributions with collective outcomes. Its properties (efficiency, symmetry, etc.) and versatility across fields like economics, AI, and engineering make it indispensable for ensuring equity in collaborative efforts. Whether splitting costs, explaining AI decisions, or rewarding teamwork, the Shapley Value provides a rigorous framework for “fairness” in complex systems.

References#

• Shapley, L. S. (1953). A Value for n-Person Games. In Contributions to the Theory of Games II (pp. 307–317). Princeton University Press.
• Lundberg, S. M., & Lee, S.-I. (2017). A Unified Approach to Interpreting Model Predictions. In Advances in Neural Information Processing Systems (pp. 4765–4774).
• Osborne, M. J., & Rubinstein, A. (1994). A Course in Game Theory. MIT Press.