Shapley value of an induced subgraph game
= Shapley value of an induced subgraph game
{c}
{title2=$\phi_i(v)=\frac12\sum_{j\ne i}w_{ij}$}
In a uniformly random player <permutation>, edge $\{i,j\}$ contributes $w_{ij}$ to $i$'s <marginal contribution> exactly when $j$ precedes $i$, which occurs with <probability> $1/2$. Sum these expected contributions over incident <graph edges> to obtain the displayed <Shapley value>. This proof works for arbitrary real edge weights; nonnegativity is not required.