Approximation and collusion in multicast cost sharing

被引:35
作者
Archer, A
Feigenbaum, J
Krishnamurthy, A [1 ]
Sami, R
Shenker, S
机构
[1] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
[2] Cornell Univ, Dept Operat Res, Ithaca, NY 14853 USA
[3] ICSI, Berkeley, CA 94704 USA
基金
美国国家科学基金会;
关键词
D O I
10.1016/S0899-8256(03)00176-3
中图分类号
F [经济];
学科分类号
02 ;
摘要
We investigate multicast cost sharing from both computational and economic perspectives. Recent work in economics leads to the consideration of two mechanisms: marginal cost (MC), which is efficient and strategyproof, and Shapley value (SH), which is budget-balanced and group-strategyproof. Subsequent work in computer science shows that the MC mechanism can be computed with only two modest-sized messages per link of the multicast tree but that computing the SH mechanism for p potential receivers can require Omega(p) bits of communication per link. We extend these results in two directions. First, we give a group-strategyproof mechanism that exhibits a tradeoff between the other properties of SH: It can be computed with exponentially lower worst-case communication than the SH algorithm, but it might fail to achieve exact budget balance (albeit by a bounded amount). Second, we completely characterize the groups that can strategize successfully against the MC mechanism. (C) 2003 Elsevier Inc. All rights reserved.
引用
收藏
页码:36 / 71
页数:36
相关论文
共 33 条
[21]   Incremental cost sharing: Characterization by coalition strategy-proofness [J].
Moulin, H .
SOCIAL CHOICE AND WELFARE, 1999, 16 (02) :279-320
[22]   Strategyproof sharing of submodular costs: budget balance versus efficiency [J].
Moulin, H ;
Shenker, S .
ECONOMIC THEORY, 2001, 18 (03) :511-533
[23]   Algorithmic mechanism design [J].
Nisan, N ;
Ronen, A .
GAMES AND ECONOMIC BEHAVIOR, 2001, 35 (1-2) :166-196
[24]  
NISAN N, 2000, P 2 ACM C EL COMM EC, P242
[25]  
Parkes DC, 2000, SEVENTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-2001) / TWELFTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE (IAAI-2000), P74
[26]  
PARKES DC, 1999, P 1 ACM C EL COMM, P148
[27]   How bad is selfish routing? [J].
Roughgarden, T ;
Tardos, É .
JOURNAL OF THE ACM, 2002, 49 (02) :236-259
[28]  
SANDHOLM TW, 1999, MULTIAGENT SYSTEMS M, P201
[29]   COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERS [J].
VICKREY, W .
JOURNAL OF FINANCE, 1961, 16 (01) :8-37
[30]  
Wellman MP, 1993, J ARTIF INTELL RES, V1, P1