On the Sybil-Proofness of Accounting Mechanisms
MetadataShow full item record
CitationSeuken, Sven and David C. Parkes. Forthcoming. On the sybil-proofness of accounting mechanisms. Proceedings of the 2011 Workshop on the Economics of Networks, Systems, and Computation (NetEcon'11).
AbstractA common challenge in distributed work systems like P2P ﬁle-sharing communities, or ad-hoc routing networks, is to minimize the number of free-riders and incentivize contributions. Without any centralized monitoring it is diﬃcult to distinguish contributors from free-riders. One way to address this problem is via accounting mechanisms which rely on voluntary reports by individual agents and compute a score for each agent in the network. In Seuken et al. , we have recently proposed a mechanism which removes any incentive for a user to manipulate the mechanism via misreports. However, we left the existence of sybil-proof accounting mechanisms as an open question. In this paper, we settle this question, and show the striking impossibility result that under reasonable assumptions no sybil-proof accounting mechanism exists. We show, that a signiﬁcantly weaker form of K-sybil-proofness can be achieved against certain classes of sybil attacks. Finally, we explain how limited robustness to sybil manipulations can be achieved by using max-ﬂow algorithms in accounting mechanism design.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4907301
- FAS Scholarly Articles