shapley-cookies
Table of Contents
1 Problem definition - How to share free cookies fairly?
Three people - Andy, Brian and Chris - are buying cookies at a cookie shop. The store runs a promotion where you get two free cokies per every three cookies buy. Each person of the group has a personal preference for how many cookies they would like to get:
| Andy | Brian | Chris |
|---|---|---|
| 4 | 3 | 2 |
Any cookies on top of that are considered a bonus, but none of the players are willing to pay extra money to get more than this amount of cookies.
1.1 Version 1 - Membership card
Consider that only one of the players, Andy, is eligible for the buy 3 get 2 for free promotion because the promotion is limited to customers who posess a membership card. Therefore the other two players have to form an alliance with Andy in order to benefit from the promotion. How many free cookies does this potential alliance buy, and how should they be split amongst the group?
Below is a table describing the value for each potential alliance, where the value of each playes is described by the total amount of free cookies they would get as part of the deal.
| v(S) | Want | Buy | Free |
|---|---|---|---|
| A | 4 | 3 | 2 |
| B | 3 | 3 | 0 |
| C | 2 | 2 | 0 |
| AB | 7 | 5 | 2 |
| AC | 6 | 4 | 2 |
| BC | 5 | 5 | 0 |
| ABC | 9 | 6 | 4 |
It's rather obvious that the more cookies you buy, the more free ones you get, so it makes sense that the grand coalition consisting of all of the players yields the most free cookies for everyone involved. But how should these four free cookies be divided amongst the group of friends?
| S1 | S2 | S3 | v(S∪{A}) - v(S) | v(A) | v(S∪{B}) - v(S) | v(B) | v(S∪{C}) - v(S) | v(C) |
|---|---|---|---|---|---|---|---|---|
| A | AB | ABC | v(A) | 2 | v(AB) - v(A) | 0 | v(ABC) - v(AB) | 2 |
| A | AC | ABC | v(A) | 2 | v(ABC) - v(AC) | 2 | v(AC) - v(A) | 0 |
| B | AB | ABC | v(AB) - v(B) | 2 | v(B) | 0 | v(ABC) - v(AB) | 2 |
| B | BC | ABC | v(ABC) - v(BC) | 4 | v(B) | 0 | v(BC) - v(B) | 0 |
| C | AC | ABC | v(AC) - v(C) | 2 | v(ABC) - v(AC) | 2 | v(C) | 0 |
| C | BC | ABC | v(ABC) - v(BC) | 4 | v(BC) - v(C) | 0 | v(C) | 0 |
| Σ/N! | 16/3! | 4/3! | 4/3! | |||||
| 8/3 | 2/3 | 2/3 |
Without the discount the friends would have been willing to pay nine units of money to get nine cookies total, but with the discount they only have to pay six units of money and they receive ten cookies, which leaves one cookie up for grabs. To see how much each friend should pay, and how many cookies they should receive, let's first make a fair split of the nine cookies the friends wanted to purchase originally. The avarage cost per cookie is 6/9 or 2/3, with the tenth cookie still left to be divided. Therefore:
| Pays | Equals | Total cookies | Equals | |
|---|---|---|---|---|
| Andy | 4*(2/3) = 8/3 | 2.67.. | 4 + (8/3)/4 | 4.67.. |
| Brian | 3*(2/3) = 2 | 2 | 3 + (2/3)/4 | 3.17.. |
| Chris | 2*(2/3) = 4/3 | 1.33.. | 2 + (2/3)/4 | 2.17.. |
1.2 Version 2 - No limitations
Now consider a case where the previous limitation to members only is lifted. Thus we get:
| v(S) | Want | Buy | Free |
|---|---|---|---|
| v(A) | 4 | 3 | 2 |
| v(B) | 3 | 3 | 2 |
| v(C) | 2 | 2 | 0 |
| v(AB) | 7 | 5 | 2 |
| v(AC) | 6 | 4 | 2 |
| v(BC) | 5 | 3 | 2 |
| v(ABC) | 9 | 6 | 4 |
Again to calculate the Shapley Values:
| S1 | S2 | S3 | v(S∪{A}) - v(S) | v(A) | v(S∪{B}) - v(S) | v(B) | v(S∪{C}) - v(S) | v(C) |
|---|---|---|---|---|---|---|---|---|
| A | AB | ABC | v(A) | 2 | v(AB) - v(A) | 0 | v(ABC) - v(AB) | 2 |
| A | AC | ABC | v(A) | 2 | v(ABC) - v(AC) | 2 | v(AC) - v(A) | 0 |
| B | AB | ABC | v(AB) - v(B) | 0 | v(B) | 2 | v(ABC) - v(AB) | 2 |
| B | BC | ABC | v(ABC) - v(BC) | 2 | v(B) | 2 | v(BC) - v(B) | 0 |
| C | AC | ABC | v(AC) - v(C) | 2 | v(ABC) - v(AC) | 2 | v(C) | 0 |
| C | BC | ABC | v(ABC) - v(BC) | 2 | v(BC) - v(C) | 2 | v(C) | 0 |
| Σ/N! | 10/3! | 10/3! | 4/3! | |||||
| 5/3 | 5/3 | 2/3 |
And to get our fair split:
| Pays | Equals | Total cookies | Equals | |
|---|---|---|---|---|
| Andy | 4*(2/3) = 8/3 | 2.67.. | 4 + (5/3)/4 | 4.42.. |
| Brian | 3*(2/3) = 2 | 2 | 3 + (5/3)/4 | 3.42.. |
| Chris | 2*(2/3) = 4/3 | 1.33.. | 2 + (2/3)/4 | 2.17.. |