Robustness and Optimization of Scrip Systems


January 11, 2013


Scrip systems, where users pay for service with an artificial currency (scrip) created for the system, are an attractive solution to a variety of problems faced by P2P and distributed systems. Despite the interest in building scrip systems, relatively little work has been done to help answer basic design questions. For example, how much money should there be in the system? What will happen if some of the users start hoarding money? I present a game-theoretic model of a scrip system and show that this model has Nash equilibria where all agents use simple strategies known as threshold strategies. In fact, the same techniques provide an efficient method of computing these equilibria as well as the equilibrium distribution of wealth. I show how these results provide practical insights into the design of scrip systems. For example, social welfare is maximized by increasing the money supply up to the point that the system experiences a “monetary crash,” where money is sufficiently devalued that no agent is willing to perform a service. Hoarders generally decrease social welfare but, surprisingly, they also promote system stability by helping prevent monetary crashes. Furthermore, the effects of hoarders can be mitigated simply by printing more money.

This represents joint work with Ian Kash and Eric Friedman.


Joe Halpern

Joseph Yehuda Halpern is a professor of computer science at Cornell University. Most of his research is on reasoning about knowledge and uncertainty. Halpern graduated in 1975 from University of Toronto with a B.S. in mathematics. He went on to earn a Ph.D. in mathematics from Harvard University in 1981 under the supervision of Albert R. Meyer and Gerald Sacks. He has written two books, Reasoning about Uncertainty and Reasoning About Knowledge and is a winner of the 1997 Gödel Prize in theoretical computer science and the 2009 Dijkstra Prize in distributed computing. In 2002 he was inducted as a Fellow of the Association for Computing Machinery and in 2012 he was selected as an IEEE Fellow. Halpern is also the administrator for the Computing Research Repository, the computer science branch of, and the moderator for the “general literature” and “other” subsections of the repository. His students include Nir Friedman, Daphne Koller, and Yoram Moses.