13 January 2011, Computational Social Choice Seminar, Joe Halpern

Abstract

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.

While scrip systems have many attractive features for a system designer, for a user they add complexity. As a user, I don't want to think about how much of my resources I should contribute or how much money I need to save. I just want service delivered when I want it, with a minimum of inconvenience the rest of the time. However, optimal behavior depends not only on my preference but on the behavior of everyone else in the system. Furthermore, this behavior cannot be directly observed. Despite this, I will show that a simple algorithm allows the system to quickly converge to optimal behavior.

This represents joint work with Ian Kash and Eric Friedman.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).