Pricing traffic in a spanning network

We construct two such rules. When all connecting costs are 0 or 1, one is derived from the random spanning tree weighted by the volume of traffic on each edge; the other is the weighted Shapley value of the Stand Alone cooperative game. Both rules are then extended by the familiar piecewise-linear technique. The former is computable in polynomial time, the latter is not.