UC Berkeley

This dissertation studies the problem of allocating heterogeneous indivisible goods to agents without the use of monetary compensation when each agent receives at most one good. The three central concerns in designing allocation mechanisms are incentives of the agents, efficiency, and fairness. There are inherent trade-offs between competing notions of the three desiderata in such assignment mechanisms. This dissertation further explores these tradeoffs and constructs novel mechanisms for such settings.

Chapter 2 focuses on random assignment mechanisms for the canonical house allocation problem. It shows that any strategy-proof and envy-free mechanism must sacrifice efficiency in a very weak form captured by the notion of contention-free efficiency. The chapter also characterizes a large family of strategy-proof and envy-free mechanisms called Rank Exchange Mechanisms thereby showing the existence of mechanisms apart from the equal division mechanism that satisfy these two properties.

Chapter 3 studies the allocation problem in the presence of arbitrary linear constraints when agents exhibit indifferences in their preferences. It proposes the Constrained Serial Rule, a mechanism that is a generalization of the well-known Probabilistic Serial mechanism, and shows that this mechanism satisfies constrained ordinal efficiency and envy-freeness among agents of the same type.

Chapter 4 introduces Generalized Hierarchical Exchange mechanisms and shows that they satisfy strategy-proofness, Pareto efficiency, and admit many bossy mechanisms. Using this generalization, the chapter proposes novel mechanisms called priority trading mechanisms. Finally, it also provides a characterization of an important sub-class of Generalized Hierarchical Exchange mechanisms.