From Monetary to Non-Monetary Mechanism Design via Artificial Currencies

Abstract

Non-monetary mechanisms for repeated allocation and decision-making are gaining widespread use in many real-world settings. Our aim in this work is to study the efficiency and incentive properties of simple mechanisms based on artificial currencies in such settings. To this end, we make three contributions:

– For a general allocation setting, we provide a black-box technique to convert any one-shot monetary mechanism to a dynamic mechanism with artificial currency that simultaneously guarantees vanishing loss in efficiency, and vanishing gains from non-truthful bidding over time.

– On a computational front, we show how such a mechanism can be implemented using only sample-access to the agents’ type distributions, and requires roughly twice the amount of computation as needed to run the monetary mechanism alone.

– For settings with two agents, we show that a particular artificial currency mechanism also results in a vanishing price of anarchy. Moreover, we leverage this result to demonstrate the existence of a Bayesian incentive-compatible mechanism with vanishing efficiency loss in this setting.

Publication
Mathematics of Operations Research

Combines results from Gorokh et al. (2017) and Gorokh et al. (2017).

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.

Related