POLS 4728
Shapley values for credit assignment
A SCROLLING EXPLAINER / MAJORITY RULE
Three votes.
One outcome.
Three people vote yes. A proposal needs just two votes to pass.
Everyone helped. But how much credit belongs to each voter?
Scroll to follow the argument
02Take one
Take one
voter away.
Remove A. The remaining pair still passes the proposal. The same happens if we remove B or C.
Each removal changes the outcome by zero. Looking only at the final group leaves us with a puzzle.
03Start with
Start with
the smallest groups.
A coalition is a group of voters whose support we count.
Start with nobody, ∅, then A, B, or C alone. None has enough votes to pass. Give each group a value of zero.
04The second vote
The second vote
makes a difference.
Every pair has two votes, so every pair passes. Give each pair a value of one.
An edge means add exactly one voter. Going from B alone to A and B changes failure to success: 0 → 1.
05Same destination.
Same destination.
Different credit.
Adding the third voter changes nothing. We now have every possible group, and every way to add one voter.
Follow an imagined order: B, then A, then C. A supplies the deciding vote.
06Count every
Count every
possible order.
There are six ways to order three voters. Give each order equal weight.
A’s four joining edges occur 2, 1, 1, and 2 times. Those counts explain their weights.
07Put the
Put the
pieces together.
Multiply each contribution by the fraction of orders in which it occurs. Then add the four terms.
A receives one-third of the total credit.
08 / EXPLOREThe whole
The whole
picture.
B and C receive one-third too. Together, their credits sum to the outcome gained: one.
This is a Hasse diagram of the groups of voters. Each edge adds one voter.
Select a voter or inspect a coalition to explore.
See the notation behind the story to connect this picture to the general formula.
09 / THE VALUE FUNCTIONName the numbers
Name the numbers
on the nodes.
When we gave a failing group zero and a passing group one, we were already using a value function.
Call a group , and call its number . counts the voters in that group.
1 means passes. 0 means fails. The proposal always needs two votes.
10 / THE FORMULAThe calculation,
The calculation,
written compactly.
We have already built every part of this weighted average. is voter ’s Shapley value in the game defined by . Here is the full group, is its size, and is the voter we follow.
The sum visits every coalition that leaves A out: ∅, {B}, {C}, and {B, C}. These are the four starting nodes for A’s joining edges.
11 / THE CONTRIBUTIONRead the change
Read the change
along one edge.
For example, start with . Adding A gives . The contribution is .
The bracketed difference in the formula is exactly this change in value. Choose another starting coalition to compare its edge.
12 / BEFORE AArrange the voters
Arrange the voters
before A.
We counted orders one by one. The members of can arrive in different orders.
With , B and C can arrive as B then C, or C then B. Both orders use the same edge when A joins.
A factorial counts arrangements: 2! = 2 × 1 = 2.
13 / AFTER AArrange the voters
Arrange the voters
after A.
Of the voters, arrived before A, and one is A. That leaves voters, with possible orders.
With , A arrives first. B and C can then arrive in either order.
0! = 1: there is one way to arrange nobody.
14 / THE WEIGHTDivide by every
Divide by every
possible order.
These are the same paths we highlighted. Multiply the choices before A by the choices after A. That counts complete orders using this particular joining edge.
The denominator counts all complete orders. Here , so the weight is the matching count divided by six.
15 / THE SAME CALCULATIONAdd the edges.
Add the edges.
Keep the meaning.
One term for each of A’s four joining edges. Each term is its contribution multiplied by its fraction of the six orders.
The full formula gives the same result: .
For a different game, change the value function . The meaning of the formula stays the same.