Hardness results for multicast cost sharing

被引:45
作者
Feigenbaum, J
Krishnamurthy, A
Sami, R
Shenker, S
机构
[1] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
[2] ICSI, Berkeley, CA 94704 USA
基金
美国国家科学基金会;
关键词
algorithmic mechanism design; communication complexity; multicast;
D O I
10.1016/S0304-3975(03)00085-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in game theory to show that no strategyproof mechanism can be both approximately efficient and approximately budget-balanced. Our results show that one important and natural case of multicast cost sharing is an example of a canonical hard problem in distributed, algorithmic mechanism design; in this sense, they represent progress toward the development of a complexity theory of Internet computation. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码:215 / 236
页数:22
相关论文
共 31 条
[1]  
[Anonymous], 1997, COMMUNICATION COMPLE
[2]  
[Anonymous], PERFORMANCE 87
[3]  
[Anonymous], P 8 INF
[4]  
[Anonymous], P ACM SIGCOM SAN FRA
[5]   The PIM architecture for wide-area multicast routing [J].
Deering, S ;
Estrin, DL ;
Farinacci, D ;
Jacobson, V ;
Liu, CG ;
Wei, LM .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1996, 4 (02) :153-162
[6]   A CONCEPT OF EGALITARIANISM UNDER PARTICIPATION CONSTRAINTS [J].
DUTTA, B ;
RAY, D .
ECONOMETRICA, 1989, 57 (03) :615-635
[7]  
FEIGENBAUM J, 2002, P 6 INT WORKSH DISCR, P1
[8]  
Fiat A., 2002, P 34 ANN ACM S THEOR, P72, DOI 10.1145/509907.509921
[9]  
Green J., 1979, Incentives in Public Decision Making
[10]   Sharing the "cost" of multicast trees: An axiomatic analysis [J].
Herzog, S ;
Shenker, S ;
Estrin, D .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1997, 5 (06) :847-860