Shapley value of an induced subgraph game (${\varphi }_i(v)=\frac{1}{2}{\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.