Coalitional Game Theory
So far we have concentrated on what has become the dominant branch of game theory, the so-called noncooperative variant. We now conclude with an overview of coalitional game theory, also known as cooperative game theory. As was mentioned at the beginning of Chapter 1, when we introduced noncooperative game theory, the term “cooperative” can be misleading. It does not mean that each agent is agreeable and will follow arbitrary instructions. Rather, it means that the basic modeling unit is the group rather than the individual agent. More precisely, in coalitional game theory we still model the individual preference of agents, but not their possible actions. Instead, we have a coarser model of the capabilities of different groups.
8.1 COALITIONAL GAMES WITH TRANSFERABLE UTILITY
In coalitional game theory our focus is on what groups of agents, rather than individual agents, can achieve. Given a set of agents, a coalitional game defines how well each group (or coalition) of agents can do for itself. We are not concerned with how the agents make individual choices within a coalition, how they coordinate, or any other such detail; we simply take the payoff1 to a coalition as given.
In this chapter we will make the transferable utility assumption—that the payoffs to a coalition may be freely redistributed among its members. This assumption is satisfied whenever there is a universal currency that is used for exchange in the system, and means that each coalition can be assigned a single value as its payoff.
Definition 8.1.1 (Coalitional game with transferable utility). A coalitional game with transferable utility is a pair (N, v), where
• N is a finite2 set of players, indexed by i; and
• v: 2N ⊆ 
associates with each coalition S ⊆ N a real-valued payoff v(S) that the coalition’s members can distribute among themselves. The function v is also called the characteristic function, and a coalition’s payoff is also called its worth. We assume that v(
) = 0.
Ordinarily, coalitional game theory is used to answer two fundamental questions:
1. Which coalition will form?
2. How should that coalition divide its payoff among its members?
It turns out that the answer to (1) is often “the grand coalition”—the name given to the coalition of all the agents in N—though this answer can depend on having made the right choice about (2). Before we go any further in answering these questions, however, we provide a coalitional game example to which we will refer throughout the chapter.
Example 8.1.2 (Voting game). A parliament is made up of four political parties, A, B, C, and D, which have 45, 25, 15, and 15 representatives, respectively. They are to vote on whether to pass a $100 million spending bill and how much of this amount should be controlled by each of the parties. A majority vote, that is, a minimum of 51 votes, is required in order to pass any legislation, and if the bill does not pass then every party gets zero to spend.
More generally, in a voting game, there is a set of agents N and a set of coalitions W ⊆ 2N that are winning coalitions, that is, coalitions that are sufficient for the passage of the bill if all its members choose to do so. To each coalition S 
W, we assign v(S) = 1, and to the others we assign v(S) = 0.
8.2 CLASSES OF COALITIONAL GAMES
In this section we will define a few important classes of coalitional games, which have interesting applications as well as useful formal properties. We start with the notion of superadditivity, a property often assumed for coalitional games.
Definition 8.2.1 (Superadditive game). A game G = (N, v) is superadditive if for all S, T ⊂ N, if S ∩ T= Ø, then v(S ∪ T) ≥ v(S) + v(T).
Superadditivity is justified when coalitions can always work without interfering with one another; hence, the value of two coalitions will be no less than the sum of their individual values. Note that superadditivity implies that the value of the entire set of players (the “grand coalition”) is no less than the sum of the value of any nonoverlapping set of coalitions. In other words, the grand coalition has the highest payoff among all coalitional structures. The voting example we gave earlier is a superadditive game.
Taking noninterference across coalitions to the extreme, when coalitions can never affect one another, either positively or negatively, then we have additive (or inessential) games.
Definition 8.2.2 (Additive game). A game G = (N, v) is additive (or inessential) if for all S, T ⊂ N, if S ∩ T = , then v(S ∩ T) = v(S) + v(T).
A related class of games is that of constant-sum games.
Definition 8.2.3 (Constant-sum game). A game G = (N, v) is constant sum if for all S ⊂ N, v(S) + v(N S) = v(N).
Note that every additive game is necessarily constant sum, but not vice versa. As in noncooperative game theory, the most commonly studied constant-sum games are zero-sum games.
An important subclass of superadditive games are convex games.
Definition 8.2.4 (Convexgame). A game G = (N, v) is convex if for all S, T ⊂ N, v(S ∪ T) ≥ v(S) + v (T) − v(S ∩ T).
Clearly, convexity is a stronger condition than superadditivity. While convex games may therefore appear to be a very specialized class of coalitional games, these games are actually not so rare in practice. Convex games have a number of useful properties, as we will discuss in the next section.
Finally, we present a class of coalitional games with restrictions on the values that payoffs are allowed to take.
Definition 8.2.5 (Simple game). A game G = (N, v) is simple if for all S ⊂ N, v(S) {0, 1}.
Simple games are useful for modeling voting situations, such as those described in Example 8.1.2. In simple games we often add the requirement that if a coalition wins, then all larger sets are also winning coalitions (i.e., if v(S) = 1, then for all T ⊃ S, v(T) = 1). This condition might seem to imply superadditivity, but it does not quite. For example, the condition is met by a voting game in which only 50% of the votes are required to pass a bill, but such a game is not superadditive. Consider two disjoint winning coalitions S and T; when they join to form the coalition S ∪ T they do not achieve at least the sum of the values that they achieve separately as superadditivity requires.
When simple games are also constant sum, they are called proper simple games. In this case, if S is a winning coalition, then N S is a losing coalition.
Figure 8.1 graphically depicts the relationship between the different classes of games that we have discussed in this section.
FIGURE 8.1: A hierarchy of coalitional game classes; X ⊃ Y means that class X is a superclass of class Y.
8.3 ANALYZING COALITIONAL GAMES
The central question in coalitional game theory is the division of the payoff to the grand coalition among the agents. This focus on the grand coalition is justified in two ways. First, since many of the most widely studied games are superadditive, the grand coalition will be the coalition that achieves the highest payoff over all coalitional structures, and hence we can expect it to form. Second, there may be no choice for the agents but to form the grand coalition; for example, public projects are often legally bound to include all participants.
If it is easy to decide to concentrate on the grand coalition, however, it is less easy to decide how this coalition should divide its payoffs. In this section we explore a variety of solution concepts that propose different ways of performing this division.
Before presenting the solution concepts, it is helpful to introduce some terminology. First, let ψ : 
× 2|N| 
|N| denote a mapping from a coalitional game (that is, a set of agents N and a value function v) to a vector of |N| real values, and let ψi (N, v) denote the ith such real value. Denote such a vector of |N| real values as x |N|. Each xi denotes the share of the grand coalition’s payoff that agent i N receives. When the coalitional game (N, v) is understood from context, we write × as a shorthand for ψ(N, v).
Now we can give some basic definitions about payoff division.
Definition 8.3.1 (Feasible payoff). Given a coalitional game (N, v), the feasible payoff set is defined as {x N | ΣiN xi ≤ v(N)}.
In other words, the feasible payoff set contains all payoff vectors that do not distribute more than the worth of the grand coalition.
Definition 8.3.2 (Pre−imputation). Given a coalitional game (N, v), the pre−imputation set, denoted P, is defined as {x N | ΣiN xi = v(N)}.
We can view the pre−imputation set as the set of feasible payoffs that are efficient, that is, they distribute the entire worth of the grand coalition.
Definition 8.3.3 (Imputation). Given a coalitional game (N, v), the imputation set, C, is defined as {x P | ∀i N, xi > v(i)}.
Under an imputation, each agent must be guaranteed a payoff of at least the amount that he could achieve by forming a singleton coalition.
Now we are ready to delve into different solution concepts for coalitional games.
8.3.1 The Shapley Value
Perhaps the most straightforward answer to the question of how payoffs should be divided is that the division should be fair. Let us begin by laying down axioms that describe what fairness means in our context.
First, say that agents i and j are interchangeable if they always contribute the same amount to every coalition of the other agents. That is, for all S that contains neither i nor j, v(S ∪ {i}) = v(S ∪ {j}). The symmetry axiom states that such agents should receive the same payments.
Axiom 8.3.4 (Symmetry). For any v, if i and j are interchangeable then ψi (N, v) = ψj(N, v).
Second, say that an agent i is a dummy player if the amount that i contributes to any coalition is exactly the amount that i is able to achieve alone. That is, for all S such that i 
S, v(S U{i}) − v(S) = v({i}). The dummy player axiom states that dummy players should receive a payment equal to exactly the amount that they achieve on their own.
Axiom 8.3.5 (Dummy player). For any v, if i is a dummy player then ψi (N, v) = v({i}).
Finally, consider two different coalitional game theory problems, defined by two different characteristic functions v1 and v2, involving the same set of agents. The additivity axiom states that if we re-model the setting as a single game in which each coalition S achieves a payoff of v1(S) + v2(S), the agents’ payments in each coalition should be the sum of the payments they would have achieved for that coalition under the two separate games.
Axiom 8.3.6 (Additivity). For any two v1 and v2, we have for any player i that ψi(N, v1 + v2) = ψi(<i.N, v1) + ψi(N, v2), where the game (N, v1 + v2) is defined by (v1 + v2)(S) = v1(S) + v2(S) for every coalition S.
If we accept these three axioms, we are led to a strong result: there is always exactly one pre−imputation that satisfies them.
Theorem 8.3.7. Given a coalitional game (N, v), there is a unique pre−imputation φ(N, v) = φ(N, v) that satisfies the Symmetry, Dummy player, Additivity axioms.
Note that our requirement that φ(N, v) be a pre−imputation implies that the payoff division be feasible and efficient.
What is this unique payoff division φ(N, v)? It is called the Shapley value, and it is defined as follows.
Definition 8.3.8 (Shapley value). Given a coalitional game (N, v), the Shapley value of player i is given by
This expression can be viewed as capturing the “average marginal contribution” of agent i, where we average over all the different sequences according to which the grand coalition could be built up from the empty coalition. More specifically, imagine that the coalition is assembled by starting with the empty set and adding one agent at a time, with the agent to be added chosen uniformly at random. Within any such sequence of additions, look at agent i’s marginal contribution at the time he is added. If he is added to the set S, his contribution is [v(S ∪ {i}) − v(S)]. Now multiply this quantity by the |S|! different ways the set S could have been formed prior to agent i’s addition and by the (|N| − |S| - 1)! different ways the remaining agents could be added afterward. Finally, sum over all possible sets S and obtain an average by dividing by |N|!, the number of possible orderings of all the agents.
For a concrete example of the Shapley value in action, consider the voting game given in Example 8.1.2. Recall that the four political parties A, B, C, and D have 45, 25, 15, and 15 representatives, respectively, and a simple majority (51 votes) is required to pass the $100 million spending bill. If we want to analyze how much money it is fair for each party to demand, we can calculate the Shapley values of the game. Note that every coalition with 51 or more members has a value of $100 million,3 and others have $0. In this game, therefore, the parties B, C, and D are interchangeable, since they add the same value to any coalition. (They add $100 million to the coalitions {B, C}, {C, D}, {B, D} that do not include them already and to {A}; they add $0 to all other coalitions.) The Shapley value of A is given by:
The Shapley value for B (and, by symmetry, also for C and D) is given by:
Thus the Shapley values are (50, 16.66, 16.66, 16.66), which add up to the entire $100 million.
8.3.2 The Core
The Shapley value defined a fair way of dividing the grand coalition’s payment among its members. However, this analysis ignored questions of stability. We can also ask: would the agents be willing to form the grand coalition given the way it will divide payments, or would some of them prefer to form smaller coalitions? Unfortunately, sometimes smaller coalitions can be more attractive for subsets of the agents, even if they lead to lower value overall. Considering the majority voting example, while A does not have a unilateral motivation to vote for a different split, A and B have incentive to defect and divide the $100 million between themselves (e.g., dividing it (75, 25)).
This leads to the question of what payment divisions would make the agents want to form the grand coalition. The answer is that they would want to do so if and only if the payment profile is drawn from a set called the core, defined as follows.
Definition 8.3.9 (Core). A payoff vector x is in the core of a coalitional game (N, v) if and only if
Thus, a payoff is in the core if and only if no sub-coalition has an incentive to break away from the grand coalition share the payoff it is able to obtain independently. That is, it requires that the sum of payoffs to any group of agents S ⊆ N must be at least as large as the amount that these agents could share among themselves if they formed a coalition on their own. Notice that Definition 8.3.9 implies that payoff vectors in the core must always be imputations.
Since the core provides a concept of stability for coalitional games we can see it as an analog of the Nash equilibrium from noncooperative games. However, it is actually a stronger notion: Nash equilibrium describes stability only with respect to deviation by a single agent. Instead, the core is an analog of the concept of strong Nash equilibrium, which requires stability with respect to deviations by arbitrary coalitions of agents.
As a notion of stability for coalitional games, the core is appealing. However, the alert reader might have two lingering doubts, arising due to its implicit definition through inequalities:
1. Is the core always nonempty?
2. Is the core always unique?
Unfortunately, the answer to both questions is no. Let us consider again the Parliament example with the four political parties. The set of minimal coalitions that meet the required 51 votes is {A, B}, {A, C}, {A, D}, and {B, C, D}. We can see that if the sum of the payoffs to parties B, C, and D is less than $100 million, then this set of agents has incentive to deviate. On the other hand, if B, C, and D get the entire payoff of $100 million, then A will receive $0 and will have incentive to form a coalition with whichever of B, C, and D obtained the smallest payoff. Thus, the core is empty for this game.
On the other hand, when the core is nonempty it may not define a unique payoff vector either. Consider changing our example so that instead of a simple majority, an 80% majority is required for the bill to pass. The minimal winning coalitions are now {A, B, C} and {A, B, D}. Any complete distribution of the $100 million among parties A and B now belongs to the core, since all winning coalitions must have both the support of these two parties.
These examples call into question the universality of the core as a solution concept for coalitional games. We already saw in the context of noncooperative game theory that solution concepts—notably, the Nash equilibrium—do not yield unique solutions in general. Here we are in an arguably worse situation, in that the solution concept may yield no solution at all.
Luckily, there exist several results that allow us to predict the emptiness or nonemptiness of the core based on a coalitional game’s membership in one of the classes we defined in Section 8.2.
Theorem 8.3.10. Every constant-sum game that is not additive has an empty core.
We say that a player i is a veto player if v(N {i}) = 0.
Theorem 8.3.11. In a simple game the core is empty iff there is no veto player. If there are veto players, the core consists of all payoff vectors in which the nonveto players get zero.
Theorem 8.3.12. Every convex game has a nonempty core.
A final question we consider regards the relationship between the core and the Shapley value. We know that the core may be empty, but if it is not, is the Shapley value guaranteed to lie in the core? The answer in general is no, but the following theorem gives us a sufficient condition for this property to hold. We already know from Theorem 8.3.12 that the core of convex games is nonempty. The following theorem further tells us that for such games the Shapley value belongs to that set.
Theorem 8.3.13. In every convex game, the Shapley value is in the core.
1Alternatively, one might assign costs instead of payoffs to coalitions. Throughout this chapter, we will focus on the case of payoffs; the concepts defined herein can be extended analogously to the case of costs.
2Observe that we consider only finite coalitional games. The infinite case is also considered in the literature; many but not all of the results from this chapter also hold in this case.
3Notice that for these calculations we scale the value function to 100 for winning coalitions and 0 for losing coalitions in order to make it align more tightly with our example.