Example 7 seems wild to me. If the applicants who don’t get the job also get some of the value, does that mean people are constantly collecting Shapley value from the world, just because they “could” have done a thing (even if they do absolutely nothing)? If there are an infinite number of cooperative games going on in the world and someone can plausibly contribute at least a unit of value to any one of them, then it seems like their total Shapley value across all games is infinite, and at that point it seems like they are as good as one can be, all without having done anything. I can’t tell if I’m making some sort of error here or if this is just how the Shapley value works.
What numerator and denominator? I am imagining that a single person could be a player in multiple cooperative games. The Shapley value for the person would be finite in each game, but if there are infinitely many games, the sum of all the Shapley values (adding across all games, not adding across all players in a single game) could be infinite.
Hmm I would guess that the number of realistic cooperative games in the world to grow ~linearly (or some approximation[1]) with the number of people in the world, hence the denominator.
[1] I suppose if you think the growth is highly superlinear and there are ~infinity people, than Shapley values can grow to be ~infinite? But this feels like a general problem with infinities and not specific to Shapleys.
I asked my question because the problem with infinities seems unique to Shapley values (e.g. I don’t have this same confusion about the concept of “marginal value added”). Even with a small population, the number of cooperative games seems infinite: for example, there are an infinite number of mathematical theorems that could be proven, an infinite number of Wikipedia articles that could be written, an infinite number of films that could be made, etc. If we just use “marginal value added”, the total value any single person adds is finite across all such cooperative games because in the actual world, they can only do finitely many things. But the Shapley value doesn’t look at just the “actual world”, it seems to look at all possible sequences of ways of adding people to the grand coalition and then averages the value, so people get non-zero Shapley value assigned to them even if they didn’t do anything in the “actual world”.
(There’s maybe some sort of “compactness” argument one could make that even if there are infinitely many games, in the real world only finitely many of them get played to completion and so this should restrict the total Shapley value any single person can get, but I’m just trying to go by the official definition for now.)
I agree that this is unintuitive. Personally the part of that that I like less is that it feels like people could cheat that, by standing in line.
But they can’t cheat it! See this example: <http://shapleyvalue.com/?example=4>. You can’t even cheat by noticing that something is impactful, and then self-modifying so that in the worlds where you were needed you would do it, because in the worlds where you would be needed, you wouldn’t have done that modification (though there are some nuances here, like if you self-modify and there is some chance that you are needed in the future).
Not sure if that addresses part of what you were asking about.
I agree that SV’s don’t play nice with infinities, though I’m not sure whether there could be an extension which could (for instance, looking at the limit of the Shapley value).
I don’t think the example you give addresses my point. I am supposing that Leibniz could have also invented calculus, so v({2})=100. But Leibniz could have also invented lots of different things (infinitely many things!), and his claim to each invention would be valid (although in the real world he only invents finitely many things). If each invention is worth at least a unit of value, his Shapley value across all inventions would be infinite, even if Leibniz was “maximally unluckly” and in the actual world got scooped every single time and so did not invent anything at all.
I don’t understand the part about self-modifications—can you spell it out in more words/maybe give an example?
his Shapley value across all inventions would be infinite
Assuming an infinite number of players. If there are only a finite number of players, there are only finite terms in the Shapley value calculation, and if each invention has finite value, that’s finite.
The Shapley value is one way to distribute the total gains to the players, assuming that they all collaborate.
This means that there must be gains to distribute for anyone to get nonzero credit from that game, and that they in fact “collaborated” (although this could be in name only) to get any credit at all. Ignoring multiverses, infinitely many things have not been invented yet, but maybe infinitely many things will be invented in the future. In general, I don’t think that Leibniz cooperated in infinitely many games, or even that infinitely many games have been played so far, unless you define games with lots of overlap and double counting (or you invoke multiverses, or consider infinitely long futures, or some exotic possibilities, and then infinite credit doesn’t seem unreasonable).
Furthermore, in all but a small number of games, he might make no difference to each coalition even when he cooperates, so get no credit at all. Or the credit could decrease fast enough to have a finite sum, even if he got nonzero credit in infinitely many games, as it becomes vanishingly unlikely that he would have made any difference even in worlds where he cooperates.
In general, I don’t think you should sum an individual’s Shapley values across possible and maybe even actual games, because some actions the individual could take could be partially valuable in the same way in multiple games simultaneously, and you would double count value by summing. The sum wouldn’t represent anything natural or useful in such cases. However, there may be specific sets of games where it works out, maybe when the value across games is in fact additive for the value to the world. This doesn’t mean the games can’t interact or compete in principle, but the value function for each game can’t depend on the specific coalition set of any other game, but it can average over them.
I think a general and theoretically sound approach would be to build a single composite game to represent all of the games together, but the details could be tricky or unnatural, because you need to represent in which games an individual cooperates, given that they can only do so much in a bounded time interval.
Maybe you use the set of all players across all games as the set of players in the composite game, and cooperating in any game counts as cooperating in the composite game. To define the value function, you could model the distribution of games the players cooperate in conditional on the set of players cooperating in any game (taking an expected value). Then you get Shapley values the usual way. But now you’re putting a lot of work into the value function.
Maybe you can define the set of players to be the product of the set of all players across all of the games and the set of games. That is, with a set I of individuals (across all games) and a set X of games, (i,x)∈I×X cooperates if and only if i cooperates in game x. Then you can define i’s Shapley value as the sum of Shapley values over the “players” (i,x), ranging over the x. If you have infinitely many games in X, you get an infinite number of “players”. There is work on games with infinitely many players (e.g. Diubin). Maybe you don’t need to actually compute the Shapley value for each (i,x), and you can directly compute the aggregate values over each x for each i.
Unless you’re double counting, I think there are only finitely many games actually being played at a time, so this is one way to avoid infinities. In counterfactuals where an individual “cooperates” in infinitely many games locally (ignoring multiverses and many worlds) and in a finite time interval, their marginal contribution to value to a coalition (i.e. v(S∪{i})−v(S)=E[U|S∪{i}]−E[U|S],i∉S) is realistically going to be 0 in all but finitely many of those games, unless you double count value, which you shouldn’t.[1] The more games an individual is playing, the less they can usually contribute to each.
I don’t know off-hand if you can guarantee that the sum of an individual’s Shapley values across separately defined games matches the individual’s Shapley value for the composite game (defined based on 1 or 2) in interesting/general enough types of sets of games.
For an infinite set of games an individual “cooperates” in, they could randomly pick finitely many games to actually contribute to according to a probability distribution with positive probability on infinitely many subsets of games, and so contribute nonzero value in expectation to infinitely many games. I suspect this isn’t physically possible in a finite time interval. Imagine the games are numbered, and the player chooses which games to actually cooperate to by generating random subsets of numbers (or even just one at a time). To have infinite support in a finite time interval, they’d need a procedure that can represent arbitrarily large numbers in that time interval. In general, they’d need to be sensitive to arbitrarily large amounts of information to decide which games to actually contribute to in order to distinguish infinitely many subsets of games.
There could also just be butterfly effects on infinitely many games, but if those don’t average out in expectation, I’d guess you’re double counting.
I think a general and theoretically sound approach would be to build a single composite game to represent all of the games together
Yeah, I did actually have this thought but I guess I turned it around and thought: shouldn’t an adequate notion of value be invariant to how I decide to split up my games? The linearity property on Wikipedia even seems to be inviting us to just split games up in however manner we want.
And yeah, I agree that in the real world games will overlap and so there will be double counting going on by splitting games up. But if that’s all that’s saving us from reaching absurd conclusions then I feel like there ought to be some refinement of the Shapley value concept...
I don’t think you should sum an individual’s Shapley values across possible and maybe even actual games, because some actions the individual could take could be partially valuable in the same way in multiple games simultaneously, and you would double count value by summing
This seems confused to me. Shapley values are additive, so one’s shapley value should be the sum of one’s Shapley value for all games.
In particular, if you do an action that is valuable for many games, e.g., writing a wikipedia article that is valuable for many projects, you could conceive of each project as its own game, and the shapley value would be the sum of the contributions to each project. There is no double-counting.
I think the linearity property holds if the two value/payoff functions themselves can be added (because Shapley values are linear combinations of the value/payoff functions’ values with fixed coefficients for fixed sets of players), but usually not otherwise. Also, I think this would generally assume a common set of players, and that a player cooperates in one game iff they cooperate in the other, so that we can use (v+w)(S)=v(S)+w(S).
I think there’s the same problem that motivated the use of Shapley values in the first place. Just imagine multiple decisions one individual makes as part of 3 separate corresponding games:
Doing the basics to avoid dying, like eating, not walking into traffic (and then working, earning money and donating some of it)
Working and earning money (to donate, where and how much to work)
Donating (how much to donate, and optionally also where)
Let’s assume earning-to-give only with low impact directly from each job option.
1 and 2 get their value from eventually donating, which is the decision made in 3, but you’d already fully count the value of your donations in 3, so you shouldn’t also count it in 1 or 2. These can also be broken down into further separate games. It doesn’t matter for your donations if you avoid dying now if you die soon after before getting to donate. You won’t get to donate more if you do 1 more minute of work in your job before quitting instead of quitting immediately.
I think people wouldn’t generally make the mistake of treating these as separate games to sum value across, because the decisions are too fine-grained and because the dependence is obvious. Even if they were earning money to donate from impactful direct work, they still wouldn’t accidentally double count their earnings/donations, because they wouldn’t represent that with multiple games.
A similar example that I think could catch someone would be someone who is both a grant advisor and doing separate fundraising work that isn’t specific to their grants but raises more money for them to grant, anyway. For example, they’re both a grant advisor for an EA Fund, and do outreach for GWWC. If they treat these as separate coalition games they’re playing, there’s a risk that they’ll double count additional money that’s been raised through GWWC and was granted on their recommendation (or otherwise affected by their grantmaking counterfactually). Maybe assume that if they don’t make grant recommendations soon, there’s a greater risk the extra funds aren’t useful at all (or are much much less useful), e.g. the extra funding is granted prioritizing other things over potential impact, the funds are misappropriated, or we go extinct. So, they’re directly or indirectly counting extra funding in both games. This seems harder to catch, because the relationship between the two games isn’t as obvious, and they’re both big natural decisions to consider.
Another example: calculus was useful to a huge number of later developments. Leibniz “cooperated” in the calculus-inventing game, but we might say he also cooperated in many later games that depended on calculus, but any value we’d credit him with generated in those later games should already be fully counted in the credit he gets in the calculus-inventing game.
There are also more degenerate cases, like two identical instances of the same game, or artificial modifications, e.g. adding and excluding different players (but counting their contributions anyway, just not giving them credit in all games).
Disagree-voting a question seems super aggressive and also nonsensical to me. (Yes, my comment did include some statements as well, but they were all scaffolding to present my confusion. I wasn’t presenting my question as an opinion, as my final sentence makes clear.) I’ve been unhappy with the way the EA Forum has been going for a long time now, but I am noting this as a new kind of low.
Example 7 seems wild to me. If the applicants who don’t get the job also get some of the value, does that mean people are constantly collecting Shapley value from the world, just because they “could” have done a thing (even if they do absolutely nothing)? If there are an infinite number of cooperative games going on in the world and someone can plausibly contribute at least a unit of value to any one of them, then it seems like their total Shapley value across all games is infinite, and at that point it seems like they are as good as one can be, all without having done anything. I can’t tell if I’m making some sort of error here or if this is just how the Shapley value works.
Presumably everything adds up to normality? Like you have a high numerator but also a high denominator.
(But this is mostly a drive-by comment, I don’t really understand Shapleys)
What numerator and denominator? I am imagining that a single person could be a player in multiple cooperative games. The Shapley value for the person would be finite in each game, but if there are infinitely many games, the sum of all the Shapley values (adding across all games, not adding across all players in a single game) could be infinite.
Hmm I would guess that the number of realistic cooperative games in the world to grow ~linearly (or some approximation[1]) with the number of people in the world, hence the denominator.
[1] I suppose if you think the growth is highly superlinear and there are ~infinity people, than Shapley values can grow to be ~infinite? But this feels like a general problem with infinities and not specific to Shapleys.
I asked my question because the problem with infinities seems unique to Shapley values (e.g. I don’t have this same confusion about the concept of “marginal value added”). Even with a small population, the number of cooperative games seems infinite: for example, there are an infinite number of mathematical theorems that could be proven, an infinite number of Wikipedia articles that could be written, an infinite number of films that could be made, etc. If we just use “marginal value added”, the total value any single person adds is finite across all such cooperative games because in the actual world, they can only do finitely many things. But the Shapley value doesn’t look at just the “actual world”, it seems to look at all possible sequences of ways of adding people to the grand coalition and then averages the value, so people get non-zero Shapley value assigned to them even if they didn’t do anything in the “actual world”.
(There’s maybe some sort of “compactness” argument one could make that even if there are infinitely many games, in the real world only finitely many of them get played to completion and so this should restrict the total Shapley value any single person can get, but I’m just trying to go by the official definition for now.)
I agree that this is unintuitive. Personally the part of that that I like less is that it feels like people could cheat that, by standing in line.
But they can’t cheat it! See this example: <http://shapleyvalue.com/?example=4>. You can’t even cheat by noticing that something is impactful, and then self-modifying so that in the worlds where you were needed you would do it, because in the worlds where you would be needed, you wouldn’t have done that modification (though there are some nuances here, like if you self-modify and there is some chance that you are needed in the future).
Not sure if that addresses part of what you were asking about.
I agree that SV’s don’t play nice with infinities, though I’m not sure whether there could be an extension which could (for instance, looking at the limit of the Shapley value).
I don’t think the example you give addresses my point. I am supposing that Leibniz could have also invented calculus, so v({2})=100. But Leibniz could have also invented lots of different things (infinitely many things!), and his claim to each invention would be valid (although in the real world he only invents finitely many things). If each invention is worth at least a unit of value, his Shapley value across all inventions would be infinite, even if Leibniz was “maximally unluckly” and in the actual world got scooped every single time and so did not invent anything at all.
I don’t understand the part about self-modifications—can you spell it out in more words/maybe give an example?
Assuming an infinite number of players. If there are only a finite number of players, there are only finite terms in the Shapley value calculation, and if each invention has finite value, that’s finite.
The Wikipedia page says:
This means that there must be gains to distribute for anyone to get nonzero credit from that game, and that they in fact “collaborated” (although this could be in name only) to get any credit at all. Ignoring multiverses, infinitely many things have not been invented yet, but maybe infinitely many things will be invented in the future. In general, I don’t think that Leibniz cooperated in infinitely many games, or even that infinitely many games have been played so far, unless you define games with lots of overlap and double counting (or you invoke multiverses, or consider infinitely long futures, or some exotic possibilities, and then infinite credit doesn’t seem unreasonable).
Furthermore, in all but a small number of games, he might make no difference to each coalition even when he cooperates, so get no credit at all. Or the credit could decrease fast enough to have a finite sum, even if he got nonzero credit in infinitely many games, as it becomes vanishingly unlikely that he would have made any difference even in worlds where he cooperates.
In general, I don’t think you should sum an individual’s Shapley values across possible and maybe even actual games, because some actions the individual could take could be partially valuable in the same way in multiple games simultaneously, and you would double count value by summing. The sum wouldn’t represent anything natural or useful in such cases. However, there may be specific sets of games where it works out, maybe when the value across games is in fact additive for the value to the world. This doesn’t mean the games can’t interact or compete in principle, but the value function for each game can’t depend on the specific coalition set of any other game, but it can average over them.
I think a general and theoretically sound approach would be to build a single composite game to represent all of the games together, but the details could be tricky or unnatural, because you need to represent in which games an individual cooperates, given that they can only do so much in a bounded time interval.
Maybe you use the set of all players across all games as the set of players in the composite game, and cooperating in any game counts as cooperating in the composite game. To define the value function, you could model the distribution of games the players cooperate in conditional on the set of players cooperating in any game (taking an expected value). Then you get Shapley values the usual way. But now you’re putting a lot of work into the value function.
Maybe you can define the set of players to be the product of the set of all players across all of the games and the set of games. That is, with a set I of individuals (across all games) and a set X of games, (i,x)∈I×X cooperates if and only if i cooperates in game x. Then you can define i’s Shapley value as the sum of Shapley values over the “players” (i,x), ranging over the x. If you have infinitely many games in X, you get an infinite number of “players”. There is work on games with infinitely many players (e.g. Diubin). Maybe you don’t need to actually compute the Shapley value for each (i,x), and you can directly compute the aggregate values over each x for each i.
Unless you’re double counting, I think there are only finitely many games actually being played at a time, so this is one way to avoid infinities. In counterfactuals where an individual “cooperates” in infinitely many games locally (ignoring multiverses and many worlds) and in a finite time interval, their marginal contribution to value to a coalition (i.e. v(S∪{i})−v(S)=E[U|S∪{i}]−E[U|S],i∉S) is realistically going to be 0 in all but finitely many of those games, unless you double count value, which you shouldn’t.[1] The more games an individual is playing, the less they can usually contribute to each.
I don’t know off-hand if you can guarantee that the sum of an individual’s Shapley values across separately defined games matches the individual’s Shapley value for the composite game (defined based on 1 or 2) in interesting/general enough types of sets of games.
For an infinite set of games an individual “cooperates” in, they could randomly pick finitely many games to actually contribute to according to a probability distribution with positive probability on infinitely many subsets of games, and so contribute nonzero value in expectation to infinitely many games. I suspect this isn’t physically possible in a finite time interval. Imagine the games are numbered, and the player chooses which games to actually cooperate to by generating random subsets of numbers (or even just one at a time). To have infinite support in a finite time interval, they’d need a procedure that can represent arbitrarily large numbers in that time interval. In general, they’d need to be sensitive to arbitrarily large amounts of information to decide which games to actually contribute to in order to distinguish infinitely many subsets of games.
There could also just be butterfly effects on infinitely many games, but if those don’t average out in expectation, I’d guess you’re double counting.
Yeah, I did actually have this thought but I guess I turned it around and thought: shouldn’t an adequate notion of value be invariant to how I decide to split up my games? The linearity property on Wikipedia even seems to be inviting us to just split games up in however manner we want.
And yeah, I agree that in the real world games will overlap and so there will be double counting going on by splitting games up. But if that’s all that’s saving us from reaching absurd conclusions then I feel like there ought to be some refinement of the Shapley value concept...
This seems confused to me. Shapley values are additive, so one’s shapley value should be the sum of one’s Shapley value for all games.
In particular, if you do an action that is valuable for many games, e.g., writing a wikipedia article that is valuable for many projects, you could conceive of each project as its own game, and the shapley value would be the sum of the contributions to each project. There is no double-counting.
<https://en.wikipedia.org/wiki/Shapley_value#Linearity>
i had to double-check, though, because you seemed so sure.
I think the linearity property holds if the two value/payoff functions themselves can be added (because Shapley values are linear combinations of the value/payoff functions’ values with fixed coefficients for fixed sets of players), but usually not otherwise. Also, I think this would generally assume a common set of players, and that a player cooperates in one game iff they cooperate in the other, so that we can use (v+w)(S)=v(S)+w(S).
I think there’s the same problem that motivated the use of Shapley values in the first place. Just imagine multiple decisions one individual makes as part of 3 separate corresponding games:
Doing the basics to avoid dying, like eating, not walking into traffic (and then working, earning money and donating some of it)
Working and earning money (to donate, where and how much to work)
Donating (how much to donate, and optionally also where)
Let’s assume earning-to-give only with low impact directly from each job option.
1 and 2 get their value from eventually donating, which is the decision made in 3, but you’d already fully count the value of your donations in 3, so you shouldn’t also count it in 1 or 2. These can also be broken down into further separate games. It doesn’t matter for your donations if you avoid dying now if you die soon after before getting to donate. You won’t get to donate more if you do 1 more minute of work in your job before quitting instead of quitting immediately.
I think people wouldn’t generally make the mistake of treating these as separate games to sum value across, because the decisions are too fine-grained and because the dependence is obvious. Even if they were earning money to donate from impactful direct work, they still wouldn’t accidentally double count their earnings/donations, because they wouldn’t represent that with multiple games.
A similar example that I think could catch someone would be someone who is both a grant advisor and doing separate fundraising work that isn’t specific to their grants but raises more money for them to grant, anyway. For example, they’re both a grant advisor for an EA Fund, and do outreach for GWWC. If they treat these as separate coalition games they’re playing, there’s a risk that they’ll double count additional money that’s been raised through GWWC and was granted on their recommendation (or otherwise affected by their grantmaking counterfactually). Maybe assume that if they don’t make grant recommendations soon, there’s a greater risk the extra funds aren’t useful at all (or are much much less useful), e.g. the extra funding is granted prioritizing other things over potential impact, the funds are misappropriated, or we go extinct. So, they’re directly or indirectly counting extra funding in both games. This seems harder to catch, because the relationship between the two games isn’t as obvious, and they’re both big natural decisions to consider.
Another example: calculus was useful to a huge number of later developments. Leibniz “cooperated” in the calculus-inventing game, but we might say he also cooperated in many later games that depended on calculus, but any value we’d credit him with generated in those later games should already be fully counted in the credit he gets in the calculus-inventing game.
There are also more degenerate cases, like two identical instances of the same game, or artificial modifications, e.g. adding and excluding different players (but counting their contributions anyway, just not giving them credit in all games).
Disagree-voting a question seems super aggressive and also nonsensical to me. (Yes, my comment did include some statements as well, but they were all scaffolding to present my confusion. I wasn’t presenting my question as an opinion, as my final sentence makes clear.) I’ve been unhappy with the way the EA Forum has been going for a long time now, but I am noting this as a new kind of low.