The main assumption in cooperative game theory is that the grand coalition N will form. The challenge is then to allocate the payoff v(N) among the players in some 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 x \in \mathbb{R}^N (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: \sum_{ i \in N } x_i = v(N) . • Individual rationality: No player receives less than what he could get on his own: x_i \geq v(\{i\}), \forall~ i \in 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: v( S \cup \{ i \} ) = w( S \cup \{ i \} ), \forall~ S \subseteq N \setminus \{ 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: v( S \cup \{ i \} ) \leq w( S \cup \{ i \} ), \forall~ S \subseteq N \setminus \{ 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( S \cup \{ i \} ) = v( S \cup \{ j \} ), \forall~ S \subseteq N \setminus \{ 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( S \cup \{ i \} ) = v( S ), \forall~ S \subseteq N \setminus \{ 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 of a game (also known as the
von Neumann-Morgenstern solution ) 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 S \neq \emptyset satisfies x_i > y _i, \forall~ i \in S and \sum_{ i \in S } x_i \leq 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 , 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 . • 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 .
The core Let v be a game. The
core of v is the set of payoff vectors : C( v ) = \left\{ x \in \mathbb{R}^N: \sum_{ i \in N } x_i = v(N); \quad \sum_{ i \in S } x_i \geq v(S), \forall~ S \subseteq N \right\}. 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 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^p_v is defined on X by x \succ^p_v y if and only if there is a winning coalition S (i.e., v(S)=1) satisfying x \succ_i^p y for all i \in 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^p_v (the set of maximal elements of X with respect to \succ^p_v): : x \in C(v,p) if and only if there is no y\in X such that y \succ^p_v x. 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 . The
strong \varepsilon -core for some number \varepsilon \in \mathbb{R} is the set of payoff vectors : C_\varepsilon( v ) = \left\{ x \in \mathbb{R}^N: \sum_{ i \in N } x_i = v(N); \quad \sum_{ i \in S } x_i \geq v(S) - \varepsilon, \forall~ S \subseteq N \right\}. 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. \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 , 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 .
The Shapley value The
Shapley value is the unique payoff vector that is efficient, symmetric, and satisfies monotonicity. It was introduced by
Lloyd Shapley 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.
The kernel Let v : 2^N \to \mathbb{R} be a game, and let x \in \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 \left\{ v(S) - \sum_{ k \in S } x_k : S \subseteq N \setminus \{ j \}, i \in S \right\}, 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 .
Harsanyi dividend The
Harsanyi dividend (named after
John Harsanyi, who used it to generalize the
Shapley value 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 subtracting the surplus that was already created by subcoalitions. To this end, the dividend d_v(S) of coalition S in game v is recursively determined by \begin{align} d_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_{T\subsetneq S }d_v(T) \end{align} An explicit formula for the dividend is given by d_v(S)=\sum_{T\subseteq S }(-1)^v(T). The function d_v:2^N \to \mathbb{R} is also known as the
Möbius inverse of v:2^N \to \mathbb{R}. Indeed, we can recover v from d_v by help of the formula v(S) = d_v(S) + \sum_{T\subsetneq S }d_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, \phi_i(v)=\sum_{S\subset N: i \in S }{d_v(S)}/.
The nucleolus Let v : 2^N \to \mathbb{R} be a game, and let x \in \mathbb{R}^N be a payoff vector. The
excess of x for a coalition S \subseteq N is the quantity v(S) - \sum_{ i \in S } x_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) . The
nucleolus of v is the
imputation for which the vector of excesses of all coalitions (a vector in \mathbb{R}^{2^N} ) is smallest in the
leximin order. The nucleolus was introduced in . 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 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.) == ==