Cooperative Game Theory

The Shapley value's first application outside economics was to politics, and it produced a result that electoral arithmetic conceals. Shapley and Martin Shubik asked in 1954 what a member of a voting body is actually worth, and answered it with the value: imagine the members declaring their support one at a time in a random order, and credit each member for the orderings in which it is the one that turns a losing coalition into a winning one.

The results are frequently nothing like the vote counts. A member holding a tenth of the votes in a body requiring a simple majority may be pivotal in a fifth of the orderings, or — if the other blocks are arranged so that it is never needed — in none at all. In the United Nations Security Council, where nine of fifteen votes are needed and any of the five permanent members can veto, the index gives each permanent member about 19.6% of the power and each of the ten elected members about 0.2%: a ratio near a hundred to one, from a voting rule that looks like 1 vote each plus a veto. Applied to shareholder blocks, to the European Union's Council of Ministers after each enlargement, and to the United States Electoral College, the same calculation has repeatedly shown that reweighting votes does not reweight power in proportion.

Which index to use is contested, and the disagreement is instructive rather than technical. The Shapley–Shubik index counts orderings, which treats a member as powerful if it often arrives at the moment a coalition becomes decisive; the Banzhaf index counts coalitions instead, which treats a member as powerful if many coalitions depend on it. The two rank the members of real voting bodies differently, and no argument internal to the mathematics settles it, because they formalise two different senses of "being decisive". That is the same problem as choosing between fairness and stability, one level down.

Take a market with three players. A seller, $A$, owns an object worth nothing to her. Buyer $B$ values it at 100, buyer $C$ at 80. The characteristic function is

$$v(A) = v(B) = v(C) = 0, \quad v(AB) = 100, \quad v(AC) = 80, \quad v(BC) = 0, \quad v(ABC) = 100.$$

The core. A division $(x_A, x_B, x_C)$ summing to 100 must satisfy $x_A + x_B \ge 100$, which given that the total is 100 forces $x_C = 0$. It must also satisfy $x_A + x_C \ge 80$, so $x_A \ge 80$. The core is therefore

$$\{(x_A,\,100 - x_A,\,0) : 80 \le x_A \le 100\}.$$

The economics is visible in the inequalities. The losing buyer gets nothing, and the seller captures at least 80 — the amount the competing buyer would pay — because $A$ and $C$ could always walk off together. What the seller gets above 80 is indeterminate: the core does not pick a point.

The Shapley value. Average each player's marginal contribution over all six orders of arrival:

Order	$A$ adds	$B$ adds	$C$ adds
$A,B,C$	0	100	0
$A,C,B$	0	20	80
$B,A,C$	100	0	0
$B,C,A$	100	0	0
$C,A,B$	80	20	0
$C,B,A$	100	0	0

Summing columns gives 380, 140 and 80, which total 600 as they must, and dividing by six:

$$\varphi_A = \tfrac{380}{6} = 63.3, \qquad \varphi_B = \tfrac{140}{6} = 23.3, \qquad \varphi_C = \tfrac{80}{6} = 13.3.$$

The fair division gives the seller 63.3, and the core requires at least 80. The Shapley value is not in the core. By the fairness axioms, the losing bidder deserves 13.3 for having been a credible alternative; by the stability requirement, he gets nothing, because the seller and the winning buyer can simply exclude him. No reconciliation is available: these are different questions, and in games like this one — where coalitions substitute rather than complement — they have different answers.

The core can also be empty. Take three players where any two can secure 1 and a single player nothing:

$$v(i) = 0, \quad v(ij) = 1, \quad v(123) = 1.$$

A core division needs $x_1 + x_2 \ge 1$, $x_1 + x_3 \ge 1$ and $x_2 + x_3 \ge 1$. Adding all three gives $2(x_1+x_2+x_3) \ge 3$, so the total must be at least 1.5, while only 1 exists. The core is empty: whatever the three agree, some pair can do better by abandoning the third. This is the structure of a three-party coalition government, and the instability is not a defect of the players.

The Shapley value, by contrast, always exists and is always unique — here $(1/3, 1/3, 1/3)$ — which is its practical advantage and the reason it is used for allocating costs and apportioning credit. It is a recommendation, not a prediction.

The field's largest practical success came from dropping money altogether. David Gale and Shapley asked, in 1962, whether two sides with preferences over each other can always be paired so that no two participants would both rather have each other than their assigned partners. Such a blocking pair would, in any real institution, simply go around the mechanism, so a matching containing one will not hold.

The proof is an algorithm. Everyone on one side proposes to their favourite. Each recipient holds the best offer received so far and rejects the others. Rejected proposers approach their next choice, and recipients again keep only the best offer in hand — including, possibly, discarding someone they were holding. Since no proposer ever revisits a rejection, the process must terminate; and at termination there is no blocking pair, because any participant a proposer prefers to their final match must have rejected them for someone better.

Two further facts made this deployable. The outcome depends on which side proposes — the proposing side gets its best achievable stable matching and the other side its worst — and the proposing side cannot gain by misreporting its preferences. The receiving side can, and Alvin Roth and others proved no mechanism is strategyproof for both sides at once.

Roth then found that the algorithm had been in use for thirty years without anyone knowing the theory. The American system for placing medical graduates, patched together in 1952 after chaotic competition for interns, turned out to be essentially deferred acceptance, and the regional medical markets that had collapsed were the ones using mechanisms that produced unstable matchings. He went on to redesign the match to handle couples, to replace Boston's school-assignment system — which had punished families for stating their true first choice — and to set up kidney exchange, in which incompatible donor-patient pairs are arranged into cycles so that each patient receives an organ from someone else's donor.

That last application is where this thread touches immunology: the compatibility graph is built from blood and tissue typing, and the algorithm's job is to find cycles in it. What the division of gains looks like when the players are not negotiating but being selected, and the payoffs are offspring, is the subject of evolutionary game theory; what happens when the coalition structure is too large to search is algorithmic game theory.