Cost allocation mechanisms in a peer‐to‐peer network

Abstract

This study analyzes a cooperative game between a service provider and a set of users. We consider a P2P network where the service provider broadcasts the content across the network and the users collaborate to seed the content to a subset of users in the network. The objective of the service provider is to determine the minimum cost network solution and to allocate this joint-cost fairly among the users. The minimum cost network solution can be determined by solving a minimum cost Steiner tree problem. We propose four cost allocation mechanisms: a dual linear programming based mechanism, an approximation mechanism to the Shapley value, a partition-based mechanism, and an approximation mechanism to the nucleolus. We conduct an extensive computational study to assess the performance of the proposed mechanisms on randomly generated instances. We conclude that our partition-based mechanism and the nucleolus-approximation outperform the other allocation mechanisms, including the benchmark mechanism.