Gtjkyu

In game theory, a cooperative game (or coalitional game) is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior (e.g. through contract law). Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing (e.g. through credible threats).^[1]

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 which focuses on predicting individual players' actions and payoffs and analyzing Nash equilibriums.^[2]^[3]

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 optimal 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 $N$ , called the grand coalition, and a characteristic function $v:2^Nto mathbb R$ ^[4] from the set of all possible coalitions of players to a set of payments that satisfies $v(emptyset )=0$ . 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 $c:2^Nto mathbb R$ satisfying $c(emptyset )=0$ . In this setting, players must accomplish some task, and the characteristic function $c$ 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.

Harsanyi dividend

The Harsanyi dividend (named after John Harsanyi, who used it to generalize the Shapley value in 1963^[5]) 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 $displaystyle d_v(S)$ of coalition $S$ in game $v$ is recursively determined by

$displaystyle beginalignedd_v(i)&=v(i)\d_v(i,j)&=v(i,j)-d_v(i)-d_v(j)\d_v(i,j,k)&=v(i,j,k)-d_v(i,j)-d_v(i,k)-d_v(j,k)-d_v(i)-d_v(j)-d_v(k)\&vdots \d_v(S)&=v(S)-sum _Tsubsetneq Sd_v(T)endaligned$

An explicit formula for the dividend is given by $textstyle d_v(S)=sum _Tsubsetneq S(-1)^v(T)$ . The function $displaystyle d_v:2^Nto mathbb R$ is also known as the Möbius inverse of $displaystyle v:2^Nto mathbb R$ .^[6] Indeed, we can recover $v$ from $d_v$ by help of the formula $textstyle v(S)=sum _Tsubseteq Sd_v(T)$ .

Harsanyi dividends are useful for analyzing both games and solution concepts, e.g. the Shapley value is obtained by distributing the dividend of each coalition among its members, i.e., the Shapley value $phi _i(v)$ of player $i$ in game $v$ is given by summing up a player's share of the dividends of all coalitions that she belongs to, $textstyle phi _i(v)=sum _Ssubset N:iin Sd_v(S)/S$ .

Duality

Let $v$ be a profit game. The dual game of $v$ is the cost game $v^*$ defined as

displaystyle v^*(S)=v(N)-v(Nsetminus S),forall ~Ssubseteq N.

Intuitively, the dual game represents the opportunity cost for a coalition $S$ of not joining the grand coalition $N$ . A dual profit game $c^*$ can be defined identically for a cost game $c$ . 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 (Bilbao 2000).

Subgames

Let $Ssubsetneq N$ be a non-empty coalition of players. The subgame $v_S:2^Sto mathbb R$ on $S$ is naturally defined as

displaystyle v_S(T)=v(T),forall ~Tsubseteq S.

In other words, we simply restrict our attention to coalitions contained in $S$ . 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 (Owen 1995, p. 213). This means that the value of a union of disjoint coalitions is no less than the sum of the coalitions' separate values:

$v(Scup T)geq v(S)+v(T)$ whenever $S,Tsubseteq N$ satisfy $Scap T=emptyset$ .

Monotonicity

Larger coalitions gain more:

$Ssubseteq TRightarrow v(S)leq v(T)$ .

This follows from superadditivity. i.e. if payoffs are normalized so singleton coalitions have zero value.

Properties for simple games

A coalitional game $v$ 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 $W$ of coalitions, where the members of $W$ 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 hypergraphs or Boolean functions (logic functions).

A simple game $W$ is monotonic if any coalition containing a winning coalition is also winning, that is, if $S in W$ and $Ssubseteq T$ imply $T in W$ .

A simple game $W$ is proper if the complement (opposition) of any winning coalition is losing, that is, if $S in W$ implies $Nsetminus S notin W$ .

A simple game W is strong if the complement of any losing coalition is winning, that is, if S∉Wdisplaystyle Snotin W $S notin W$ implies N∖S∈Wdisplaystyle Nsetminus Sin W $Nsetminus S in W$ .
- If a simple game $W$ is proper and strong, then a coalition is winning if and only if its complement is losing, that is, $S in W$ iff $Nsetminus S notin W$ . (If $v$ is a colitional simple game that is proper and strong, $v(S)=1-v(Nsetminus S)$ for any $S$ .)

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 W is weak (collegial) if it has a veto player, that is, if the intersection ⋂W:=⋂S∈WSdisplaystyle bigcap W:=bigcap _Sin WS $bigcap W:=bigcap _Sin WS$ 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 games in experimental economics are unrelated to this.)

A carrier of a simple game $W$ is a set $T subseteq N$ such that for any coalition $S$ , we have $S in W$ iff $Scap T in W$ . 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 $N$ is infinite).

The Nakamura number 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^[7]):

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^[8]
has been made (Kumabe and Mihara, 2011^[9]),
whose results are summarized in the Table "Existence of Simple Games" below.

Existence of Simple Games^[10]
Type	Finite Non-comp	Finite Computable	Infinite Non-comp	Infinite Computable
.mw-parser-output .monospacedfont-family:monospace,monospace.mw-parser-output .monospaced-boldfont-weight:bold 1111	No	Yes	Yes	Yes
1110	No	Yes	No	No
1101	No	Yes	Yes	Yes
1100	No	Yes	Yes	Yes
1011	No	Yes	Yes	Yes
1010	No	No	No	No
1001	No	Yes	Yes	Yes
1000	No	No	No	No
0111	No	Yes	Yes	Yes
0110	No	No	No	No
0101	No	Yes	Yes	Yes
0100	No	Yes	Yes	Yes
0011	No	Yes	Yes	Yes
0010	No	No	No	No
0001	No	Yes	Yes	Yes
0000	No	No	No	No

The restrictions that various axioms for simple games impose on their Nakamura number were also studied extensively. ^[11]
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:^[12]

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 $N$ will form.^{[citation needed]} The challenge is then to allocate the payoff $v(N)$ 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 $xin mathbb R^N$ 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: $sum _iin Nx_i=v(N)$ .

Individual rationality: No player receives less than what he could get on his own: $x_igeq v(i),forall ~iin N$ .

Existence: The solution concept exists for any game $v$ .

Uniqueness: The solution concept is unique for any game $v$ .

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: $displaystyle v(Scup i)=w(Scup i),forall ~Ssubseteq Nsetminus i$ implies that $x_i$ is the same in $v$ and in $w$ .

Monotonicity: The payoff of a player increases if the marginal contribution of this player increase: $displaystyle v(Scup i)leq w(Scup i),forall ~Ssubseteq Nsetminus i$ implies that $x_i$ is weakly greater in $w$ than in $v$ .

Computational ease: The solution concept can be calculated efficiently (i.e. in polynomial time with respect to the number of players $|N|$ .)

Symmetry: The solution concept $x$ allocates equal payments $x_i = x_j$ to symmetric players $i$ , $j$ . Two players $i$ , $j$ are symmetric if $v(Scup i)=v(Scup j),forall ~Ssubseteq Nsetminus i,j$ ; 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 $v$ and $omega$ are games, the game $(v+omega )$ 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 $(v+omega )$ the sum of what he would receive in $v$ and $omega$ .

Zero Allocation to Null Players: The allocation to a null player is zero. A null player $i$ satisfies $v(Scup i)=v(S),forall ~Ssubseteq Nsetminus i$ . 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

The stable set of a game (also known as the von Neumann-Morgenstern solution (von Neumann & Morgenstern 1944)) was the first solution proposed for games with more than 2 players. Let $v$ be a game and let $x$ , $y$ be two imputations of $v$ . Then $x$ dominates $y$ if some coalition $Sneq emptyset$ satisfies $x_i>y_i,forall ~iin S$ and $sum _iin Sx_ileq v(S)$ . In other words, players in $S$ prefer the payoffs from $x$ to those from $y$ , and they can threaten to leave the grand coalition if $y$ is used because the payoff they obtain on their own is at least as large as the allocation they receive under $x$ .

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 (Lucas 1969), and if it exists it is typically not unique (Lucas 1992). 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 (Owen 1995, p. 240).

A positive fraction of cooperative games have stable sets which discriminate $n-2$ players. In such sets at least $n-3$ of the discriminated players are excluded (Owen 1995, p. 240).

The core

Let $v$ be a game. The core of $v$ is the set of payoff vectors

displaystyle C(v)=leftxin mathbb R ^N:sum _iin Nx_i=v(N);quad sum _iin Sx_igeq v(S),forall ~Ssubseteq Nright.

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 of a game may be empty (see the Bondareva–Shapley theorem). Games with non-empty cores are called balanced.

If it is non-empty, the core does not necessarily contain a unique vector.

The core is contained in any stable set, and if the core is stable it is the unique stable set; see (Driessen 1988) 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 $X$ of alternatives.
A profile is a list $p=(succ_i^p)_i in N$ of individual preferences $succ_i^p$ on $X$ .
Here $x succ_i^p y$ means that individual $i$ prefers alternative $x$
to $y$ at profile $p$ .
Given a simple game $v$ and a profile $p$ , a dominance relation $succ _v^p$ is defined
on $X$ by $xsucc _v^py$ if and only if there is a winning coalition $S$
(i.e., $v(S)=1$ ) satisfying $x succ_i^p y$ for all $iin S$ .
The core $C(v,p)$ of the simple game $v$ with respect to the profile $p$ of preferences
is the set of alternatives undominated by $succ _v^p$
(the set of maximal elements of $X$ with respect to $succ _v^p$ ):

xin C(v,p)

if and only if there is no

yin X

such that

ysucc _v^px

.

The Nakamura number of a simple game is the minimal number of winning coalitions with empty intersection.
Nakamura's theorem states that the core $C(v,p)$ is nonempty for all profiles $p$ of acyclic (alternatively, transitive) preferences
if and only if $X$ is finite and the cardinal number (the number of elements) of $X$ is less than the Nakamura number of $v$ .
A variant by Kumabe and Mihara states that the core $C(v,p)$ is nonempty for all profiles $p$ of preferences that have a maximal element
if and only if the cardinal number of $X$ is less than the Nakamura number of $v$ . (See Nakamura number for details.)

The strong epsilon-core

Because the core may be empty, a generalization was introduced in (Shapley & Shubik 1966). The strong $varepsilon$ -core for some number $varepsilon in mathbb R$ is the set of payoff vectors

C_varepsilon (v)=leftxin mathbb R^N:sum _iin Nx_i=v(N);quad sum _iin Sx_igeq v(S)-varepsilon ,forall ~Ssubseteq Nright.

In economic terms, the strong $varepsilon$ -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 $varepsilon$ for leaving. Note that $varepsilon$ 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 $varepsilon$ -core will be non-empty for a large enough value of $varepsilon$ and empty for a small enough (possibly negative) value of $varepsilon$ . Following this line of reasoning, the least-core, introduced in (Maschler, Peleg & Shapley 1979), is the intersection of all non-empty strong $varepsilon$ -cores. It can also be viewed as the strong $varepsilon$ -core for the smallest value of $varepsilon$ that makes the set non-empty (Bilbao 2000).

The Shapley value

The Shapley value is the unique payoff vector that is efficient, symmetric, and satisfies monotonicity.^[13] It was introduced by Lloyd Shapley (Shapley 1953) 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 game is individually rational, but this is not true in general. (Driessen 1988)

The kernel

Let $v:2^Nto mathbb R$ be a game, and let $xin mathbb R^N$ be an efficient payoff vector. The maximum surplus of player i over player j with respect to x is

s_ij^v(x)=max leftv(S)-sum _kin Sx_k:Ssubseteq Nsetminus j,iin Sright,

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 i's 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 $v$ is the set of imputations x that satisfy

$(s_ij^v(x)-s_ji^v(x))times (x_j-v(j))leq 0$ , and

$(s_ji^v(x)-s_ij^v(x))times (x_i-v(i))leq 0$

for every pair of players i and j. Intuitively, player i has more bargaining power than player j with respect to imputation x if $s_ij^v(x)>s_ji^v(x)$ , but player j is immune to player i's threats if $x_j=v(j)$ , 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 (Davis & Maschler 1965).

The nucleolus

Let $v:2^Nto mathbb R$ be a game, and let $xin mathbb R^N$ be a payoff vector. The excess of $x$ for a coalition $Ssubseteq N$ is the quantity $v(S)-sum _iin Sx_i$ ; that is, the gain that players in coalition $S$ can obtain if they withdraw from the grand coalition $N$ under payoff $x$ and instead take the payoff $v(S)$ .

Now let $theta (x)in mathbb R^2^N$ be the vector of excesses of $x$ , arranged in non-increasing order. In other words, $theta _i(x)geq theta _j(x),forall ~i<j$ . Notice that $x$ is in the core of $v$ if and only if it is a pre-imputation and $theta _1(x)leq 0$ . To define the nucleolus, we consider the lexicographic ordering of vectors in $mathbb R^2^N$ : For two payoff vectors $x, y$ , we say $theta (x)$ is lexicographically smaller than $theta (y)$ if for some index $k$ , we have $theta _i(x)=theta _i(y),forall ~i<k$ and $theta _k(x)<theta _k(y)$ . (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) The nucleolus of $v$ is the lexicographically minimal imputation, based on this ordering. This solution concept was first introduced in (Schmeidler 1969).

Although the definition of the nucleolus seems abstract, (Maschler, Peleg & Shapley 1979) 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 $C_varepsilon (v)$ 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 (Driessen 1988) 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 (Driessen 1988) for details.)

Convex cooperative games

Introduced by Shapley in (Shapley 1971), convex cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is convex if its characteristic function $v$ is supermodular:

displaystyle v(Scup T)+v(Scap T)geq v(S)+v(T),forall ~S,Tsubseteq N.

It can be shown (see, e.g., Section V.1 of (Driessen 1988)) that the supermodularity of $v$ is equivalent to

displaystyle v(Scup i)-v(S)leq v(Tcup i)-v(T),forall ~Ssubseteq Tsubseteq Nsetminus i,forall ~iin N;

that is, "the incentives for joining a coalition increase as the coalition grows" (Shapley 1971), 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 of a convex game is non-empty, and since any subgame of a convex game is convex, the core of any subgame is also non-empty.

A convex game has a unique stable set that coincides with its core.

The Shapley value of a convex game is the center of gravity of its core.

An extreme point (vertex) of the core can be found in polynomial time using the greedy algorithm: Let $pi :Nto N$ be a permutation of the players, and let $S_i=jin N:pi (j)leq i$ be the set of players ordered $1$ through $i$ in $pi$ , for any $i=0,ldots ,n$ , with $S_0=emptyset$ . Then the payoff $xin mathbb R^N$ defined by $x_i=v(S_pi (i))-v(S_pi (i)-1),forall ~iin N$ is a vertex of the core of $v$ . Any vertex of the core can be constructed in this way by choosing an appropriate permutation $pi$ .

Similarities and differences with combinatorial optimization

Submodular and supermodular set functions are also studied in combinatorial optimization. Many of the results in (Shapley 1971) have analogues in (Edmonds 1970), where submodular functions were first presented as generalizations of matroids. In this context, the core of a convex cost game is called the base polyhedron, because its elements generalize base properties of matroids.

However, the optimization community generally considers submodular functions to be the discrete analogues of convex functions (Lovász 1983), 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".

References

^ Shor, Mike. "Non-Cooperative Game - Game Theory .net". www.gametheory.net. Retrieved 2016-09-15.

^ Chandrasekaran, R. "Cooperative Game Theory" (PDF).

^ Brandenburger, Adam. "Cooperative Game Theory: Characteristic Functions, Allocations, Marginal Contribution" (PDF).

^ $2^N$ denotes the power set of $N$ .

^ Harsanyi, John C. (1982). Papers in Game Theory. Theory and Decision Library. Springer, Dordrecht. pp. 44–70. doi:10.1007/978-94-017-2527-9_3. ISBN 9789048183692.

^ Set Functions, Games and Capacities in Decision Making | Michel Grabisch | Springer.

^ Peleg, B. (2002). "Chapter 8 Game-theoretic analysis of voting in committees". Handbook of Social Choice and Welfare Volume 1. Handbook of Social Choice and Welfare. 1. pp. 195–201. doi:10.1016/S1574-0110(02)80012-1. ISBN 9780444829146.

^ See
a section for Rice's theorem
for the definition of a computable simple game. In particular, all finite games are computable.

^ Kumabe, M.; Mihara, H. R. (2011). "Computability of simple games: A complete investigation of the sixty-four possibilities" (PDF). Journal of Mathematical Economics. 47 (2): 150–158. doi:10.1016/j.jmateco.2010.12.003.

^ Modified from Table 1 in Kumabe and Mihara (2011).
The sixteen types are defined by the four conventional axioms (monotonicity, properness, strongness, and non-weakness).
For example, type
1110 indicates monotonic (1), proper (1), strong (1), weak (0, because not nonweak) games.
Among type
1110 games, there exist no finite non-computable ones, there exist finite computable ones, there exist no infinite non-computable ones, and there exist no infinite computable ones.
Observe that except for type
1110, the last three columns are identical.

^ Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439 . doi:10.1007/s00355-008-0300-5.

^ Aumann, Robert J. "The core of a cooperative game without side payments." Transactions of the American Mathematical Society (1961): 539-552.

^ Young, H. P. (1985-06-01). "Monotonic solutions of cooperative games". International Journal of Game Theory. 14 (2): 65–72. doi:10.1007/BF01769885. ISSN 0020-7276.

External links

Hazewinkel, Michiel, ed. (2001) [1994], "Cooperative game", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4

[1] Shor, Mike. "Non-Cooperative Game - Game Theory .net". www.gametheory.net. Retrieved 2016-09-15.

[2] Chandrasekaran, R. "Cooperative Game Theory" (PDF).

[3] Brandenburger, Adam. "Cooperative Game Theory: Characteristic Functions, Allocations, Marginal Contribution" (PDF).

[4] $2^N$ denotes the power set of $N$ .

[5] Harsanyi, John C. (1982). Papers in Game Theory. Theory and Decision Library. Springer, Dordrecht. pp. 44–70. doi:10.1007/978-94-017-2527-9_3. ISBN 9789048183692.

[6] Set Functions, Games and Capacities in Decision Making | Michel Grabisch | Springer.

[peleg02hbscw-7] Peleg, B. (2002). "Chapter 8 Game-theoretic analysis of voting in committees". Handbook of Social Choice and Welfare Volume 1. Handbook of Social Choice and Welfare. 1. pp. 195–201. doi:10.1016/S1574-0110(02)80012-1. ISBN 9780444829146.

[8] See
a section for Rice's theorem
for the definition of a computable simple game. In particular, all finite games are computable.

[kumabe-m11jme-9] Kumabe, M.; Mihara, H. R. (2011). "Computability of simple games: A complete investigation of the sixty-four possibilities" (PDF). Journal of Mathematical Economics. 47 (2): 150–158. doi:10.1016/j.jmateco.2010.12.003.

[10] Modified from Table 1 in Kumabe and Mihara (2011).
The sixteen types are defined by the four conventional axioms (monotonicity, properness, strongness, and non-weakness).
For example, type
1110 indicates monotonic (1), proper (1), strong (1), weak (0, because not nonweak) games.
Among type
1110 games, there exist no finite non-computable ones, there exist finite computable ones, there exist no infinite non-computable ones, and there exist no infinite computable ones.
Observe that except for type
1110, the last three columns are identical.

[kumabe-m08scw-11] Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439 . doi:10.1007/s00355-008-0300-5.

[12] Aumann, Robert J. "The core of a cooperative game without side payments." Transactions of the American Mathematical Society (1961): 539-552.

[13] Young, H. P. (1985-06-01). "Monotonic solutions of cooperative games". International Journal of Game Theory. 14 (2): 65–72. doi:10.1007/BF01769885. ISSN 0020-7276.

v t e Topics in game theory
Definitions	Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game
Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium
Strategies	Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy
Classes of games	Symmetric game Perfect information Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global game Strictly determined game Potential game
Games	Chess Infinite chess Checkers Tic-tac-toe Prisoner's dilemma Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock–paper–scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and Monster game Rendezvous problem
Theorems	Minimax theorem Nash's theorem Purification theorem Zermelo's theorem Folk theorem Revelation principle Arrow's impossibility theorem
Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith Antoine Augustin Cournot John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition First-move advantage in chess Game mechanics Glossary of game theory List of game theorists List of games in game theory No-win situation Solving chess Topological game Tragedy of the commons Tyranny of small decisions

搜尋此網誌

Gtjkyu

Cooperative game theory

Contents

Mathematical definition

Harsanyi dividend

Duality

Subgames

Properties for characterization

Superadditivity

Monotonicity

Properties for simple games

Relation with non-cooperative theory

Solution concepts

The stable set

Properties

The core

Properties

The core of a simple game with respect to preferences

The strong epsilon-core

The Shapley value

The kernel

The nucleolus

Properties

Convex cooperative games

Properties

Similarities and differences with combinatorial optimization

See also

References

Further reading

External links

Popular posts from this blog

Movies - Topic

Rothschild family

Cinema of Italy