Cooperative Games and the Core

Buy the book! It has so much more .... at Amazon, Game Theory: A Non-Technical Introduction to the Analysis of Strategy at Barnes and Noble -- of course! Game Theory: A Non-Technical Introduction to the Analysis of Strategy

• Language for Cooperative Games
• The Core
• A Market Game
• The Queuing Game and the Core

Language for Cooperative Games

We will need a bit of language to talk about cooperative games with more than two persons. A group of players who commit themselves to coordinate their strategies is called a "coalition." What the members of the coalition get, after all the bribes, side payments, and quids pro quo have cleared, is called an "allocation" or "imputation."

(The problem of coalitions also arises in zero-sum games, if there are more than two players. With three or more players, some of the players may profit by "ganging up" on the rest. For example, in poker, two or more players may cooperate to cheat a third, dividing the pelf between themselves. This is cheating, in poker, because the rules of poker forbid cooperation among the players. For the members of a coalition of this kind, the game becomes a non-zero sum game -- both of the cheaters can win, if they cheat efficiently).

"Allocation" and "imputation" are economic terms, and economists are often concerned with the efficiency of allocations. The standard definition of efficient allocation in economics is "Pareto optimality." Let us pause to recall that concept. In defining an efficient allocation, it is best to proceed by a double-negative. An allocation is inefficient if there is at least one person who can do better, while no other person is worse off. (That makes sense -- if somebody can do better without anyone else being made worse off, then there is an unrealized potential for benefits in the game). Conversely, the allocation is efficient in the Paretian sense if no-one can be made better off without making someone else worse off.

The members of a coalition, C, are a subset of the set of players in the game. (Remember, a "subset" can include all of the players in the game. If the subset is less than the whole set of players in the game, it is called a "proper" subset). If all of the players in the game are members of the coalition, it is called the "grand" coalition. A coalition can also have only a single member. A coalition with just a single member is called a "singleton coalition."

Let us say that the members of coalition C get payoff A. (A is a vector or list of the payoffs to all the members of C, including side payments, if any). Now suppose that some of the members of coalition C could join another coalition, C'; with an allocation of payoffs A'. The members of C who switch to C' may be called "defectors." If the payoffs to defectors in A' are greater than those in A, then we say that A' "dominates" A through coalition C. In other words: an allocation is dominated if some of the members of the coalition can do better for themselves by deserting that coalition for some other coalition.

The Core

We can now define one important concept of the solution of a cooperative game. The core of a cooperative game consists of all undominated allocations in the game. In other words, the core consists of all allocations with the property that no subgroup within the coalition can do better by deserting the coalition.

Notice that an allocation in the core of a game will always be an efficient allocation. Here, again, the best way to show this is to reason in double-negatives -- that is, to show that an inefficient allocation cannot be in the core. To say that the allocation A is inefficient is to say that a grand coalition can be formed in which at least one person is better off, and no-one worse off, than they are in A. Thus, any inefficient coalition is dominated through the grand coalition.

Now, two very important limitations should be mentioned. The core of a cooperative game may be of any size -- it may have only one allocation, or there may be many allocations in the core (corresponding either to one or many coalitions), and it is also possible that there may not be any allocations in the core at all. What does it mean to say that there are no allocations in the core? It means that there are no stable coalitions -- whatever coalition may be formed, there is some subgroup that can benefit by deserting it. A game with no allocations in the core is called an "empty-core game."

I said that the rational player in a cooperative game must ask "not only 'What strategy choice will lead to the best outcome for all of us in this game?' but also 'How large a bribe may I reasonably expect for choosing it?'" The core concept answers this question as follows" "Don't settle for a smaller bribe than you can get from an other coalition, and don't make any commitments until you are sure."

We will now consider two applications of the concept of the core. The first is a "market game," a game of exchange. We then return to a game we have looked at from the noncooperative viewpoint: the queuing game.

A Market Game

Economists often claim that "increasing competition" (an increasing number of participants on both sides of the market, demanders and suppliers) limits monopoly power. Our market game is designed to bring out that idea.

The concept of the core, and the effect of "increasing competition" on the core, can be illustrated by a fairly simple numerical example, provided we make some simplifying assumptions. We will assume that there are just two goods: "widgets" and "money." We will also use what I call the benefits hypothesis -- that is, that utility is proportional to money. In other words, we assume that the subjective benefits a person obtains from her or his possessions can be expressed in money terms, as is done in cost-benefit analysis. In a model of this kind, "money" is a stand-in for "all other goods and services." Thus, people derive utility from holding "money," that is, from spending on "all other goods and services," and what we are assuming is that the marginal utility of "all other goods and services" is (near enough) constant, so that we can use equivalent amounts of "money" or "all other goods and services" as a measure of the utility of widgets. Since money is transferable, that is very much like the "transferable utility" conception originally used by Shubik in his discussions of the core.

We will begin with an example in which there are just two persons, Jeff and Adam. At the beginning of the game, Jeff has 5 widgets but no money, and Adam has $22 but no widgets. The benefits functions are

Table 13-1

Adam's demand curve for widgets will be his marginal benefit curve, while Jeff's supply curve will be the reverse of his marginal benefit curve. These are shown in Figure 13-1.

Figure 13-1

Market equilibrium comes where p=3, Q=2, i.e. Jeff sells Adam 2 widgets for a total payment of $6. The two transactors then have total benefits of

The total benefit divided between the two persons is $24+$29=$53.

Now we want to look at this from the point of view of the core. The "strategies' that Jeff and Adam can choose are unilateral transfers -- Jeff can give up 0, 1, 2, 3, 4, or 5 widgets, and Adam can give up from 0-22 dollars. Presumably both would choose "zero" in a noncooperative game. The possible coalitions are a) a grand coalition of both persons, or b) two singleton coalitions in which each person goes it alone. In this case, a cooperative solution might involve a grand coalition of the two players. In fact, a cooperative solution to this game is a coordinated pair of strategies in which Jeff gives up some widgets to Adam and Adam gives up some money to Jeff. (In more ordinary terms, that is, of course, a market transaction). The core will consist of all such coordinated strategies such that a) neither person (singleton coalition) can do better by going it alone, and b) the coalition of the two cannot do better by a different coordination of their strategies. In this game, the core will be a set of transactions each of which fulfills both of those conditions.

Let us illustrate both conditions: First, suppose Jeff offers to sell Adam one widget for $10. But Adam's marginal benefit is only nine -- Adam can do better by going it alone and not buying anything. Thus, "one widget for $10" is not in the core. Second, suppose Jeff proposes to sell Adam one widget for $5. Adam's total benefit would then be 22-5+9=26, Jeff's 5+21=26. Both are better off, with a total benefit of 52. However, they can do better, if Jeff now sells Adam a second widget for $3.50. Adam now has benefits of 13+22-8.50=26.50, and Jeff has benefits of 18+8.50=26.50, for a total benefit of 53. Thus, a sale of just one widget is not in the core. In fact, the core will include only transactions in which exactly two widgets are sold.

We can check for this in the following way. If the "benefits hypothesis" is correct, the only transactions in the core will be transactions that maximize the total benefits for the two persons. When the two person shift from a transaction that does not maximize benefits to one that does, they can divide the increase in benefits among themselves in the form of money, and both be better off -- so a transaction that does not maximize benefits cannot satisfy condition b) above. From Table 13-1,

Table 13-2

and we see that a trade of 2 maximizes total benefits.

But we have not figured out the price at which the two units will be sold. This is not necessarily the competitive "supply-and-demand" price, since the two traders are both monopolists and one may successfully hold out for a better-than-competitive price.

Here are some examples:

What all of these transactions have in common is that the total benefits are maximized -- at 53 -- but the benefits are distributed in very different ways between the two traders. All the same, each trader does no worse than the 22 of benefits he can have without trading at all. Thus each of these transactions is in the core.

It will be clear, then, that there are a wide range of transactions in the core of this two-person game. We may visualize the core in a diagram with the benefits to Jeff on the horizontal axis and benefits to Adam on the vertical axis. The core then is the line segment ab. Algebraically, it is the line BA=53-BJ, where BA means "Adam's benefits" and BJ means "Jeff's benefits," and the line is bounded by BA>=22 and BJ>=22. The competitive equilibrium is at C.

Figure 13-2

The large size of the core is something of a problem. The cooperative solution must be one of the transactions in the core, but which one? In the two-person game, there is just no answer. The "supply-and-demand" approach does give a definite answer, shown as point C in the diagram. According to the supply-and-demand story, this equilibrium comes about because there are many buyers and many sellers. In our example, instead, we have just one of each, a bilateral monopoly. That would seem to be the problem: the core is large because the number of buyers and sellers is small.

So what happens if we allow the number of buyers and sellers to increase until it is very large? To keep things simple, we will continue to suppose that there are just two kinds of people -- jeffs and adams -- but we will consider a sequence of games with 2, 3, ..., 10, ..., 100,... adams and an equal number of jeffs and see what happens to the core of these games as the number of traders gets large.

First, suppose that there are just two jeffs and two adams. Each jeff and each adam has just the same endowment and benefit function as before.

What coalitions are possible in this larger economy? There could be two one-to-one coalitions of a jeff and an adam. Two jeffs or two adams could, in principle, form a coalition; but since they would have nothing to exchange, there would be little point in it. There could also be coalitions of two jeffs and an adam, two adams and a jeff, or a grand coalition of both jeffs and both adams.

We want to show that this bigger game has a smaller core. There are some transactions in the core of the first game that are not in this one.

Here is an example: In the 2-person game, an exchange of 12 dollars for 2 widgets is in the core. But it is not in the core of this game. At an exchange of 12 for 2, each adam gets total benefits of 23, each jeff or 30. Suppose then that a jeff forms a coalition with 2 adams, so that the jeff sells each adam one widget for $7. The jeff gets total benefits of 18+7+7=32, and so is better off. Each adam gets benefits of 15+9=24, and so is better off. This three-person coalition -- which could not have been formed in the two-person game -- "dominates" the 12-for-2 allocation and so the 12-for-2 allocation is not in the core of the 4-person game. (Of course, the other jeff is out in the cold, but that's his look-out -- the three-person coalition are better off. But, in fact, we are not saying that the three-person coalition is in the core either. It probably isn't, since the odd jeff out is likely to make an offer that would dominate this one).

This is illustrated by the diagram in Figure 13-3. Line segment de shows the trade-off between benefits to the jeffs and the adams in a 3-person coalition. It means that, from any point on line segment fb, a shift to a 3-person coalition makes it possible to move to the northwest -- making all members of the coalition better off -- to a point on fe. Thus all of the allocations on fb are dominated, and not in the core of the 4-person game.

Figure 13-3

Here is another example: in the two-person game, an exchange of two widgets for five dollars is in the core. Again, it will not be in the core of a four-person game. Each jeff gets benefits of 23 and each adam of 30. Now, suppose an adam proposes a coalition with both jeffs. The adam will pay each jeff $2.40 for one widget. The adam then has 30.20 of benefits and so is better off. Each jeff gets 23.40 of benefits and is also better off. Thus the one-adam-and-two-jeffs coalition dominates the 2-for-5 coalition, which is no longer in the core. Figure 13-4 illustrates the situation we now have. The benefit trade-off for a 2-jeff-one-adam coalition is shown by line gj. Every allocation on ab to the left of h is dominated. Putting everything together, we see that allocations on ab to the left of h and to the right of f are dominated by 3-person coalitions, but the 3-person coalitions are dominated by the 2-person coalitions between h and f. (Four-person coalitions function like pairs of two-person coalitions, adding nothing to the game).

Figure 13-4

We can now see the core of the four-person game in Figure 13-4. It is shown by the line segment hf. It is limited by BA>=27, BJ>=24. The core of the four-person game is part of the core of the two-person game, but it is a smaller part, because the four-person game admits of coalitions which cannot be formed in the two-person game. Some of these coalitions dominate some of the coalitions in the core of the smaller game. This illustrates an important point about the core. The bigger the game, the greater the variety of coalitions that can be formed. The more coalitions, often, the smaller the core.

Let us pursue this line of reasoning one more step, considering a six-person game with three jeffs and three adams. We notice that a trade of two widgets for $8 is in the core of the four-person game and we will see that it is not in the core of the 6-person game. Beginning from the 2-for-8 allocation, a coalition of 2 jeffs and 3 adams is proposed, such that each jeff gives up three widgets and each adam buys two, at a price of 3.50 each. The results are shown in Table 13-3

Table 13-3

We see that both the adams and the jeffs within the coalition are better off, so the two-and-three coalition dominates the two-for-eight bilateral trade. Thus the two-for-eight trade is not in the core of the six-person game.

What is in it? This is shown by Figure 13-5. As before, the line segment ab is the core of the two-person game and line segment gj is the benefits trade-off for the coalition of two jeffs and one adam. Segment kl is the benefits trade-off for the coalition of of two jeffs and thee adams. We see that every point on a, b except point h is dominated, either by a 2-jeff 1-adam coalition or by a two-jeff three-adam coalition. The core of a six-player game is exactly one allocation: the one at point h. And this is the competitive equilibrium! No coalition can do better than it.

Figure 13-5

If we were to look at 8, 10, 100, 1000, or 1,000,000 player games, we would find the same core. This series of examples illustrates a key point about the core of an exchange game: as the number of participants (of each type) increases without limit, the core of the game shrinks down to the competitive equilibrium. This result can be generalized in various ways. First, we should observe that in some games, any game with a finite number of players has more than one allocation in the core. This game has been simplified by only allowing players to trade in whole numbers of widgets. That is one reason why the core shrinks to the competitive equilibrium so soon in our example. We may also eliminate the benefits hypothesis, assuming instead that utility is nontransferable and not proportional to money. We can also allow for more than two kinds of players, and get rid of the "types" assumption completely, at the cost of much greater mathematical complexity. But the general idea is simple enough. With more participants, more kinds of coalitions can form, and some of those coalitions dominate coalitions that could form in smaller games. Thus a bigger game will have a smaller core; in that sense "more competition limits monopoly power." But (in a market game) the supply-and-demand is the one allocation that is always in the core. And this provides us with a new understanding of the unique role of the market equilibrium.

The Queuing Game and the Core

We have seen that the market game has a non-empty core, but some very important games have empty cores. From the mathematical point of view, this seems to be a difficulty -- the problem has no solution. But from the economic point of view it may be an important diagnostic point. The University of Chicago economist Lester Telser has argued that empty-core games provide a rationale for government regulation of markets. The core is empty because efficient allocations are dominated -- people can defect to coalitions that can promise them more than they can get from an efficient allocation. What government regulation does in such a case is to prohibit some of the coalitions. Ruling out some coalitions by means of regulation may allow an efficient coalition to form and to remain stable -- the coalitions through which it might be dominated are prohibited by regulation.

In another segment, we have looked at a game that has an inefficient noncooperative equilibrium: the queuing game. We shall see that the Queuing Game also is an empty-core game. Recalling that every allocation in the core is Pareto Optimal, and that Pareto Optimality in this game presupposes a grand coalition of all players to refrain from starting a queue, it will suffice to show that the grand coalition is unstable against a defection of a single agent to form a singleton coalition and form a one-person queue.

It is easy to see that the defector will be better off if the rump coalition (the five remaining in a coalition not to queue) continues its strategy of not contesting for any place in line. Then the defector gets a net payoff of 18 with certainty, better than the average payoff of 12.5 she would get with the grand coalition -- and this observation is just a repetition of the argument that the grand coalition is not a Nash equilibrium. But the rump coalition needs not simply continue with its policy of noncontesting. For example, it can contest the first position in line, while continuing the agreement to allocate the balance at random. This would leave the aggressor with a one-sixth chance of the first place, but she can do no worse than second, so her expected payoff would then be (1/6)(18)+(5/6)(15)=15.5. She will not be deterred from defecting by this possible strategy response from the rump coalition.

That is not the only strategy response open to the rump coalition. Table 13-4 presents a range of strategy alternatives available to the rump coalition:

Table 13-4

These are not the only strategy options available to the rump coalition. For example, the rump coalition might choose to contest just the first and third positions in line, leaving the second uncontested. But this would serve only to assure the defector of a better outcome than she could otherwise be sure of, making the members of the rump coalition worse off. Thus, the rump coalition will never choose a strategy like that, and it cannot be relevant to the defector's strategy. Conversely, we see that the rump coalition's best response to the defection is to contest the first two positions in line, but no more -- leaving the defector better off as a result of defecting, with an expected payoff of 13.5 rather than 12.5. If follows that the grand coalition is unstable under recontracting.

To illustrate the reasoning that underlies the table, let us compute the payoffs for the case in which the rump coalition contests the first two positions in line, the optimal response. 1) The aggressor has a one/sixth chance of first place in line for a payoff of 18, one/sixth of second place for 15, and four-fifths chance of being third, for 12. (The aggressor must still stand in line to be sure of third place, rather than worse, although that position is uncontested). Thus the expected payoff is 18/6+15/6+4*12/6, for 13.5. 2a) With one chance in six, the aggressor is first, leaving the rump coalition to allocate among themselves rewards of 15 (second place in queue), 14, 11, 8, and 5 (third through last places without standing in the queue). Each of these outcomes has a conditional probability of one-fifth for each of the five individuals in the rump coalition. This accounts for expectations of one in thirty (one-sixth times one-fifth) of each of those rewards. 2b) With one chance in six, the aggressor is second, and the rump coalition allocate among themselves, at random, payoffs of 18 (first place in queue), 14, 11, 8 and 5 (as before) accounting for yet further expectations of one in thirty of each of these rewards. 2c) With four chances in six, the aggressor is third -- without contest -- and the members of the rump coalition allocate among themselves, at random, rewards of 18, 15, (first two places in the queue), 11, 8, and 5 (last three places without queuing). 2d) Thus the expected payoff of a member of the rump coalition is (15+14+11+8+5)/30+(18+14+11+8+5)/30+4*(18+15+11+8+5)/30, or 11.233.

Roger A. McCain