= Solution
\b[$G_1$ cannot have an <induced subgraph game> representation. $G_2$ is represented by a weighted triangle with edge weights $w_{12}=2$, $w_{13}=3$, $w_{23}=3$, and has <Shapley value> vector $(5/2,5/2,3)$.]
In an <induced subgraph game>, players are <graph vertices> and a <coalition> receives the sum of the weights of <graph edges> whose two endpoints lie in it. Therefore each two-player <coalition> determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand <coalition> worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player <coalition>'s value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.
For $G_2$, the stated weighted <graph triangle> has grand <coalition> value $2+3+3=8$ and reproduces all three pair values. Empty and singleton <coalitions> contain no <graph edges>, so their values are zero. This verifies all eight <coalitions> and supplies the complete representation.
To compute the <Shapley value>, reveal players in a uniformly random <permutation>. An edge's weight contributes to an endpoint's <marginal contribution> precisely when the other endpoint appeared earlier. Each endpoint is later with <probability> $1/2$, independently of where the third player appears. Linearity of the <expected value> therefore splits each edge weight equally between its two endpoints:
$$
\boxed{\phi_1=\frac{2+3}{2}=\frac52,\quad
\phi_2=\frac{2+3}{2}=\frac52,\quad
\phi_3=\frac{3+3}{2}=3.}
$$
The values sum to $8=v_2(N)$, as required by the <Shapley value>'s efficiency property. This is the general <Shapley value of an induced subgraph game> formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.
Back to article page
