Very nice text, thank you for writing it!! I’m not sure whether this statement is universally true (and I’m also not entirely clear on what exactly it means): ”Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.”
Let’s take Example 2: If the invention of calculus had a very large benefit, then both Newton and Leibniz optimized their cost-effectiveness in terms of Shapley value by working on it. However, the global cost-effectiveness would have been higher if only one of them had made the invention and the other had contributed to something else valuable instead.
One solution would be to first decide for the project with the highest cost-effectiveness (in Shapley value) and then recalculate the Shapley values. In that case, either Newton or Leibniz would work on the invention of calculus (depending on who had lower costs), and the other would not. But there are still situations where this approach does not lead to the highest cost-effectiveness (if the Shapley value is based on coalitions that are unrealistic due to limited available resources):
Let’s assume that the three charities A, B, and C can finance a campaign for better chicken welfare with $1m. If only Charity A runs the campaign, it helps 200,000 chickens, and the same applies to Charity B. If Charities A and B launch a joint campaign, it helps 600,000 chickens. Charity C can only work alone and would help 250,000 chickens.
If a donor had $1m available, they would have to choose Charity A or B according to the Shapley value (300,000 chickens), but in reality, they would only help 200,000 chickens (assuming that a joint campaign by Charity A and B with $0.5m each is not possible or would also only help 200,000 chickens). It would be better to give the $1m to Charity C and help 250,000 chickens.
I’m not sure I’m following, and suspect you might be missing some terms; can you give me an example I can plug into shapleyvalue.com ? If there is some uncertainty that’s fine (so if e.g., in your example Newton has a 50% chance of inventing calculus and ditto for Leibniz, that’s fine).
Assume that the invention of calculus has utility 100 and the invention of Shapley value has utility 10. Newton (player 1) can invest one year to invent calculus or invest one year to invent Shapley values. Leibniz (player 2) can invest 350 days to invent calculus or invest one year to invent Shapley values. For the invention of calculus:
Shapley values for invention of calculus:
For the invention of Shapley values:
Shapley values for invention of Shapley values:
For both Newton and Leibniz the Shapley value is higher for the invention of calculus (50 compared to 5), so they both invent calculus. Overall result: +100 utility. It would have been better if Leibniz had invented calculus and Newton had invented Shapley values in that time. Overall result: +110 utility.
Improved approach: “One solution would be to first decide for the project with the highest cost-effectiveness (in Shapley value) and then recalculate the Shapley values.” The project with the highest cost-effectiveness (in Shapley value) is that Leibniz invents calculus (Shapley value = 50 / 350 days). So Leibniz will invent calculus. Now, the Shapley values are recalculated. Leibniz only has 15 days left in that year. That’s not enough for inventing Shapley values.
For the invention of calculus (it is already invented by Leibniz, so no additional benefit):
Shapley values for invention of calculus:
For the invention of Shapley values (Leibniz does not have enough time):
Shapley values for invention of Shapley values:
So, Newton would decide to invent Shapley values (Shapley value = 10 compared to Shapley value = 0 when inventing calculus).
Overall result: +110 utility.
PS. Sorry, I don’t know how to make the screenshots smaller...
You can also have something like this: if either of them is alone, go for Calculus, but if they know about the other, one goes for Calculus and the other goes for Shapley values. This gives them a SV of 55, greater than that of any of your examples.
Yes, it’s a coordination problem. I understand the claim”Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.” in the way that they don’t coordinate but optimize individually.
What about this example? Intervention A Value of {}: 0 Value of {1}: 0 Value of {2}: 0 Value of {1,2}: 100 -> Shapley value of 1 is: 50, shapley value of 2 is: 50. Intervention B Value of {0}: 0 Value of {1}: 60 Value of {2}: 0 Value of {1,2}: 60 -> Shapley value of 1 is: 60, shapley value of 2 is: 0. Player 1 would go for intervention B, player 2 would go for intervention A. Result: value of A = 0; value of B = 60 → total utility 60. It would be better if both players decide for A.
My assumption was that player 1 and player 2 each have one year and can dedicate that year either to Intervention A or Intervention B. In the joint game, Player 1 would choose Intervention A if they were alone and Intervention B if Player 2 was also involved. If we always construct a joint game in this way—so that, depending on the coalition formed, the interventions are chosen and divided in a way that achieves the best overall outcome—then this joint game, by definition, leads to the best overall outcome.
Additionally, I am unclear on what “optimizing for cost-effectiveness in terms of Shapley value” is supposed to mean. In order to optimize something, there must be multiple options—so, multiple games, right? Even if we include the joint game, it would still be best for Player 2, in terms of the Shapley value, to play the game “Intervention A” with a Shapley value of 50.
But I think it’s not very useful to continue discussing this unless the claim “Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.” is precisely defined.
Very nice text, thank you for writing it!!
I’m not sure whether this statement is universally true (and I’m also not entirely clear on what exactly it means):
”Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.”
Let’s take Example 2: If the invention of calculus had a very large benefit, then both Newton and Leibniz optimized their cost-effectiveness in terms of Shapley value by working on it. However, the global cost-effectiveness would have been higher if only one of them had made the invention and the other had contributed to something else valuable instead.
One solution would be to first decide for the project with the highest cost-effectiveness (in Shapley value) and then recalculate the Shapley values. In that case, either Newton or Leibniz would work on the invention of calculus (depending on who had lower costs), and the other would not. But there are still situations where this approach does not lead to the highest cost-effectiveness (if the Shapley value is based on coalitions that are unrealistic due to limited available resources):
Let’s assume that the three charities A, B, and C can finance a campaign for better chicken welfare with $1m. If only Charity A runs the campaign, it helps 200,000 chickens, and the same applies to Charity B. If Charities A and B launch a joint campaign, it helps 600,000 chickens. Charity C can only work alone and would help 250,000 chickens.
If a donor had $1m available, they would have to choose Charity A or B according to the Shapley value (300,000 chickens), but in reality, they would only help 200,000 chickens (assuming that a joint campaign by Charity A and B with $0.5m each is not possible or would also only help 200,000 chickens). It would be better to give the $1m to Charity C and help 250,000 chickens.
Thanks Felix, great question.
I’m not sure I’m following, and suspect you might be missing some terms; can you give me an example I can plug into shapleyvalue.com ? If there is some uncertainty that’s fine (so if e.g., in your example Newton has a 50% chance of inventing calculus and ditto for Leibniz, that’s fine).
Assume that the invention of calculus has utility 100 and the invention of Shapley value has utility 10. Newton (player 1) can invest one year to invent calculus or invest one year to invent Shapley values. Leibniz (player 2) can invest 350 days to invent calculus or invest one year to invent Shapley values.
For the invention of calculus:
Shapley values for invention of calculus:
For the invention of Shapley values:
Shapley values for invention of Shapley values:
For both Newton and Leibniz the Shapley value is higher for the invention of calculus (50 compared to 5), so they both invent calculus. Overall result: +100 utility.
It would have been better if Leibniz had invented calculus and Newton had invented Shapley values in that time. Overall result: +110 utility.
Improved approach: “One solution would be to first decide for the project with the highest cost-effectiveness (in Shapley value) and then recalculate the Shapley values.”
The project with the highest cost-effectiveness (in Shapley value) is that Leibniz invents calculus (Shapley value = 50 / 350 days). So Leibniz will invent calculus. Now, the Shapley values are recalculated. Leibniz only has 15 days left in that year. That’s not enough for inventing Shapley values.
For the invention of calculus (it is already invented by Leibniz, so no additional benefit):
Shapley values for invention of calculus:
For the invention of Shapley values (Leibniz does not have enough time):
Shapley values for invention of Shapley values:
So, Newton would decide to invent Shapley values (Shapley value = 10 compared to Shapley value = 0 when inventing calculus).
Overall result: +110 utility.
PS. Sorry, I don’t know how to make the screenshots smaller...
You can also have something like this: if either of them is alone, go for Calculus, but if they know about the other, one goes for Calculus and the other goes for Shapley values. This gives them a SV of 55, greater than that of any of your examples.
Yes, it’s a coordination problem. I understand the claim”Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.” in the way that they don’t coordinate but optimize individually.
What about this example?
Intervention A
Value of {}: 0
Value of {1}: 0
Value of {2}: 0
Value of {1,2}: 100
-> Shapley value of 1 is: 50, shapley value of 2 is: 50.
Intervention B
Value of {0}: 0
Value of {1}: 60
Value of {2}: 0
Value of {1,2}: 60
-> Shapley value of 1 is: 60, shapley value of 2 is: 0.
Player 1 would go for intervention B, player 2 would go for intervention A. Result: value of A = 0; value of B = 60 → total utility 60. It would be better if both players decide for A.
These are two different games. The joint game would be
Value of {}: 0 Value of {1}: 60 Value of {2}: 0 Value of {1,2}: 100`
and in that game player one is indeed better off in shapley value terms if he joins together with 2.
I’ll let you reflect on how/whether adding an additional option can’t decrease someone’s shapley value, but I’ll get back to my job :)
My assumption was that player 1 and player 2 each have one year and can dedicate that year either to Intervention A or Intervention B. In the joint game, Player 1 would choose Intervention A if they were alone and Intervention B if Player 2 was also involved. If we always construct a joint game in this way—so that, depending on the coalition formed, the interventions are chosen and divided in a way that achieves the best overall outcome—then this joint game, by definition, leads to the best overall outcome.
Additionally, I am unclear on what “optimizing for cost-effectiveness in terms of Shapley value” is supposed to mean. In order to optimize something, there must be multiple options—so, multiple games, right? Even if we include the joint game, it would still be best for Player 2, in terms of the Shapley value, to play the game “Intervention A” with a Shapley value of 50.
But I think it’s not very useful to continue discussing this unless the claim “Agents individually optimizing for cost-effectiveness in terms of Shapley value globally optimize for total cost-effectiveness.” is precisely defined.