Scrip Economies Are Fair and (Approximately) Efficient

Abstract

In many settings, resources are allocated among agents repeatedly over time without the use of monetary transfers: consider, for example, allocating server-time to company employees, rooms to students, or food among food banks. Here, the central challenge is to allocate resources efficiently despite the absence of payments. In this work we investigate scrip mechanisms, which endow agents with a budget of artificial credits (scrip), and allocate resources via an auction with payments in scrip. Owing to their simplicity, such mechanisms have been gaining in popularity, with several recent successful implementations, most notably, by Feeding America for US food banks. Our goal in this paper is to understand the incentive and efficiency properties of these mechanisms.

Our main contribution in this work is to show that such simple mechanisms enjoy strong performance guarantees under minimal rationality assumptions. Formally, we consider a dynamic allocation setting, where multiple items are available in each period, and each agent’s preference is a fractionally subadditive (XOS) valuation function, drawn independently from some underlying distributions. Agents start with some initial endowment of scrips, and in each round, participate in simultaneous first-price auctions for each item. We benchmark the performance this mechanism against widely-adopted solution concepts from the literature on bargaining. In particular, we show that irrespective of the strategies of other agents, each agent can obtain a 12 − o(1) approximation of their ideal utility, i.e., the utility they derive from their favorite allocation subject to giving other agents their share (proportional to initial endowments) of the items. We do this by providing a lower-bound on the maximum value of each agent in the mechanism.

Our results provide strong argument for a wider adoption of artificial currency mechanisms in several ways. First, our guarantees have frugal strategic and informational requirements – agents do not need to know the preferences or strategies of other participants in order to secure a half of their ideal utility. Second, the performance guarantees are independent of the cardinality of the type-space, and agnostic of the underlying type distributions. Finally, our results also yield operational insights into how the principal can choose the appropriate scrip endowments as to target a particular ideal utility profile.

Publication
Preprint SSRN_id:3411444
Siddhartha Banerjee
Siddhartha Banerjee
Assistant Professor

Sid Banerjee is an assistant professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making, market design, and algorithms for large-scale networks.