Efficiency and nash equilibria in a scrip system for P2P networks

ABSTRACT

A model of providing service in a P2P network is analyzed. It is shown that by adding a scrip system, a mechanism that admits a reasonable Nash equilibrium that reduces free riding can be obtained. The effect of varying the total amount of money (scrip) in the system on efficiency (i.e., social welfare) is analyzed, and it is shown that by maintaining the appropriate ratio between the total amount of money and the number of agents, efficiency is maximized. The work has implications for many online systems, not only P2P networks but also a wide variety of online forums for which scrip systems are popular, but formal analyses have been lacking.

REFERENCES

• 1: E. Adar and B. A. Huberman. Free riding on Gnutella. First Monday, 5(10), 2000.
• 2: Kostas G. Anagnostakis , Michael B. Greenwald, Exchange-Based Incentive Mechanisms for Peer-to-Peer File Sharing, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.524-533, March 24-26, 2004
• 3: BitTorrent Inc. BitTorrent web site. http://www.bittorent.com.
• 4: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceeding 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: Cornell Information Technologies. Cornell's ccommodity internet usage statistics. http://www.cit.cornell.edu/computer/students/ bandwidth/charts.html.
• 6: 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
• 7: G. Ellison. Cooperation in the prisoner's dilemma with anonymous random matching. Review of Economic Studies, 61:567--588, 1994.
• 8: eMule Project. eMule web site. http://www.emule-project.net/.
• 9: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 10: Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779978]
• 11: E. J. Friedman and P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173--199, 2001.
• 12: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 13: Minaxi Gupta , Paul Judge , Mostafa Ammar, A reputation system for peer-to-peer networks, Proceedings of the 13th international workshop on Network and operating systems support for digital audio and video, June 01-03, 2003, Monterey, CA, USA [doi>10.1145/776322.776346]
• 14: Z. Gyongi, P. Berkhin, H. Garcia-Molina, and J. Pedersen. Link spam detection based on mass estimation. Technical report, Stanford University, 2005.
• 15: J. Ioannidis, S. Ioannidis, A. D. Keromytis, and V. Prevelakis. Fileteller: Paying and getting paid for file storage. In Financial Cryptography, pages 282--299, 2002.
• 16: E. T. Jaynes. Where do we stand on maximum entropy? In R. D. Levine and M. Tribus, editors, The Maximum Entropy Formalism, pages 15--118. MIT Press, Cambridge, Mass., 1978.
• 17: 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]
• 18: M. Kandori. Social norms and community enforcement. Review of Economic Studies, 59:63--80, 1992.
• 19: LogiSense Corporation. LogiSense web site. http://www.logisense.com/tm p2p.html.
• 20: László Lovász , Peter Winkler, Mixing of random walks and other diffusions on a graph, Surveys in combinatorics, 1995, Cambridge University Press, New York, NY, 1995
• 21: Open Source Technology Group. Slashdot FAQ - comments and moderation. http://slashdot.org/faq/com-mod.shtml#cm700.
• 22: OSMB LLC. Gnutella web site. http://www.gnutella.com/.
• 23: M. L. Puterman. Markov Decision Processes. Wiley, 1994.
• 24: SETI@home. SETI@home web page. http://setiathome.ssl.berkeley.edu/.
• 25: Sharman Networks Ltd. Kazaa web site. http://www.kazaa.com/.
• 26: V. Vishnumurthy, S. Chandrakumar, and E. Sirer. Karma: A secure economic framework for peer-to-peer resource sharing. In Workshop on Economics of Peer-to-Peer Systems (P2PECON), 2003.
• 27: L. Xiong and L. Liu. Building trust in decentralized peer-to-peer electronic communities. In Internation Conference on Electronic Commerce Research (ICECR), 2002.
• 28: H. Zhang, A. Goel, R. Govindan, K. Mason, and B. V. Roy. Making eigenvector-based reputation systems robust to collusion. In Workshop on Algorithms and Models for the Web-Graph(WAW), pages 92--104, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Economics, Theory

Keywords:
P2P networks, game theory, scrip systems