Neural Sync Active

Cooperative Games

Registry Synced

Cooperative Games

1037 words

5 min read

Reading compass

Now · 🎯 Learning Objectives

Cooperative Games

🎯 Learning Objectives

Distinguish cooperative from non-cooperative games
Define coalitional games with transferable utility
Compute the Shapley value and understand its axioms
Find and interpret the core of a game
Understand the relationship between core and Shapley value

10.1 Intuition: Binding Agreements

In cooperative games, players can form binding agreements — contracts enforceable by a third party. The question isn't "what will happen?" but "which coalitions will form and how will they split the gains?"

🔑 Key Insight: Cooperative game theory asks: given that players can commit to any agreement, which payoffs are stable and fair? Real-world examples:

Business partnerships: How to split profits among co-founders
Cost allocation: How to divide joint costs among departments
Voting power: How much power does each member of a committee have?

10.2 Formal Definition

A coalitional game (with transferable utility) is a pair

(N, v)

$N = \{1, 2, \dots, n\}$ — set of players
$v: 2^N \to \mathbb{R}$ — characteristic function, where $v(S)$ is the total value coalition $S$ can generate Properties:
$v(\emptyset) = 0$ (empty coalition generates nothing)
Superadditivity: $v(S \cup T) \geq v(S) + v(T)$ for disjoint $S, T$ (merging coalitions don't destroy value)

10.3 The Shapley Value

Idea: What is a fair way to distribute the total value

v(N)

among players? A player's contribution depends on when they join the coalition — first movers add more, latecomers add less. The Shapley value averages over all possible orders.

Formula

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

Where:

$S$ is a coalition that does not include $i$
$v(S \cup \{i\}) - v(S)$ is $i$ 's marginal contribution to coalition $S$
The weight $\frac{|S|! (n-|S|-1)!}{n!}$ is the probability of joining $S$ in a random permutation

Shapley Value Axioms

Axiom	Meaning
Efficiency	$\sum_i \phi_i = v(N)$ — total value is fully distributed
Symmetry	If $i$ and $j$ have identical marginal contributions, $\phi_i = \phi_j$
Dummy player	If $i$ adds nothing to any coalition, $\phi_i = 0$
Additivity	For two games $v$ and $w$ , $\phi_i(v+w) = \phi_i(v) + \phi_i(w)$

Example: Three-Player Game

v(1) = v(2) = v(3) = 0

v(12) = 60

v(13) = 40

v(23) = 30

v(123) = 90

Computing

\phi_1

: |

S

\|S\|

v(S \cup \{1\}) - v(S)

| Weight | Contribution | |-----|-------|--------------------------|--------|-------------| |

\emptyset

| 0 |

v(1) - 0 = 0

\frac{0!2!}{3!} = \frac{1}{3}

| 0 | |

\{2\}

| 1 |

v(12) - v(2) = 60 - 0 = 60

\frac{1!1!}{3!} = \frac{1}{6}

| 10 | |

\{3\}

| 1 |

v(13) - v(3) = 40 - 0 = 40

\frac{1!1!}{3!} = \frac{1}{6}

| 6.67 | |

\{2,3\}

| 2 |

v(123) - v(23) = 90 - 30 = 60

\frac{2!0!}{3!} = \frac{1}{3}

| 20 |

\phi_1 = 0 + 10 + 6.67 + 20 = 36.67

Similarly:

\phi_2 = 31.67

\phi_3 = 21.67

Check:

36.67 + 31.67 + 21.67 \approx 90 = v(123)

✓

10.4 The Core

Idea: An allocation

(x_1, \dots, x_n)

is in the core if no coalition can do better by leaving the grand coalition.

Definition

An imputation

x = (x_1, \dots, x_n)

is in the core if:

Efficiency: $\sum_{i \in N} x_i = v(N)$
Coalitional rationality: $\sum_{i \in S} x_i \geq v(S)$ for all $S \subseteq N$

Example: Three-Player Game

Core conditions:

$x_1 + x_2 + x_3 = 90$
$x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$
$x_1 + x_2 \geq 60$
$x_1 + x_3 \geq 40$
$x_2 + x_3 \geq 30$ From $x_1 + x_2 \geq 60$ and $x_1 + x_2 + x_3 = 90$ : $x_3 \leq 30$ From $x_1 + x_3 \geq 40$ : $x_2 \leq 50$ From $x_2 + x_3 \geq 30$ : $x_1 \leq 60$ Core: $\{(x_1, x_2, x_3): x_i \geq 0, x_1 + x_2 \geq 60, x_1 + x_3 \geq 40, x_2 + x_3 \geq 30, x_1 + x_2 + x_3 = 90\}$

Core vs. Shapley Value

Aspect	Core	Shapley Value
Focus	Stability	Fairness
Uniqueness	May be empty or large	Always unique
Computation	LP feasibility	Formula
Axiomatic	Coalitional rationality	Symmetry, additivity

10.5 Simple Games and Voting Power

A simple game is a coalitional game where

v(S) \in \{0, 1\}

— a coalition either wins or loses. Weighted voting: Each player

i

has weight

w_i

, and a coalition wins if total weight

\geq Q

(quota). Shapley-Shubik Power Index: The Shapley value of a simple game measures voting power — the probability of being the "pivotal" member.

Example: UN Security Council

5 permanent members (veto power)
10 rotating members
9 votes needed to pass The Shapley-Shubik index shows permanent members have vastly more power than rotating members.

📊 Formula Summary

Concept	Formula
Shapley value	$\phi_i = \sum_{S \subseteq N \setminus {i}} \frac{
Core condition	$\sum_{i \in S} x_i \geq v(S) \ \forall S \subseteq N$

✅ Practice Questions

Q1: In a 2-player game with

v(1)=5

v(2)=3

v(12)=12

, find the Shapley value for each player.

Solution

Order (1,2): P1 adds 5 (v(1)-0), P2 adds 7 (v(12)-v(1)) Order (2,1): P2 adds 3 (v(2)-0), P1 adds 9 (v(12)-v(2))

$\phi_1 = \frac{5 + 9}{2} = 7$ $\phi_2 = \frac{7 + 3}{2} = 5$

Check: $7 + 5 = 12 = v(12)$ ✓ Q2: For the same game, find the core. Solution

$x_1 + x_2 = 12$ , $x_1 \geq 5$ , $x_2 \geq 3$ Core: $\{(x_1, x_2): x_1 \geq 5, x_2 \geq 3, x_1 + x_2 = 12\}$ This is the line segment from (5,7) to (9,3). Q3: True or False: The Shapley value is always in the core. Solution

False. The Shapley value may fall outside the core. In the three-player example above, $\phi = (36.67, 31.67, 21.67)$ . Check $x_1 + x_2 = 68.33 \geq 60$ ✓, $x_1 + x_3 = 58.33 \geq 40$ ✓, $x_2 + x_3 = 53.33 \geq 30$ ✓. But this is not always the case — Shapley value can violate coalitional rationality for some games. Join Discord PreviousMechanism Design DeepNextVoting Power