User:IssaRice/Shapley value

most expositions of the Shapley value SUCK BALLS because they try to sum over the subsets excluding the playing in question (usually called "player i"). so here we go, here's a TRUE REDPILLED exposition of the shapley value!

first of all, what's the shapley value even trying to do? once we understand it in words, we can just convert our verbal understanding into symbols. and then we will be done.

...

So, the shapley value is an average. but what kind of average? an arithmetic average. well, an arithmetic average takes a specific form. it looks like this. if you're averaging the elements of some set $X$, then the arithmetic average ${\bar {X}}$ is

${\bar {X}}={\frac {1}{|X|}}\sum _{x\in X}f(x)$

We throw in the function f because the elements of X might not be numbers. or even if they are numbers, you might want to apply some weighting other than the default one (the identity function).

Now, let's take the ugly-ass formula for the shapley value that you always see:

$\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\ (n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))$

how is that supposed to be an average? well first of all, we said above that the shapley value is averaging over all sequences of ways to add the n players. one way to formalize the concept of a "sequence" or "ordering" is to use permutations. a permutation is just a function that reorders the elements of of a set. so each sequence corresponds to a permutation. we can recover a sequence $(x_{1},x_{2},\ldots ,x_{n})$ by defining the permutation $\sigma (k):=x_{k}$.

So in what sense is the shapley value an average? if $N=\{1,\ldots ,n\}$ is the set of players, then we can define the set of all permutations $\mathrm {Sym} (N)$ on $N$. (This is also denoted as $\mathrm {Sym} (n)$ and called the "symmetric group of degree n" since $N=\{1,\ldots ,n\}$ is the "default" set of size n.)

since the shapley value is an average and we are in particular averaging over all sequences, we want to rewrite the formula as something that looks like:

${\frac {1}{|\mathrm {Sym} (n)|}}\sum _{\sigma \in \mathrm {Sym} (n)}f(\sigma )$

And in fact, at this point we know enough to convert our verbal understanding into a formula like the one above.

$\varphi _{i}(v)={\frac {1}{|\mathrm {Sym} (n)|}}\sum _{\sigma \in \mathrm {Sym} (n)}(v(\{k:\sigma (k)<\sigma (i)\}\cup \{i\})-v(\{k:\sigma (k)<\sigma (i)\}))$

a relevant fact is that the size of $\mathrm {Sym} (n)$ is $n!$.

the Shapley value is ${\frac {1}{|\mathrm {Sym} (n)|}}\sum _{\sigma \in \mathrm {Sym} (n)}f_{i}(\sigma (1),\ldots ,\sigma (n))$