How to calculate Shapley Value with uncertainty?

So I'm trying to estimate a Shapley value in a game with uncertain payoffs. Specifically, imagine a game where the payoff function as as follows

(A) = 1
(B) = 2
(B,C) = 4


For instance, you can imagine this game representing Person A and Person B deciding whether to go into business by themselves or together.

Calculating the Shapley value for this game is very straightforward by listing all the permutations along with the marginal contribution of each person in the given permutation divided by the number of permutations:

[A, B] = [1, 3]
[B, A] = [2, 2]

[A, B] = [(1+2)/2, (3+2)/2]
[A, B] = [1.5, 2.5]


So Person A should get \$1.5 and Person B should get \$2.5 in the grand coalition.

However, I am struggling to figure out how I would go about computing the Shapley value in the presence of uncertainty. For instance, imagine I change the payoff function to use confidence intervals as follows:

(A) = 1 ± 0.2
(B) = 2 ± 0.6
(B,C) = 4 ± 0.5


This is important as I am trying to compute the Shapley value in an real life setting with experimental data.

What will the Shapley value be in this case WITH uncertainty?

• What exactly is your question? Right now it invites speculation, which is not something the SE format supports. – Giskard Nov 27 '17 at 9:04
• Without uncertainty, the Shapley value is [1.5, 2.5]. What would it be WITH uncertainty? – Scottmas Nov 27 '17 at 13:34
• What does your cost or utility function look like? What is the nature of the experiment? – Dave Harris Nov 27 '17 at 14:28
• In my particular use case there is no cost or utility function. We assign various coalitions of players, each coalition performs an activity multiple times, which allows us to estimate a payoff for each coalition. For example, some coalitions may produce a high average payoff but have a high variance in their performance, other coalitions may have a low payoff but be tightly clustered. – Scottmas Nov 27 '17 at 14:44
• You are misunderstanding what a confidence interval is. A confidence interval says nothing about your actual data, it talks about your model. If your model is the true model and you repeat the experiment an infinite amount of times, then your intervals will cover the parameter no less than x% of the time. It does not mean it will cover it during this experiment. You know nothing about its properties on one use. What you are thinking about is a credible interval and I doubt you can collect the information to calculate it. – Dave Harris Nov 28 '17 at 15:04

2 Answers

It sounds like you may have a quadratic loss function, but I am guessing a little. If the players have played enough to be experienced in how the game works, then I would simply use the sample mean reward as my calculation point.

You should read up on the theory behind loss functions. The players are making estimates, certain types of estimates are the natural minimization of certain loss functions. Most gambling type behavior results from quadratic loss, though there are particular exceptions. Equity securities center of location is the mode because there can be no such thing as a mean return. Equity securities behaviors should result from an all-or-nothing loss function. Physicians are another example where there is an asymmetric loss.

If a physician fails to diagnose you with a disease, then they lost the revenue from treatment and face malpractice claims. If they misdiagnose you as having a disease but you do not, then they still collect the medical billings and may not face malpractice claims, especially if they do not reveal it was a misdiagnosis. A diagnosis is a form of gamble.

Take a look at the losses experienced from failing to take a particular type of behavior.

• This isn't quite what I'm looking for. Would something like assuming a probability distribution and then summing the difference work? – Scottmas Nov 28 '17 at 14:36
• There is no rational grounding for it. You do not and cannot know the probability mass or density functions running around inside their heads. They were forced to make "decisions," which are point solutions. They are minimizing a cost in their heads but against a density of their own making. If I were a referee I would toss it as without any rational merit. You need a solution that does not depend upon what is happening inside their head, with regard to uncertainty. – Dave Harris Nov 28 '17 at 15:00

I talked with an economist friend and it appears the best way to get what I'm after is to bootstrap estimate the Shapley value.

e.g. Randomly sample with replacement my experimental data 1000 times, compute the Shapley value with each sample, and then average those computations. And at that point, it's not hard to construct a confidence interval using the 5% and 95% percentiles of the computations.

This may not be the most theoretically correct way, but it gives me precisely what I'm looking for - namely confidence intervals on the computed Shapley value. Except incidentally, I don't care about the confidence intervals on the data points themselves.