Abstract
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. We study algorithms and mechanisms for achieving either goal from a theoretical perspective. When the goal is maximizing social welfare, we prove that the problem is NP-hard, and provide a simple 3-approximation algorithm. We 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. When the goal is revenue maximization, we first design an algorithm that computes the revenue-maximizing layer pricing scheme, assuming truthful valuation reports. This algorithm, coupled with a new revenue extraction procedure for layered multicast, is used to design a randomized, strategyproof auction that elicits truthful reports. Employing discrete martingales to model the auction, we show that a constant fraction of the optimal revenue can be guaranteed with high probability. Finally, we study the efficacy of our algorithms via simulations.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Kurose, J., Ross, K.: Computer networking: a top-down approach featuring the Internet. Addison-Wesley, Reading (2003)
Jain, K., Mahdian, M., Salavatipour, M.R.: Packing Steiner Trees. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA (2003)
Thimm, M.: On the approximability of the steiner tree problem. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, p. 678. Springer, Heidelberg (2001)
McCanne, S., Jacobson, V., Vetterli, M.: Receiver-driven layered multicast. In: Proceedings of ACM SIGCOMM (1996)
Zhao, J., Yang, F., Zhang, Q., Zhang, Z., Zhang, F.: Lion: Layered overlay multicast with network coding. IEEE Transactions on Multimedia 8, 1021 (2006)
Gopinathan, A., Li, Z.: Optimal layered multicast. ACM Transactions on Multimedia Computing, Communications and Applications 7(2) (2011)
Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: Proceedings of the ACM Symposium on Theory of computing, STOC (1999)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Ahlswede, R., Cai, N., Li, S.R., Yeung, R.W.: Network Information Flow. IEEE Transactions on Information Theory 46(4), 1204–1216 (2000)
Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 8–37 (1961)
Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17–33 (1971)
Groves, T.: Incentives in teams. Econometrica: Journal of the Econometric Society, 617–631 (1973)
Goldberg, A., Hartline, J., Karlin, A., Saks, M., Wright, A.: Competitive auctions. Games and Economic Behavior 55(2), 242–269 (2006)
Azuma, K.: Weighted sums of certain dependent random variables. Tohoku Mathematical Journal 19(3), 357–367 (1967)
Gopinathan, A., Li, Z.: Strategyproof mechanisms for layered multicast, http://ajay.gopinathan.net
Li, Z., Li, B., Jiang, D., Lau, L.C.: On Achieving Optimal Throughput with Network Coding. In: Proceedings of IEEE INFOCOM (2005)
Li, Z., Li, B.: Efficient and Distributed Computation of Maximum Multicast Rates. In: Proceedings of IEEE INFOCOM (2005)
Myerson, R.B.: Optimal auction design. Mathematics of Operations Research, 58–73 (1981)
Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: Proceedings of the ACM Conference on Electronic Commerce, EC (2005)
ISO/IEC, Generic coding of moving pictures and association audio information, ISO/IEC 13 818–2 (1995)
ITU, Video coding for low bit rate communication. ITU-T Recommendation H.263 (1998)
Boston University Representative Internet Topology gEnerator, http://www.cs.bu.edu/brite/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 IFIP International Federation for Information Processing
About this paper
Cite this paper
Gopinathan, A., Li, Z. (2011). Strategyproof Mechanisms for Content Delivery via Layered Multicast. In: Domingo-Pascual, J., Manzoni, P., Palazzo, S., Pont, A., Scoglio, C. (eds) NETWORKING 2011. NETWORKING 2011. Lecture Notes in Computer Science, vol 6641. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20798-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-20798-3_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20797-6
Online ISBN: 978-3-642-20798-3
eBook Packages: Computer ScienceComputer Science (R0)