Faithful Distributed Shapley Mechanisms for Sharing the Cost of Multicast Transmissions

Sharing the cost of multicast transmissions was studied in the past and two mechanisms, Marginal Cost and Shapley Value, were proposed. Compared to the Marginal Cost Mechanism the Shapley Value mechanism has the advantage of being budget balanced. Although both of them are strategyproof mechanisms, the distributed protocols implementing them are susceptible to manipulation by autonomous nodes. We propose two protocols that implement the Shapley Value mechanism in which the nodes do not have incentives to deviate from the protocol specifications. We show that the proposed protocols are faithful implementations of the Shapley Value mechanism. We deploy these protocols on PlanetLab and analyze their performance.