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!$.

There is another way to look at this. or rather, a way to extend our understanding. a common thing done in algebra is to symmetrize a function by adding up all the permutations of the variables. a symmetric function is one in which you can interchange any of the variables and the function will stay the same. not in the trivial sense that $f(x,y)$ is "the same" as $f(y,x)$ since x and y are "just variables". but rather, in the sense that $f(x,y)=f(y,x)$. in symbols:

• we are NOT saying $(x,y)\mapsto f(x,y)=(y,x)\mapsto f(y,x)$. this is trivially true for all functions!
• but rather: $(x,y)\mapsto f(x,y)=(x,y)\mapsto f(y,x)$. or in other words: $\forall x\forall y[f(x,y)=f(y,x)]$ (this is not trivially true! it's false for many functions including $f(x,y):=x-y$)

in the case of the shapley value, the "marginal contribution" function is NOT symmetric. so the naive fix that we would hope would work is to symmetrize it by adding all the possible permutations of the variables, forming a new function.

wait, what? what even is the "marginal contribution function"?? for a player i of interest, it's the function that gives player i's marginal contribution, given an arbitrary sequence of players as input. let's say we are given a sequence $(x_{1},x_{2},\ldots ,x_{n})$. what's player i's marginal contribution in this sequence? well, if x1 = i, then player i is the first player to join, so the marginal contribution is $v(\{i\})-v(\emptyset )=v(\{i\})$. if x2=i, then the marginal contribution of player i is $v(\{x_{1},i\})-v(\{x_{1}\})$. and so on. in general, if $x_{j}=i$ then player i's marginal contribution is $v(\{x_{1},\ldots ,x_{j-1},i\})-v(\{x_{1},\ldots ,x_{j-1}\})$.

as i said, this function, which we can call $f_{i}$, is not symmetric. but we can symmetrize $f_{i}$ by adding up all the possible orderings of the input variables:

$\sum _{\sigma \in \mathrm {Sym} (n)}f_{i}(x_{\sigma (1)},\ldots ,x_{\sigma (n)})$

given a permutation $\sigma \in \mathrm {Sym} (n)$ and a function $f:X^{n}\to \mathbf {R}$, we can define the permutation of the function $\sigma ^{*}:(X^{n}\to \mathbf {R} )\to X^{n}\to \mathbf {R}$ by:

$\sigma ^{*}(f):=(x_{1},\ldots ,x_{n})\mapsto f(x_{\sigma (1)},\ldots ,x_{\sigma (n)})$

By an abuse of notation, we can drop the star in $\sigma ^{*}$ and just call the resulting extension $\sigma$. Using this new notation, we can rewrite the symmetrization as

$\sum _{\sigma \in \mathrm {Sym} (n)}\sigma (f_{i})$

There are now two problems:

1. the expression above is in terms of variables $x_{1},\ldots ,x_{n}$ or in other words it's a function, not a number; we need to evaluate it somehow
2. the expression is not normalized. the total value of the grand coalition is $v(\{1,\ldots ,n\})$. we need to make sure that when we add up all the shapley values we give to each player, that that sum is equal to $v(\{1,\ldots ,n\})$.

problem 1 is easy to solve. because we symmetrized the function, we can evaluate the function on any ordering of the players!

$\left(\sum _{\sigma \in \mathrm {Sym} (n)}\sigma (f_{i})\right)(1,\ldots ,n)$

is one such way to get a number. but really, the ordering of (1, ..., n) does not matter.

as for problem 2, we want to find a value of $\alpha$ such that the following is satisfied:

$v(\{1,\ldots ,n\})=\alpha \sum _{i=1}^{n}\left(\sum _{\sigma \in \mathrm {Sym} (n)}\sigma (f_{i})\right)(1,\ldots ,n)$

so just rearrange to solve for $\alpha$, and we are done. at least, conceptually. it would be nice if we could prove that $\alpha ={\frac {1}{|\mathrm {Sym} (n)|}}$. this is not hard to do (just interchange the two sums. for fixed sigma, the form of f_i means you can telescope-sum it to get $v(N)-v(\emptyset )=v(N)$ in each inner sum. see wikipedia for details.)

So the fully honest shapley value expression is the following:

${\frac {v(\{1,\ldots ,n\})}{\sum _{i=1}^{n}\left(\sum _{\sigma \in \mathrm {Sym} (n)}\sigma (f_{i})\right)(1,\ldots ,n)}}\left(\sum _{\sigma \in \mathrm {Sym} (n)}\sigma (f_{i})\right)(1,\ldots ,n)$