Shapley value with large number of players

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?

• Is the game in question specific in any sense? Jul 22, 2015 at 19:48
• @denesp Not really, I was just interested in knowing if this method is considered in games with a large number of players. Jul 22, 2015 at 19:56
• 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 Jul 22, 2015 at 20:44

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.