This is extremely well produced, I think it’s the best introduction to Shapley values I’ve ever seen. Kudos for the simple explanation and approachable designs!
(Not an indictment of this site, but with this as with other explainers, I still struggle to see how to apply Shapley values to any real world problems haha—unlike something like quadratic funding, which also sports fancy mechanism math but is much more obvious how to use)
(maybe the part that seems unrealistic is the difficulty of eliciting values for the power set of possible coalitions, as generating a value for any one coalition feels like an expensive process, and the size of a power set grows exponentially with the number of players)
Thanks Austin, yes—the weeks I’ve spent trying to really understand why Shapley uses such a complicated method to calculate the possible coalitions, has left me feeling that it is actually prohibitively cumbersome for most applications. It has been popular in machine learning algorithms, but faces the problem that it is computationally expensive.
I created a comparison calculator to show Shapley next to my own method that simply weights by dividing all the explicit marginal values by the total of all the explicit marginal values and multiplying that by the grand coalition value. I found that, for realistic values being entered, it yields very similar results to Shapley, and yet is easy to calculate on a spare napkin. It also satisfies Shapley’s 4 axioms, and seems more intuitive to me at least.
There might be an issue with mine that you need the total of all marginal values (which is involved in the weighting) to find any one weighted value, whereas Shapley can be used to calculate each weighted marginal value in isolation.
Regardless… who am I to argue with a Nobel Prize winning economist? But I can’t be accused of not trying to get on board :) I like the look of Quadratic Funding, perhaps for a future post.
Thanks, this looks good. I agree on the reason for the factorial method of weighting being very unclear. Unfortunately most sources, like Wikipedia, don’t really try to explain the motivation behind it.
But it seems to me there is a fundamental problem with Shapley values: They ignore probabilities. For example, they assume all necessary conditions are equally important. But this doesn’t seem right.
Say a successful surgery needs both a surgeon and a nurse, otherwise the patient dies. Shapley values (or really any purely counterfactuals account of causal contribution) will then assume that both have contributed equally to the successful surgery. Which arguably isn’t true, because surgeons are much less available (less replaceable) than nurses. If the nurse becomes ill, a different nurse could probably do the task, while if the surgeon becomes ill, the surgery may well have to be postponed. So the surgeon is more important for (contributes more to) a successful surgery.
This apparently comes down to probability. The task of the surgeon was, from a prior perspective, less likely to be fulfilled because it is harder to get hold of a surgeon.
Similarly: What was the main cause of the match getting lit? The match being struck? Or the atmosphere containing oxygen? Both are necessary in the sense that if either hadn’t occurred the match wouldn’t be lit. So their Shapley values would be equal. But it seems clear that the main cause was the match being struck. Why? Because matches being struck is relatively rare, and hence unlikely, while the atmosphere contains oxygen pretty much always.
So I think the contributions calculated for Shapley values should be weighted by something like the inverse of their prior probabilities.
Other notes:
There is another Shapley value calculator. The website isn’t designed as well as the one above, but it contains several examples and it allows assigning a value to the empty coalition, instead assigning it always the value 0.
Several years ago, the EA Forum user George Bridgewater actually pointed out an issue with Shapley values (point 1 here) which is very similar to the one I made above, though he didn’t identify missing probabilities as the problem.
Nice observation. I’m certainly not meaning to advocate for Shapley value—this was largely an attempt to adjust my negative attitude about Shapley value’s flaws, and the attempt was not very successful, but I thought it would be useful to others struggling to understand it, as I was.
I can imagine a way to address the probability issue you raise could be to create probabilistic value entries, where, let’s say we add the participants in the ratio they exist in reality, so pretending there are twice as many nurses as doctors, you could fill out values for a 3 person coalition (2 nurses, 1 doctor), with a value of 10 awarded to any coalition that satisfies a successful surgery (at least one doctor and one nurse). This results in the nurses being awarded a Shapley Value of 1.67 and the doctor being awarded 6.67.
This hack would give a reasonable answer, in this limited situation. But the oxygen:match-strike would lead to a computationally prohibitive outcome given that this hack would require a massive increase in coalitions, leading to exponentially massive computation required.
Thanks for your comments. I might incorporate the empty coalition actually, thank for alerting me to that.
Adding such virtual players is an interesting idea. I guess it should be possible to properly add probability weighting, without virtual players, once one has fully understood the reason for Shapley’s permutation method of weighting. (Which I have not.)
Another thing I noticed: It seems one can generalize a “coalition” of “players” as a conjunction of propositions, where the propositions of the players not participating in the coalition are negated. So for players/propositions A, B, C, the coalition {A, C} would correspond to the proposition A∧¬B∧C. The Shapley value of a player would simply be the value of a proposition, like A. Since coalitions are just propositions as well, this has the (intuitive?) consequence that coalitions can also be players.
Furthermore, instead of talking about “values” one could talk about “utility”, as in expected utility theory. There is actually a formalization of utility theory, by Richard Jeffrey, which applies to a Boolean algebra of propositions (or “events”, as they are called in probability theory). So theoretically it should be possible to determine which restrictions placed on a Jeffrey utility function are equivalent to Shapley’s formula. Which could, presumably, aid understanding the assumptions behind it, and help with things like integrating probabilities into the Shapley formalism, since those are already integrated into Jeffrey’s theory.
Thanks Cubefox, very interesting ideas, I like the idea of generalising a coalition so that it can be treated as a player, that seems to make a lot of practical sense, I’ll look into Jeffrey to try and get my head around that.
If you want to look into Jeffrey, his utility theory is in his book “The Logic of Decision”, second/1983 edition, sections 4.4 and 5.5 to 5.9. It’s less than 10 pages overall, the rest isn’t really necessary.
This is extremely well produced, I think it’s the best introduction to Shapley values I’ve ever seen. Kudos for the simple explanation and approachable designs!
(Not an indictment of this site, but with this as with other explainers, I still struggle to see how to apply Shapley values to any real world problems haha—unlike something like quadratic funding, which also sports fancy mechanism math but is much more obvious how to use)
(maybe the part that seems unrealistic is the difficulty of eliciting values for the power set of possible coalitions, as generating a value for any one coalition feels like an expensive process, and the size of a power set grows exponentially with the number of players)
Thanks Austin, yes—the weeks I’ve spent trying to really understand why Shapley uses such a complicated method to calculate the possible coalitions, has left me feeling that it is actually prohibitively cumbersome for most applications. It has been popular in machine learning algorithms, but faces the problem that it is computationally expensive.
I created a comparison calculator to show Shapley next to my own method that simply weights by dividing all the explicit marginal values by the total of all the explicit marginal values and multiplying that by the grand coalition value. I found that, for realistic values being entered, it yields very similar results to Shapley, and yet is easy to calculate on a spare napkin. It also satisfies Shapley’s 4 axioms, and seems more intuitive to me at least.
There might be an issue with mine that you need the total of all marginal values (which is involved in the weighting) to find any one weighted value, whereas Shapley can be used to calculate each weighted marginal value in isolation.
Regardless… who am I to argue with a Nobel Prize winning economist? But I can’t be accused of not trying to get on board :) I like the look of Quadratic Funding, perhaps for a future post.
Thanks, this looks good. I agree on the reason for the factorial method of weighting being very unclear. Unfortunately most sources, like Wikipedia, don’t really try to explain the motivation behind it.
But it seems to me there is a fundamental problem with Shapley values: They ignore probabilities. For example, they assume all necessary conditions are equally important. But this doesn’t seem right.
Say a successful surgery needs both a surgeon and a nurse, otherwise the patient dies. Shapley values (or really any purely counterfactuals account of causal contribution) will then assume that both have contributed equally to the successful surgery. Which arguably isn’t true, because surgeons are much less available (less replaceable) than nurses. If the nurse becomes ill, a different nurse could probably do the task, while if the surgeon becomes ill, the surgery may well have to be postponed. So the surgeon is more important for (contributes more to) a successful surgery.
This apparently comes down to probability. The task of the surgeon was, from a prior perspective, less likely to be fulfilled because it is harder to get hold of a surgeon.
Similarly: What was the main cause of the match getting lit? The match being struck? Or the atmosphere containing oxygen? Both are necessary in the sense that if either hadn’t occurred the match wouldn’t be lit. So their Shapley values would be equal. But it seems clear that the main cause was the match being struck. Why? Because matches being struck is relatively rare, and hence unlikely, while the atmosphere contains oxygen pretty much always.
So I think the contributions calculated for Shapley values should be weighted by something like the inverse of their prior probabilities.
Other notes:
There is another Shapley value calculator. The website isn’t designed as well as the one above, but it contains several examples and it allows assigning a value to the empty coalition, instead assigning it always the value 0.
Several years ago, the EA Forum user George Bridgewater actually pointed out an issue with Shapley values (point 1 here) which is very similar to the one I made above, though he didn’t identify missing probabilities as the problem.
Nice observation. I’m certainly not meaning to advocate for Shapley value—this was largely an attempt to adjust my negative attitude about Shapley value’s flaws, and the attempt was not very successful, but I thought it would be useful to others struggling to understand it, as I was.
I can imagine a way to address the probability issue you raise could be to create probabilistic value entries, where, let’s say we add the participants in the ratio they exist in reality, so pretending there are twice as many nurses as doctors, you could fill out values for a 3 person coalition (2 nurses, 1 doctor), with a value of 10 awarded to any coalition that satisfies a successful surgery (at least one doctor and one nurse). This results in the nurses being awarded a Shapley Value of 1.67 and the doctor being awarded 6.67.
This hack would give a reasonable answer, in this limited situation. But the oxygen:match-strike would lead to a computationally prohibitive outcome given that this hack would require a massive increase in coalitions, leading to exponentially massive computation required.
Thanks for your comments. I might incorporate the empty coalition actually, thank for alerting me to that.
Adding such virtual players is an interesting idea. I guess it should be possible to properly add probability weighting, without virtual players, once one has fully understood the reason for Shapley’s permutation method of weighting. (Which I have not.)
Another thing I noticed: It seems one can generalize a “coalition” of “players” as a conjunction of propositions, where the propositions of the players not participating in the coalition are negated. So for players/propositions A, B, C, the coalition {A, C} would correspond to the proposition A∧¬B∧C. The Shapley value of a player would simply be the value of a proposition, like A. Since coalitions are just propositions as well, this has the (intuitive?) consequence that coalitions can also be players.
Furthermore, instead of talking about “values” one could talk about “utility”, as in expected utility theory. There is actually a formalization of utility theory, by Richard Jeffrey, which applies to a Boolean algebra of propositions (or “events”, as they are called in probability theory). So theoretically it should be possible to determine which restrictions placed on a Jeffrey utility function are equivalent to Shapley’s formula. Which could, presumably, aid understanding the assumptions behind it, and help with things like integrating probabilities into the Shapley formalism, since those are already integrated into Jeffrey’s theory.
Of course this would probably be a lot of work...
Thanks Cubefox, very interesting ideas, I like the idea of generalising a coalition so that it can be treated as a player, that seems to make a lot of practical sense, I’ll look into Jeffrey to try and get my head around that.
If you want to look into Jeffrey, his utility theory is in his book “The Logic of Decision”, second/1983 edition, sections 4.4 and 5.5 to 5.9. It’s less than 10 pages overall, the rest isn’t really necessary.
Brilliant, thanks.