Seuken, SvenParkes, David2011-06-072011Seuken, 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).http://nrs.harvard.edu/urn-3:HUL.InstRepos:4907301A common challenge in distributed work systems like P2P file-sharing communities, or ad-hoc routing networks, is to minimize the number of free-riders and incentivize contributions. Without any centralized monitoring it is difficult 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. [11], 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 significantly 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-flow algorithms in accounting mechanism design.en-USalgorithmsdesigneconomicsMonograph or Book2011-06-07