Phase VII — Game Theory for Optimization & Robotics | Week 15 | 2.5 hours The unique fair way to split the pie — backed by four irrefutable axioms.
When three robots complete a multi-pick order, how much credit does each deserve? The Shapley value answers this: evaluate each robot's marginal contribution across every possible joining order. This same principle powers SHAP values in ML — explaining which sensor or subsystem contributed most to a prediction or fault diagnosis.
For a TU game $(N, v)$, a value is a function $\phi: \mathcal{G}^N \to \mathbb{R}^n$ assigning a payoff to each player. Shapley (1953) showed exactly one value satisfies:
$$\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\;(n - |S| - 1)!}{n!} \left[ v(S \cup \{i\}) - v(S) \right]$$
Interpretation: Average the marginal contribution $v(S \cup \{i\}) - v(S)$ over all possible orderings in which player $i$ joins.
Equivalently, using permutations $\pi$ of $N$:
$$\phi_i(v) = \frac{1}{n!} \sum_{\pi \in \Pi(N)} \left[ v(P_i^\pi \cup \{i\}) - v(P_i^\pi) \right]$$
where $P_i^\pi$ is the set of players preceding $i$ in permutation $\pi$.
"""Shapley value computation — Day 100"""
import numpy as np
from itertools import permutations, combinations
from math import factorial
def shapley_value(N, v):
"""Compute exact Shapley value for a TU game.
Args:
N: set of players
v: characteristic function v(S) -> float, S is frozenset
Returns:
dict mapping player -> Shapley value
"""
players = sorted(N)
n = len(players)
phi = {i: 0.0 for i in players}
for i in players:
others = [p for p in players if p != i]
for size in range(0, n):
for S_tuple in combinations(others, size):
S = frozenset(S_tuple)
s = len(S)
weight = factorial(s) * factorial(n - s - 1) / factorial(n)
marginal = v(S | {i}) - v(S)
phi[i] += weight * marginal
return phi
def shapley_via_permutations(N, v):
"""Compute Shapley value by averaging over all permutations (brute force)."""
players = sorted(N)
n = len(players)
phi = {i: 0.0 for i in players}
count = 0
for perm in permutations(players):
count += 1
predecessors = set()
for p in perm:
marginal = v(frozenset(predecessors | {p})) - v(frozenset(predecessors))
phi[p] += marginal
predecessors.add(p)
return {i: phi[i] / count for i in players}
def verify_axioms(N, v, phi):
"""Verify Shapley axioms hold for computed values."""
players = sorted(N)
# Efficiency
total = sum(phi[i] for i in players)
eff = abs(total - v(frozenset(players))) < 1e-9
print(f"Efficiency: sum={total:.4f}, v(N)={v(frozenset(players)):.4f} -> {'PASS' if eff else 'FAIL'}")
# Null player check
for i in players:
is_null = all(
abs(v(frozenset(S) | {i}) - v(frozenset(S))) < 1e-9
for r in range(len(players))
for S in combinations([p for p in players if p != i], r)
)
if is_null:
print(f"Null player {i}: phi={phi[i]:.4f} -> {'PASS' if abs(phi[i]) < 1e-9 else 'FAIL'}")
def voting_game_shapley(weights, quota):
"""Shapley-Shubik power index for a weighted voting game."""
n = len(weights)
N = set(range(n))
def v(S):
return 1.0 if sum(weights[i] for i in S) >= quota else 0.0
return shapley_value(N, v)
# --- Demo ---
if __name__ == "__main__":
# Example: 3-player game
v_dict = {
frozenset(): 0,
frozenset([1]): 0, frozenset([2]): 0, frozenset([3]): 0,
frozenset([1, 2]): 5, frozenset([1, 3]): 6, frozenset([2, 3]): 7,
frozenset([1, 2, 3]): 10
}
v = lambda S: v_dict.get(frozenset(S), 0)
N = {1, 2, 3}
phi_exact = shapley_value(N, v)
phi_perm = shapley_via_permutations(N, v)
print(f"Shapley (formula): {phi_exact}")
print(f"Shapley (permutations): {phi_perm}")
verify_axioms(N, v, phi_exact)
# UN Security Council-style voting
# 5 permanent (veto) + 10 non-permanent, quota = 39 (with vetoes)
weights = [7]*5 + [1]*10 # permanent members have high weight
quota = 39
power = voting_game_shapley(weights, quota)
print(f"\nVoting game power index:")
for i, p in power.items():
label = "Permanent" if i < 5 else "Non-perm"
print(f" Player {i} ({label}): {p:.4f}")
P1. Compute the Shapley value for the glove game: $N=\{L_1, L_2, R\}$, $v(S) = \min(\text{left gloves in } S, \text{right gloves in } S)$.
P2. Three towns share an airport runway. Costs: Town A needs 100m ($1M), Town B needs 200m ($3M), Town C needs 300m ($6M). Use Shapley to allocate costs.
P3. Show that the Shapley value of a convex game lies in the core.
E1. Implement a Monte Carlo approximation of the Shapley value using random permutation sampling. Compare accuracy vs. exact for $n=10$ players with $K=1000$ samples.
E2. Compute the nucleolus for the 3-player game above and compare with the Shapley value. When do they coincide?
E3. Connect Shapley values to SHAP: for a linear model $f(x) = \beta_0 + \sum \beta_i x_i$, show $\text{SHAP}_i = \beta_i (x_i - \mathbb{E}[x_i])$.