Sharing the cost of muliticast transmissions (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sharing the cost of muliticast transmissions (preliminary version)

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 218 - 227

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Joan Feigenbaum	AT&T Labs - Research, 180 Park Ave., C203, Florham Park, NJ
Christos Papadimitriou	Computer Science Dept., U. C. Berkeley, Berkeley, CA
Scott Shenker	ACIRI/ICSI, 1947 Center Street, Suite 600, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 44, Citation Count: 29

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335332 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), Conference proceedings on Communications architectures, protocols and applications, p.85-95, September 13-17, 1993, San Francisco, California, United States
	2	E. H. Clarke, Multipart pricing of public goods, Public Choice 11 (1971), 17-33.
	3	P. Dasgupta, P. Hammond, and E. Maskin, The implementation of social choice rules, Review of Economics Studies 46 (1979), 185-216.
	4	Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
	5	Stephen Deering , Deborah L. Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, The PIM architecture for wide-area multicast routing, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.153-162, April 1996 [doi>10.1109/90.490743]
	6	D. Ferguson, C. Nikolaou, and Y. Yemini, An economy for flow control in computer networks, in "Proceedings of the 8th Infocom," pp. 100-118, IEEE Computer Society Press, Los Alamitos, 1989.
	7	E. Friedman and S. Shenker, "Learning and Implementation in the Internet," preprint, 1997. Available at ht tp: //www. ac ir i. org/shenk er/decent, ps
	8	A. V. Goldberg, J. D. Hartline, and A. Wright, "Competitive Auctions and Digital Goods," InterTrust Technical Report 99-01. Available at http: //www. intertrust, corn/st ar/tr/t r-99-01, html
	9	J. Green, E. Kohlberg, and J. J. Lattont, Partial equilibrium approach to the free rider problem, Journal of Public Economics 6 (1976), 375-394.
	10	J. Green and J. J. Laffont, Incentives in public decision making, in "Studies in Public Economics," pp. 65-78, North-Holland, Amsterdam, 1979, Vol. 1.
	11	T. Groves, Incentives in teams, Econometrica 41 (1973), 617-663.
	12	T. Groves and J. Ledyard, Incentive compatibility since 1972, in "Information, Incentives, and Economics Mechanisms," pp. 48-111, University of Minnesota Press, Minneapolis, 1987.
	13	Hugh W. Holbrook , David R. Cheriton, IP multicast channels: EXPRESS support for large-scale single-source applications, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.65-78, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	14	Man-tung T. Hsiao , Aurel A. Lazar, A Game Theoretic Approach to Decentralized Flow Control of Markovian Queueing Networks, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.55-73, December 07-09, 1987
	15	David S. Johnson , Maria Minkoff , Steven Phillips, The prize collecting Steiner tree problem: theory and practice, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.760-769, January 09-11, 2000, San Francisco, California, United States
	16	Y. Korilis, A. A. Lazar, and A. Orda, Architecting noncooperative networks, Journal or, Selected Areas in Communications 13 (1995), 1241-1251.
	17	James F. Kurose , Rahul Simha, A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems, IEEE Transactions on Computers, v.38 n.5, p.705-717, May 1989 [doi>10.1109/12.24272]
	18	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	19	E. Maskin, The theory of implementation in Nash equilibrium, in "Social Goals and Organization: Essays in Memory of Elisha Pazner," pp. 173-204, Cambridge University Press, Cambridge UK, 1985.
	20	N. Megiddo, Computational complexity of the game theory approach to cost allocation for a tree, Mathematics of Operations Research 3 (1978), 189-196.
	21	H. Moulin, Incremental cost sharing; characterization by strategyproofness, Social Choice and Welfare 16 (1999), 279-320.
	22	H. Moulin and S. Shenker, "Strategyproof Sharing nof Submodular Costs: Budget Balance Versus Efficiency," to appear in Economic Theory. Available in preprint form at http://www, aciri, org/shenker/cost, ps
	23	N. Nisan, Algorithms for selfish agents, in "Proceedings of 16th Symposium on Theoretical Aspects of Computer Science," pp. 1-17, Springer-Verlag, Berlin, 1999. Lecture Notes in Computer Science, Vol. 1563.
	24	Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
	25	M. J. Osborne and A. Rubinstein, "A Course in Game Theory," MIT Press, Cambridge MA, 1994.
	26	R. Perlman, (2.-Y. Lee, A. Ballardie, J. Crowcroft., Z. Wang, T. Maufer, C. Diot, and M. Green, Simple multicast: A design for simple low-overhead multicast, iETF Internet Draft (Work in Progress), 1999.
	27	K. Roberts, The Characterization of Implementable Choice Rules, in "Aggregation and Revelation of Preferences,'' pp. 321-348, North-Holland, Amsterdam, 1979.
	28	Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
	29	B. A. Sanders, An Incentive Compatible Flow Control Algorithm for Rate Allocation in Computer Networks, IEEE Transactions on Computers, v.37 n.9, p.1067-1072, September 1988 [doi>10.1109/12.2257]
	30	L. S. Shapley, A value for n-person games, in "Contributions to the Theory of Games," pp. 31-40, Princeton University Press, Princeton, 1953.
	31	Scott Shenker, Efficient Network Allocations with Selfish Users, Proceedings of the 14th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.279-285, September 12-14, 1990
	32	Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
	33	Craig Boutilier , Yoav Shoham , Michael P. Wellman, Economic principles of multi-agent systems, Artificial Intelligence, v.94 n.1-2, p.1-6, July 1997 [doi>10.1016/S0004-3702(97)00029-5]
	34	M. Shubik, Incentives, decentralized controls, the assignment of joint costs and internal pricing, Management Science 8 (1962), 325-343.
	35	W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, Journal of Finance 16 (1961), 8- 37.
	36	William E. Walsh , Michael P. Wellman, A Market Protocol for Decentralized Task Allocation, Proceedings of the 3rd International Conference on Multi Agent Systems, p.325, July 03-07, 1998

CITED BY 29

	Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece
	Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece
	Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
	Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece
	Micah Adler , Dan Rubenstein, Pricing multicasting in more practical network models, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.981-990, January 06-08, 2002, San Francisco, California
	Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece
	Markus Bläser , Bodo Manthey, Budget balanced mechanisms for the multicast pricing problem with rates, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA
	Pragyansmita Paul , S. V. Raghavan, Survey of multicast routing algorithms and protocols, Proceedings of the 15th international conference on Computer communication, p.902-926, August 12-14, 2002, Mumbai, Maharashtra, India
	Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
	Vittorio Bilè , Chiara Di Francescomarino , Michele Flammini , Giovanna Melideo, Sharing the cost of multicast transmissions in wireless networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Artur Czumaj , Amir Ronen, On the expected payment of mechanisms for task allocation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Debasis Mishra , Bharath Rangarajan, Cost sharing in a job scheduling problem using the Shapley value, Proceedings of the 6th ACM conference on Electronic commerce, p.232-239, June 05-08, 2005, Vancouver, BC, Canada
	Andrew V. Goldberg , Jason D. Hartline, Competitiveness via consensus, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005
	Micah Adler , Dan Rubenstein, Pricing multicasting in more flexible network models, ACM Transactions on Algorithms (TALG), v.1 n.1, p.48-73, July 2005
	Andrew V. Goldberg , Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Vittorio Bilò , Michele Flammini , Giovanna Melideo , Luca Moscardelli, On Nash equilibria for multicast transmissions in ad-hoc wireless networks, Wireless Networks, v.14 n.2, p.147-157, March 2008
	Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA
	Liad Blumrosen , Shahar Dobzinski, Welfare maximization in congestion games, Proceedings of the 7th ACM conference on Electronic commerce, p.52-61, June 11-15, 2006, Ann Arbor, Michigan, USA
	Dennis Geels , John Kubiatowicz, Replica management should be a game, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France
	Yogeshwer Sharma , David P. Williamson, Stackelberg thresholds in network routing games or the value of altruism, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Angelo Fanelli , Michele Flammini , Luca Moscardelli, On the convergence of multicast games in directed networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Yuval Shavitt , Peter Winkler , Avishai Wool, On the Economics of Multicasting, Netnomics, v.6 n.1, p.1-20, April 2004
	Jing Chen , Silvio Micali, A new approach to auctions and resilient mechanism design, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Journal of Artificial Intelligence Research, v.29 n.1, p.19-47, May 2007