Arrovian efficiency in allocation of discrete resources

Abstract

Efficiency in the Pareto sense and strategy-proofness have been the central design desiderata in market design for allocation of discrete resources, such as dorm allocation, school choice, and kidney exchange. However, more precise efficiency objectives, such as welfare maximization, have been neglected. In a setting where heterogeneous indivisible goods are being allocated without monetary transfers and each agent has a unit demand, we use Arrovian efficiency as the notion of welfare optimization and show that a mechanism is individually strategy-proof and Arrovian efficient, i.e., it always selects the best outcome with respect to some Arrovian social welfare function, if and only if the mechanism is group strategy-proof and Pareto efficient. If the Arrovian social welfare function completely ranks all matchings, then the individually strategy-proof and Arrovian-efficient mechanisms are almost sequential dictatorships.