Collaboration of untrusting peers with changing interests

ABSTRACT

Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by disreputable peers defrauding others. In a reputation system, participant spost information about every transaction,and routinely check the posted information before taking any action to avoid other participants with a bad history.In this paper, we introduce a framework for optimizing reputation systems for objects.We study reputation systems in an asynchronous setting, and in the context of restricted access to the objects. Specifically, we study the cases where access may be restricted in time (objects arrive and depart from system) and inspace (each peer has access to only a subset of the objects).

REFERENCES

• 1: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 3: Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509922]
• 4: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 5: David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
• 6: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 7: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 8: Jon Kleinberg , Mark Sandler, Convergent algorithms for collaborative filtering, Proceedings of the 4th ACM conference on Electronic commerce, p.1-10, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779929]
• 9: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
• 10: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 11: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 12: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 13: A. C. Yao. Probabilistic computations: toward a unified measure of complexity. In Proc. 17th IEEE Symp. on Foundations of Computer Science (FOCS), pages 222--227, 1977.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services; Commercial services

General Terms:
Algorithms, Reliability, Theory

Keywords:
electronic commerce, peer-to-peer systems, reputation systems