In
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, a cooperative game (or coalitional game) is a
game
A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...
with
competition
Competition is a rivalry where two or more parties strive for a common goal which cannot be shared: where one's gain is the other's loss (an example of which is a zero-sum game). Competition can arise between entities such as organisms, indivi ...
between groups of
players
Players may refer to:
Art, entertainment, and media
* ''Players'' (1979 film), a film starring Ali MacGraw
* ''Players'' (2012 film), a Bollywood film
* ''Players'' (Dicks novel), a novel by Terrance Dicks, based on the television series ''Doc ...
("coalitions") due to the possibility of external enforcement of cooperative behavior (e.g. through
contract law
A contract is a legally enforceable agreement between two or more parties that creates, defines, and governs mutual rights and obligations between them. A contract typically involves the transfer of goods, services, money, or a promise to tran ...
). Those are opposed to
non-cooperative game
In game theory, a non-cooperative game is a game with competition between individual players, as opposed to cooperative games, and in which alliances can only operate if self-enforcing (e.g. through credible threats). However, 'cooperative' and ...
s in which there is either no possibility to forge alliances or all agreements need to be
self-enforcing (e.g. through
credible threat
A non-credible threat is a term used in game theory and economics to describe a threat in a sequential game that a ''rational'' player would not actually carry out, because it would not be in his best interest to do so.
A threat, and its counter ...
s).
Cooperative games are often analysed through the framework of cooperative game theory, which focuses on predicting which coalitions will form, the joint actions that groups take and the resulting collective payoffs. It is opposed to the traditional
non-cooperative game theory
In game theory, a non-cooperative game is a game with competition between individual players, as opposed to cooperative games, and in which alliances can only operate if self-enforcing (e.g. through credible threats). However, 'cooperative' ...
which focuses on predicting individual players' actions and payoffs and analyzing
Nash equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
.
Cooperative game theory provides a high-level approach as it only describes the structure, strategies and payoffs of coalitions, whereas non-cooperative game theory also looks at how bargaining procedures will affect the distribution of payoffs within each coalition. As non-cooperative game theory is more general, cooperative games can be analyzed through the approach of non-cooperative game theory (the converse does not hold) provided that sufficient assumptions are made to encompass all the possible strategies available to players due to the possibility of external enforcement of cooperation. While it would thus be possible to have all games expressed under a non-cooperative framework, in many instances insufficient information is available to accurately model the formal procedures available to the players during the strategic bargaining process, or the resulting model would be of too high complexity to offer a practical tool in the real world. In such cases, cooperative game theory provides a simplified approach that allows the analysis of the game at large without having to make any assumption about bargaining powers.
Mathematical definition
A cooperative game is given by specifying a value for every coalition. Formally, the 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''.
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.
Cooperative game theory definition
Cooperative game is a mandatory binding contract that can be reached by all parties on the basis of information exchange. Moreover, cooperative game is a mechanism to establish cooperative consciousness, mutual trust, restraint and commitment through negotiation and communication.
There are four main points:
1. Common interests
2. Necessary information exchange
3. Voluntariness, equality and mutual benefit
4. Compulsory contract
Harsanyi dividend
The ''Harsanyi dividend'' (named after
John Harsanyi
John Charles Harsanyi ( hu, Harsányi János Károly; May 29, 1920 – August 9, 2000) was a Hungarian-American economist and the recipient of the Nobel Memorial Prize in Economic Sciences in 1994.
He is best known for his contributions to the ...
, who used it to generalize the
Shapley value
The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012. To each cooperative game it assigns a uniq ...
in 1963) identifies the surplus that is created by a coalition of players in a cooperative game. To specify this surplus, the worth of this coalition is corrected by the surplus that is already created by subcoalitions. To this end, the dividend
of coalition
in game
is recursively determined by
An explicit formula for the dividend is given by
. The function
is also known as the
Möbius inverse of
. Indeed, we can recover
from
by help of the formula
.
Harsanyi dividends are useful for analyzing both games and solution concepts, e.g. the
Shapley value
The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012. To each cooperative game it assigns a uniq ...
is obtained by distributing the dividend of each coalition among its members, i.e., the Shapley value
of player
in game
is given by summing up a player's share of the dividends of all coalitions that she belongs to,
.
Duality
Let
be a profit game. The ''dual game'' of
is the cost game
defined as
:
Intuitively, the dual game represents the
opportunity cost
In microeconomic theory, the opportunity cost of a particular activity is the value or benefit given up by engaging in that activity, relative to engaging in an alternative activity. More effective it means if you chose one activity (for example ...
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
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
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.
Properties for characterization
Superadditivity
Characteristic functions are often assumed to be
superadditive In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The ter ...
. 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 In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The ter ...
. i.e. if payoffs are normalized so singleton coalitions have zero value.
Properties for simple games
A coalitional game is considered 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. However, in other areas of mathematics, simple games are also called
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
s or
Boolean functions
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
(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
implies
.
** 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 coalitional simple game that is proper and strong,
for any .)
* A veto player (vetoer) in a simple game is a player that belongs 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 game
The dictator game is a popular experimental instrument in social psychology and economics, a derivative of the ultimatum game. The term "game" is a misnomer because it captures a decision by a single player: to send money to another or not. Thus, t ...
s in experimental economics are unrelated to this.)
* 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 number In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality
of preference aggregation rules (collective decision rules), such as voting rules.
It is an indicator of the extent to which an aggregation r ...
of a simple game is the minimal number of ''winning coalitions'' with empty intersection. According to Nakamura's theorem, the number measures the degree of rationality; it is an indicator of the extent to which an aggregation rule can yield well-defined choices.
A few relations among the above axioms have widely been recognized, such as the following
(e.g., Peleg, 2002, Section 2.1
):
* If a simple game is weak, it is proper.
* A simple game is dictatorial if and only if it is strong and weak.
More generally, a complete investigation of the relation among the four conventional axioms
(monotonicity, properness, strongness, and non-weakness), finiteness, and algorithmic computability
has been made (Kumabe and Mihara, 2011
),
whose results are summarized in the Table "Existence of Simple Games" below.
The restrictions that various axioms for simple games impose on their
Nakamura number In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality
of preference aggregation rules (collective decision rules), such as voting rules.
It is an indicator of the extent to which an aggregation r ...
were also studied extensively.
In particular, a computable simple game without a veto player has a Nakamura number greater than 3 only if it is a ''proper'' and ''non-strong'' game.
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 two standard representations are:
* 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
(or a set of vectors) 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
.
* Marginality: The payoff of a player depends only on the marginal contribution of this player, i.e., if these marginal contributions are the same in two different games, then the payoff is the same:
implies that
is the same in
and in
.
* Monotonicity: The payoff of a player increases if the marginal contribution of this player increase:
implies that
is weakly greater in
than in
.
* 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. Most solution concepts are imputations.
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
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:
* 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
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
.
* 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
''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.
Properties
* The
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
of a game may be empty (see the
Bondareva–Shapley theorem The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game in characteristic function form. Specifically, the game's core is non-empty if and only if the g ...
). Games with non-empty cores are called ''balanced''.
* If it is non-empty, the core does not necessarily contain a unique vector.
* The
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
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 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 In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality
of preference aggregation rules (collective decision rules), such as voting rules.
It is an indicator of the extent to which an aggregation r ...
for details.)
The strong epsilon-core
Because the
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
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
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
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, and satisfies monotonicity. It was introduced by
Lloyd Shapley
Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
who showed that it is the unique payoff vector that is efficient, symmetric, additive, and assigns zero payoffs to dummy players. The Shapley value of a
superadditive In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The ter ...
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
imputations ''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 ''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 .
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
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
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.
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.)
Introduced by
Shapley Shapley is a surname that might refer to one of the following:
* Lieutenant General Alan Shapley (1903–1973), of the U.S. Marine Corps, was a survivor the sinking of the USS Arizona in the attack on Pearl Harbor
* Harlow Shapley (1885–1972), Am ...
in , convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is ''convex'' if its characteristic function
is
supermodular
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the componentw ...
:
:
It can be shown (see, e.g., Section V.1 of ) that the
supermodular
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the componentw ...
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
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
.
Properties
Convex cooperative games have many nice properties:
*
Supermodularity
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the component ...
trivially implies
superadditivity In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The ter ...
.
* Convex games are ''totally balanced'': The
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
of a convex game is non-empty, and since any subgame of a convex game is convex, the
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
of any subgame is also non-empty.
* A convex game has a unique stable set that coincides with its
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
.
* The
Shapley value
The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012. To each cooperative game it assigns a uniq ...
of a convex game is the center of gravity of its
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
.
* An
extreme point
In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or ...
(vertex) of the
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
can be found in polynomial time using the
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
: Let
be a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
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
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
of
. Any vertex of the
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
can be constructed in this way by choosing an appropriate
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
.
Similarities and differences with combinatorial optimization
Submodular
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
and
supermodular
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the componentw ...
set functions are also studied in
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
. Many of the results in have analogues in , where
submodular
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
functions were first presented as generalizations of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s. In this context, the
core
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the central ...
of a convex cost game is called the ''base polyhedron'', because its elements generalize base properties of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s.
However, the optimization community generally considers
submodular
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
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
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the componentw ...
functions as "convex".
The relationship between cooperative game theory and firm
Corporate strategic decisions can develop and create value through cooperative game theory.
This means that cooperative game theory can become the strategic theory of the firm, and different CGT solutions can simulate different institutions.
See also
*
Consensus decision-making
Consensus decision-making or consensus process (often abbreviated to ''consensus'') are group decision-making processes in which participants develop and decide on proposals with the aim, or requirement, of acceptance by all. The focus on es ...
*
Coordination game A coordination game is a type of simultaneous game found in game theory. It describes the situation where a player will earn a higher payoff when they select the same course of action as another player. The game is not one of pure conflict, which r ...
*
Intra-household bargaining Intra-household bargaining refers to negotiations that occur between members of a household in order to arrive at decisions regarding the household unit, like whether to spend or save, whether to study or work.
Bargaining is traditionally defined i ...
*
Hedonic game In cooperative game theory, a hedonic game
Haris Aziz and Rahul Savani, "Hedonic Games". Chapter 15 in: (also known as a hedonic coalition formation game) is a game that models the formation of coalitions (groups) of players when players have pref ...
*
Linear production game Linear production game (LP Game) is a N-person game in which the value of a coalition can be obtained by solving a linear programming problem. It is widely used in the context of resource allocation and payoff distribution. Mathematically, there are ...
References
Further reading
*
*
*
*
*
* . An 88-page mathematical introduction; see Chapter 8
Free onlineat many universities.
*
*
*
Luce, R.D. and
Raiffa, H. (1957) ''Games and Decisions: An Introduction and Critical Survey'', Wiley & Sons. (see Chapter 8).
*
* Osborne, M.J. and
Rubinstein, A. (1994) ''A Course in Game Theory'', MIT Press (see Chapters 13,14,15)
*
*
*
*
*
*
* . A comprehensive reference from a computational perspective; see Chapter 12
Downloadable free online
*
* Yeung, David W.K. and Leon A. Petrosyan. Cooperative Stochastic Differential Games (Springer Series in Operations Research and Financial Engineering), Springer, 2006. Softcover-.
* Yeung, David W.K. and Leon A. Petrosyan. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis (Static & Dynamic Game Theory: Foundations & Applications), Birkhäuser Boston; 2012.
External links
*
{{Game theory
Game theory
Mathematical and quantitative methods (economics)