This exercise considers maintenance costs associated with a road network connecting villages to a central township. The network is depicted as a tree, with the central township at the root of the tree. Each village is associated with a node of the tree, and there are additional nodes of the tree that represent road intersections.
The villages vary in their numbers of inhabitants. An example appears in the following figure, which depicts six villages and two intersections; the number of inhabitants in each village appears in the figure, near that village's name, and each segment of road connecting two intersections, or connecting the township to an intersection, is labeled with that segment's maintenance cost.
A cost game (N; c) is derived from the network, where N is the set of residents in all the villages (in this example |N| = 200), and for each coalition S ⊆ N, c(S) is the maintenance cost of the minimal subtree required to maintain the network of roads connecting all the members in S to the central township.
Prove that if the Shapley value of such a game is used to determine the allocation of costs, then the maintenance cost of each road segment is borne equally by all the people using that segment. For example, in the figure above, the Shapley value of every resident of Hobbiton is
(500/60) + (1,000/90) + (3,000/200) = 34.(4/9)