Cooperative game theory
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). 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 equilibria. 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 formula_1, called the "grand coalition", and a "characteristic function" formula_2 from the set of all possible coalitions of players to a set of payments that satisfies formula_3. 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 formula_4 satisfying formula_5. In this setting, players must accomplish some task, and  the characteristic function formula_6 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) 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 formula_7 of coalition formula_8 in game formula_9 is recursively determined by formula_10 An explicit formula for the dividend is given by formula_11. The function formula_12 is also known as the Möbius inverse of formula_13. Indeed, we can recover formula_9 from formula_15 by help of the formula formula_16. 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 formula_17 of player formula_18 in game formula_9 is given by summing up a player's share of  the dividends of all coalitions that she belongs to, formula_20. Duality. Let formula_21 be a profit game. The "dual game" of formula_21 is the cost game formula_23 defined as Intuitively, the dual game represents the opportunity cost for a coalition formula_25 of not joining the grand coalition formula_1. A dual profit game formula_27 can be defined identically for a cost game formula_6. 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  . Subgames. Let formula_29 be a non-empty coalition of players. The "subgame" formula_30 on formula_25 is naturally defined as In other words, we simply restrict our attention to coalitions contained in formula_25. 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 . This means that the value of a union of disjoint coalitions is no less than the sum of the coalitions' separate values: formula_34 whenever formula_35 satisfy formula_36. Monotonicity. Larger coalitions gain more: formula_37. This follows from superadditivity . 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 hypergraphs or Boolean functions (logic functions). A few relations among  the above axioms have widely been recognized, such as the following (e.g., Peleg, 2002, Section 2.1): 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 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: Solution concepts. The main assumption in cooperative game theory is that the grand coalition formula_1 will form. The challenge is then to allocate the payoff formula_53 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 formula_54 (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: 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 formula_21 be a game and let formula_68, formula_85 be two imputations of formula_21. Then formula_68 "dominates" formula_85 if some coalition formula_89 satisfies formula_90 and formula_91. In other words, players in formula_25 prefer the payoffs from formula_68 to those from formula_85, and they can threaten to leave the grand coalition if formula_85 is used because the payoff they obtain on their own is at least as large as the allocation they receive under formula_68. 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. The core. Let formula_21 be a game. The "core" of formula_21 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. 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 formula_102 of alternatives. A "profile" is a list formula_103 of individual preferences formula_104 on formula_102. Here formula_106 means that individual formula_18 prefers alternative formula_108 to formula_109 at profile formula_110. Given a simple game formula_9 and a profile formula_110, a "dominance" relation formula_113 is defined on formula_102 by formula_115 if and only if there is a winning coalition formula_8 (i.e., formula_117) satisfying formula_106 for all formula_119. The "core" formula_120 of the simple game formula_9  with respect to the profile formula_110 of preferences is the set of alternatives undominated by formula_113 (the set of maximal elements of formula_102 with respect to formula_113): The "Nakamura number" of a simple game is the minimal number of winning coalitions with empty intersection. "Nakamura's theorem" states that the core formula_120 is nonempty for all profiles formula_110 of "acyclic" (alternatively, "transitive") preferences if and only if formula_102 is finite "and" the cardinal number (the number of elements) of formula_102 is less than the Nakamura number of formula_9. A variant by Kumabe and Mihara states that the core formula_120 is  nonempty for all profiles formula_110 of preferences that have a "maximal element" if and only if the cardinal number of formula_102 is less than the Nakamura number of formula_9. (See Nakamura number for details.) The strong epsilon-core. Because the core may be empty, a generalization was introduced in . The "strong formula_138-core" for some number formula_139 is the set of payoff vectors In economic terms, the strong formula_138-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 formula_138 for leaving. Note that  formula_138 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 formula_138-core will be non-empty for a large enough value of formula_138 and empty for a small enough (possibly negative) value of formula_138. Following this line of reasoning, the "least-core", introduced in , is the intersection of all non-empty strong formula_138-cores. It can also be viewed as the strong formula_138-core for the smallest value of formula_138 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 formula_2 be a game, and let formula_54 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 "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 formula_9 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 formula_156, but player "j" is immune to player "i"'s threats if formula_157, 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 formula_2 be a game, and let formula_54 be a payoff vector. The "excess" of formula_68 for a coalition formula_161 is the quantity formula_162; that is, the gain that players in coalition formula_25 can obtain if they withdraw from the grand coalition formula_1 under payoff formula_68 and instead take the payoff formula_166. Now let formula_167 be the vector of excesses of formula_68, arranged in non-increasing order. In other words, formula_169. Notice that formula_68 is in the core of formula_21  if and only if it is a pre-imputation and formula_172. To define the nucleolus, we consider the lexicographic ordering of vectors in formula_173: For two payoff vectors formula_174, we say formula_175 is lexicographically smaller than formula_176 if for some index formula_177, we have formula_178 and formula_179. (The ordering is called lexicographic because it mimics alphabetical ordering used to arrange words in a dictionary.) The "nucleolus" of formula_21 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 formula_181 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. Introduced by Shapley in , convex  cooperative games capture the intuitive property some games have of "snowballing". Specifically, a game is "convex" if its characteristic function formula_21 is supermodular: It can be shown (see, e.g., Section V.1 of ) that the supermodularity of formula_21 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: 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 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 , 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".