Game Theory · Chapter 13
Coalitions, the Core and the Shapley Value
Three firms merge, two airlines share a runway, a startup’s founders split the equity. Once people can sign binding agreements, the question is no longer how they will play, but which groups will form and how they’ll divide what they create together. Here you’ll let players walk into a room one at a time and pay each one what they add, which is Lloyd Shapley’s famous answer to “who deserves what”. Then you’ll look for splits that no group would reject, and measure how much power each member of a council really has, which can be very different from how many votes they hold.
Games
What each coalition is worth
Change any number to make your own game.
Live numbers
Missions
What you’re seeing
The game. A coalitional game lists what every group of players could earn on its own. In the glove game, Lefty owns a left glove and the two Rightys own right gloves; only a matched pair is worth anything, $1. So any group with Lefty and at least one Righty is worth $1, and every other group is worth $0.
The room. Imagine the players arriving one at a time in a random order. Each one is paid what they add when they walk in: the group’s worth with them, minus its worth without them. That’s their marginal contribution. If Righty 1 arrives first, she adds nothing; if she arrives right after Lefty, she adds the whole $1.
The average. Different orders pay different amounts. Average each player’s marginal contribution over all the orders (6 for three players, 24 for four), and you get the Shapley value. The bars show the running average and the white lines show where it ends up.
Coalitional games
John von Neumann and Oskar Morgenstern introduced the idea in 1944. A coalitional game with transferable payoff has a set of players N and a characteristic function v that gives each coalition S ⊆ N its worth v(S), with v(∅) = 0. “Transferable” means the worth can be divided any way the members like, as with money. The game says nothing about how players act; it only lists what each group could guarantee itself.
- A game is superadditive if two separate groups can always do at least as well together: v(S ∪ T) ≥ v(S) + v(T) whenever S and T don’t overlap. Then the grand coalition of everyone is the natural one to form, and the question is how to split v(N).
- An imputation is a split x = (x1, …, xn) of v(N) that gives each player at least what they could get alone: xi ≥ v({i}).
Firms A, B and C earn $10M, $20M and $30M a year alone. Any two merged earn more: A+B $40M, A+C $50M, B+C $60M. All three together earn $80M. The game is superadditive, so all three should merge. But how should they split $80M? Equal thirds (26.7 each) would give C less than it earns alone. Splitting in proportion to stand-alone profits (13.3, 26.7, 40) gives B and C together 66.7, more than the 60 they could get by merging without A, so they can afford it; is A getting enough? The next two sections give two different answers to “how much is fair” and “how much is safe”.
The core: splits no group would reject
A split is stable if no group of players can do better by breaking away. That set of splits is the core, introduced by Donald Gillies in his 1953 doctoral thesis (published 1959):
With three players, every imputation is a point in a triangle: each corner gives all of the extra worth to one player. Each pair’s demand cuts off a slice of the triangle; what’s left is the core. Drag the white dot. If a group would walk out, the live numbers name it.
The triangle uses the game chosen in the main simulation above. Pick a three-player game there.
The core needs xA ≥ 10, xB ≥ 20, xC ≥ 30, and for each pair, say B and C, xB + xC ≥ 60. Since all three add to 80, that last condition means xA ≤ 20. In the same way xB ≤ 30 and xC ≤ 40. The core is the small triangle with corners (20, 30, 30), (10, 30, 40) and (20, 20, 40), in $M. The proportional split (13.3, 26.7, 40) is inside it; equal thirds is not.
Empty cores. In the majority game, any two of three players can take the whole $1. Whatever split you propose, the two players with the least can grab everything together; every pair needs at least $1, so the three pairs together need $3, but there is only $1 to go around. Olga Bondareva (1963) and Shapley (1967) found exactly when a core is non-empty: when the game is balanced. For three players whose singletons are worth 0, it comes down to a simple test: no pair is worth more than v(N), and the three pairs’ worths add to at most 2v(N).
The Shapley value: a fair split
The core asks what is stable. In 1953 Lloyd Shapley asked what is fair, and wrote down four properties a fair rule should have:
The whole worth v(N) is divided, no more and no less.
Two players who add the same to every coalition get the same.
A player who adds nothing to any coalition gets nothing.
If two games are played, a player’s share of the combined game is the sum of their shares of each.
He proved that exactly one rule has all four, and it is the average marginal contribution over all orders of arrival. Counting how many orders put exactly the coalition S ahead of player i gives the formula:
Order the players and see who adds the $1:
| Order | Lefty adds | Righty 1 adds | Righty 2 adds |
|---|---|---|---|
| L, R1, R2 | 0 | 1 | 0 |
| L, R2, R1 | 0 | 0 | 1 |
| R1, L, R2 | 1 | 0 | 0 |
| R1, R2, L | 1 | 0 | 0 |
| R2, L, R1 | 1 | 0 | 0 |
| R2, R1, L | 1 | 0 | 0 |
| Average | 4/6 = 2/3 | 1/6 | 1/6 |
Lefty gets two thirds because left gloves are scarce. Notice that the core says something harsher: the only stable split is (1, 0, 0). If Lefty offered Righty 1 anything, Lefty and Righty 2 could do better together. Competition between the Rightys drives their share to zero, while the Shapley value rewards each for being needed in some orders.
A small, a medium and a large plane need runways costing $8M, $11M and $13M; one runway long enough for the largest serves all. Stephen Littlechild and Guillermo Owen (1973) showed that the Shapley value then has a simple form: split the first $8M of runway equally among all three planes, the next $3M between the two that need it, and the last $2M to the large plane alone. Shares: small 8/3 ≈ $2.67M, medium 2.67 + 1.5 = $4.17M, large 4.17 + 2 = $6.17M. They add to $13M. Littlechild and Gary Thompson (1977) used this idea to work out landing fees for Birmingham Airport in England.
Fair versus stable. The Shapley value always exists and is unique; the core can be empty or contain many splits. When they overlap, everyone is happy. Shapley proved in 1971 that in convex games, where a player adds more to bigger coalitions (v(S ∪ T) + v(S ∩ T) ≥ v(S) + v(T)), the Shapley value is always in the core. The airport game is convex (as a cost game), and so is the merger. The glove game is not.
Voting power
A weighted voting game [q; w1, …, wn] gives member i wi votes; a motion passes with at least q. Treat a winning coalition as worth 1 and a losing one as worth 0, and the Shapley value becomes a measure of power. Shapley and Martin Shubik proposed it in 1954: a member’s power is the share of orders in which they are pivotal, turning a losing group into a winning one as they join. In 1965 the lawyer John Banzhaf proposed a cousin: count the winning coalitions in which a member is a swing (the coalition would lose without them), and divide by the total number of swings.
Under the 1957 Treaty of Rome, the Council of the European Economic Community voted with France, Germany and Italy holding 4 votes each, Belgium and the Netherlands 2 each, and Luxembourg 1; a qualified majority needed 12 of the 17. Every other member’s votes are even, so every coalition without Luxembourg has an even total, and adding Luxembourg’s single vote to a total of 11 is impossible. Luxembourg could never be pivotal: its power was exactly zero, by both measures.
Nassau County’s Board of Supervisors had weights 31, 31, 28, 21, 2 and 2, and a simple majority of 58 out of 115 votes passed a motion. Any two of the three biggest districts make at least 59, a majority. The other three together have only 25 votes, not enough to turn any losing group into a winner. So North Hempstead, with 21 votes, Long Beach and Glen Cove had no power at all; the three big districts had a third each. Banzhaf used this case to argue that weighted voting “doesn’t work”.
Power depends on how often you can swing an outcome, not on your share of the votes. Two shareholders with 49% each and a third with 2% have exactly equal power when 51% is needed: any two of them win. A member with 18% of the votes can have none, as in Nassau County. When you look at a voting rule, count pivots, not votes.
Where it shows up
- Cost sharing. Runways, pipelines, power lines and shared IT systems are paid for by users with different needs; the airport rule is the classic way to split them fairly.
- Profit splitting. Partnerships, joint ventures and mergers face the core’s question (will anyone leave?) and the Shapley value’s (does each partner get what they add?).
- Voting rules. Councils, shareholder meetings and international bodies use weighted votes; power indices have been used in court cases and in debates over the European Union’s voting rules.
- Attributing results. Whenever several causes produce an outcome together, from team members on a project to marketing channels behind a sale, the Shapley value is a principled way to credit each one.
A little history
John von Neumann and Oskar Morgenstern introduced the characteristic function in Theory of Games and Economic Behavior (1944), most of which is about coalitions.
Lloyd Shapley (1923–2016) published “A Value for n-Person Games” in 1953 in Contributions to the Theory of Games II, and with Martin Shubik applied it to voting in the American Political Science Review in 1954. He shared the 2012 Nobel Memorial Prize in Economic Sciences with Alvin Roth, mainly for his work on stable matching (Chapter 12).
Donald Gillies defined the core in his 1953 Princeton thesis; Olga Bondareva (1963) and Shapley (1967) characterized when it is non-empty. John Banzhaf published his index in the Rutgers Law Review in 1965.
Practice
1. Three players: every single player and the pair {2, 3} are worth 0; {1, 2} and {1, 3} are worth 6; all three are worth 12. Find the Shapley value.
Show the answer
Player 1 adds 0 when first (2 orders), 6 when second (2 orders) and 12 when last (2 orders): (0 + 0 + 6 + 6 + 12 + 12)/6 = 6. Player 2 adds 0 when first, 6 after player 1, 0 after player 3, and 12 − 6 = 6 when last (2 orders): (0 + 0 + 6 + 0 + 6 + 6)/6 = 3. Player 3 also gets 3 by symmetry. Check: 6 + 3 + 3 = 12.
2. Is the split (6, 3, 3) from problem 1 in the core?
Show the answer
Yes. {1, 2} gets 9 ≥ 6, {1, 3} gets 9 ≥ 6, {2, 3} gets 6 ≥ 0, and everyone gets at least 0. The core is every split with x2 ≤ 6, x3 ≤ 6 and all shares non-negative.
3. Three planes need runways costing $6M, $10M and $16M. Split the $16M runway by the Shapley value.
Show the answer
The first $6M is split three ways: $2M each. The next $4M is split by the two larger planes: $2M each. The last $6M goes to the largest. Shares: $2M, $4M and $10M.
4. Prove that the three-player majority game (any two players win $1) has an empty core.
Show the answer
The core needs x1 + x2 ≥ 1, x1 + x3 ≥ 1 and x2 + x3 ≥ 1. Adding them: 2(x1 + x2 + x3) ≥ 3, so the total must be at least 1.5. But only 1 is available.
5. A council has three members with 5, 3 and 2 votes; 6 votes pass a motion. Find the Shapley–Shubik and Banzhaf indices.
Show the answer
Of the 6 orders, the 5-vote member is pivotal in 4 (whenever they are not first), and the other two in 1 each: Shapley–Shubik (2/3, 1/6, 1/6). Winning coalitions: {5, 3}, {5, 2} and {5, 3, 2}. Swings: the 5-vote member in all three, the 3-vote member only in {5, 3}, the 2-vote member only in {5, 2}: Banzhaf (3/5, 1/5, 1/5). The members with 3 and 2 votes have exactly the same power. Set this council up in the simulation to check.
6. Compute the Shapley value of the merger game (alone 10, 20, 30; pairs 40, 50, 60; all 80). Is it in the core?
Show the answer
Firm A adds 10 first (2 orders), 20 after B, 20 after C, and 80 − 60 = 20 last (2 orders): (10 + 10 + 20 + 20 + 20 + 20)/6 = 16.67. Firm B adds 20, 20, 30 after A, 30 after C, and 30, 30 last: 26.67. Firm C gets 80 − 16.67 − 26.67 = 36.67. It satisfies every core condition (for example, A gets 16.67 ≤ 20), so yes; the merger game is convex.
7. (Harder) For three players whose singletons are worth 0 and whose pairs are worth no more than v(N), prove that the core is non-empty exactly when v(12) + v(13) + v(23) ≤ 2v(N).
Show the answer
With Σx = v(N), the pair condition xi + xj ≥ v(ij) is the same as xk ≤ yk := v(N) − v(ij), where k is the third player, and yk ≥ 0. So the core is {x: 0 ≤ xk ≤ yk, Σx = v(N)}, which is non-empty exactly when Σyk ≥ v(N), that is, 3v(N) − Σv(ij) ≥ v(N). This is the three-player case of the Bondareva–Shapley theorem. Our test checked it against the triangle picture for 20,000 random games.
How the interactive works
The orders. The simulation lists every order of arrival (6 or 24) and plays them in turn. Each player’s bar is the average of their marginal contributions over the orders done so far; after the last order it equals the Shapley value, which is also computed directly from the formula. For the airport games, which are about costs, the numbers are costs and the Shapley value is each plane’s share of the bill.
The triangle. A split x of a three-player game is drawn by its shares of the extra worth E = v(N) − Σv({i}). Each pair’s condition becomes a straight line; the core is the triangle clipped by the three lines. Power indices are computed exactly by listing all orders (up to 720) and all coalitions (up to 64).
What’s simplified. Worth can be split freely (transferable payoff), and the grand coalition forms. Other solution ideas, like the nucleolus (the split that makes the unhappiest coalition as happy as possible), are left out.
How it was checked (Node.js tests, run before the page was built):
- Gloves: (2/3, 1/6, 1/6) by the formula and by averaging the 6 orders; the core is the single point (1, 0, 0), and the Shapley value is not in it.
- Airports: (2.667, 4.167, 6.167) for runways of 8, 11 and 13; (5, 15, 30, 70) for 20, 50, 80 and 120, matching Littlechild and Owen’s rule. Merger: (16.67, 26.67, 36.67), inside the core with corners (20, 30, 30), (10, 30, 40), (20, 20, 40). Majority: empty core.
- 20,000 random three-player games: the clipped triangle is empty exactly when the Bondareva–Shapley test says so, and its center is always in the core. 2,000 random four-player games satisfy efficiency, additivity and the null-player rule; 2,000 convex games always had the Shapley value in the core.
- Voting: Luxembourg’s power is 0 in the 1958 Council (the big three 0.2333 each by Shapley–Shubik); Nassau’s three small districts have 0 and the big three 1/3 each; 49/49/2 gives equal thirds.
Check yourself
What is a player’s marginal contribution to a coalition S?
Show the answer
It’s the difference the player makes. The Shapley value averages it over all orders of arrival.
In the glove game with one left glove and two right gloves, what does the left-glove owner get by the Shapley value?
Show the answer
Lefty adds the $1 in 4 of the 6 orders. (The core, by contrast, gives Lefty everything.)
What does it mean for the core to be empty?
Show the answer
No split is stable. The majority game is the classic example.
Which property does not appear among Shapley’s axioms?
Show the answer
Stability is the core’s requirement, and the Shapley value can violate it.
Three shareholders own 49%, 49% and 2%, and 51% is needed. How is power divided?
Show the answer
Any two shareholders together pass a motion, and no one alone can, so all three are in exactly the same position.
Sources
- M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapter 8, “Coalitional Games and the Core”.
- R. B. Myerson, Game Theory: Analysis of Conflict (Harvard University Press, 1991), chapter 9, “Coalitions in Cooperative Games”.
- L. S. Shapley, “A Value for n-Person Games”, in H. W. Kuhn and A. W. Tucker (eds.), Contributions to the Theory of Games II, Annals of Mathematics Studies 28, 307–317 (Princeton University Press, 1953); “Cores of Convex Games”, International Journal of Game Theory 1, 11–26 (1971); “On Balanced Sets and Cores”, Naval Research Logistics Quarterly 14(4), 453–460 (1967).
- L. S. Shapley and M. Shubik, “A Method for Evaluating the Distribution of Power in a Committee System”, American Political Science Review 48(3), 787–792 (1954).
- J. F. Banzhaf III, “Weighted Voting Doesn’t Work: A Mathematical Analysis”, Rutgers Law Review 19(2), 317–343 (1965); University of Alabama at Birmingham, Weighted Voting notes (the Nassau County weights).
- S. C. Littlechild and G. Owen, “A Simple Expression for the Shapley Value in a Special Case”, Management Science 20(3), 370–372 (1973); S. C. Littlechild and G. F. Thompson, “Aircraft Landing Fees: A Game Theory Approach”, Bell Journal of Economics 8(1), 186–204 (1977).
- D. B. Gillies, “Solutions to General Non-Zero-Sum Games”, in Contributions to the Theory of Games IV, Annals of Mathematics Studies 40 (Princeton University Press, 1959); J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, 1944).
- Treaty establishing the European Economic Community (Rome, 1957), Article 148: the weighting of votes in the Council.
- The Nobel Prize, The Prize in Economic Sciences 2012.
- Wikipedia (secondary): Shapley value, Core (game theory), Banzhaf power index, Shapley–Shubik power index.