Approximation and collusion in multicast cost sharing

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.