Randomized strategyproof mechanisms with best of both worlds fairness and efficiency

Abstract

We study the problem of mechanism design for allocating a set of indivisible items among agents with private preferences on items. We aim to design a mechanism that is strategyproof (in which agents find it optimal to report their true preferences) and ensures a certain level of fairness and efficiency. We first establish that no deterministic mechanism can simultaneously be strategyproof, fair, and efficient for the allocation of indivisible chores. We then introduce randomness to address this impossibility. For allocating indivisible chores, we propose randomized mechanisms that are strategyproof in expectation as well as ex-ante and ex-post (best of both worlds) fair and efficient. For allocating mixed items—where an item may be a good (positive utility) for one agent and a chore (negative utility) for another, we propose randomized mechanisms that are strategyproof in expectation while ensuring fairness and efficiency for two-agent scenarios.