= Solution
\b[A loop-free <induced subgraph game> is a <convex cooperative game> if and only if every <edge weight> is nonnegative.] Necessity follows by applying the <supermodular> inequality to $S=\{i\}$ and $T=\{j\}$. Since both singleton values and the empty value are zero,
$$
v(\{i,j\})+v(\varnothing)\ge v(\{i\})+v(\{j\})
\quad\Longrightarrow\quad w_{ij}\ge0.
$$
Conversely, direct cancellation of common <edge> contributions gives, for any <coalitions> $S,T$,
$$
v(S\cup T)+v(S\cap T)-v(S)-v(T)
=\sum_{\substack{i\in S\setminus T\\j\in T\setminus S}}w_{ij}.
$$
Every summand is nonnegative, proving that $v$ is a <supermodular set function> and hence convexity. Equivalently, a player's <marginal contribution> to $S$ is $\Delta_i(S)=\sum_{j\in S}w_{ij}$, which cannot decrease as $S$ grows. This establishes the <convexity criterion for an induced subgraph game> directly.<On the Complexity of Cooperative Solution Concepts by Xiaotie Deng and Christos Papadimitriou>[§1, printed p. 258, nonnegative-weight convexity; §2.2, printed p. 260, discussion preceding Lemma 4]{ref}
Back to article page
