Sharing the cost of muliticast transmissions (preliminary version). (English) Zbl 1296.68066
Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 218-227 (2000).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | A. Ballardie, Core Based Trees (CBT), in “Proceedings of Sigcomm ”93,” pp. 85-95, ACM Press, New York, 1993. 10.1145/166237.166246 |
| [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. · Zbl 0413.90007 |
| [4] | S. Deering and D. Cheriton, Multicast routing in datagram internetworks and extended LANs, A CM Transactions on Computer Systems 8 (1990), 85-110. 10.1145/78952.78953 |
| [5] | S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, The PIM architecture for wide-area multicast routing, A CM/IEEE Transactions on Networking 54 (1996), 153-162. 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 · Zbl 0988.91024 |
| [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. · Zbl 0417.90001 |
| [11] | T. Groves, Incentives in teams, Econometrica 41 (1973), 617-663. · Zbl 0311.90002 |
| [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] | H. Holbrook and D. Cheriton, IP multicast channels: EXPRESS support for large-scale single-source applications, in “Proceedings of Sigcomm ”99,” pp. 65-78, ACM Press, New York, 1999. 10.1145/316188.316207 |
| [14] | M.-T. Hsiao and A. Lazar, A game theoretic approach to decentralized flow control of markovian queueing networks, in “Performance ”87,” pp. 55-74, North-Holland, Amsterdam, 1988. |
| [15] | D. S. Johnson, M. Minkoff, and S. Phillips, The prize collecting steiner tree problem: theory and practice, in “Proceedings of the 11th Symposium on Discrete Algorithms,” pp. 760-769, ACM Press/SIAM, New York/Philadelphia, 2000. · Zbl 0956.68112 |
| [16] | Y. Korilis, A. A. Lazar, and A. Orda, Architecting noncooperative networks, Journal or, Selected Areas in Communications 13 (1995), 1241-1251. 10.1109/49.414643 |
| [17] | J. F. Kurose and R. Simha, A microeconomic approach to optimal resource allocation in distributed computer systems, IEEE Transactions on Computers 38 (1989), 705-717. 10.1109/12.24272 |
| [18] | E. Kushilevitz and N. Nisan, “Communication Complexity,” Cambridge University Press, Cambridge UK, 1997. · Zbl 0869.68048 |
| [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. · Zbl 0397.90111 |
| [21] | H. Moulin, Incremental cost sharing; characterization by strategyproofness, Social Choice and Welfare 16 (1999), 279-320. · Zbl 1066.91502 |
| [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 · Zbl 1087.91509 |
| [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] | N. Nisan and A. Ronen, Algorithmic mechanism design, in “Proceedings of 31st Symposium on Theory of Computing,” pp. 129-140, ACM Press, New York, 1999. 10.1145/301250.301287 · Zbl 1346.68246 |
| [25] | M. J. Osborne and A. Rubinstein, “A Course in Game Theory,” MIT Press, Cambridge MA, 1994. · Zbl 1194.91003 |
| [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. · Zbl 0429.90009 |
| [28] | J. Rosenschein and G. Zlotkin, “Rules of Encounter: Designing Conventions for Automated Negotiation Among Computers,” MIT Press, Cambridge MA, 1994. |
| [29] | B. Sanders, An incentive compatible flow control algorithm for rate allocation in computer networks, IEEE Transactions on Computers 37 (1988), 1067-1072. 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] | S. \(henker, Efficient network allocations with selfish users, in ``Performance ''90," pp. 279-285, North- Holland, Amsterdam, 1990\) |
| [32] | S. Shenker, Making greed work in networks, ACM/IEEE Transactions on Networking 3 (1995), 819-831. 10.1109/90.477727 |
| [33] | Y. Shoham and M. Wellman, Economic principles of multi-agent systems, Artificial Intelligence 94 (1997), 1-6. 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. · Zbl 0995.90578 |
| [35] | W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, Journal of Finance 16 (1961), 8- 37. |
| [36] | W. Walsh and M. Wellman, A market protocol for decentralized task allocation, in “Proceedings of the Third International Conference on Multi-Agent Systems,” pp. 325-332, IEEE Computer Society Press, Los Alamitos, 1998. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
