The Shapley value is a central concept in cooperative game theory, named after Lloyd Shapley, who introduced it in 1953. It provides a way to fairly distribute the total payoff among the players of a cooperative game, based on their marginal contributions. This chapter introduces the Shapley value, its definition, importance, and historical background.
The Shapley value is defined as the average marginal contribution of a player across all possible orders of player participation. Mathematically, for a game with n players, the Shapley value ϕi of player i is given by:
ϕi = ∑S ⊆ N \ {i} [1 / n!] * [(|S|!) * ((n - |S| - 1)!) * (v(S ∪ {i}) - v(S))]
Where:
This formula essentially calculates the average contribution of player i by considering all possible ways the players can join the coalition, weighted by the probability of each ordering.
The Shapley value is crucial in game theory for several reasons:
The concept of the Shapley value builds upon earlier work in cooperative game theory, particularly the contributions of John von Neumann and Oskar Morgenstern. However, it was Lloyd Shapley who formalized the idea and provided the axiomatic foundation in his 1953 paper "A Value for n-Person Games."
Shapley's work was motivated by the need for a fair and efficient method to distribute the proceeds of a cooperative venture among its members. His solution not only addressed this practical need but also laid the groundwork for numerous advancements in game theory and its applications.
Cooperative game theory is a branch of game theory that studies situations in which groups of players can form coalitions to achieve common goals. Unlike non-cooperative games, where players act independently, cooperative games focus on the strategic interactions within and between coalitions. This chapter delves into the foundational concepts of cooperative game theory, providing a robust understanding of its key components and principles.
The characteristic function is a fundamental concept in cooperative game theory. It assigns a value to each coalition, representing the maximum total payoff that the coalition can achieve by working together. Formally, for a game with n players, the characteristic function v is defined as:
v(S) = maximum payoff that coalition S can achieve, for all S ⊆ N,
where N is the set of all players. The characteristic function encapsulates the essential cooperative aspects of the game, as it captures the gains from cooperation among different groups of players.
In cooperative games, players can form coalitions to maximize their collective payoffs. A coalition is a subset of players who decide to work together to achieve a common objective. The payoff distribution among the players within a coalition is a critical aspect of cooperative games. Various methods exist for distributing the total payoff among the coalition members, such as the Shapley value, the nucleolus, and the core.
The formation of coalitions and the subsequent distribution of payoffs are governed by the rules of the game and the strategies employed by the players. Understanding these dynamics is essential for analyzing the stability and efficiency of cooperative games.
Superadditivity and convexity are important properties of characteristic functions that influence the stability and efficiency of cooperative games. A game is superadditive if the payoff of any two disjoint coalitions is less than or equal to the sum of their individual payoffs:
v(S ∪ T) ≥ v(S) + v(T) for all disjoint S, T ⊆ N.
A game is convex if the payoff of any coalition is less than or equal to the sum of the payoffs of its subsets:
v(S) ≥ ∑T ⊆ S v(T) for all S ⊆ N.
Superadditivity ensures that players have an incentive to form larger coalitions, as the combined payoff of disjoint coalitions is not greater than the sum of their individual payoffs. Convexity, on the other hand, guarantees that the payoff of a coalition is not excessively high compared to the sum of the payoffs of its subsets, promoting a more balanced distribution of power among players.
Understanding these properties is crucial for analyzing the strategic interactions and outcomes in cooperative games, as they provide insights into the stability and efficiency of different game structures.
The axiomatic approach to the Shapley value provides a set of desirable properties that a fair allocation of payoffs in cooperative games should satisfy. This chapter delves into the key axioms that define the Shapley value and explores their implications.
Efficiency, also known as the total payoff axiom, states that the sum of the payoffs to all players should equal the total value of the grand coalition. Mathematically, for a game with n players, the efficiency axiom can be expressed as:
Efficiency:
∑i=1n φi(v) = v(N)
where φi(v) is the payoff to player i, and v(N) is the value of the grand coalition containing all players.
Symmetry ensures that players with the same contribution to the coalition's value receive the same payoff. This axiom is crucial for fairness in allocation. The symmetry axiom can be stated as:
Symmetry: If players i and j have the same marginal contribution to every coalition, then φi(v) = φj(v).
Additivity requires that the payoff allocation for the sum of two games should be the sum of the payoffs for each game individually. This axiom is formalized as:
Additivity: For any two games v and w, φ(v + w) = φ(v) + φ(w).
The null player axiom states that a player who does not contribute to any coalition's value should receive a payoff of zero. This axiom can be expressed as:
Null Player: If player i is a null player (i.e., v(S ∪ {i}) = v(S) for all S ⊆ N \ {i}), then φi(v) = 0.
These axioms collectively define the Shapley value as the unique solution that satisfies efficiency, symmetry, additivity, and the null player property. The Shapley value, thus defined, provides a fair and intuitive way to allocate payoffs in cooperative games.
The computation of the Shapley value is a fundamental aspect of cooperative game theory. It involves determining the contribution of each player to the overall value of the game. This chapter delves into the methods and techniques used to compute the Shapley value.
The marginal contribution of a player is the additional value they bring to a coalition when they join it. The Shapley value is based on the average marginal contribution of a player over all possible orders in which players can join a coalition.
Mathematically, for a player \( i \) in a game with \( n \) players, the marginal contribution when player \( i \) joins a coalition \( S \) is given by:
\[ v(S \cup \{i\}) - v(S) \]where \( v \) is the characteristic function of the game.
To compute the Shapley value, we consider all possible permutations of the \( n \) players. For each permutation, we calculate the marginal contribution of each player as they join the coalition in that order. The Shapley value of player \( i \) is then the average of their marginal contributions over all permutations.
The formula for the Shapley value \( \phi_i \) of player \( i \) is:
\[ \phi_i = \frac{1}{n!} \sum_{\sigma \in \Pi} [v(P_{\sigma}(i) \cup \{i\}) - v(P_{\sigma}(i))] \]where \( \Pi \) is the set of all permutations of the \( n \) players, and \( P_{\sigma}(i) \) is the set of players that precede player \( i \) in permutation \( \sigma \).
The Banzhaf power index is another method to measure the power of players in a game. It is based on the number of coalitions that a player can swing from losing to winning or vice versa. The Banzhaf power index of player \( i \) is given by:
\[ \beta_i = \frac{1}{2^{n-1}} \sum_{S \subseteq N \setminus \{i\}} [v(S \cup \{i\}) - v(S)] \]where \( N \) is the set of all players, and the sum is over all subsets \( S \) of \( N \) that do not contain player \( i \). The factor \( \frac{1}{2^{n-1}} \) normalizes the index to sum to 1.
The Banzhaf power index provides an alternative perspective on the power distribution in a game, highlighting the importance of pivotal coalitions.
The Shapley value, with its robust theoretical foundation and intuitive appeal, has found numerous applications across various fields. This chapter explores some of the most significant applications of the Shapley value in economics, political science, and computer science.
In economics, the Shapley value is extensively used for cost allocation in cooperative games. Consider a scenario where a group of individuals or firms collaborate to achieve a common goal, such as building a road or developing a new product. The total cost of the project is shared among the participants based on their individual contributions.
The Shapley value provides a fair and efficient way to distribute the costs by considering each player's marginal contribution to the coalition. This method ensures that players with higher marginal contributions receive a larger share of the costs, thereby incentivizing their participation.
For example, in a cost allocation problem involving the construction of a public project, the Shapley value can be used to determine how much each stakeholder should contribute based on their unique capabilities and resources. This application helps in preventing free-riding and ensures that all participants contribute according to their abilities.
In political science, the Shapley value is employed to analyze voting power in committees and legislatures. By treating each member of the committee as a player in a cooperative game, the Shapley value can be used to determine the voting power of each member based on their ability to influence the outcome of decisions.
This application is particularly relevant in weighted voting systems, where members have different voting weights. The Shapley value helps in understanding how these weights translate into actual voting power, taking into account the strategic interactions between members.
For instance, in a parliamentary system with a weighted voting system, the Shapley value can be used to assess the influence of different factions or parties. This analysis can provide insights into the stability of the system and the potential for coalition formation, thereby aiding in the design of more effective electoral systems.
In computer science, the Shapley value finds applications in resource allocation problems, particularly in the context of distributed systems and cloud computing. In these systems, resources such as processing power, memory, and bandwidth need to be allocated efficiently among competing tasks or users.
The Shapley value can be used to determine the fair share of resources for each task based on its contribution to the overall system performance. This approach ensures that tasks with higher contributions receive a larger share of the resources, thereby optimizing the system's overall efficiency.
For example, in a cloud computing environment, the Shapley value can be used to allocate virtual machines or containers to different users based on their resource demands and contributions. This dynamic allocation helps in maximizing the utilization of resources and ensuring fair access to computational power.
In summary, the applications of the Shapley value are vast and span across multiple disciplines. Its ability to provide a fair and efficient distribution of resources, costs, or voting power makes it a valuable tool in various decision-making processes.
Transferable Utility (TU) games are a fundamental concept in cooperative game theory, where players can freely transfer utility among themselves. In this chapter, we delve into the application of Shapley Value in such games, exploring how it distributes the total surplus generated by cooperation among the players.
The characteristic function in a TU game, denoted as \( v(S) \), assigns a real number to each coalition \( S \) of players. This value represents the maximum utility that the coalition can achieve by cooperating. The characteristic function must satisfy certain properties, such as:
These properties ensure that the value of a coalition does not decrease when new players join, and the marginal contribution of a player is non-decreasing as the coalition grows.
The Shapley Value in a TU game is a unique solution concept that allocates the total surplus generated by cooperation among the players. It is defined as the average marginal contribution of each player over all possible orders of player entry into the coalition. Mathematically, the Shapley Value \( \phi_i \) for player \( i \) is given by:
\[ \phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{(n-|S|-1)!|S|!}{n!} [v(S \cup \{i\}) - v(S)] \]where \( N \) is the set of all players, and \( n \) is the number of players. This formula accounts for the marginal contribution of player \( i \) to every possible coalition \( S \), weighted by the probability of that coalition forming.
To illustrate the application of Shapley Value in TU games, let's consider a few examples:
These examples demonstrate how Shapley Value can be used to allocate resources or dividends fairly in TU games, ensuring that each player receives a share proportional to their contribution.
In cooperative game theory, the concept of Shapley value is fundamental for distributing payoffs among players in a fair and efficient manner. However, many real-world situations involve non-transferable utility (NTU) games, where the utility of a payoff cannot be easily combined or divided. This chapter explores the application of Shapley value in such NTU games, highlighting the unique challenges and solutions specific to this context.
The characteristic function in NTU games differs from that in transferable utility (TU) games. In NTU games, the characteristic function maps each coalition to a set of feasible payoff vectors rather than a single value. This set represents the possible outcomes that the coalition can achieve without external intervention. The key challenge is to ensure that the payoff vectors are feasible and satisfy the individual rationality and collective rationality constraints.
Feasibility in NTU games requires that the payoff vectors be achievable by the coalition members through their own efforts. This contrasts with TU games, where the characteristic function directly provides a single value that can be divided among coalition members. In NTU games, the complexity arises from the need to consider the individual preferences and constraints of each player within the coalition.
The Shapley value in NTU games is defined similarly to TU games, but with adjustments to account for the non-transferable nature of utility. The Shapley value for each player in an NTU game is the average marginal contribution of that player across all possible permutations of players entering the coalition. However, unlike TU games, the marginal contribution in NTU games is not a simple difference in payoffs but rather a change in the set of feasible payoff vectors.
Calculating the Shapley value in NTU games involves iterating over all possible permutations of players and determining the marginal contribution of each player in terms of the change in the feasible payoff vectors. This process requires a more sophisticated analysis of the game's structure and the interactions between players. The final Shapley value for each player is obtained by averaging these marginal contributions over all permutations.
In NTU games, the coalitional function plays a crucial role in determining the feasible payoff vectors for each coalition. The coalitional function maps each coalition to a set of payoff vectors that represent the possible outcomes achievable by the coalition members. This function must satisfy several properties, including individual rationality, collective rationality, and convexity.
Individual rationality ensures that no player in a coalition receives a payoff that is worse than what they could achieve on their own. Collective rationality guarantees that the total payoff to the coalition is at least as good as the payoff that could be achieved by any subset of players acting alone. Convexity ensures that the set of feasible payoff vectors is convex, allowing for a linear combination of payoff vectors within the set.
Dividing the payoffs in NTU games involves selecting a payoff vector from the feasible set that maximizes the overall utility of the coalition. This selection process can be complex and may require the use of optimization techniques to find the most efficient payoff vector. The Shapley value provides a fair and efficient method for dividing the payoffs among the players based on their marginal contributions to the coalition.
In summary, the application of Shapley value in non-transferable utility games presents unique challenges and requires a more nuanced approach to calculating marginal contributions and feasible payoff vectors. By considering the individual preferences and constraints of each player, the Shapley value can still provide a fair and efficient method for distributing payoffs in NTU games.
Weighted voting games are a fundamental concept in cooperative game theory, where players have different voting powers. The Shapley value provides a fair method to distribute the total surplus among players in such games. This chapter explores how the Shapley value can be applied to weighted voting games, highlighting its significance in various fields such as political science and economics.
In a weighted voting game, each player is assigned a weight that represents their voting power. The total weight of all players is normalized to 1. A coalition wins if the sum of the weights of its members exceeds a certain quota, typically set at 0.5 (simple majority).
Formally, let N be the set of players, and let wi be the weight of player i. The characteristic function v(S) for a coalition S is defined as:
v(S) = 1 if ∑i∈S wi > 0.5, and 0 otherwise.
The Shapley value for a weighted voting game is calculated based on the marginal contribution of each player. The marginal contribution of a player is the difference between the probability that the player causes a winning coalition and the probability that the player causes a losing coalition.
For a player i with weight wi, the Shapley value ϕi is given by:
ϕi = ∑S⊆N\{i} [v(S ∪ {i}) - v(S)] * (|S|! * (n - |S| - 1)!) / n!
where n is the number of players, and the summation is over all subsets S of N that do not contain player i.
The Shapley value has numerous applications in electoral systems. It can be used to determine the voting power of different groups or parties, helping to ensure fairness and transparency in elections. For example, in a parliamentary system, the Shapley value can be used to allocate seats in the legislature based on the voting power of political parties.
In addition, the Shapley value can be applied to analyze the impact of strategic voting and coalitions in elections. By understanding the marginal contribution of different voters or groups, policymakers can design more effective electoral systems that promote participation and representation.
Furthermore, the Shapley value can be used to study the power dynamics in weighted voting bodies, such as the United Nations Security Council. By assigning weights to different countries based on their influence, the Shapley value can help determine the voting power of each member state and identify potential areas for reform.
This chapter has explored the application of the Shapley value in weighted voting games, highlighting its importance in cooperative game theory and its practical applications in various fields. By understanding the marginal contribution of each player, the Shapley value provides a fair and efficient method for distributing the total surplus in weighted voting games.
The computation of the Shapley value in cooperative game theory is a critical aspect that has garnered significant attention due to its computational complexity. This chapter delves into the complexities involved in calculating the Shapley value, exploring various computational aspects, algorithms, and approximation schemes.
The computational complexity of the Shapley value can be analyzed using tools from computational complexity theory. The problem of computing the Shapley value is known to be #P-complete, which means it is at least as hard as any problem in the class #P. This class includes problems that count the number of solutions to a given problem.
Specifically, the problem of computing the Shapley value for a given cooperative game is #P-complete. This implies that unless P = NP, there is no polynomial-time algorithm that can exactly compute the Shapley value for all instances of the problem. This complexity result highlights the inherent difficulty in computing the Shapley value efficiently.
Despite the theoretical complexity, several algorithms have been proposed to compute the Shapley value. One of the most straightforward methods is the direct computation approach, which involves evaluating the characteristic function for all possible coalitions and then averaging the marginal contributions of each player. However, this method is computationally expensive, with a time complexity of O(n * 2^n), where n is the number of players.
Another approach is the Monte Carlo method, which approximates the Shapley value by sampling a large number of permutations of the players and averaging the marginal contributions. This method reduces the time complexity to O(m * n^2), where m is the number of samples. While it provides an approximation, the accuracy depends on the number of samples taken.
More advanced algorithms, such as the Banzhaf power index and the Harsanyi dividend method, have also been proposed. These methods aim to reduce the computational burden by focusing on specific aspects of the game or using more efficient sampling techniques.
Given the computational complexity of exactly computing the Shapley value, approximation schemes have been developed to provide near-optimal solutions. These schemes trade off some accuracy for a significant reduction in computational time.
One popular approximation scheme is the sampling-based approach, which involves sampling a subset of coalitions and estimating the Shapley value based on these samples. This method can provide a good approximation with a time complexity of O(k * n^2), where k is the number of samples. The accuracy of the approximation depends on the size of the sample and the structure of the game.
Another approach is the use of linear programming relaxations, which provide lower and upper bounds on the Shapley value. These bounds can be used to guide the search for an approximate solution, reducing the computational effort required to find a near-optimal value.
In summary, the computational complexity of the Shapley value presents a significant challenge, but various algorithms and approximation schemes have been developed to address these complexities. Understanding these methods is crucial for applying the Shapley value in practical scenarios where computational efficiency is a concern.
This chapter delves into more specialized and complex applications of the Shapley value in cooperative game theory. We will explore how the Shapley value can be extended and adapted to handle various advanced scenarios that go beyond the basic models.
In cooperative games with side payments, players can make transfers among themselves. This extension allows for a more flexible allocation of payoffs. The Shapley value in such games is computed by considering the characteristic function that includes the possibility of side payments. This leads to a more nuanced distribution of the total surplus among the players.
The characteristic function in games with side payments is defined as \( v(S) \), where \( S \) is a coalition, and \( v(S) \) represents the maximum total payoff that coalition \( S \) can achieve, including internal transfers. The Shapley value for each player \( i \) is then given by:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{(|S|)! (n - |S| - 1)!}{n!} [v(S \cup \{i\}) - v(S)] \]where \( N \) is the set of all players, and \( n \) is the total number of players. This formula accounts for the additional complexity introduced by side payments, ensuring that the Shapley value remains a fair and efficient allocation mechanism.
Coalitional games with externalities consider the impact of a coalition's actions on players outside the coalition. Externalities can be positive (beneficial) or negative (harmful). The Shapley value in such games must account for these external effects, making the computation more intricate.
The characteristic function in games with externalities is defined as \( v(S, T) \), where \( S \) is a coalition, and \( T \) represents the external environment. The Shapley value for each player \( i \) is then given by:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{(|S|)! (n - |S| - 1)!}{n!} [v(S \cup \{i\}, T) - v(S, T)] \]This formula ensures that the Shapley value takes into account the externalities, providing a more accurate representation of each player's contribution to the overall game.
Dynamic games involve sequences of decisions made over time. The Shapley value in dynamic games must consider the temporal aspect of the game, where the order of play and the timing of contributions are crucial. This requires a more sophisticated approach to computing the Shapley value.
The characteristic function in dynamic games is defined as \( v(S, t) \), where \( S \) is a coalition, and \( t \) represents the time at which the coalition forms. The Shapley value for each player \( i \) is then given by:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{(|S|)! (n - |S| - 1)!}{n!} \sum_{t} [v(S \cup \{i\}, t) - v(S, t)] \]This formula accounts for the dynamic nature of the game, ensuring that the Shapley value reflects the temporal aspects of player contributions.
In conclusion, the Shapley value can be extended to handle advanced topics in cooperative game theory, including games with side payments, externalities, and dynamics. These extensions provide a more comprehensive framework for analyzing complex cooperative scenarios.
Log in to use the chat feature.