Strategyproof Assignment by Hierarchical Exchange

Abstract

We give a characterization of the set of group-strategyproof, Pareto-optimal, and reallocation-proof allocation rules for the assignment problem, where individuals are assigned at most one indivisible object, without any medium of exchange. Although there are no property rights in the model, the rules satisfying the above criteria imitate a trading procedure with individual endowments, in which individuals exchange objects from their hierarchically determined endowment sets in an iterative manner. In particular, these assignment rules generalize Gale's top trading cycle procedure, the classical rule for the model in which each individual owns an indivisible good.