Approximation and collusion in multicast cost sharing
成果类型：
Article; Proceedings Paper
署名作者：
Archer, A; Feigenbaum, J; Krishnamurthy, A; Sami, R; Shenker, S
署名单位：
Yale University; Cornell University
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/S0899-8256(03)00176-3
发表日期：
2004
页码：
36-71
关键词：
摘要：
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.
来源URL：