Title: | Sharing the Cost of Multicast Transmissions |

Author: | Joan Feigenbaum, Christos H. Papadimitriou, and Scott Shenker |

Journal: | Journal of Computer and System Sciences |

Volume: | 63 |

Number: | 1 |

Pages: | 21--41 |

Month: | August |

Year: | 2001 |

DOI: | 10.1006/jcss.2001.1754 |

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. |

Cited by 180

@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} }Last modified: Wed Mar 9 10:15:15 EST 2011