An incentive mechanism for message relaying in unstructured peer-to-peer systems

Distributed message relaying is an important function of a peer-to-peer system to discover service providers. Existing search protocols in unstructured peer-to-peer systems create huge burden on communications, cause long response time, or result in unreliable performance. Moreover, with self-interested peers, these systems are vulnerable to the free-riding problem. In this paper we present an incentive mechanism that not only mitigates the free-riding problem, but also achieves good system efficiency in message relaying for peer discovery. In this mechanism promised rewards are passed along the message propagation process. A peer is rewarded if a service provider is found via a relaying path that includes this peer. The mechanism allows peers to rationally trade-off communication efficiency and reliability while maintaining information locality. We provide some analytic insights to the symmetric Nash equilibrium strategies of this game, and an approximate approach to calculate this equilibrium. Experiments show that this incentive mechanism brings a system utility generally higher than breadth-first search and random walks, based on both the estimated utility from our approximate equilibrium and the utility generated from learning in the incentive mechanism.