Strategyproof Mechanisms for Content Delivery Via Layered Multicast

Layered multicast exploits the heterogeneity of user capacities, making it ideal for delivering content such as media streams over the Internet. In order to maximize either its revenue or the total utility of users, content providers employing layered multicast need to carefully choose a routing, layer allocation and pricing scheme. The authors study algorithms and mechanisms for achieving either goal from a theoretical perspective. When the goal is maximizing social welfare, they prove that the problem is NP-hard, and provide a simple 3-approximation algorithm. They next tailor a payment scheme based on the idea of critical bids to derive a truthful mechanism that achieves a constant fraction of the optimal social welfare.