Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Optimizing scrip systems: crashes, altruists, hoarders, sybils and collusion

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

Scrip, or artificial currency, is a useful tool for designing systems that are robust to selfish behavior by users. However, it also introduces problems for a system designer, such as how the amount of money in the system should be set. In this paper, the effect of varying the total amount of money in a scrip system on efficiency (i.e., social welfare—the total utility of all the agents in the system) 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. This ratio can be found by increasing the money supply to just below the point that the system would experience a “monetary crash,” where money is sufficiently devalued that no agent is willing to perform a service. The implications of the presence of altruists, hoarders, sybils, and collusion on the performance of the system are examined. Approaches are discussed to identify the strategies and types of agents.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In: 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–62 (2006)

  2. Adar, E., Huberman, B.A.: Free riding on Gnutella. First Monday 5(10) (2000)

  3. Aperjis, C., Freedman, M.J., Johari, R.: Peer-assisted content distribution with prices. In: 2008 ACM Conference on Emerging Network Experiment and Technology (CoNEXT 2008), 17:1–17:12 (2008)

  4. Aumann, R.J.: Acceptable points in general cooperative n-person games. In: Tucker, A., Luce, R. (eds.) Contributions to the Theory of Games IV, Annals of Mathematical Studies, vol. 40. Princeton University Press, Princeton, N.J., pp. 287–324 (1959)

  5. Brunelle, J., Hurst, P., Huth, J., Kang, L., Ng, C., Parkes, D., Seltzer, M., Shank, J., Youssef, S.: Egg: an extensible and economics-inspired open grid computing platform. In: Third Workshop on Grid Economics and Business Models (GECON), pp. 140–150 (2006)

  6. Cover T., Thomas J.: Elements of Information Theory. Wiley, New York (1991)

    Book  MATH  Google Scholar 

  7. Douceur, J.R.: The sybil attack. In: First International Workshop on Peer-to-Peer Systems (IPTPS), pp. 251–260 (2002)

  8. Friedman E.J., Resnick P.: The social cost of cheap pseudonyms. J. Econ. Manag. Strateg. 10(2), 173–199 (2001)

    Article  Google Scholar 

  9. Friedman, E.J., Halpern, J.Y., Kash, I.A.: Efficiency and Nash equilibria in a scrip system for P2P networks. In: Seventh ACM Conference on Electronic Commerce (EC 2006), pp. 140–149 (2006)

  10. Fudenberg D., Tirole J.: Game Theory. MIT Press, Cambridge, MA (1991)

    Google Scholar 

  11. Gupta, M., Judge, P., Ammar, M.H.: A reputation system for peer-to-peer networks. In: Network and Operating System Support for Digital Audio and Video (NOSSDAV), pp. 144–152 (2003)

  12. Hauert C., Traulsen A., Brandt H., Nowak M.A., Sigmund K.: Via freedom to coercion: the emergence of costly punishment. Science 316, 1905–1907 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hayrapetyan, A., Tardos, É., Wexler, T.: The effect of collusion in congestion games. In: 38th Annual ACM Symposium on Theory of Computing, pp. 89–98 (2006)

  14. Hughes, D., Coulson, G., Walkerdine, J.: Free riding on Gnutella revisited: the bell tolls? IEEE Distrib. Syst. Online 6(6) (2005)

  15. Ioannidis, J., Ioannidis, S., Keromytis, A.D., Prevelakis, V.: Fileteller: paying and getting paid for file storage. In: Financial Cryptography, pp. 282–299 (2002)

  16. Kash, I.A., Friedman, E.J., Halpern, J.Y.: Optimizing scrip systems: efficiency, crashes, hoarders and altruists. In: Eighth ACM Conference on Electronic Commerce (EC 2007), pp. 305–315 (2007)

  17. Kash, I.A., Friedman, E.J., Halpern, J.Y.: Manipulating scrip systems: sybils and collusion. In: First Conference on Auctions, Market Mechanisms and Their Applications (AMMA) (2009)

  18. Kash, I.A., Friedman, E.J., Halpern, J.Y.: An equilibrium analysis of scrip systems, arxiv:1204.2942 (2012)

  19. Krugman P.: The Accidental Theorist. Norton, NY (1999)

    Google Scholar 

  20. Mas-Colell A., Whinston M.D., Green J.R.: Microeconomic Theory. Oxford University Press, Oxford, U.K. (1995)

    Google Scholar 

  21. Miller, M.S., Drexler, K.E.: Markets and computation: agoric open systems. In: Huberman, B. (ed.) The Ecology of Computation. Elsevier, Amsterdam, pp. 133–175 (1988)

  22. Peterson, R.S., Sirer, E.G.: Antfarm: efficient content distribution with managed swarms. In: Networked Systems Design and Implementation (NSDI) (2009)

  23. Puterman M.L.: Markov Decision Processes. Wiley, New York (1994)

    Book  MATH  Google Scholar 

  24. Reeves, D.M., Soule, B.M., Kasturi, T.: Group decision making with Yootles. http://ai.eecs.umich.edu/people/dreeves/yootles/yootles.pdf (2007)

  25. Sirivianos, M., Park, J.H., Chen, R., Yang, X.: Free-riding in bittorrent networks with the large view exploit. In: Sixth International Workshop on Peer-to-Peer Systems (IPTPS) (2007)

  26. Stonebraker M., Aoki P.M., Litwin W., Pfeffer A., Sah A., Sidell J., Stelin C., Yu A.: Mariposa: a wide-area distributed database system. VLDB J. 5(1), 48–63 (1996)

    Article  Google Scholar 

  27. Sweeney J., Sweeney R.J.: Monetary theory and the great capitol hill babysitting co-op crisis: comment. J. Money Credit Bank. 9(1), 86–89 (1977)

    Article  Google Scholar 

  28. Vishnumurthy, V., Chandrakumar, S., Sirer, E.G.:KARMA: a secure economic framework for peer-to-peer resource sharing. In: First Workshop on Economics of Peer-to-Peer Systems (P2PECON) (2003)

  29. Walsh, K., Sirer, E.G.: Experience with an object reputation system for peer-to-peer filesharing. In: Third Symposium on Network Systems Design & Implementation (NSDI), pp. 1–14 (2006)

  30. Yokoo M., Sakurai Y., Matsubara S.: The effect of false-name bids in combinatorial auctions: new fraud in internet auctions. Games Econ. Behav. 46(1), 174–188 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  31. Zhao, S., Lo, V.M., Dickey, C.G.: Result verification and trust-based scheduling in peer-to-peer grids. In: Fifth IEEE International Conference on Peer-to-Peer Computing (P2P 2005), pp. 31–38 (2005)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ian A. Kash.

Additional information

Portion of the material in this paper appeared in preliminary form in papers in the Proceedings of the 7th and 8th ACM Conferences on Electronic Commerce [9, 16] and the Proceedings of the First Conference on Auctions, Market Mechanisms and Their Applications [17]. Section 2 and Appendix [A] are reproduced from a companion paper [18]to make this paper self-contained. Much of the work was performed while Ian Kash and Eric Friedman were at Cornell University.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kash, I.A., Friedman, E.J. & Halpern, J.Y. Optimizing scrip systems: crashes, altruists, hoarders, sybils and collusion. Distrib. Comput. 25, 335–357 (2012). https://doi.org/10.1007/s00446-012-0170-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-012-0170-z

Keywords

Navigation