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.
Combines results from Gorokh et al. (2017) and Gorokh et al. (2017).
Siddhartha Banerjee
Associate Professor
Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making and stochastic control, economics and computation, and large-scale network algorithms.