Induced subgraph game ($v(S)={\sum }_{\{i,j\}\subseteq S}{w}_{ij}$)

A transferable utility game represented by a weighted undirected graph, with one player per graph vertex. A coalition receives the sum of weights of the graph edges in its induced subgraph; absent edges have weight zero. Singleton and empty coalitions have value zero. This is a representation of a transferable utility game, distinct from a graphical description of local payoffs in a normal-form game.

A loop-free induced subgraph game is a convex cooperative game exactly when all edge weights are nonnegative. Necessity follows by testing the supermodular inequality on two distinct singleton coalitions. For sufficiency,Only edges connecting the two set differences survive cancellation. Loop contributions cancel as well, so the same off-diagonal condition remains sufficient and necessary when self-loops are added.

An induced subgraph game extended by one self-loop weight ${\ell }_i$ per player. Each loop is counted once, so $v(\{i\})={\ell }_i$ andSingleton and pair coalition values determine all weights; larger coalition values must then agree with their sums. Signed weights are allowed. For example, two loops of weight $1$ joined by an edge of weight $-1$ represent the simple cooperative game in which any coalition meeting those two players wins.

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.