4

I'm building an algorithm in R to calculate the Shapley Value for players in a collaborative game. However, I do not have an outcome value for all possible coalitions, partially because the number of players is relatively high (in the 100s/1000s), and number of observations will never cover all permutations.

My question is: If I calculate the Shapley Value for players just using the information available, how valid is this in the context of fair distribution of credit? Also, is there a method to calculate how far from optimal distribution of credit I might be?

If it is not reasonable to use the standard calculation of Shapley Values with incomplete information, is there an algorithm that is more appropriate?

[EDIT - added a worked example]

A worked example using 3 players and manual calcs:

ALL coalitions observed, with values:

A   -> 5
B   -> 8
C   -> 3
AB  -> 9
AC  -> 8
BC  -> 15
ABC -> 18

Permutations and marginal additional value:

       A   B   C
A,B,C: 5,  4,  9
A,C,B: 5,  3,  10
B,A,C: 1,  8,  9
B,C,A: 3,  8,  7
C,A,B: 5,  10, 3
C,B,A: 3,  12, 3

A = 3.67
B = 7.5
C = 6.83

One coalition (AB) NEVER observed, with values:

A   -> 5
B   -> 8
C   -> 3
AB  -> ? - Never seen - let's use 0
AC  -> 8
BC  -> 15
ABC -> 18

Permutations and marginal additional value:

       A   B   C
A,B,C: 5,  0,  13
A,C,B: 5,  3,  10
B,A,C: 0,  8,  10
B,C,A: 3,  8,  7
C,A,B: 5,  10, 3
C,B,A: 3,  12, 3

A = 3.5
B = 6.83
C = 7.67

As you can see - C gets a bit more of a share of the spoils in the second example, at the expense of A and B. This seems intuitively OK seeing as the coalition AB never occurs and therefore C is working harder across all observed coalitions to produce value. My question is, is this mathematically reasonable as well? And does this reasonableness extend to, say, half of all possible coalitions never being observed?

As an addition, if anyone can point to some R code for calculating Shapley Values for large numbers of players that would also be appreciated.

[To give a hint of my level - I'm not a hard core statistician (but have a Th. Physics degree, some time ago!), but understand the maths and stats behind calculating Shapley Values pretty well]

Many thanks,

Andy.

Andy C
  • 83
  • 8
  • 1
    Can you provide a simple example? – gung - Reinstate Monica Oct 22 '16 at 11:58
  • You might use a statistical model to *predict* outcomes for unobserved coalitions. – Scortchi - Reinstate Monica Oct 22 '16 at 13:51
  • @gung - Thanks for your comment. I've added an example to hopefully explain my question more clearly. – Andy C Oct 22 '16 at 15:29
  • @Scortchi - That may be an option, and I've not considered that previously. That could hold some very interesting possibilities. – Andy C Oct 22 '16 at 15:30
  • Your calculation method isn't very clear even for the standard Shapley values. How do you get 7 for the marginal contribution of A over B & C, but 3 for the marginal contribution of A over C & B? – Scortchi - Reinstate Monica Oct 23 '16 at 00:17
  • Without any context it's hard to imagine what sort of answer you want. (1) Modelling outcomes for unobserved coalitions requires assumptions about the data-generating process. (2) The outcome for the unobserved coalition can only be between 8 & 18, implying bounds on the Shapley values - perhaps that idea could be extended to more complicated situations, but it sounds more like a q. for the Mathematics or Scientific Computing sites. (3) Variations on the standard calculation would presumably have some but not others of the properties of the Shapley value - again that's not really a ... – Scortchi - Reinstate Monica Oct 23 '16 at 00:36
  • ... statistical q. (& for anyone to suggest what properties you need they'd need to know the context). – Scortchi - Reinstate Monica Oct 23 '16 at 00:39
  • @Scortchi - Thanks for noticing the transposition - I've rectified that in the example. – Andy C Oct 23 '16 at 10:51
  • @Scortchi - Thanks for noticing the transposition - I've rectified that in the example. Context may help: I'm working in an online journey analysis context - trying to assign fair value to the drivers of certain events (arriving at a certain website, or purchasing a certain product for example). Attribution modelling in essence. This is why I have incomplete information for the permutations of drivers (campaigns) - you never see all possible permutations of campaigns in a journey. In fact you see a tiny subset of them as the campaigns can number in the hundreds. – Andy C Oct 23 '16 at 11:01
  • In fact your point 3 may give me what I'm after - Although the mathematics assumes all permutations' values are known (I believe), I'm asking if the assumption that unobserved coalitions provide zero value is reasonable. Maybe my language is wrong? Maybe I should _not_ be saying "unobserved coalitions" (which hints that they exists but are just not seen) - but rather non-existent coalitions? Thanks for helping me clarify my thinking. – Andy C Oct 23 '16 at 11:07
  • (a) Please edit the q. to add info. rather than appending more comments. Besides some permutations' not being observed, wouldn't some be observed many times? And isn't there variation in the value of the outcome within the same permutation? It'd probably be helpful to amplify your example to make things clear. (BTW a common application of Shapley's method in Marketing is to partition the coefficient of determination from a regression of the outcome value on campaign variables - the "coalitions" are subsets of predictors, so there's no problem of non-observed coalitions.) – Scortchi - Reinstate Monica Oct 24 '16 at 10:46
  • (b) There are still errors in your 1st calculation, which, carried through to the 2nd, make it hard to understand what you intend. The value of the outcome for AB can't be zero (as suggested by "Never seen - let's use 0") without violating super-additivity; nor can the marginal value of the outcome for AB over A & the marginal value of the outcome for AB over B both be zero (as suggested by the table of permutations) when the values of the outcome for A & B differ. I'd advise explicitly showing your calculations. – Scortchi - Reinstate Monica Oct 24 '16 at 10:47

0 Answers0