<p>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.</p>

<p>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 <em>e.g.</em> <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_inequality" rel="nofollow">Hoeffding's inequality</a>, which says</p>

<blockquote>
  <p>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} . $$</p>
</blockquote>

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

<p>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.</p>

<p>As comments have mentioned, there are big improvements for many special cases.</p>

CC BY-SA 3.0
2015-07-26T13:04:56.720Z
2015-07-26T13:04:56.720Z
usul
<p>I'm a complete statistics rookie but I'm looking for some general advice on workarounds if I'm trying to calculate the <a href="https://en.wikipedia.org/wiki/Shapley_value" rel="nofollow">Shapley Value</a> in games featuring many players.</p>

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

<p>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?</p>

CC BY-SA 3.0
2015-07-22T19:48:59.410Z
Is the game in question specific in any sense?
Giskard
CC BY-SA 3.0
2015-07-22T19:56:34.210Z
@denesp Not really, I was just interested in knowing if this method is considered in games with a large number of players.
n4cer500
CC BY-SA 3.0
2015-07-22T20:44:48.270Z
On the class of voting games there is a linear time approximation: http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2008.pdf
Also on the class of tree network cost allocation games: http://theory.stanford.edu/~megiddo/pdf/cost_tree.pdf
Giskard
<game-theory>
Shapley value with large number of players
n4cer500
# Shapley value with large number of players

(Asked by: username_0 on 2015-07-22)

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](https://en.wikipedia.org/wiki/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?

**Tags:** game-theory
> **Comments:**
> **username_1**: Is the game in question specific in any sense?  
> **username_0**: @denesp Not really, I was just interested in knowing if this method is considered in games with a large number of players.  
> **username_1**: On the class of voting games there is a linear time approximation: http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2008.pdf Also on the class of tree network cost allocation games: http://theory.stanford.edu/~megiddo/pdf/cost_tree.pdf  

---

## 1 answers

### Answer by username_2 on 2015-07-26. Score: 1

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](https://en.wikipedia.org/wiki/Hoeffding%27s_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.


---

