Cooperative Game Theory: How to Split the Pie Fairly

Three friends start a company together. After five years of hard work, they sell it for $10 million.

How should they split the money?

• Equal shares? ($3.33M each)
• Proportional to hours worked?
• Based on who contributed what?
• What if one person brought the key technology, another the business connections, and the third the execution?

Cooperative game theory provides mathematical answers to these questions.

Unlike traditional game theory (where players compete), cooperative game theory studies how players form coalitions and divide the gains from cooperation.

Cooperative vs Non-Cooperative Game Theory

Non-Cooperative Game Theory:

• Players act independently
• Focus: What strategies will players choose?
• Solution concept: Nash Equilibrium
• Examples: Prisoner’s Dilemma, auctions, oligopoly competition

Cooperative Game Theory:

• Players form binding coalitions
• Focus: How should coalitions divide their gains?
• Solution concept: Shapley value, Core, Nucleolus
• Examples: Profit-sharing, cost allocation, voting power

Key assumption in cooperative games: Players can make binding agreements (enforced by contracts, law, or social norms).

The Characteristic Function

Definition: A cooperative game is defined by a characteristic function $v(S)$ that assigns a value to each coalition $S$.

$v(S)$ = the total value (profit, utility) that coalition $S$ can achieve on its own.

Example: Three-player game

Players: Alice (A), Bob (B), Carol (C)

Coalition values:

• $v(\emptyset) = 0$ (empty coalition gets nothing)
• $v({A}) = 10$ (Alice alone gets 10)
• $v({B}) = 15$ (Bob alone gets 15)
• $v({C}) = 12$ (Carol alone gets 12)
• $v({A,B}) = 40$ (Alice + Bob together get 40)
• $v({A,C}) = 35$ (Alice + Carol get 35)
• $v({B,C}) = 38$ (Bob + Carol get 38)
• $v({A,B,C}) = 60$ (All three together get 60)

Observation: $v({A,B,C}) = 60 > 40 + 12 = 52$ — cooperation creates value!

Question: If A, B, and C form the grand coalition and get 60, how should they split it?

Desirable Properties of a Fair Division

Before diving into solutions, what properties should a “fair” division have?

1. Efficiency (Pareto Optimality)

The coalition should create maximum value — typically the grand coalition.

$$\sum_{i} x_i = v(N)$$

(Where $N$ is the set of all players)

Translation: Split the whole pie, don’t leave value on the table.

2. Individual Rationality

No player should get less than they could achieve alone.

$$x_i \geq v({i})$$

Translation: No one agrees to cooperate if they’d be worse off.

3. Coalitional Rationality (The Core)

No subset of players should have incentive to break away.

For any coalition $S$: $$\sum_{i \in S} x_i \geq v(S)$$

Translation: Every subgroup gets at least what they could achieve independently.

4. Symmetry

Players who contribute equally should receive equal payoffs.

Translation: Fairness demands treating identical contributions identically.

5. Additivity

If two games are played, the payoff in the combined game should equal the sum of payoffs in each game.

Translation: Payoffs shouldn’t depend on arbitrary framing.

Problem: No division scheme satisfies all properties for all games!

We must choose which properties to prioritize.

The Shapley Value: A Unique Fair Solution

Lloyd Shapley (Nobel Prize, 2012) proved there is exactly one division scheme satisfying efficiency, symmetry, additivity, and the null player property.

The Shapley value answers: What is each player’s marginal contribution on average?

Intuition

Imagine players join the coalition one by one in random order.

Each player’s Shapley value = their average marginal contribution across all possible orderings.

Formula

For player $i$:

$$\phi_i(v) = \sum_{S \subseteq N \setminus {i}} \frac{|S|! (|N| - |S| - 1)!}{|N|!} \left[ v(S \cup {i}) - v(S) \right]$$

Translation:

• Consider all coalitions $S$ that don’t include $i$
• Compute $i$’s marginal contribution when joining $S$: $v(S \cup {i}) - v(S)$
• Weight by probability of that ordering occurring
• Sum over all coalitions

Example: Computing Shapley Values

Three players: A, B, C

Coalition values (from earlier):

• $v(\emptyset) = 0$
• $v({A}) = 10$, $v({B}) = 15$, $v({C}) = 12$
• $v({A,B}) = 40$, $v({A,C}) = 35$, $v({B,C}) = 38$
• $v({A,B,C}) = 60$

Compute Shapley value for Alice (A):

Possible orderings and A’s marginal contribution:

1. A, B, C: A joins empty set → contributes $10 - 0 = 10$
2. A, C, B: A joins empty set → contributes $10 - 0 = 10$
3. B, A, C: A joins {B} → contributes $40 - 15 = 25$
4. B, C, A: A joins {B,C} → contributes $60 - 38 = 22$
5. C, A, B: A joins {C} → contributes $35 - 12 = 23$
6. C, B, A: A joins {B,C} → contributes $60 - 38 = 22$

Average: $(10 + 10 + 25 + 22 + 23 + 22) / 6 = 112 / 6 \approx 18.67$

Similarly, compute for B and C:

• $\phi_B \approx 24.67$
• $\phi_C \approx 16.67$

Check: $18.67 + 24.67 + 16.67 = 60$ ✓ (Efficient)

Interpretation:

• Bob (B) gets the most because he’s valuable individually (15) and in coalitions
• Alice gets more than Carol despite lower individual value because she synergizes better with Bob

The Core: Stable Coalitions

Definition: The Core is the set of payoff distributions where no coalition has incentive to break away.

Formal: An allocation $(x_1, x_2, …, x_n)$ is in the Core if:

1. Efficiency: $\sum_i x_i = v(N)$
2. Coalitional Rationality: For all coalitions $S$, $\sum_{i \in S} x_i \geq v(S)$

If the Core is non-empty, its allocations are stable — no subgroup wants to defect.

Problem: The Core can be empty!

Example: Glove Game

Players:

• Alice has 1 left glove
• Bob has 1 right glove

Coalition values:

• $v({A}) = 0$ (left glove alone worthless)
• $v({B}) = 0$ (right glove alone worthless)
• $v({A,B}) = 1$ (pair of gloves worth 1)

Core: Any split $(x_A, x_B)$ where $x_A + x_B = 1$ and $x_A, x_B \geq 0$.

Shapley value: $(0.5, 0.5)$ — symmetric players split equally.

Both are reasonable here.

Example: Empty Core

Three-player voting game:

• Any two players can form a majority and split $100
• All three together still only have $100

Coalition values:

• $v({A}) = v({B}) = v({C}) = 0$
• $v({A,B}) = v({A,C}) = v({B,C}) = 100$
• $v({A,B,C}) = 100$

Suppose allocation is $(x_A, x_B, x_C)$ with $x_A + x_B + x_C = 100$.

For Core, need:

• $x_A + x_B \geq 100$
• $x_A + x_C \geq 100$
• $x_B + x_C \geq 100$

Summing these: $2(x_A + x_B + x_C) \geq 300$, so $x_A + x_B + x_C \geq 150$.

But we also need: $x_A + x_B + x_C = 100$.

Contradiction! The Core is empty.

Interpretation: No matter how you split the $100, some pair will defect and take it all for themselves.

When the Core is empty:

• No stable allocation exists
• Coalitions constantly shift
• Leads to political instability, cycling, chaos

Real-world: This explains coalition instability in parliamentary systems!

The Nucleolus: Minimizing Dissatisfaction

When the Core is empty, the Nucleolus provides an alternative.

Idea: Find the allocation that minimizes the maximum complaint.

For each coalition $S$, define excess:

$$e(S, x) = v(S) - \sum_{i \in S} x_i$$

Excess = how much coalition $S$ could improve by defecting.

Nucleolus: The allocation that lexicographically minimizes the excess vector (sorted from largest to smallest).

Translation: Make the most unhappy coalition as happy as possible, then the second-most unhappy, etc.

Properties:

• Always unique
• Always exists
• If Core is non-empty, Nucleolus is in the Core (specifically, the center)
• Minimizes instability

Interpretation: The Nucleolus is a compromise solution that balances all coalitions’ complaints.

Applications of Cooperative Game Theory

1. Cost Allocation

Problem: Multiple users share a facility (e.g., airport runway, water treatment plant). How to split costs?

Example: Airport runway

Three types of planes use the runway:

• Small planes: Need 1km runway, their cost $c_S = 10M$
• Medium planes: Need 2km runway, incremental cost $c_M = 15M$
• Large planes: Need 3km runway, incremental cost $c_L = 20M$

Total cost: $10M + 15M + 20M = 45M$

Shapley value allocation:

• Small planes pay for their own needs + share of incremental costs: ~$15M
• Medium planes: ~$16M
• Large planes: ~$14M

Justification: Large planes benefit from infrastructure built for small/medium planes, so they don’t pay full incremental cost alone.

2. Voting Power

Problem: In a voting body, how much power does each member really have?

Shapley-Shubik Power Index: Player’s power = probability they are the pivotal voter in a random voting order.

Example: UN Security Council

• 5 permanent members (veto power)
• 10 non-permanent members
• Need 9 votes + no vetoes to pass

Computing Shapley-Shubik index reveals:

• Each permanent member has much more power than each non-permanent member
• Quantifies veto power mathematically

3. Profit Sharing in Joint Ventures

Example: Three companies collaborate on a project.

• Company A brings technology
• Company B brings distribution
• Company C brings manufacturing

Without cooperation:

• A can earn 10 alone
• B can earn 15 alone
• C can earn 12 alone

With cooperation:

• A + B can earn 40
• A + C can earn 35
• B + C can earn 38
• A + B + C can earn 60

Shapley value provides principled profit split:

• A: $18.67
• B: $24.67
• C: $16.67

Reflects each company’s marginal contribution across all possible partnerships.

4. Matching and Assignment Problems

Marriage matching problem (Gale-Shapley):

• Men and women have preferences
• Find stable matching (no pair prefers each other to current partners)

The Core of the marriage game = set of stable matchings

Applications:

• Medical residency matching
• School choice
• Kidney exchange

Bargaining Solutions

Nash Bargaining Solution (1950):

Two players negotiate over surplus. What’s a fair outcome?

Nash’s axioms:

1. Pareto efficiency
2. Symmetry
3. Independence of irrelevant alternatives
4. Invariance to affine transformations

Unique solution: Maximize the product of players’ gains:

$$\max_{(x_1, x_2)} (x_1 - d_1)(x_2 - d_2)$$

Where $(d_1, d_2)$ is the disagreement point (what they get if negotiation fails).

Example:

• Total surplus: $100
• Disagreement point: (0, 0)

Nash solution: $(50, 50)$ — equal split.

If disagreement point is (10, 20):

Nash solution: Maximize $(x_1 - 10)(x_2 - 20)$ subject to $x_1 + x_2 = 100$.

Result: $(45, 55)$ — player with better outside option gets more.

Fair Division Beyond Numbers

Cake cutting: How to divide a heterogeneous good (cake with different toppings)?

Envy-free division: No player prefers another player’s piece.

Proportional division: Each player gets at least 1/n of the value (by their own valuation).

“I cut, you choose” for two players:

• Player 1 cuts cake into two pieces
• Player 2 chooses their preferred piece
• Player 1 gets remaining piece

Result: Both get at least 50% by their own valuation!

For n > 2 players, more complex protocols exist (moving knife, divide-and-conquer).

Key Takeaways

1. Cooperative game theory studies coalition formation and how to divide gains from cooperation
2. Characteristic function $v(S)$ defines the value each coalition can achieve
3. Shapley value — unique fair division based on average marginal contributions
4. The Core — set of allocations where no coalition wants to defect (can be empty!)
5. Nucleolus — minimizes dissatisfaction when Core is empty
6. Applications — cost allocation, voting power, profit sharing, matching markets
7. Nash bargaining solution — maximize product of gains above disagreement point
8. Fair division — envy-free and proportional cake cutting protocols

Cooperative game theory transforms vague notions of “fairness” into precise mathematical concepts, enabling principled solutions to real-world allocation problems.

Practice Problem

Three countries (A, B, C) negotiate a trade agreement.

Coalition values:

• Individual: $v({A}) = 20$, $v({B}) = 30$, $v({C}) = 25$
• Pairs: $v({A,B}) = 70$, $v({A,C}) = 60$, $v({B,C}) = 75$
• All three: $v({A,B,C}) = 120$

Questions:

1. Compute the Shapley value for each country.
2. Is the allocation (35, 50, 35) in the Core?

This post is part of the Game Theory Series, where we explore the mathematics of strategic decision-making. Cooperative game theory provides mathematical foundations for fair allocation, from dividing profits to allocating costs to measuring voting power.