Just a little idea that I suddenly remembered but realized I don’t exactly remember now. So writing it down for memory.

Imagine you (“A”) were with two of your friends, B and C. There’s been a long night of drinking and partying, and now the three of you want to go home. Sharing a cab back home makes sense, since you’re nowhere near a train station.

At first, you suggest splitting the cab fare equally three-way, but then you realize that B and C stay (essentially) next to each other. It would be cheaper (per person) for them to just leave you here and to get a cab of their own, but everyone’s being nice and you feel slightly bad about this. So you offer to pay a little more… how much more?

Suppose the cost for each subset of people to take the cab was as follows:

A - 14
B - 16
C - 16
A, B - 25
A, C - 25
B, C - 16
A, B, C - 25

Here’s the way to do it. Take all 6 possible orderings:

And now in each column, we will imagine that the first person (in the ordering) gets the cab, then the second person shows up to join the same cab, and then the third. Each time, the cost goes up a little, so we record the increment in the (respective) new person’s column.

For example, if we start with “A,B,C”, then with A only, A pays 14 dollars. Then B shows up, and pays the additional 11 dollars. Finally, C shows up but doesn’t have to pay anything. Here’s the result for each ordering:

and now you average it:

This is called the Shapley value for each person.

How do we know this is the right value for each person? There are a bunch of intuitive properties that the Shapley values satisfies that makes it tempting to call it the right value:

1. Supposed you switched residences with B, then you would also switch Shapley values with B. (This is called symmetry.)

2. Suppose there were a dummy: maybe imagine that your host, D, is here to send the three of you off. D doesn’t really affect the cab fare, so their value should be zero. This is captured correctly by the Shapley value.

3. Suppose you had another situation where you, B and C were splitting cab fares. Then you expect that doing the Shapley value calculation on the combination of both cab fares should just give you the sum of the two individual Shapley values. (This is called additivity.)

In fact, any value assignment satisfying these three properties has to be the Shapley value (!). Here’s one last property that also makes sense:

4. Suppose that you were in two “cab situations”, and it so happens that the difference between you being on the cab ride or not was the same in both situations, for each combination of people on the cab ride (i.e. your marginal contribution was the same in both situations, regardless of subset). Then you should expect to have the same value in both situations. (This is called marginalist.)

Any symmetric and marginalist value is also forced to be the Shapley value!