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

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 that you have read and understand our privacy policy and code of conduct.

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