Robust content-driven reputation

ABSTRACT

In content-driven reputation systems for collaborative content, users gain or lose reputation according to how their contributions fare: authors of long-lived contributions gain reputation, while authors of reverted contributions lose reputation. Existing content-driven systems are prone to Sybil attacks, in which multiple identities, controlled by the same person, perform coordinated actions to increase their reputation. We show that content-driven reputation systems can be made resistant to such attacks by taking advantage of the fact that the reputation increments and decrements depend on content modifications, which are visible to all. We present an algorithm for content-driven reputation that prevents a set of identities from increasing their maximum reputation without doing any useful work. Here, work is considered useful if it causes content to evolve in a direction that is consistent with the actions of high-reputation users. We argue that the content modifications that require no effort, such as the insertion or deletion of arbitrary text, are invariably non-useful. We prove a truthfullness result for the resulting system, stating that users who wish to perform a contribution do not gain by employing complex contribution schemes, compared to simply performing the contribution at once. In particular, splitting the contribution in multiple portions, or employing the coordinated actions of multiple identities, do not yield additional reputation. Taken together, these results indicate that content-driven systems can be made robust with respect to Sybil attacks.

REFERENCES

• 1: B.T. Adler, J. Benterou, K. Chatterjee, L. de Alfaro, I. Pye, and V. Raman. Assigning trust to Wikipedia content. Technical Report UCSC-CRL-07-09, School of Engineering, University of California, Santa Cruz, CA, USA, 2007.
• 2: B. Thomas Adler , Luca de Alfaro, A content-driven reputation system for the wikipedia, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242608]
• 3: Wikipedia article:. Flagged revisions / Sighted versions, 2008.
• 4: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080202]
• 5: E.H. Clarke. Multipart pricing of public goods. Public Choice, 8:17--33, 1971.
• 6: Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007 [doi>10.1145/1186810.1186812]
• 7: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 8: T. Groves. Incentive in teams. Econometrica, 41(4):617--631, 1973.
• 9: K. Hoffman, D. Zage, and C. Nita--Rotaru. A survey of attack and defense techniques for reputation systems. Technical Report CSD TR #07-013, Purdue University, 2007.
• 10: Aniket Kittur , Bongwon Suh , Bryan A. Pendleton , Ed H. Chi, He says, she says: conflict and coordination in Wikipedia, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240698]
• 11: B.N. Levine, C. Shields, and N.B. Margolin. A survey of solutions to the sybil attack. Technical Report Technical Report 2006--052, Univ. of Massachussets Amherst, 2006.
• 12: M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 13: Reid Priedhorsky , Jilin Chen , Shyong (Tony) K. Lam , Katherine Panciera , Loren Terveen , John Riedl, Creating, destroying, and restoring value in wikipedia, Proceedings of the 2007 international ACM conference on Supporting group work, November 04-07, 2007, Sanibel Island, Florida, USA [doi>10.1145/1316624.1316663]
• 14: J.--M. Seigneur, A. Gray, and C.D. Jensen. Trust transfer: Encouraging self-recommendations without sybil attack. In Trust Management, volume 3477 of Lect. Notes in Comp. Sci. Springer-Verlag, 2005.
• 15: Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]
• 16: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 17: Fernanda B. Viégas , Martin Wattenberg , Kushal Dave, Studying cooperation and conflict between authors with history flow visualizations, Proceedings of the SIGCHI conference on Human factors in computing systems, p.575-582, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985765]
• 18: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Computer-supported cooperative work

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Web-based interaction

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.3 Organizational Impacts
          Subjects: Computer-supported collaborative work

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
reputation, user-generated content, wikipedia