2
$\begingroup$

I'm a complete statistics rookie but I'm looking for some general advice on workarounds if I'm trying to calculate the Shapley Value in games featuring many players.

i.e. If I have 20 players, I need to run all combinations (n!) which is 2,432,902,008,176,640,000.

Is there a solid method of solving the problem by taking a sample of the combinations? What do I need to look out for in order to make the results of using a sample as accurate as possible?

$\endgroup$
3
  • $\begingroup$ Is the game in question specific in any sense? $\endgroup$
    – Giskard
    Commented Jul 22, 2015 at 19:48
  • $\begingroup$ @denesp Not really, I was just interested in knowing if this method is considered in games with a large number of players. $\endgroup$
    – n4cer500
    Commented Jul 22, 2015 at 19:56
  • 2
    $\begingroup$ On the class of voting games there is a linear time approximation: cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2008.pdf Also on the class of tree network cost allocation games: theory.stanford.edu/~megiddo/pdf/cost_tree.pdf $\endgroup$
    – Giskard
    Commented Jul 22, 2015 at 20:44

1 Answer 1

1
+50
$\begingroup$

The sampling approach rigorously would look like this. For each player $i$, we want to estimate the expected marginal contribution, where the expectation is taken over a the subset of players that precede $i$ in the permutation ordering. So for each $i$, we do the following.

Let $X_i$ be a random variable equal to the marginal contribution of $i$, when we draw the permutation of players randomly. Let $\mu_i$ be the true Shapley value of $i$ (which we do not know). Then $\mathbb{E} X_i = \mu_i$. Now, if we sample many independent copies of $X_i$ and average them, this average, call it $\bar{X}_i$, should be very close to $\mu_i$, and the closeness is given by e.g. Hoeffding's inequality, which says

Let $K$ be an upper bound on any marginal contribution (so they are always between $0$ and $K$). Let $m$ be the number of independent copies of $X_i$ that we draw. Then $$ \Pr[ | \bar{X}_i - \mu_i | \geq \epsilon ] \leq 2e^{-2m \epsilon^2 / K^2} . $$

So for each $i$, we sample $m$ permutations randomly and calculate the average marginal contribution $\bar{X}_i$.

For example, if $K=100$ and we want an accuracy of $\epsilon = 0.01$ and a probability of failure of $2e^{-50}$, then we need $2m\epsilon^2/K^2 = 50$, so $m = 25K^2/\epsilon^2 = 2.5$ billion. So we need to sample $2.5$ billion permutations to "guarantee" accuracy of $0.01$, except with a miniscule $2e^{-50}$ chance of failure.

As comments have mentioned, there are big improvements for many special cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.