Shapley values

A pizza's quality score, built from three upgrades: fresh dough, extra cheese, toppings. Cheese and toppings together are worth much more than their solo effects added up — a real synergy. The bars are each feature's Shapley value: the one splitting of the total credit that accounts for that synergy fairly.

Add features to an empty pizza in some order, and each one's marginal contribution is how much the score jumps when it joins:

• $\pi$ — one possible order in which features could arrive.
• $i$ — the feature whose contribution is being measured.
• $v(S)$ — the value function: the score achieved by a coalition (subset of features) $S$.
• $\text{marginal}(\pi, i)$ — how much the score jumps when feature $i$ joins, given the features already present ahead of it in order $\pi$.

A feature's Shapley value is that marginal contribution, averaged over every possible order features could arrive in:

• $\phi_i$ — feature $i$'s Shapley value: its marginal contribution, averaged over every possible arrival order.
• $n$ — the total number of features being split credit among.

1. Averaging over every order is what makes this fair

   A feature that only pays off in combination with another gets credit for that exactly as often as the ordering happens to reward it, rather than however an arbitrarily chosen single order would credit it.

Step through all six arrival orders. Extra cheese's marginal contribution swings from as little as $2$ (arriving first, alone) to as much as $13$ (arriving after toppings, where the synergy kicks in) — the same feature, wildly different credit, depending only on who got there first. The Shapley value is the one number that averages all six of those swings into a single fair answer.

Baseline (no upgrades) scores $50$; the full pizza scores $80$ — a gap of $30$ to split three ways:

1. Order matters for any one feature

   • In the order dough → cheese → toppings, cheese joins a pizza that already has dough: $v(\{A,B\})-v(\{A\}) = 62-55 = 7$.
   • In the order toppings → cheese → dough, cheese joins a pizza that already has toppings: $v(\{B,C\})-v(\{C\}) = 65-53 = 12$.

   Same feature, same final pizza, different credit, because cheese's payoff depends on what's already there.

2. Average over all 6 orders

   Each feature's marginal contribution across all 6 orderings:

   • Fresh dough: $5, 5, 10, 15, 8, 15$ — summing to $58$, so $\phi_A = 58/6 = 29/3 \approx 9.67$
   • Extra cheese: $7, 19, 2, 2, 19, 12$ — summing to $61$, so $\phi_B = 61/6 \approx 10.17$
   • Toppings: by the same process, also summing to $61$, so $\phi_C = 61/6 \approx 10.17$

   Extra cheese and toppings tie, even though their solo effects ($2$ and $3$) weren't, because they share the same synergy with each other in every ordering that puts them together.

3. The credits add up exactly

   $9.67 + 10.17 + 10.17 = 30$ — precisely the gap between the baseline and the full pizza. This isn't a coincidence: it's the efficiency property built into Shapley values by construction.