%%javascript
MathJax.Hub.Config({
TeX: { equationNumbers: { autoNumber: "AMS" } }
});
A clear version of http://neconomides.stern.nyu.edu/networks/Shapley_A_value_for_n-person_games.pdf.
Suppose we'd like to come up with a formula for a value that calculates the division of payoff among of a gorup of players for a game $v$. We'll denote this value as $\phi_i(v)$ for the $i$th player, and it needs satisfy the following three axioms.
For each permutation $\pi$ in $\Pi(N)$, where $N$ is the universe of all players,
Here $v$ is a $2^{n - 1}$-dimension vector indexed by $i$, and $\pi v$ is a vector with reordered elements and can be indexed by $\pi(i)$.
The formulation of $v$ as a vector here is confusion, needs better notations here
For each carrier $C$ of $v$,
Note a carrier is a subset of $C$ that includes all the influential players and perhaps some non-influential players, so $v(S) = v(C \cap S)$.
For any two games $v$ and $w$,
If $C$ is a finite carrier of $v$, then for $j \notin C$,
.
Proof: since $C$ and $C \cup \{j\}$ are both carriers, by Axiom 2,
so $\phi_j(v) = 0$
In other words, $j$ is a dummy player. The carrier axiom integrates both efficiency and dummy axioms as described in later literatures.
Define a game
where both $S \subseteq N$ and $R \subseteq N, R \neq \emptyset$ (Not sure if the emptyset part matters).
We'll use $s, r, n \dots$ to denote the size of sets $S, R, N \dots$.
The game $w_R$ can be thought as such: given $R$, it calculates the payoffs for all subsets ($S$) of $N$, therefore, we can define $2^{n - 1}$ ($R \neq \emptyset$) of such games.
Note,
Therefore, we always have
.
i.e. $R$ is a carrier of $w_R(S)$.
Now, the lemma is that for $w_R(S)$,
Proof:
Given the definition of $w_R$ and players in $R$ are indistinguishable, so they all get the same payoff.
$v$ is a linear combination of $2^{n} - 1$ $w_R$s:
where
This coefficient seems magical.
Now, we prove for any subset $S \subseteq N$,
Transforming the right-hand side,
Note,
Given we know $\phi_i(w_R) = 1 / r$, we can calculate $\phi_i(v)$ based on Axiom 3,
Note,
Considering the definition of $\gamma_i(T)$
It's apparent that if $i \notin T$, then
$$ \gamma_i(T \cup \{ i \}) = - \gamma_i(T) $$So $\phi_i(v)$ can be rewritten as
Further transforming $\gamma_i(T \cup \{i\})$,
Note,
Therefore, we get the familiar equation for Shapley value:
TODO: prove $c_R$ is unique if $v$ is a linear combination of $w_R$s.