Proof that the Shapley value satisfies the balanced contribution axiom

Question

I have read that Shapley values satisfy the balanced contribution axiom (e.g., p. 6).

However, I have not been able to show that this is indeed the case. I tried to prove it using the definition of the Shapley value: $$ \phi_{i}(v)-\phi_{i}(v \backslash j)=\phi_{j}(v)-\phi_{j}(v \backslash i) \\ \sum_{\mathcal{C} \subseteq N \backslash\{i\}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}(v(\mathcal{C} \cup\{i\})-v(\mathcal{C})) - \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{(n -1)!}(v(\mathcal{C} \cup\{i\})-v(\mathcal{C})) = \sum_{\mathcal{C} \subseteq N \backslash\{j\}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}(v(\mathcal{C} \cup\{j\})-v(\mathcal{C})) - \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{(n-1) !}(v(\mathcal{C} \cup\{j\})-v(\mathcal{C})) $$

But the only thing that can be reduced seems to be the $v(C)$ in the sum over $N \setminus \{i, j\}$. Is this the wrong approach?

Answer 1

LHS expands to

$$\sum_{\mathcal{C} \subseteq N \backslash\{i\}\ \color{blue}{ \wedge\ j \in \mathcal{C}}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}v(\mathcal{C} \cup\{i\}) - \sum_{\mathcal{C} \subseteq N \backslash\{i\}\ \color{blue}{ \wedge\ j \in \mathcal{C}}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}v(\mathcal{C}) - \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}+1| !(n-(|\mathcal{C}|+1)-1) !}{n !} v(\mathcal{C} \cup\{i\}) + \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}+1| !(n-(|\mathcal{C}|+1)-1) !}{n !} v(\mathcal{C})$$

The idea is to divide subsets of $N \setminus \{i\}$ into two: subsets without $i$ but must have $j$ (the colored text) and subsets without both $i$ and $j$. The first subsets are unaffected by $\phi_i(v \setminus j)$, hence the first and second summations are expansions of $\phi_i(v)$ by simply separating $v(\mathcal{C} \cup \{i\})$ and $v(\mathcal{C})$. Now for the second subsets, perform

$$\frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !} - \frac{|\mathcal{C}| !(n-|\mathcal{C}|-2)!}{(n-1) !}$$

The third and fourth summations are also from separating $v(\mathcal{C} \cup \{i\})$ and $v(\mathcal{C})$.

Similarly, RHS expands to

$$\sum_{\mathcal{C} \subseteq N \backslash\{j\}\ \color{blue}{ \wedge\ i \in \mathcal{C}}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}v(\mathcal{C} \cup\{j\}) - \sum_{\mathcal{C} \subseteq N \backslash\{j\}\ \color{blue}{ \wedge\ i \in \mathcal{C}}} \frac{|\mathcal{C}| !(n-|\mathcal{C}|-1) !}{n !}v(\mathcal{C}) - \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}+1| !(n-(|\mathcal{C}|+1)-1) !}{n !} v(\mathcal{C} \cup\{j\}) + \sum_{\mathcal{C} \subseteq N \backslash\{i, j\}} \frac{|\mathcal{C}+1| !(n-(|\mathcal{C}|+1)-1) !}{n !} v(\mathcal{C})$$

For the first summation of LHS and RHS: Now let $\mathcal{C}_1$ satisfy the condition of $\mathcal{C}$ in LHS. Let $\mathcal{C}_2 = \mathcal{C}_1 \cup \{i\} \setminus \{j\}$. Observe that $\mathcal{C}_2$ satisfies the condition of $\mathcal{C}$ in RHS, $|\mathcal{C}_1| = |\mathcal{C}_2|$, and $\mathcal{C}_1 \cup \{i\} = \mathcal{C}_2 \cup \{j\}$. This implies a one-to-one correspondence between the $\mathcal{C}$'s in the first summation of LHS and in RHS, and the addends of the correspondence are equal.

For the second and third summation of LHS and RHS: observe that the second summation of LHS is identical to the third summation of RHS, and vice versa!

For the fourth summation of LHS and RHS: identical.

Note: in the summation over $N \setminus \{i,j\}$, $(n-|\mathcal{C}|-1)!$ should be $((n-1)-|\mathcal{C}|-1)! = (n-|\mathcal{C}|-2)!$.

Answer 2

The Shapley Value $\phi_i(v)$ is an average over all permutations in $S_n$ of the marginal contribution of player $i$ when that player arrives. For every permutation $\pi$ where $j$ precedes $i$, consider the permutation $\pi':=(ij)\circ\pi $ obtained by transposing players $i$ and $j$. We will check that the total contribution of $\pi,\pi'$ to the LHS and the RHS of the desired identity $$(*) \quad \phi_{i}(v)-\phi_{i}(v \backslash j)=\phi_{j}(v)-\phi_{j}(v \backslash i)$$ agree. $\quad$ Note: Then summing this equality of contributions over all permutations $\pi$ where $j$ precedes $i$, and dividing by $ n!$, will finish the proof.

Indeed, if $\pi$ begins with $A,j,B,i$, then the contribution of $\pi$ to $\phi_i(v)$ is $$v(A\cup \{j\} \cup B \cup \{i\})-v(A\cup \{j\} \cup B)$$ so the contribution of $\pi$ to the LHS of $(*)$ is $$(**) \quad v(A\cup \{j\} \cup B \cup \{i\})-v(A\cup \{j\} \cup B) -v(A\cup B \cup \{i\})+v(A \cup B)\,.$$ Now $\pi'$ begins with $A,i,B,j$, so it also begins with $A,i$. Thus the contribution of $\pi'$ to the LHS of $(*)$ is zero.

With the RHS of $(*)$, the situation is reversed: The contribution of $\pi$ to the RHS is zero, since $\pi$ starts with $A,j$. The contribution of $\pi'$ to $\phi_j(v)$ is $$v(A\cup \{i\} \cup B \cup \{j\})-v(A\cup \{i\} \cup B)$$ so the contribution of $\pi'$ to the RHS of $(*)$ is exactly $(**)$. This completes the proof, in view of the note above.