4
$\begingroup$

Page 227 of An Introductory Course on Mathematical Game Theory by Gonzalez-Diaz, Garcia-Jurado, and Fiestras-Janeiro gives a formula for the Shapley value $\Phi$ of transferable utility games $v\in G^N$ as: $$\Phi_i(v):=\sum_{S\subset N \setminus \{i\}}\frac{|S|!(n-|S|-1)!}{n!}(v(S \cup \{i\})-v(S)).$$ It goes on to state that "therefore, in the Shapley value, each player gets a weighted average of the contributions he makes to the different coalitions." Saying that this is a weighted average of the values $(v(S \cup \{i\})-v(S))$ implies that $\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$, but I'm curious as to why this is true.

Can someone please give a detailed proof that $\sum_{S \subset N \setminus \{i\}} {|S|!(n-|S|-1)!}=n!$ ?

Thank you.

$\endgroup$
  • $\begingroup$ The right side, $n!$, clearly denotes the number of permutations of $\{1,2,\dots,n\}$. The left side is a summation, and a specific term in the summation denotes the number permutations of $\{1,2,\dots,n\}$ where all elements in $S$ appear before $1$ (meaning the remaining $n-|S|-1$ elements which are not 1 nor an element of $S$ appear after $1$). $\endgroup$ – JMoravitz Jul 16 '18 at 17:39
1
$\begingroup$

Let $A$ be the number of ways of listing the elements of $N$.

First way: $n!$. This comes about by first choosing one number at random and writing it first. Then choosing a second number at random and writing in second, etc. There are $n!$ ways to do this.

Second way. Start by fixing $S\subset N\setminus\{i\}$. Then one way to list out the elements in $N$ is to first list out the elements in $S$ (there are $|S|!$ was to do this), then to append the number $i$, and finally to list out the remaining $n-|S|-1$ elements (there are $(n-|S|-1)!$ ways to do this). Thus, for a fixed $S$, if we insist on listing the elements within $S$ first, then there are $|S|!(n-|S|-1)!$ ways to do this. We can get all possible lists this way as we consider all possible choices of $S$: $$ \sum_{S\subset N\setminus\{i\}}|S|!(n-|S|-1)! $$ Therefore, $$ n!=\sum_{S\subset N\setminus\{i\}}|S|!(n-|S|-1)! $$

$\endgroup$
1
$\begingroup$

I assume that $N$ is a set with $n$ elements. I am giving an algebraic proof, since a combinatorial proof has been provided. The required equality is equivalent to $$n!=\sum_{r=0}^{n-1}\,\binom{n-1}{r}\,r!\,(n-r-1)!\,,$$ as there are $\binom{n-1}{r}$ sets $S$ with $r$ elements contained in $N\setminus \{i\}$, where $i \in N$ and $r\in\{0,1,2,\ldots,n-1\}$. Now, $\binom{n-1}{r}=\frac{(n-1)!}{r!\,\big((n-1)-r\big)!}$ by definition, so $$\sum_{r=0}^{n-1}\,\binom{n-1}{r}\,r!\,(n-r-1)!=\sum_{r=0}^{n-1}\,(n-1)!=n\cdot(n-1)!=n!\,.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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