An Incentive Mechanism for Message Relaying in Unstructured Peer to peer Systems

May 2007

An Incentive Mechanism for Message Relaying in Unstructured Peer to peer Systems

Authors:

C. Li, B. Yu, and Katia Sycara

Abstract:

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 either create huge burden on communications or cause long response time. Moreover, these systems are also 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. 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.
@conference{Li-2007-9742,
author = {C. Li And B. Yu And Katia Sycara},
title = {An Incentive Mechanism for Message Relaying in Unstructured Peer to peer Systems},
booktitle = {Proceedings of 6th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '07)},
year = {2007},
month = {May},
pages = {259 - 266},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.