= Convexity criterion for an induced subgraph game
{title2=$v\text{ is supermodular}\iff w_{ij}\ge0\text{ for all }i\ne j$}
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,
$$
v(S\cup T)+v(S\cap T)-v(S)-v(T)
=\sum_{i\in S\setminus T,\ j\in T\setminus S}w_{ij}\ge0.
$$
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.
Back to article page
