I come from an Engineering background and I am trying to understand the shapley value formula.
$$ \phi_i(v)=\sum_{S\subseteq N-i} \frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S)) $$
I understand that this term $(v(S\cup\{i\})-v(S))$ calculates the worth of feature i by creating a collation with and without feature i and subtracting the worth (v is the worth function).
I also understand that we average over the worth of i, considering all the permutations possible in creating the collations.
However, I don't understand the following points:
What does |S| and |N| mean? Is || this operator an absolute value? And why do we need it?
Why do we average over the permutations and not the combinations?
What does this weight factor mean $\frac{|S|!(|N|-|S|-1)!}{|N|!}$ in the weighted sum?
$|S|$ is the cardinality of $S$. For a finite set, the cardinality is simply the number of elements in the set.
We average over permutations because the contribution made by a player (you seem to be calling the players “features”?) depends on the order in which the players contribute. $v(S\cup \{i\})-v(S))$ represents the contribution of player $i$ if player $i$ joins the coalition after all players in $S$ have joined.
The weight factor is the overall normalization constant $\frac1{|N|!}$ (since we’re averaging over $|N|!$ permutations) times $|S|!(|N|-|S|-1)!$, which represents the number of orders in which the $|S|$ members of $S$ can join the coalition before player $i$ and the $|N|-|S|-1$ members of $N\setminus (S\cup\{i\})$ can join the coalition after player $i$. That is, instead of summing over all permutations individually, we collect all those in which a certain set of players join before player $i$ (in whatever order) and the rest join afterwards (in whatever order); the contribution of player $i$ is the same, $v(S\cup \{i\})-v(S))$, for each of these permutations, so we multiply by their count.