Strategyproof Mechanisms for Content Delivery via Layered Multicast

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.
Type de document :
Communication dans un congrès
Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6641 (Part II), pp.82-96, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20798-3_7〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01597964
Contributeur : Hal Ifip <>
Soumis le : vendredi 29 septembre 2017 - 09:45:50
Dernière modification le : vendredi 29 septembre 2017 - 10:00:22
Document(s) archivé(s) le : samedi 30 décembre 2017 - 12:46:23

Fichier

978-3-642-20798-3_7_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ajay Gopinathan, Zongpeng Li. Strategyproof Mechanisms for Content Delivery via Layered Multicast. Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6641 (Part II), pp.82-96, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20798-3_7〉. 〈hal-01597964〉

Partager

Métriques

Consultations de la notice

20

Téléchargements de fichiers

3