Cooperative game theory explores how players can work together to achieve better outcomes. Solution concepts like the core, Shapley value, and nucleolus help determine fair and stable ways to divide the gains from cooperation.
These concepts offer different approaches to allocating payoffs. The core focuses on stability, the Shapley value on fairness, and the nucleolus on minimizing dissatisfaction. Understanding these solutions helps analyze real-world cooperative situations and negotiate mutually beneficial agreements.
Core and Stability
Definition and Properties of the Core
- Core represents the set of payoff allocations in a cooperative game that no coalition can improve upon
- For an allocation to be in the core, it must be both feasible (within the total value of the grand coalition) and stable (no coalition has an incentive to deviate)
- Core allocations are Pareto optimal since no player can be made better off without making another player worse off
- Core can be empty in some games (no stable allocation exists) or may contain multiple allocations
Stability and Its Implications
- Stability is a key concept in cooperative game theory ensures that no coalition has an incentive to break away from the grand coalition and form a separate agreement
- When an allocation is in the core, it is stable because no group of players can cooperate to achieve a better outcome for themselves
- Stability is important for the long-term sustainability of cooperative agreements and prevents players from constantly seeking new coalitions
Empty Core and Its Consequences
- In some games, the core may be empty, meaning that no allocation satisfies both feasibility and stability simultaneously
- Empty core occurs when the game has no stable solution, and any proposed allocation will be challenged by some coalition
- Games with an empty core are inherently unstable, and players may struggle to reach a long-lasting agreement (voting games with cyclical preferences)
- When the core is empty, alternative solution concepts like the Shapley value or nucleolus may be used to find a "fair" allocation, even if it is not stable
Shapley Value and Fairness
Definition and Computation of Shapley Value
- Shapley value is a solution concept that assigns a unique payoff to each player in a cooperative game based on their average marginal contribution
- To calculate a player's Shapley value, consider all possible orderings in which players can join the coalition and compute the player's marginal contribution in each ordering
- The Shapley value is the average of a player's marginal contributions across all possible orderings
- Shapley value provides a measure of a player's importance or power in the game, taking into account their contributions to all possible coalitions
Fairness and Its Axioms
- Fairness is a desirable property for payoff allocations in cooperative games, ensuring that players are rewarded according to their contributions
- Shapley value satisfies several axioms of fairness:
- Efficiency: The sum of players' Shapley values equals the total value of the grand coalition
- Symmetry: Players with identical marginal contributions receive the same Shapley value
- Dummy player: A player who contributes nothing to any coalition receives a Shapley value of zero
- Additivity: The Shapley value of a game that is the sum of two games is equal to the sum of the Shapley values of the individual games
- These axioms provide a foundation for the Shapley value as a fair and reasonable solution concept
Uniqueness and Its Implications
- The Shapley value is the unique solution concept that satisfies all four axioms of fairness simultaneously
- Uniqueness implies that there is only one allocation that meets these fairness criteria, making the Shapley value a compelling choice when fairness is a primary concern
- The uniqueness property also makes the Shapley value easier to interpret and compare across different games
- However, the Shapley value may not always be in the core, meaning that it may not be stable against coalitional deviations (profit sharing in a joint venture)
Nucleolus and Excess
Definition and Computation of Nucleolus
- Nucleolus is another solution concept for cooperative games that minimizes the maximum dissatisfaction (excess) of any coalition
- To compute the nucleolus, first calculate the excess of each coalition for a given allocation, which is the difference between the coalition's value and the sum of its members' payoffs
- The nucleolus is the allocation that lexicographically minimizes the excesses of all coalitions, starting with the coalition with the highest excess
- Nucleolus can be thought of as the "least worst" allocation, as it seeks to minimize the worst-case dissatisfaction among all coalitions
Excess and Its Role in Nucleolus
- Excess is a measure of a coalition's dissatisfaction with a given payoff allocation
- For a coalition S and an allocation x, the excess of S is defined as e(S, x) = v(S) - ∑(i∈S) xi, where v(S) is the value of coalition S
- A positive excess indicates that a coalition is receiving less than its standalone value, while a negative excess means the coalition is receiving more than its value
- The nucleolus aims to minimize the maximum excess across all coalitions, ensuring that no coalition is too dissatisfied with the allocation (resource allocation in a shared facility)
- By focusing on the excesses of coalitions, the nucleolus takes into account the potential for coalitional deviations and seeks to find an allocation that is as stable as possible