Game Theory: An Introduction, 2nd Edition

CHAPTER SIX

Cooperative Games

Government and cooperation are in all things the laws of life; anarchy and competition the laws of death.

—John Ruskin, Unto this Last

We must all hang together, or assuredly we will all hang separately.

—Benjamin Franklin, at the signing of the Declaration of Independence

There are two kinds of people: Those who say to God “Thy will be done, ” and those to whom God says, “All right, then, have it your way.”

—C.S. Lewis

6.1 Coalitions and Characteristic Functions

There are n > 1 players numbered 1, 2, …, n. In this chapter, we use the letter n to denote the number of players and N to denote the set of all the players N = {1, 2, …, n}. We consider a game in which the players may choose to cooperate by forming coalitions. A coalition is any subset S ⊂ N, or numbered collection of the players. Since there are 2n possible subsets of N, there are 2n possible coalitions. Coalitions form in order to benefit every member of the coalition so that all members might receive more than they could individually on their own. In this section, we try to determine a fair allocation of the benefits of cooperation among the players to each member of a coalition. A major problem in cooperative game theory is to precisely define what fair means. The definition of fair, of course, determines how the allocations to members of a coalition are made.

First, we need to quantify the benefits of a coalition through the use of a real-valued function, called the characteristic function ...