Allocation of indivisible objects.

摘要

In this thesis, we study allocation of indivisible objects using the mechanism design approach. The class of problems we study fit in the matching literature. They can be described as one-sided matching problems without side payments.; We devote the first two chapters to the study of lotteries in object allocation problems. In Chapter 1, we introduce a lottery mechanism that is seemingly alternative to the random priority mechanism: For each object allocation problem, choose an endowment profile with uniform distribution, and select the core of the induced object exchange problem. We refer to this mechanism as the core mechanism from random endowments. The core mechanism from random endowments is equivalent to the random priority mechanism.; In Chapter 2, we address the issue of efficiency of lotteries in object allocation problems. We introduce a new concept of domination over sets of assignments. We show that this new domination concept is essential in understanding stochastic efficiency: A lottery induces a stochastically efficient random assignment if, and only if its support does not contain a dominated set of assignments.; In Chapter 3, we introduce a richer class of problems that incorporates property rights. We propose a class of mechanisms, namely the top trading cycles mechanisms. They are Pareto efficient, individually rational, and strategy-proof. They can also accommodate any hierarchy of seniorities. Given a hierarchy of seniorities, the induced top trading cycles mechanism respects the hierarchy more than any other mechanism that is Pareto efficient, individually rational and strategy-proof does.; In Chapter 4, we study a central issue in public school choice: The design of a student assignment mechanism. We propose a model of it. This new model can be interpreted as a class of object allocation problems without property rights, and each object having its priority ordering of students. We propose a simple mechanism that responds to priority requirements. It generalizes the top trading cycles mechanism of Chapter 3. It is Pareto efficient and strategy-proof. It can be easily modified to respect racial and ethnic balance constraints.