A
cooperative game is a
gameA game is a structured activity, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more concerned with the expression of ideas...
where groups of players ("coalitions") may enforce cooperative behaviour, hence the game is a competition between
coalitions of players, rather than between individual players. An example is a
coordination gameIn game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies...
, when players choose the strategies by a
consensus decision-makingConsensus decision-making is a group decision making process that not only seeks the agreement of most participants, but also the resolution or mitigation of minority objections. Consensus is usually defined as meaning both general agreement and the process of getting to such agreement...
process.
Recreational games are rarely cooperative, because they usually lack mechanisms by which coalitions may enforce coordinated behaviour on the members of the coalition. Such mechanisms, however, are abundant in real life situations (e.g. contract law).
Mathematical definition
A cooperative game is given by specifying a value for every coalition. Formally, the game is a finite set of players , called the
grand coalition, and a
characteristic function from the set of coalitions to a set of payments that satisfies . The function describes how much collective payoff a set of players can gain by forming a coalition, and the game is sometimes called a
value game or a
profit game . The players are assumed to choose which coalitions to form, according to their estimate of the way the payment will be divided among coalition members.
Conversely, a cooperative game can also be defined with a characteristic cost function satisfying . In this setting, players must accomplish some task, and the characteristic function represents the cost of a set of players accomplishing the task together. A game of this kind is known as a
cost game. Although most cooperative game theory deals with profit games, all concepts can easily be translated to the cost setting.
Duality
Let be a profit game. The
dual game of is the cost game defined as
Intuitively, the dual game represents the
opportunity costOpportunity cost or economic opportunity loss is the value of the next best alternative foregone as the result of making a decision. Opportunity cost analysis is an important part of a company's decision-making processes but is not treated as an actual cost in any financial statement...
for a coalition of not joining the grand coalition . A dual profit game can be defined identically for a cost game . A cooperative game and its dual are in some sense equivalent, and they share many properties. For example, the
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of a game and its dual are equal. For more details on cooperative game duality, see for instance .
Subgames
Let be a non-empty coalition of players. The
subgame on is naturally defined as
In other words, we simply restrict our attention to coalitions contained in . Subgames are useful because they allow us to apply solution concepts defined for the grand coalition on smaller coalitions.
Superadditivity
Characteristic functions are often assumed to be
superadditiveIn mathematics, a sequence { an }, n ≥ 1, is called superadditive if it satisfies the inequalityfor all m and n. The major reason for the use of superadditive sequences is the following lemma due to Fekete....
. This means that the value of a union of
disjointIn mathematics and computer science, two sets are said to be disjoint if they have no element in common. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets.- Explanation :...
coalitions is no less than the sum of the coalitions' separate values:
whenever satisfy .
Monotonicity
Larger coalitions gain more: . This follows from
superadditivityIn mathematics, a sequence { an }, n ≥ 1, is called superadditive if it satisfies the inequalityfor all m and n. The major reason for the use of superadditive sequences is the following lemma due to Fekete....
if payoffs are normalized so singleton coalitions have value zero.
Simple games
A game is
simple if payoffs are either 1 or 0, i.e. coalitions are either "winning" or "losing".
- A simple game is called proper if the complement (opposition) of any winning coalition is losing. It is called strong if ; that is, a coalition is winning if and only if its complement is losing.
- A veto player in a simple game is a player who is included in all winning coalitions. That is, all coalitions not containing the veto player are losing. A dictator is a veto player who also does not belong to any losing coalitions (in this context unrelated to dictator game
The dictator game is a very simple game in experimental economics, similar to the ultimatum game. Experimental results in the dictator game have often been cited as a conclusive rebuttal of the rationally self-interested individual model of economic behavior, although precisely what to conclude...
s.)
Relation with non-cooperative theory
Let
G be a strategic (non-cooperative) game. Then, assuming that coalitions have the ability to enforce coordinated behaviour, there are several cooperative games associated with
G. These games are often referred to as
representations of G.
- The α-effective game associates with each coalition the sum of gains its members can 'guarantee' by joining forces. By 'guaranteeing', it is meant that the value is the max-min, e.g. the maximal value of the minimum taken over the opposition's strategies.
- The β-effective game associates with each coalition the sum of gains its members can 'strategically guarantee' by joining forces. By 'strategically guaranteeing', it is meant that the value is the min-max, e.g. the minimal value of the maximum taken over the opposition's strategies.
Solution concepts
The main assumption in cooperative game theory is that the grand coalition will form. The challenge is then to allocate the payoff among the players in some fair way. (This assumption is not restrictive, because even if players split off and form smaller coalitions, we can apply solution concepts to the subgames defined by whatever coalitions actually form.) A
solution concept is a vector that represents the allocation to each player. Researchers have proposed different solution concepts based on different notions of fairness. Some properties to look for in a solution concept include:
- Efficiency: The payoff vector exactly splits the total value: .
- Individual rationality: No player receives less than what he could get on his own: .
- Existence: The solution concept exists for any game .
- Uniqueness: The solution concept is unique for any game .
- Computational ease: The solution concept can be calculated efficiently (i.e. in polynomial time with respect to the number of players .)
- Symmetry: The solution concept allocates equal payments to symmetric players , . Two players , are symmetric if ; that is, we can exchange one player for the other in any coalition that contains only one of the players and not change the payoff.
- Additivity: The allocation to a player in a sum of two games is the sum of the allocations to the player in each individual game. Mathematically, if and are games, the game simply assigns to any coalition the sum of the payoffs the coalition would get in the two individual games. An additive solution concept assigns to every player in the sum of what he would receive in and .
- Zero Allocation to Null Players: The allocation to a null player is zero. A null player satisfies . In economic terms, a null player's marginal value to any coalition that does not contain him is zero.
An efficient payoff vector is called a
pre-imputation, and an individually rational pre-imputation is called an
imputationIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
. Most solution concepts are imputations.
The stable set
The stable set of a game (also known as the
von Neumann-Morgenstern solution ) was the first solution proposed for games with more than 2 players. Let be a game and let , be two
imputationsIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
of . Then
dominates if some coalition satisfies and . In other words, players in prefer the payoffs from to those from , and they can threaten to leave the grand coalition if is used because the payoff they obtain on their own is at least as large as the allocation they receive under .
A
stable set is a set of
imputationsIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
that satisfies two properties:
- Internal stability: No payoff vector in the stable set is dominated by another vector in the set.
- External stability: All payoff vectors outside the set are dominated by at least one vector in the set.
Von Neumann and Morgenstern saw the stable set as the collection of acceptable behaviours in a society: None is clearly preferred to any other, but for each unacceptable behaviour there is a preferred alternative. The definition is very general allowing the concept to be used in a wide variety of game formats.
Properties
- A stable set may or may not exist , and if it exists it is typically not unique . Stable sets are usually difficult to find. This and other difficulties have led to the development of many other solution concepts.
- A positive fraction of cooperative games have unique stable sets consisting of the core
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
.
- A positive fraction of cooperative games have stable sets which discriminate players. In such sets at least of the discriminated players are excluded .
The core
Let be a game. The
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of is the set of payoff vectors
In words, the core is the set of
imputationsIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
under which no coalition has a value greater than the sum of its members' payoffs. Therefore, no coalition has incentive to leave the grand coalition and receive a larger payoff.
Properties
- The core
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of a game may be empty (see the Bondareva-Shapley theoremIn game theory, the Bondareva-Shapley theorem describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game. Specifically, the game's core is non-empty if and only if the game is balanced. The Bondareva-Shapley theorem implies that market games and convex...
). Games with non-empty cores are called balanced.
- If it is non-empty, the core does not necessarily contain a unique vector.
- The core
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
is contained in any stable set, and if the core is stable it is the unique stable set (see for a proof.)
The strong epsilon-core
Because the
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
may be empty, a generalization was introduced in . The
strong -core for some number is the set of payoff vectors
In economic terms, the strong -core is the set of pre-imputations where no coalition can improve its payoff by leaving the grand coalition, if it must pay a penalty of for leaving. Note that may be negative, in which case it represents a bonus for leaving the grand coalition. Clearly, regardless of whether the
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
is empty, the strong -core will be non-empty for a large enough value of and empty for a small enough (possibly negative) value of . Following this line of reasoning, the
least-core, introduced in , is the intersection of all non-empty strong -cores. It can also be viewed as the strong -core for the smallest value of that makes the set non-empty .
The Shapley value
The
Shapley value is the unique payoff vector that is efficient, symmetric, additive, and assigns zero payoffs to dummy players. It was introduced by
Lloyd ShapleyLloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...
. The Shapley value of a
superadditiveIn mathematics, a sequence { an }, n ≥ 1, is called superadditive if it satisfies the inequalityfor all m and n. The major reason for the use of superadditive sequences is the following lemma due to Fekete....
game is individually rational, but this is not true in general .
The kernel
Let be a game, and let be an efficient payoff vector. The
maximum surplus of Player over Player with respect to is
the maximal amount Player can gain without the cooperation of Player by withdrawing from the grand coalition under payoff vector , assuming that the other players in 's withdrawing coalition are satisfied with their payoffs under . The maximum surplus is a way to measure one player's bargaining power over another. The
kernel of is the set of
imputationsIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
that satisfy
and
for every pair of players . Intuitively, Player has more bargaining power than Player with respect to
imputationIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
if , but Player is immune to Player 's threats if , because he can obtain this payoff on his own. The kernel contains all
imputationsIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
where no player has this bargaining power over another. This solution concept was first introduced in .
The nucleolus
Let be a game, and let be a payoff vector. The
excess of for a coalition is the quantity ; that is, the gain that players in coalition can obtain if they withdraw from the grand coalition under payoff and instead take the payoff .
Now let be the vector of excesses of , arranged in non-increasing order. In other words, . Notice that is in the
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of if and only if it is a pre-imputation and . To define the nucleolus, we consider the lexicographic ordering of vectors in : For two payoff vectors , we say is lexicographically smaller than if for some index , we have and . (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) The
nucleolus of is the lexicographically minimal
imputationIn fully cooperative games players act efficiently when they form a single coalition, the grand coalition. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating...
, based on this ordering. This solution concept was first introduced in .
Although the definition of the nucleolus seems abstract, gave a more intuitive description: Starting with the least-core, record the coalitions for which the right-hand side of the inequality in the definition of cannot be further reduced without making the set empty. Continue decreasing the right-hand side for the remaining coalitions, until it cannot be reduced without making the set empty. Record the new set of coalitions for which the inequalities hold at equality; continue decreasing the right-hand side of remaining coalitions and repeat this process as many times as necessary until all coalitions have been recorded. The resulting payoff vector is the nucleolus.
Properties
- Although the definition does not explicitly state it, the nucleolus is always unique. (See Section II.7 of for a proof.)
- If the core is non-empty, the nucleolus is in the core.
- The nucleolus is always in the kernel, and since the kernel is contained in the bargaining set, it is always in the bargaining set (see for details.)
Convex cooperative games
Introduced by
ShapleyLloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...
in , convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is
convex if its characteristic function is
supermodularIn mathematics, a functionis supermodular iffor all x, y Rk, where x y denotes the componentwise maximum and x y the componentwise minimum of x and y....
:
It can be shown (see, e.g., Section V.1 of ) that the
supermodularIn mathematics, a functionis supermodular iffor all x, y Rk, where x y denotes the componentwise maximum and x y the componentwise minimum of x and y....
ity of is equivalent to
that is, "the incentives for joining a coalition increase as the coalition grows" , leading to the aforementioned snowball effect. For cost games, the inequalities are reversed, so that we say the cost game is
convex if the characteristic function is submodular.
Properties
Convex cooperative games have many nice properties:
- Supermodularity trivially implies superadditivity.
- Convex games are totally balanced: The core
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of a convex game is non-empty, and since any subgame of a convex game is convex, the coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of any subgame is also non-empty.
- A convex game has a unique stable set that coincides with its core
The core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
.
- The Shapley value
In game theory, a Shapley value, named in honour of Lloyd Shapley, who introduced it in 1953, describes one approach to the fair allocation of gains obtained by cooperation among several actors....
of a convex game is the center of gravity of its coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
.
- An extreme point
An extreme point or an extremal point is a point that belongs to the extremity of something.*In mathematics, an extreme point of a convex set S in a real vector space is a point in S which does not lie in any open line segment joining two points of S. Intuitively, an extreme point is a "corner" of S...
(vertex) of the coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
can be found in polynomial time using the greedy algorithmthumb|280px|right|The greedy algorithm determines the minimum number of US coins to give while [[Change-making problem|making change]]. These are the steps a human would take to emulate a greedy algorithm. The coin of the highest value, less than the remaining change owed, is the local optimum...
: Let be a permutationIn several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging elements of a set.- Definitions :The general concept of permutation can be...
of the players, and let be the set of players ordered through in , for any , with . Then the payoff defined by is a vertex of the coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of . Any vertex of the coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
can be constructed in this way by choosing an appropriate permutationIn several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging elements of a set.- Definitions :The general concept of permutation can be...
.
Similarities and differences with combinatorial optimizationCombinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution....
Submodular and
supermodularIn mathematics, a functionis supermodular iffor all x, y Rk, where x y denotes the componentwise maximum and x y the componentwise minimum of x and y....
set functions are also studied in
combinatorial optimizationCombinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution....
. Many of the results in have analogues in , where submodular functions were first presented as generalizations of
matroidIn combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s. In this context, the
coreThe core is the set of feasible allocations that cannot be improved upon by a subset of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first...
of a convex cost game is called the
base polyhedron, because its elements generalize base properties of
matroidIn combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s.
However, the optimization community generally considers submodular functions to be the discrete analogues of convex functions , because the minimization of both types of functions is computationally tractable. Unfortunately, this conflicts directly with
Shapley'sLloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...
original definition of
supermodularIn mathematics, a functionis supermodular iffor all x, y Rk, where x y denotes the componentwise maximum and x y the componentwise minimum of x and y....
functions as "convex".