Cooperative game
Encyclopedia
In game theory
, a cooperative game is a game 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 game
, when players choose the strategies by a consensus decision-making
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).
, called the grand coalition, and a characteristic function 
from the set of all possible coalitions of players 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.
be a profit game. The dual game of 
is the cost game 
defined as
Intuitively, the dual game represents the opportunity cost
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 core
of a game and its dual are equal. For more details on cooperative game duality, see for instance .
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.
whenever 
satisfy 
.
. This follows from superadditivity if payoffs are normalized so singleton coalitions have value zero.
is simple if payoffs are either 1 or 0, i.e., coalitions are either "winning" or "losing".
Equivalently, a simple game can be defined as a collection
of coalitions,
where the members of
are called winning coalitions, and the others losing coalitions.
It is sometimes assumed that a simple game is nonempty or that it does not contain an empty set.
In other areas of mathematics, simple games are also called hypergraph
s or Boolean functions (logic functions).
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:
An efficient payoff vector is called a pre-imputation, and an individually rational pre-imputation is called an imputation
. Most solution concepts are imputations.
be a game and let 
, 
be two imputations
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 imputations
that satisfies two properties:
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.
be a game. The core
of
is the set of payoff vectors
In words, the core is the set of imputations
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.
of alternatives.
A profile is a list
of individual preferences 
on 
.
Here
means that individual 
prefers alternative 
to
at profile 
.
Given a simple game
and a profile 
, a dominance relation 
is defined
on
by 
if and only if there is a winning coalition 
(i.e.,
) satisfying 
for all 
.
The core
of the simple game 
with respect to the profile 
of preferences
is the set of alternatives undominated by
(the set of maximal elements of
with respect to 
):
if and only if there is no 
such that 
.
The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection.
Nakamura's theorem states that the core
is nonempty for all profiles 
of acyclic (alternatively, transitive) preferences
if and only if
is finite and the cardinal number (the number of elements) of 
is less than the Nakamura number of 
.
A variant by Kumabe and Mihara states that the core
is nonempty for all profiles 
of preferences that have a maximal element
if and only if the cardinal number of
is less than the Nakamura number of 
. (See Nakamura number
for details.)
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 core
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 of a superadditive game is individually rational, but this is not true in general .
be a game, and let 
be an efficient payoff vector. The maximum surplus of player i over player j with respect to x is
the maximal amount player i can gain without the cooperation of player j by withdrawing from the grand coalition N under payoff vector x, assuming that the other players in is withdrawing coalition are satisfied with their payoffs under x. The maximum surplus is a way to measure one player's bargaining power over another. The kernel of
is the set of imputations
x that satisfy
for every pair of players i and j. Intuitively, player i has more bargaining power than player j with respect to imputation
x if
, but player j is immune to player is threats if 
, because he can obtain this payoff on his own. The kernel contains all imputations
where no player has this bargaining power over another. This solution concept was first introduced in .
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 core
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 imputation
, 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.
in , convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is convex if its characteristic function
is supermodular
:
It can be shown (see, e.g., Section V.1 of ) that the supermodular
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.
Similarities and differences with combinatorial optimization
Submodular and supermodular
set functions are also studied in combinatorial optimization
. Many of the results in have analogues in , where submodular functions were first presented as generalizations of matroid
s. In this context, the core
of a convex cost game is called the base polyhedron, because its elements generalize base properties of matroid
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's
original definition of supermodular
functions as "convex".
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, a cooperative game is a game 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 game
Coordination game
In 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-making
Consensus decision-making
Consensus decision-making is a group decision making process that seeks the consent, not necessarily the agreement, of participants and the resolution of objections. Consensus is defined by Merriam-Webster as, first, general agreement, and second, group solidarity of belief or sentiment. It has its...
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 (coalitional game) consists of a finite set of players, called the grand coalition, and a characteristic function from the set of all possible coalitions of players 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 cost
Opportunity cost
Opportunity cost is the cost of any activity measured in terms of the value of the best alternative that is not chosen . It is the sacrifice related to the second best choice available to someone, or group, who has picked among several mutually exclusive choices. The opportunity cost is also the...
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 coreCore (economics)
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 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 superadditive . This means that the value of a union of disjoint coalitions is no less than the sum of the coalitions' separate values: whenever satisfy .Monotonicity
Larger coalitions gain more:. This follows from superadditivity if payoffs are normalized so singleton coalitions have value zero.Properties for Simple games
A coalitional game is simple if payoffs are either 1 or 0, i.e., coalitions are either "winning" or "losing".Equivalently, a simple game can be defined as a collection
of coalitions,where the members of
are called winning coalitions, and the others losing coalitions.It is sometimes assumed that a simple game is nonempty or that it does not contain an empty set.
In other areas of mathematics, simple games are also called hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s or Boolean functions (logic functions).
- A simple game
is monotonic if any coalition containing a winning coalition is also winning, that is, if 
and 
imply 
.
- A simple game
is proper if the complement (opposition) of any winning coalition is losing, that is, if 
implies 
.
- A simple game
is strong if the complement of any losing coalition is winning, that is, if 
imples
.
- If a simple game
is proper and strong, then a coalition is winning if and only if its complement is losing, that is, 
iff 
. (If 
is a colitional simple game that is proper and strong, 
for any 
.)
- If a simple game
- A veto player (vetoer) in a simple game is a player that belong to all winning coalitions. Supposing there is a veto player, any coalition not containing a veto player is losing. A simple game
is weak (collegial) if it has a veto player, that is, if the intersection 
of all winning coalitions is nonempty.
- A dictator in a simple game is a veto player such that any coalition containing this player is winning. The dictator does not belong to any losing coalition. (Dictator gameDictator gameThe dictator game is a game in experimental economics, similar to the ultimatum game. Experimental results offer evidence against the rationally self-interested individual concept of economic behavior, though precisely what to conclude from the evidence is controversial.-Description:In the...
s in experimental economics are unrelated to this.)
- A dictator in a simple game is a veto player such that any coalition containing this player is winning. The dictator does not belong to any losing coalition. (Dictator game
- A carrier of a simple game
is a set 
such that for any coalition 
, we have 
iff 
. When a simple game has a carrier, any player not belonging to it is ignored. A simple game is sometimes called finite if it has a finite carrier (even if 
is infinite).
- The Nakamura numberNakamura numberIn cooperative game theory and social choice theory, the Nakamura number measures the degree of rationalityof preference aggregation rules , such as voting rules....
of a simple game is the minimal number of winning coalitions with empty intersection. The number measures the degree of rationality; it is an indicator of the extent to which an aggregation rule can yield well-defined choices.
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 imputation
Imputation (game theory)
In 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 imputationsImputation (game theory)
In 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 imputations
Imputation (game theory)
In 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 coreCore (economics)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 coreCore (economics)
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
is the set of payoff vectors
In words, the core is the set of imputations
Imputation (game theory)
In 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 coreCore (economics)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 theoremBondareva-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 coreCore (economics)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 core of a simple game with respect to preferences
For simple games, there is another notion of the core, when each player is assumed to have preferences on a set of alternatives.A profile is a list
of individual preferences on .Here
means that individual prefers alternative to
at profile .Given a simple game
and a profile , a dominance relation is definedon
by if and only if there is a winning coalition (i.e.,
) satisfying for all .The core
of the simple game with respect to the profile of preferencesis the set of alternatives undominated by
(the set of maximal elements of
with respect to ): if and only if there is no such that .The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection.
Nakamura's theorem states that the core
is nonempty for all profiles of acyclic (alternatively, transitive) preferencesif and only if
is finite and the cardinal number (the number of elements) of is less than the Nakamura number of .A variant by Kumabe and Mihara states that the core
is nonempty for all profiles of preferences that have a maximal elementif and only if the cardinal number of
is less than the Nakamura number of . (See Nakamura numberNakamura number
In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationalityof preference aggregation rules , such as voting rules....
for details.)
The strong epsilon-core
Because the coreCore (economics)
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...
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 coreCore (economics)
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 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 Shapley
Lloyd 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 superadditive 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 i over player j with respect to x is
the maximal amount player i can gain without the cooperation of player j by withdrawing from the grand coalition N under payoff vector x, assuming that the other players in is withdrawing coalition are satisfied with their payoffs under x. The maximum surplus is a way to measure one player's bargaining power over another. The kernel of
is the set of imputationsImputation (game theory)
In 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...
x that satisfy
-
, and -
for every pair of players i and j. Intuitively, player i has more bargaining power than player j with respect to imputation
Imputation (game theory)
In 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...
x if
, but player j is immune to player is threats if , because he can obtain this payoff on his own. The kernel contains all imputationsImputation (game theory)
In 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 coreCore (economics)
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
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 imputationImputation (game theory)
In 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 Shapley
Lloyd 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 supermodularSupermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...
:
It can be shown (see, e.g., Section V.1 of ) that the supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...
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 coreCore (economics)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 coreCore (economics)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 any subgame is also non-empty. - A convex game has a unique stable set that coincides with its coreCore (economics)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 valueShapley valueIn game theory, the Shapley value, named in honour of Lloyd Shapley, who introduced it in 1953, is a solution concept in cooperative game theory. To each cooperative game it assigns a unique distribution of a total surplus generated by the coalition of all players...
of a convex game is the center of gravity of its coreCore (economics)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...
. - An extreme pointExtreme pointIn 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...
(vertex) of the coreCore (economics)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...
can be found in polynomial time using the greedy algorithmGreedy algorithmA greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
: Let
be a permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
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 coreCore (economics)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
. Any vertex of the coreCore (economics)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...
can be constructed in this way by choosing an appropriate permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
.
Similarities and differences with combinatorial optimizationCombinatorial optimizationIn applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
Submodular and supermodularSupermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...
set functions are also studied in combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. Many of the results in have analogues in , where submodular functions were first presented as generalizations of matroid
Matroid
In 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 core
Core (economics)
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 cost game is called the base polyhedron, because its elements generalize base properties of matroid
Matroid
In 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's
Lloyd Shapley
Lloyd 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 supermodular
Supermodular
In mathematics, a functionf\colon R^k \to Ris supermodular iff + f \geq f + ffor all x, y \isin Rk, where x \vee y denotes the componentwise maximum and x \wedge y the componentwise minimum of x and y.If −f is supermodular then f is called submodular, and if the inequality is changed to an...
functions as "convex".
See also
- Consensus decision-makingConsensus decision-makingConsensus decision-making is a group decision making process that seeks the consent, not necessarily the agreement, of participants and the resolution of objections. Consensus is defined by Merriam-Webster as, first, general agreement, and second, group solidarity of belief or sentiment. It has its...
- Coordination gameCoordination 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...
- Intra-household bargainingIntra-household bargainingIntra-household bargaining refers to negotiations that occur between members of a household in order to arrive at decisions regarding the household unit....