= Solution
An <induced subgraph game> is a <transferable utility game> represented by a weighted <undirected graph> with one <vertex> per player; a <coalition>'s value is the sum of the <edge weights> in its <induced subgraph>. With no <self-loops>,
$$
\boxed{v(S)=\sum_{\{i,j\}\subseteq S,\ i\ne j}w_{ij},}
$$
where each unordered pair is counted once and an absent <edge> has weight zero. Weights may have either sign. In an <induced subgraph game with self-loops>, write the loop weight at $i$ as $\ell_i$ and add $\sum_{i\in S}\ell_i$, counting each loop once. In particular, $v(\{i\})=\ell_i$ when loops are allowed and is zero otherwise.<On the Complexity of Cooperative Solution Concepts by Xiaotie Deng and Christos Papadimitriou>[§1, printed p. 258: weighted induced-subgraph representation; the self-loop extension is stated explicitly here]{ref}
Back to article page
