Robust Pseudo-Markets for Reusable Public Resources

We study non-monetary mechanisms for the fair and efficient allocation of reusable public resources. We consider settings where a limited resource is shared among a set of agents, each of whom may request to use the resource over multiple consecutive rounds, receiving some utility only if they get to use the resource for the full duration of their request. Such settings are of particular significance in scientific research where large-scale instruments such as electron microscopes, particle colliders, and telescopes are shared between multiple research groups; this model also subsumes and extends existing models of repeated non-monetary allocation where resources are required for a single round only. We study a simple pseudo-market mechanism where upfront we endow each agent with some budget of artificial credits, with the budget proportion reflecting the fair share of the resource we want the agent to receive. The endowments thus define for each agent her ideal utility as that which she derives from her favorite allocation with no competition, but subject to getting at most her fair share of the items across rounds. Next, on each round, and for each available item, our mechanism runs a first-price auction with a selective reserve, wherein each agent submits a desired duration and per-round-bid (which must be at least the reserve price), and the highest bidder gets to use the item for the desired duration. We consider this problem in a Bayesian setting and show that under a carefully chosen reserve price, irrespective of how others bid, each agent has a strategy that guarantees her a $1/2$ fraction of her ideal utility in expectation. We also show this result is tight, i.e., there is no mechanism that can guarantee that all agents get more than half of their ideal utility.