@Article{feigenbaum01a,
  author =	 {Joan Feigenbaum and Christos H. Papadimitriou and
                  Scott Shenker},
  title =	 {Sharing the Cost of Multicast Transmissions},
  journal =	 {Journal of Computer and System Sciences},
  year =	 2001,
  volume =	 63,
  number =	 1,
  pages =	 {21--41},
  month =	 {August},
  abstract =	 {We investigate cost-sharing algorithms for multicast
                  transmission. Economic considerations point to two
                  distinct mechanisms, marginal cost and Shapley
                  value, as the two solutions most appropriate in this
                  context. We prove that the former has a natural
                  algorithm that uses only two messages per link of
                  the multicast tree, while we give evidence that the
                  latter requires a quadratic total number of
                  messages. We also show that the welfare value
                  achieved by an optimal multicast tree is NP-hard to
                  approximate within any constant factor, even for
                  bounded-degree networks. The lower-bound proof for
                  the Shapley value uses a novel algebraic technique
                  for bounding from below the number of messages
                  exchanged in a distributed computation; this
                  technique may prove useful in other contexts as
                  well.},
  keywords =     {networks routing mechanism-design},
  doi = 	 {10.1006/jcss.2001.1754},
  url = 	 {http://jmvidal.cse.sc.edu/library/feigenbaum01a.pdf},
  googleid = 	 {AqzKOFdnikYJ:scholar.google.com/},
  cluster = 	 {5082988753753648130}
}