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).

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.)

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

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

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