The Shapley value is a solution concept in cooperative game theory that determines a fair distribution of a total pay-off among players, taking into account their individual contributions to different coalitions. Named after Lloyd Shapley, who introduced it in 1953, this concept ensures that each player receives an allocation proportional to their contribution.
Historical Context
Lloyd Shapley, a prominent American mathematician and economist, introduced the concept of the Shapley value in his 1953 paper “A Value for n-Person Games.” His work laid the foundation for modern game theory, providing a way to allocate resources among players who cooperate to achieve a common goal.
Types/Categories
- Cooperative Games: Games where players form coalitions and work together to achieve the best possible outcome.
- Non-Cooperative Games: Games where players make decisions independently to maximize their own pay-offs.
Key Events
- 1953: Lloyd Shapley introduced the Shapley value.
- 2012: Lloyd Shapley received the Nobel Prize in Economic Sciences, jointly with Alvin Roth, for their contributions to the theory of stable allocations and the practice of market design.
Detailed Explanations
Computation Process
- Marginal Contribution: For each player, calculate their marginal contribution to every possible coalition.
- Weighted Sum: Compute the weighted sum of these marginal contributions, with the weights being the probability that each coalition forms.
Mathematically, the Shapley value for player \(i\) is given by:
where:
- \( \phi_i(v) \) is the Shapley value for player \(i\),
- \( v \) is the value function,
- \( S \) is a subset of players excluding \(i\),
- \( |S| \) is the number of players in \(S\),
- \( n \) is the total number of players.
Mermaid Chart
Below is a flowchart representing the steps involved in computing the Shapley value:
graph TD
A[Start] --> B[Identify all possible coalitions]
B --> C[Calculate marginal contribution for each player]
C --> D[Compute weighted sum of marginal contributions]
D --> E[Determine Shapley value]
E --> F[End]
Importance and Applicability
The Shapley value is crucial in fields such as economics, political science, and operations research for fair resource allocation. It is particularly valuable in scenarios where cooperation among agents is essential, such as cost-sharing in public projects, profit distribution in business ventures, and voting power assessment in political coalitions.
Examples
- Cost-Sharing: In a project involving multiple companies, the Shapley value can determine each company’s fair share of the total project cost.
- Profit Distribution: In a business partnership, it helps in distributing profits fairly based on each partner’s contribution.
Considerations
- Complexity: Computation can be complex for large coalitions.
- Assumptions: Assumes rational behavior and complete information among players.
Related Terms
- Nash Equilibrium: A solution concept in non-cooperative games where no player can benefit by unilaterally changing their strategy.
- Core: A set of imputations where no subgroup of players can achieve a better outcome by deviating from the grand coalition.
Comparisons
- Shapley Value vs. Nash Equilibrium: Shapley value is used in cooperative games focusing on fair allocation, while Nash equilibrium applies to non-cooperative games, emphasizing strategic decision-making.
Interesting Facts
- The Shapley value is used in Google’s AdWords to allocate advertisement space.
- It is applied in network analysis to measure the influence of nodes in a network.
Inspirational Stories
Lloyd Shapley’s work revolutionized game theory and had a significant impact on various fields, earning him the Nobel Prize in 2012 at the age of 89.
Famous Quotes
“A beautiful mind is a terrible thing to waste.” - Lloyd Shapley
Proverbs and Clichés
- “Fair is fair.”
- “Everyone gets what they deserve.”
Jargon and Slang
- Pay-off: The reward or outcome received from a game.
- Coalition: A group of players cooperating to achieve a common goal.
FAQs
-
What is the Shapley value used for?
- The Shapley value is used for fair allocation of resources or pay-offs in cooperative games.
-
How is the Shapley value calculated?
- By computing the marginal contributions of each player to all possible coalitions and taking a weighted sum.
-
Why is the Shapley value important?
- It ensures fair and equitable distribution based on individual contributions.
References
- Shapley, L. S. (1953). “A Value for n-Person Games.” Contributions to the Theory of Games, Vol. II. Princeton University Press.
- Roth, A. E., & Shapley, L. S. (2012). Nobel Prize in Economic Sciences.
Summary
The Shapley value is a fundamental concept in cooperative game theory that provides a method for fair resource allocation based on each player’s contribution. Introduced by Lloyd Shapley in 1953, it remains a critical tool in various domains, from economics to network analysis. By considering the marginal contributions of players to all possible coalitions, the Shapley value ensures that resources are distributed equitably, promoting fairness and cooperation.
