Cooperative game theory is a branch of game theory that studies situations in which groups of players can form coalitions to achieve a collective gain. Unlike non-cooperative games, where players act independently to maximize their own payoffs, cooperative games focus on the strategic interactions and outcomes that arise from collective action.
This chapter provides an introduction to the fundamental concepts and importance of cooperative game theory. We will explore the key differences between cooperative and non-cooperative games, and delve into the historical background that has shaped the development of this field.
Cooperative game theory is defined by the possibility of forming binding agreements between players. These agreements can lead to cooperative behavior, where players work together to achieve a common goal. The importance of cooperative game theory lies in its ability to model and analyze situations where cooperation is a viable strategy, leading to more efficient and stable outcomes.
In many real-world scenarios, such as international trade agreements, corporate mergers, and environmental policy, cooperation among stakeholders can yield significant benefits. Cooperative game theory provides the theoretical framework to understand and predict these outcomes, making it a valuable tool for economists, political scientists, and other social scientists.
The primary distinction between cooperative and non-cooperative games lies in the binding nature of agreements. In non-cooperative games, players make decisions independently, and any agreements reached are not enforceable. In contrast, cooperative games allow for the formation of coalitions, which can make binding agreements and enforce them through collective action.
This difference has profound implications for the analysis and outcomes of the games. In non-cooperative games, the focus is often on equilibrium concepts, such as Nash equilibrium, where players choose strategies that maximize their individual payoffs. In cooperative games, the focus shifts to the stability and efficiency of the outcomes that arise from coalition formation.
The origins of cooperative game theory can be traced back to the early 20th century, with contributions from economists, mathematicians, and social scientists. One of the earliest formalizations of cooperative game theory was the concept of the characteristic function, introduced by Gillies (1953). This function assigns a value to each coalition, representing the maximum payoff that the coalition can achieve by working together.
Over the years, cooperative game theory has evolved and expanded, incorporating new concepts, solution methods, and applications. Notable contributions include the development of the core (von Neumann & Morgenstern, 1944), the Shapley value (Shapley, 1953), and the Nash bargaining solution (Nash, 1950). These concepts have not only enriched the theoretical foundations of cooperative game theory but also facilitated its application to a wide range of real-world problems.
In the following chapters, we will delve deeper into the basic concepts, solution concepts, and advanced topics of cooperative game theory. By the end of this book, readers will have a comprehensive understanding of the principles and applications of this fascinating field.
Cooperative game theory is built upon a foundation of fundamental concepts and terminology. Understanding these elements is crucial for grasping the intricacies of cooperative games. This chapter delves into the key concepts that form the backbone of cooperative game theory.
In cooperative game theory, the primary actors are players. Players are the decision-makers who can form coalitions. A coalition is a subset of players who can work together to achieve a common goal. The study of coalitions and their interactions is central to cooperative game theory.
For example, in a game with three players, {1, 2, 3}, the possible coalitions include {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. The empty set is not considered a coalition because it lacks players.
The characteristic function is a crucial concept in cooperative game theory. It assigns a value to each coalition, representing the maximum utility that the coalition can achieve by working together. Formally, for a game with N players, the characteristic function v is defined as:
v: 2^N → ℝ
where 2^N denotes the set of all subsets of N, and ℝ represents the real numbers. The value v(S) for a coalition S is the maximum utility that coalition S can achieve.
In Transferable Utility (TU) games, players can transfer utility among themselves. This means that if a coalition achieves a certain utility, the members of the coalition can distribute this utility among themselves. TU games are characterized by their characteristic function, which satisfies certain properties such as efficiency and additivity.
TU games are widely studied because they simplify the analysis of cooperative games. Many solution concepts, such as the core and the Shapley value, are defined for TU games.
In contrast to TU games, Non-Transferable Utility (NTU) games do not allow for the transfer of utility among players. In NTU games, the utility achieved by a coalition must be distributed among its members according to some predetermined rule. This makes NTU games more complex to analyze but also more realistic in many practical scenarios.
NTU games are characterized by their coalitional form, which specifies the preferences of each player over the outcomes of the game. The analysis of NTU games often involves concepts from social choice theory and mechanism design.
Cooperative solution concepts are fundamental to the study of cooperative game theory. These concepts provide a framework for understanding how players can form coalitions and distribute the total payoff among themselves. This chapter explores some of the key cooperative solution concepts, including the Dominant Core, Shapley Value, Nash Bargaining Solution, and Kernel.
The Dominant Core is a solution concept that focuses on the stability of coalitions. It is defined as the set of payoff vectors that are undominated by any other coalition. In other words, no coalition can improve its payoff without reducing the payoff of another coalition. The Dominant Core provides a robust framework for analyzing the stability of coalitions and has been applied in various fields, including economics and political science.
The Shapley Value is another crucial solution concept in cooperative game theory. It is named after Lloyd Shapley, who developed the concept in the 1950s. The Shapley Value assigns a unique payoff to each player based on their marginal contribution to every possible coalition. This concept ensures that each player's payoff is proportional to their importance in the game. The Shapley Value has wide-ranging applications and is often used as a benchmark for comparing different solution concepts.
The Nash Bargaining Solution is a solution concept that focuses on the bargaining process between two players. It is named after John Nash, who developed the concept in the 1950s. The Nash Bargaining Solution provides a unique payoff vector that maximizes the product of the players' payoffs, subject to the constraint that neither player can be made better off without making the other player worse off. This concept has been applied in various fields, including economics and game theory.
The Kernel is a solution concept that focuses on the stability of coalitions in the context of the bargaining set. It is defined as the set of payoff vectors that satisfy a certain set of axioms, including efficiency, symmetry, and individual rationality. The Kernel provides a robust framework for analyzing the stability of coalitions and has been applied in various fields, including economics and political science.
In conclusion, cooperative solution concepts play a crucial role in cooperative game theory. They provide a framework for understanding how players can form coalitions and distribute the total payoff among themselves. By exploring the Dominant Core, Shapley Value, Nash Bargaining Solution, and Kernel, we gain insights into the stability, fairness, and efficiency of coalitions in cooperative games.
The Shapley value is a fundamental solution concept in cooperative game theory, named after Lloyd Shapley, who introduced it in 1953. It provides a unique and fair way to distribute the total payoff among the players in a cooperative game. This chapter delves into the definition, properties, calculation methods, applications, criticisms, and extensions of the Shapley value.
The Shapley value is defined as the average marginal contribution of each player to all possible coalitions. Mathematically, for a game \( (N, v) \) with \( N \) players and characteristic function \( v \), the Shapley value \( \phi_i \) for player \( i \) is given by:
\[ \phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(|N|-|S|-1)!}{|N|!} [v(S \cup \{i\}) - v(S)] \]where \( |S| \) denotes the number of elements in set \( S \). This formula can be interpreted as follows: for each subset \( S \) of players not including \( i \), calculate the marginal contribution of \( i \) to \( S \) (i.e., the difference between the value of the coalition with \( i \) and without \( i \)). Then, weight this contribution by the probability that \( i \) joins \( S \) in a random order of players.
Key properties of the Shapley value include:
Calculating the Shapley value involves evaluating the marginal contributions for all possible subsets of players. This can be computationally intensive, especially for large games. Several methods have been developed to simplify the calculation:
The Shapley value has wide-ranging applications in various fields, including:
While the Shapley value is a powerful tool, it is not without criticisms. Some key issues include:
To address these criticisms, various extensions and modifications of the Shapley value have been proposed, such as:
These extensions aim to provide more realistic and robust solutions for various cooperative games.
The Core is a fundamental solution concept in cooperative game theory, introduced by Gillies (1953) and further developed by Shapley (1953). It provides a set of stable imputations for TU (Transferable Utility) games, where the utility is divisible and can be transferred between players.
The Core of a TU game is defined as the set of all imputations (payoff vectors) that satisfy the following conditions:
Mathematically, for a game \( (N, v) \) with player set \( N \) and characteristic function \( v \), an imputation \( x \in \mathbb{R}^N \) is in the Core if:
Intuitively, the Core represents a stable set of payoffs where no coalition has an incentive to deviate and no player has an incentive to leave the grand coalition.
The existence of a non-empty Core is not guaranteed for all TU games. The existence of the Core depends on the structure of the game, specifically the relationship between the characteristic function \( v \) and the grand coalition \( N \).
For example, the Core is non-empty if the game satisfies the balanced contributions property, which states that for every pair of players \( i, j \in N \), there exists a coalition \( S \subseteq N \setminus \{i, j\} \) such that \( v(S \cup \{i\}) - v(S) \geq v(S \cup \{j\}) - v(S) \).
In general, the non-emptiness of the Core is a complex issue that has been extensively studied in the literature. Several sufficient conditions have been identified, such as superadditivity, convexity, and the absence of certain types of externalities.
The Core is closely related to other solution concepts in cooperative game theory, such as the Shapley Value and the Bargaining Set. In fact, the Shapley Value can be seen as a specific point in the Core, if the Core is non-empty.
Moreover, the Core is a subset of the Bargaining Set, which is a more general solution concept that allows for the possibility of side payments. The Bargaining Set includes all imputations that can be supported as the outcome of a bargaining process among the players.
Despite these relationships, the Core remains an important solution concept due to its intuitive appeal and its role in characterizing stable outcomes in cooperative games.
The computation of the Core is a non-trivial task, especially for large games. Several algorithms have been proposed to compute the Core, both exactly and approximately. These algorithms exploit the structure of the game and the properties of the Core to improve efficiency.
For example, the Core Polyhedron Algorithm (Davis and Maschler, 1965) computes the Core by solving a series of linear programming problems. This algorithm has been successfully applied to a variety of games, including those arising in economics, politics, and biology.
In recent years, there has been a growing interest in the development of approximation algorithms for the Core. These algorithms provide near-optimal solutions to the Core computation problem, even when exact computation is infeasible.
Overall, the study of the Core and its algorithmic aspects continues to be an active area of research in cooperative game theory.
The bargaining set is a fundamental solution concept in cooperative game theory, particularly in the context of transferable utility (TU) games. It provides a set of outcomes that are considered stable and fair, taking into account the bargaining power of the players.
The bargaining set, denoted as B, is defined as the set of all imputations (payoff vectors) that satisfy the following conditions:
These conditions ensure that the bargaining set includes only those outcomes that are stable and fair, as they cannot be improved upon by any player or coalition of players.
The bargaining set is closely related to the core, another important solution concept in cooperative game theory. In fact, the bargaining set can be seen as a refinement of the core, as it imposes additional stability conditions. Specifically, the bargaining set is a subset of the core that satisfies the coalitional rationality condition.
However, the bargaining set is not always non-empty, unlike the core. The existence of the bargaining set depends on the specific structure of the game and the bargaining powers of the players.
The bargaining set has been applied in various economic contexts to analyze bargaining situations between firms, labor unions, and governments. For example, it has been used to study:
In these applications, the bargaining set provides a set of stable and fair outcomes that can help predict the outcome of bargaining negotiations.
Determining whether a given imputation belongs to the bargaining set is a computationally complex task. In fact, deciding whether the bargaining set is non-empty is an NP-hard problem. This complexity arises from the need to check the coalitional rationality condition for all possible coalitions.
Despite this complexity, various algorithms and heuristics have been developed to approximate the bargaining set and compute its elements for specific games. These algorithms leverage insights from game theory and computational complexity theory to provide efficient solutions.
Cooperative games with side payments, also known as Transferable Utility (TU) games, are a fundamental concept in cooperative game theory. In these games, players can make binding agreements and transfer payments among themselves, allowing for a more flexible and efficient allocation of resources.
A cooperative game with side payments is defined by a pair \((N, v)\), where \(N\) is the set of players and \(v\) is the characteristic function that assigns a value \(v(S)\) to each coalition \(S \subseteq N\). The value \(v(S)\) represents the maximum total payoff that coalition \(S\) can achieve by working together, assuming that the members of \(S\) can make binding agreements and transfer payments among themselves.
Examples of TU games include:
Several solution concepts have been proposed to predict the outcome of TU games. Some of the most important ones include:
TU games have numerous applications in economics. Some of the most important ones include:
While TU games are a powerful tool for modeling cooperative behavior, they have some limitations. In particular, they assume that players can make binding agreements and transfer payments among themselves, which may not always be the case. To address this limitation, researchers have proposed extensions of TU games to Non-Transferable Utility (NTU) games, where players cannot transfer payments among themselves.
NTU games are defined by a pair \((N, v)\), where \(N\) is the set of players and \(v\) is the characteristic function that assigns a value \(v(S)\) to each coalition \(S \subseteq N\). However, unlike TU games, the value \(v(S)\) is not necessarily transferable among the members of \(S\).
Examples of NTU games include:
Solution concepts for NTU games include the Nash Bargaining Solution and the Kernel. These concepts provide a framework for predicting the outcome of NTU games, even when players cannot transfer payments among themselves.
Cooperative games without side payments, also known as non-transferable utility (NTU) games, are a fundamental concept in cooperative game theory. In these games, players cannot make side payments to each other, and the utility of a coalition is not necessarily additive. This chapter delves into the definition, examples, solution concepts, applications, and comparisons with transferable utility (TU) games.
In NTU games, the utility of a coalition is represented by a characteristic function that assigns a subset of outcomes to each coalition. Unlike TU games, where the utility is a single number, NTU games have a more complex structure. The characteristic function \( v \) maps each coalition \( S \) to a set of outcomes \( v(S) \), which represents the set of feasible outcomes for the players in \( S \).
Examples of NTU games include:
Solution concepts for NTU games are more complex than those for TU games. Some of the key solution concepts include:
NTU games have numerous applications in political science, particularly in the study of voting, coalition formation, and bargaining. For example, they can be used to model the formation of political parties, the negotiation of treaties, and the distribution of power among different political actors.
Comparing NTU games with TU games reveals several key differences:
Despite these differences, NTU games share many of the same underlying principles and techniques as TU games, making them an important area of study in cooperative game theory.
Cooperative game theory, with its focus on strategic interactions among groups of players, has found numerous applications across various disciplines. This chapter explores some of the key areas where cooperative game theory has been put into practice, demonstrating its versatility and relevance in real-world scenarios.
Economics is one of the primary fields where cooperative game theory has been extensively applied. The theory helps in understanding how firms, industries, and governments can form coalitions to maximize collective benefits. Key applications include:
Political science benefits from cooperative game theory by providing tools to analyze political coalitions, voting systems, and public policy decisions. Some notable applications include:
In biology, cooperative game theory is used to study the evolution of cooperation among organisms, including animals and plants. Key areas of application include:
To illustrate the practical applications of cooperative game theory, let's consider a few case studies from different fields:
These case studies demonstrate the wide-ranging applications of cooperative game theory and its potential to provide insights into complex real-world problems. By understanding the strategic interactions among players, cooperative game theory can help design more effective policies, allocate resources efficiently, and promote cooperation in various domains.
This chapter delves into some of the more advanced topics and future directions in cooperative game theory. These areas are at the forefront of research and offer exciting avenues for further exploration.
Coalitional graphs provide a novel approach to studying the formation of coalitions in cooperative games. Unlike traditional models where coalitions are formed based on utility, coalitional graphs consider the social or structural aspects of coalition formation. Nodes in the graph represent players, and edges represent potential coalitions. The structure of the graph can reveal important insights into the stability and efficiency of coalition formations.
Dynamic coalitional games extend the static framework of cooperative games by introducing time-dependent dynamics. In these games, coalitions can form, dissolve, and reform over time, influenced by various factors such as external shocks, player behavior, and strategic interactions. Dynamic games are particularly relevant in fields like economics and political science, where the environment is constantly changing.
Learning theories in the context of cooperative games explore how players adapt their strategies based on their experiences and observations. This area combines elements of game theory, machine learning, and cognitive science. Understanding learning dynamics can provide deeper insights into the stability and efficiency of cooperative outcomes. For example, reinforcement learning algorithms can be applied to study how players learn to form optimal coalitions over time.
Cooperative game theory is a rich field with many open problems and potential research directions. Some of the key areas for future research include:
Addressing these open problems and exploring these research directions can advance the field of cooperative game theory and its practical applications.
Log in to use the chat feature.