Faking the Market: Efficient Allocation via Artificial Currencies
In some resource allocation problems it is infeasible to use monetary payments to incentivize strategic participants to reveal their preferences honestly, e.g. allocating cluster time to employees, course seats to students, food to foodbanks. Many such problems posses a special structure: the allocation is repeated through time and the preferences of participants are stochastic. Recent work has demonstrated that such structure allows implementing approximately efficient allocations without resorting to payments. We consider a particular class of solutions - endowing participants with artificial currency and asking them to bid with it just as they would with money. This approach is sometimes adopted in practice, but little is known about the incentives it creates. Via a series of results we show how such mechanisms can perform well in spite of their simplicity: (i) For a general class of allocation problems, we construct a blackbox reduction that takes a one-shot monetary mechanism and converts it into a repeated artificial currency mechanism that approximately preserves efficiency and incentive compatibility. (ii) Restricting attention to repeated allocation of a single item, we establish a price of anarchy result for a simple (and hence more practical) artificial currency mechanism.
Anyone who would like to give one of the weekly seminars on the RTDM program can fill in the survey at https://goo.gl/forms/Li5jQ0jm01DeYZVC3.