Strategyproof Allocation of a Single Object

Abstract

The problem of allocating a single indivisible object to one of several selfish agents is considered, where monetary payments are not allowed, and the object is not necessarily desirable to each agent. It is shown that ordinality and positive responsiveness together are necessary and sufficient conditions for strategyproofness, which implies that efficient social choice functions are not strategyproof. However, any Pareto-optimal, ordinal social choice function is strategyproof. A Gibbard-Satterthwaite-type impossibility result is established for nonbossy mechanisms. Thus, the best the planner can do without monetary transfers is to give the object to an agent who desires it, but whose valuation of the object may not be the highest among the agents, using a mechanism that is either dictatorial or bossy. It is also shown that all strategyproof, nonbossy, and Pareto-optimal social choice functions are serial dictatorships.