𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sharing the Cost of Multicast Transmissions

✍ Scribed by Joan Feigenbaum; Christos H. Papadimitriou; Scott Shenker

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
207 KB
Volume
63
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Hardness results for multicast cost shar
Hardness results for multicast cost sharing
✍ Joan Feigenbaum; Arvind Krishnamurthy; Rahul Sami; Scott Shenker πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 308 KB

We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in gam

The -serial cost-sharing rule
The -serial cost-sharing rule
✍ M. Josune Albizuri πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 314 KB
The dual serial cost-sharing rule
The dual serial cost-sharing rule
✍ M. Josune Albizuri; JosΓ© M. Zarzuelo πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 201 KB
Health status and heterogeneity of cost-
Health status and heterogeneity of cost-sharing responsiveness: how do sick people respond to cost-sharing?
✍ Dahlia K. Remler; Adam J. Atherly πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 142 KB

## Abstract This paper examines whether the responsiveness of health care utilization to cost‐sharing varies by health status and the implications of such heterogeneity. First, we show theoretically that if health care utilization of those in poor health is less responsive to cost sharing, this, co

Reliability analysis of a data transmiss
Reliability analysis of a data transmission model for multicast
✍ Mitsuhiro Imaizumi; Mitsutaka Kimura; Kazumi Yasui πŸ“‚ Article πŸ“… 2006 πŸ› Elsevier Science 🌐 English βš– 295 KB

## As computer systems have been widely used, Internet, which is a network-of-network, has been greatly developed and rapidly spread all over the world. In addition to unicast transmissions of point-to-point, multicast transmissions of one-to-many and many-to-many have been recently used. This pape