Shapley value, explanation needed, normalization coefficient

Question

Does anybody know the detailed explanation how the coefficient with $3$ factorials in wikipedia in the "Formal definition" section arises?

Answer 1

We have a coalitional game $(v,N)$: $N$ is a set of $n$ players, and $v:\wp(N)\to\Bbb R$ is a function such that $v(\varnothing)=0$. The intended interpretation is that for each $S\subseteq N$, $v(S)$ is the expected sum of payoffs that the members of $S$ can obtain by cooperation. The Shapley value of player $i$ in this game is defined to be

$$\begin{align*} \varphi_i(v)&=\sum_{S\subseteq N\setminus\{i\}}\frac{|S|!(n-|S|-1)!}{n!}\big(v(S\cup\{i\})-v(S)\big)\\ &=\frac1n\sum_{S\subseteq N\setminus\{i\}}\frac{v(S\cup\{i\})-v(S)}{\binom{n-1}{|S|}}\;. \end{align*}$$

The basic idea is that a player’s value should depend on how much the expected aggregate payoff to a coalition increases when he is added to it. Of course this depends on the coalition, so we average it over all coalitions not containing him. Let $S\subseteq N\setminus\{i\}$: $S$ is a set of players not including $i$. For convenience let $k=|S|$, the number of players in $S$.

• $v(S)$ is the expected payoff to the coalition $S$, i.e., to the set $S$ if its members cooperate, and $v(S\cup\{i\})$ is the expected aggregate payoff to the coalition if player $i$ joins it, so $v(S\cup\{i\})-v(S)$ is the amount by which the expected aggregate payoff increases when $i$ joins the coalition $S$.

• $\binom{n-1}{|S|}=\binom{n-1}k$ is the number of subsets of $N\setminus\{i\}$ of cardinality $k$, the number of possible coalitions that are the same size as $S$ and do not already contain $i$.

Thus, if $\mathscr{S}_k(i)=\{S\subseteq N\setminus\{i\}:|S|=k\}$ is the collection of all possible coalitions of size $k$ that do not contain player $i$,

$$\varphi_i(v)=\frac1n\sum_{k=0}^{n-1}\sum_{S\in\mathscr{S}_k(i)}\frac{v(S\cup\{i\})-v(S)}{\binom{n-1}k}\;,$$

where

$$\sum_{S\in\mathscr{S}_k(i)}\frac{v(S\cup\{i\})-v(S)}{\binom{n-1}{k}}=\binom{n-1}k^{-1}\sum_{S\in\mathscr{S}_k(i)}\big(v(S\cup\{i\})-v(S)\big)$$

is the average amount by which a coalition of size $k$ that does not include player $i$ can increase its aggregate payoff by adding player $i$ to the coalition. Call this amount the $k$-value of player $i$ and denote it by $\varphi_i(v,k)$; then

$$\varphi_i(v)=\frac1n\sum_{k=0}^{n-1}\varphi_i(v,k)$$

is the average of the $k$-values of player $i$ as $k$ runs over its $n$ possibly values. In other words, we first compute the average extra value that player $i$ brings to a coalition of size $k$ for each possible $k$, and then we take the average of those averages and call it the value of player $i$.

As is noted in the article, we can also interpret this as follows. Suppose that we build a coalition by starting with one player and adding one player at a time until the whole group $N$ is a single coalition. Adding player $i$ to an existing coalition $S$ increases the expected payoff to the coalition by $v(S\cup\{i\})-v(S)$, so player $i$ can reasonably claim this amount as his fair share of the aggregate payoff. There are $n!$ possible ways to line up the $n$ players; in how many of these lineups will player $i$ be joining the coalition $S$?

Player $i$ must be preceded by the members of $S$ and followed by everyone else in $N$. There are $|S|!$ possible orders in which the $|S|$ members of $S$ could have been lined up to join the growing coalition, and there are $(n-1-|S|)!$ ways in which the remaining $n-1-|S|$ members of $N$ can be lined up after player $i$. Thus, there are $|S|!(n-1-|S|)!$ lineups in which player $i$ joins the existing coalition $S$. In each of those lineups player $i$ adds $v(S\cup\{i\})-v(S)$ to the value of the growing coalition, so if we sum his contribution over all lineups in which he joins $S$, we get a total of

$$|S|!(n-1-|S|)!\big(v(S\cup\{i\})-v(S)\big)\;.$$

If we now sum those totals over all possible existing coalitions $S$ that he might join, we get a grand total contribution of

$$\sum_{S\subseteq N\setminus\{i\}}|S|!(n-1-|S|)!\big(v(S\cup\{i\})-v(S)\big)\;.$$

That’s his total contribution over all possible lineups of $N$, all possible ways of starting with one player and building a grand coalition of everybody. We now divide by $n!$, the number of possible lineups, to get his average contribution per lineup; it’s

$$\sum_{S\subseteq N\setminus\{i\}}\frac{|S|!(n-|S|-1)!}{n!}\big(v(S\cup\{i\})-v(S)\big)\;,$$

and we define this to be his (Shapley) value in the game, $\varphi_i(v)$.