Understanding Shapley Values with Venn Diagrams
post by Carson L · 2024-12-06T21:56:43.960Z · LW · GW · 34 commentsThis is a link post for https://medium.com/@carson.loughridge/shapley-values-unlocking-intuition-with-venn-diagrams-86e76d8c99c5
Contents
34 comments
34 comments
Comments sorted by top scores.
comment by ProgramCrafter (programcrafter) · 2024-12-12T00:15:14.744Z · LW(p) · GW(p)
Shapley values are the ONLY way to guarantee: <Efficiency, Symmetry, Linearity, Null player properties>
Well it doesn't end at that: it turns out Shapley values for more than 2 players are not nicely behaved and instead violate Maximin Dominance, as demonstrated in https://www.lesswrong.com/posts/vJ7ggyjuP4u2yHNcP/threat-resistant-bargaining-megapost-introducing-the-rose#ROSE_Value__N_Player_Case__ [LW · GW].
The article I link showed how this is fixed:
Shapley values are about adding everyone one-by-one to a team in a random order and everyone gets their marginal value they contributed to the team.
And that's kinda like giving everyone a random initiative ordering and giving everyone the surplus they can extract in the resulting initiative game.
If we're doing that, then maybe a player, regardless of their position, can ensure they get their maximin value? Maybe this sort of Random-Order Surplus Extraction can work. ROSE.
comment by Dweomite · 2024-12-17T03:47:04.747Z · LW(p) · GW(p)
A problem I have with Shapley Values is that they can be exploited by "being more people".
Suppose Alice and Bob can make a joint venture with a payout of $300. Synergies:
- A: $0
- B: $0
- A+B: $300
Shapley says they each get $150. So far, so good.
Now suppose Bob partners with Carol and they make a deal that any joint ventures require both of them to approve; they each get a veto. Now the synergies are:
- A+B: $0 (Carol vetoes)
- A+C: $0 (Bob vetoes)
- B+C: $0 (venture requires Alice)
- A+B+C: $300
Shapley now says Alice, Bob, and Carol each get $100, which means Bob+Carol are getting more total money ($200) than Bob alone was ($150), even though they are (together) making exactly the same contribution that Bob was paid $150 for making in the first example.
(Bob personally made less, but if he charges Carol a $75 finder's fee then Bob and Carol both end up with more money than in the first example, while Alice ends up with less.)
By adding more partners to their coalition (each with veto power over the whole collective), the coalition can extract an arbitrarily large share of the value.
Replies from: Radamantis↑ comment by NunoSempere (Radamantis) · 2024-12-17T06:46:16.458Z · LW(p) · GW(p)
Adding a person with veto power is not a neutral change.
Replies from: Dweomite, Ninety-Three↑ comment by Dweomite · 2024-12-17T09:55:29.649Z · LW(p) · GW(p)
I'm not sure what you're trying to say.
My concern is that if Bob knows that Alice will consent to a Shapley distribution, then Bob can seize more value for himself without creating new value. I feel that a person or group shouldn't be able to get a larger share by intentionally hobbling themselves.
↑ comment by Ninety-Three · 2024-12-18T20:13:30.608Z · LW(p) · GW(p)
You can make it work without an explicit veto. Bob convinces Alice that Carol will be a valuable contributor to the team. In fact, Carol does nothing, but Bob follows a strategy of "Do nothing unless Carol is present". This achieves the same synergies:
- A+B: $0 (Venture needs action from both A and B, B chooses to take no action)
- A+C: $0 (Venture needs action from both A and B)
- B+C: $0 (Venture needs action from both A and B)
- A+B+C: $300
In this way Bob has managed to redirect some of Alice's payouts by introducing a player who does nothing except remove a bottleneck he added into his own playstyle in order to exploit Alice.
Replies from: Radamantis↑ comment by NunoSempere (Radamantis) · 2024-12-18T21:45:14.796Z · LW(p) · GW(p)
Shapley values are constructed such that introducing a null player doesn't change the result. You are doing something different by considering the wrong counterfactual (one where C exists but isn't part of the coalition, vs one when it doesn't exist)
Replies from: Dweomitecomment by cubefox · 2024-12-08T00:31:14.121Z · LW(p) · GW(p)
Explaining the Shapley value in terms of the "synergies" (and the helpful split in the Venn diagram) makes much more intuitive sense than the more complex normal formula without synergies, which is usually just given without motivation. That being said, it requires first computing the synergies, which seems somewhat confusing for more than three players. The article itself doesn't mention the formula for the synergy function, but Wikipedia has it.
Replies from: eric-kibogo↑ comment by ostentatiousfox (eric-kibogo) · 2024-12-12T06:32:04.380Z · LW(p) · GW(p)
I thought this too- working with Shapley values is quite intuitive, and the article does an excellent job of this- but how do we derive the synergy values to plug-in in the first place? How do we know that Liam + Emma’s synergy = 0?
Replies from: GuySrinivasan↑ comment by SarahNibs (GuySrinivasan) · 2024-12-13T19:54:20.275Z · LW(p) · GW(p)
Liam alone makes $10
Emma alone makes $20
Liam + Emma make $30
$30 - ($10 + $20) = $0, their synergy.
In general: the synergy is how much more or less the coalition gets than each member's individual contribution plus all subset synergies.
comment by Raemon · 2024-12-11T20:50:13.178Z · LW(p) · GW(p)
Curated. This was a quite nice introduction. I normally see Shapley values brought up in a context that's already moderately complicated, and having a nice simple explainer is helpful!
I'd like it if the post went into a bit more detail about when/how Shapley values tend to get used in real world contexts.
comment by habryka (habryka4) · 2024-12-07T22:51:59.645Z · LW(p) · GW(p)
Do you know whether the person who wrote this would be OK with crossposting the complete content of the article to LW? I would be interested in curating it and sending it out in our 30,000 subscriber curation newsletter, if they were up for it.
Replies from: agucovacomment by P. João (gabriel-brito) · 2024-12-19T23:23:13.369Z · LW(p) · GW(p)
Thank you for this insightful post! When discussing value distribution with my partners, we faced the challenge of fairly allocating contributions without precise knowledge of their impact. I proposed a solution: involving an external evaluator with business expertise but no direct access to the function. Their task was to predict value splits, and their reward was proportional to how accurate their estimates were compared to the final distribution.
This approach aimed to handle uncertainty while guiding team efforts strategically. It’s fascinating to see how Shapley values offer a theoretical foundation for such practical challenges.
comment by David James (david-james) · 2024-12-16T13:47:33.502Z · LW(p) · GW(p)
Hopefully, you have gained some intuition for why Shapley values are “fair” and why they account for interactions among players.
The article fails to make a key point: in political economy and game theory, there are many definitions of "fairness" that seem plausible at face value, especially when considered one at a time. Even if one puts normative questions to the side, there are mathematical limits and constraints as one tries to satisfy various combinations simultaneously. Keeping these in mind, you can think of this as a design problem; it takes some care to choose metrics that reinforce some set of desired norms.
comment by aphyer · 2024-12-12T21:11:04.058Z · LW(p) · GW(p)
I think you may have mixed up the ordering halfway through the example: in the first and third tables 'Emma and you' is $90 while 'Emma and Liam'is $30, but in the second it's the other way around, and some of the charts seem odd as a result?
comment by Ninety-Three · 2024-12-18T20:06:48.054Z · LW(p) · GW(p)
Shapley values are the ONLY way to guarantee:
- Efficiency — The sum of Shapley values adds up to the total payoff for the full group (in our case, $280).
- Symmetry — If two players interact identically with the rest of the group, their Shapley values are equal.
- Linearity — If the group runs a lemonade stand on two different days (with different team dynamics on each day), a player’s Shapley value is the sum of their payouts from each day.
- Null player — If a player contributes nothing on their own and never affects group dynamics, their Shapley value is 0.
I don't think this is true. Consider an alternative distribution in which each player receives their full "solo profits", and receives a share of each synergy bonus equal to their solo profits divided by the sum of all solo profits of all players involved in the synergy bonus. In the above example, you receive 100% of your solo profits, 30/(30+10)=3/4 of the You-Liam synergy, 30/(30+20)=3/5 of the You-Emma synergy, and (30/30+20+10)=1/2 of the everyone synergy, for a total payout of $159. This is justified on the intuition that your higher solo profits suggest you are doing "more work" and deserve a larger share.
This distribution does have the unusual property that if a player's solo profits are 0, they can never receive any payouts even if they do produce synergy bonuses. This seems like a serious flaw, since it gives "synergy-only" players no incentive to participate, but unless I've missed something it does meet all the above criteria.
↑ comment by Martin Randall (martin-randall) · 2024-12-19T01:18:50.360Z · LW(p) · GW(p)
I don't think this proposal satisfies Linearity (sorry, didn't see kave's reply before posting). Consider two days, two players.
Day 1:
- A => $200
- B => $0
- A + B => $400
Result: $400 to A, $0 to B.
Day 2:
- A => $100
- B => $100
- A + B => $200
Result: $100 to A, $100 to B.
Combined:
- A => $300
- B => $100
- A + B => $600
- So: Synergy(A+B) => $200
Result: $450 to A, $150 to B. Whereas if you add the results for day 1 and day 2, you get $500 to A, $100 to B.
Replies from: Ninety-Three, rj-wright↑ comment by Ninety-Three · 2024-12-19T11:38:57.076Z · LW(p) · GW(p)
Ah, I was going off the given description of linearity which makes it pretty trivial to say "You can sum two days of payouts and call that the new value", looking up the proper specification I see it's actually about combining two separate games into one game and keeping the payouts the same. This distribution indeed lacks that property.
↑ comment by RJ Wright (rj-wright) · 2024-12-21T17:10:18.561Z · LW(p) · GW(p)
I'm just learning this, please forgive me if I'm misunderstanding. I'm calculating your example differently though:
Day 1: (200 + (400-200-0)/2) = 300 to A (0 + (400-200-0)/2) = 100 to B
Day 2: (100 + (200-100-100)/2) = 100 to A (100 + (200-100-100)/2) = 100 to B
Day 1+2: (300 + (600-300-100)/2) = 400 to A (100 + (600-300-100)/2) = 200 to A
300+100 does equal 400, 100+100 does equal 200
Sum of parts does equal the combined?
Replies from: martin-randall↑ comment by Martin Randall (martin-randall) · 2024-12-21T22:54:34.061Z · LW(p) · GW(p)
Your calculations look right for Shapley Values. I was calculating based on Ninety-Three's proposal (see here [LW(p) · GW(p)]). So it's good that in your calculations the sum of parts equals the combined, that's what we'd expect for Shapley Values.
Replies from: rj-wright↑ comment by RJ Wright (rj-wright) · 2024-12-22T17:10:28.702Z · LW(p) · GW(p)
Doh! Thanks for the clarification. I see I misunderstood you targeting Ninety-Three's proposal about locking in a "more work" ratio.
For me, locking in the ratio of solo profits intuitively feels unfair, and would not be a deal I'd agree to. Translating feeling to words, my personally-intuitive Alice (A) and Bethany (B) story would go:
Alice is a trained watchmaker, Bethany makes robots. They both go into the business of watch-making.
Alone, Alice pulls in $10,000/day. Expensive watches, but very slow to make.
Alone, Bethany pulls a meer $150/day. Cheapo ones, but she can produce tons!
Together, with Alice's expertise + Bethany's robot automation, they make $150,000/day!
Alone, neither is able to compensate for their weakness: Alice's is production speed, Bethany's being quality. The magic from their synergy comes from their individual weaknesses being overwritten by the other's strengths. Value added is a completely separate entity versus the ratio of their solo efforts; it simply does not exist unless they partner up. Hence, I must treat it separately and that difference in total value vs. the sum of their individual efforts rightfully should be divided equally.
The value/cost of doing business w/ others, perhaps?
comment by David James (david-james) · 2024-12-16T13:54:55.633Z · LW(p) · GW(p)
To clarify: the claim is that Shapley values are the only way to guarantee the set containing all four properties: {Efficiency, Symmetry, Linearity, Null player}. There are other metrics that can achieve proper subsets.
comment by cabbageknees · 2024-12-12T20:59:19.685Z · LW(p) · GW(p)
Emma, Liam$20 + $30 + $40$90
I think the emma/liam and you/emma rows are switched in the synergy table
Replies from: Carson Lcomment by XelaP (scroogemcduck1) · 2025-01-04T07:52:32.661Z · LW(p) · GW(p)
I often find illustrative explanations like these either obvious or useless. But this was amazing! Those venn diagrams really are an extremely simple and intuitive and beautiful way to see Shapley values!
comment by mbissell (mbiss) · 2024-12-30T18:53:38.617Z · LW(p) · GW(p)
Very cool — one of the best explanations of Shapley values I've seen! Thinking abstractly — is it fair to say that the Great Man Theory of history is essentially an argument about the magnitude of the Shapley values of prominent historical figures (where the payoff is some measure of societal impact)?
comment by Martin Randall (martin-randall) · 2024-12-15T16:09:19.320Z · LW(p) · GW(p)
Playing around with the math, it looks like Shapley Values are also cartel-independent, which was a bit of a surprise to me given my prior informal understanding. Consider a lemonade stand where Alice (A) has the only lemonade recipe and Bob (B1) and Bert (B2) have the only lemon trees. Let's suppose that the following coalitions all make $100 (all others make $0):
- A+B1
- A+B2
- A+B1+B2 (excess lemons get you nothing)
Then the Shapley division is:
- A: $50
- B1: $25
- B2: $25
If Bob and Bert form a cartel/union/merger and split the profits then the fair division is the same.
Previously I was expecting that if there are a large number of Bs and they don't coordinate, then Alice would get a higher proportion of the profits, which is what we see in real life. This also seems to be the instinct of others (example [LW(p) · GW(p)]).
I think I'm still missing something, not sure what.
Replies from: Dweomite↑ comment by Dweomite · 2024-12-17T04:10:51.678Z · LW(p) · GW(p)
If B1 and B2 structure their cartel such that each of them gets a veto over the other, then the synergies change so that A+B1 and A+B2 both generate nothing, and you need A+B1+B2 to make the $100, which means B1 and B2 each now have a Shapley value of $33.3 (up from $25).
Also, I wouldn't describe the original Shapley Values as "no coordination". With no coordination, there's no reason the end result should involve paying any non-zero amount to both B1 and B2, since you only need one of them to assent. I think Shapley Values represent a situation that's more like "everyone (including Alice) coordinates".
comment by WitheringWeights (EZ97) · 2024-12-09T13:25:09.219Z · LW(p) · GW(p)
I was teaching myself bits of cooperative game theory and this is the clearest explanation I've found so far. I think it's a nice complement to this one [LW · GW].
comment by depressurize (anchpop) · 2024-12-07T22:24:49.078Z · LW(p) · GW(p)
Thanks, this is a beautiful explanation