Essays on Matching Theory

Citation

Zhang, Jun (2017) Essays on Matching Theory. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9S75DCJ. https://resolver.caltech.edu/CaltechTHESIS:05192017-101424341

Abstract

Matching theory is a rapidly growing field in economics that often deals with markets in which monetary transfers are forbidden. Hence, policy makers often use centralized procedures to organize markets and coordinate players' behavior. Three concerns play central roles in designing the procedures: efficiency, fairness, and incentive compatibility. These concerns are also what I focus on in my studies. Specifically, my dissertation consists of three original studies on the allocation of indivisible resources to agents. The first chapter studies school choice, which is a centralized market to assign students to public schools. I compare popular matching mechanisms used in school choice by accommodating the fact that students and their parents often have heterogeneous sophistication in understanding the mechanisms. In the second chapter I study abstract object allocation problem in which objects do not have priority rankings of agents. I want to show that the three objectives of efficiency, fairness, and incentive compatibility can be incompatible with each other: a mechanism that satisfies a minimal efficiency requirement and mild fairness requirements must be manipulable by some group of agents in a strong sense. Since the efficiency requirement is weak enough such that policy makers are likely to pursue, my results suggest that policy makers have to make a choice between fairness and group incentive compatibility. In the third chapter I study same object allocation problems except that some agents have private endowments. I propose a new mechanism that has desirable properties in efficiency, fairness, and incentive compatibility. In the following I provide more details of each chapter.

School choice is a trend in the K-12 public education of US and many other countries that allows children to choose schools across neighborhoods. In Chapter 1, "Level-k Reasoning in School Choice", I compare two matching algorithms that many cities use to assign children to public schools in school choice. The algorithms are called Boston Mechanism and Deferred Acceptance. BM is manipulable, while DA is strategy-proof. Recently several cities decide to switch from BM to DA to avoid manipulation. However, the effect of the switch has not been well understood. In this paper I use the level-k model to study the strategies used by parents in BM by taking account of the fact that parents often have different abilities to manipulate BM, which are due to their heterogeneous sophistication. Interestingly, I find that the level-k reasoning process in BM is analogous to the procedure of DA. This analogy provides a new way to understand how parents may behave in BM. Under some mild assumption it implies that for any school choice problem and any sophistication distribution of parents, the assignment found by BM is never less efficient than the assignment found by DA. I also examine how parents' beliefs about others' sophistication affect their welfare. I find that, in general, a child is guaranteed to benefit from his parent's sophistication in BM only when his parent's level is high relative to others and his parent's belief about others' sophistication levels is accurate. The simulation results of my model exhibit patterns similar to empirical datasets.

Without monetary transfers, the concern of fairness motivates policy makers to use random assignments in objection allocation problems. In Chapter 2, "Efficient and Fair Assignment Mechanism is Strongly Group Manipulable", I study group incentive compatibility in random assignment mechanisms. I show that if a mechanism satisfies the minimal efficiency requirement (ex-post efficiency), then it cannot satisfy some mild fairness requirements and be minimally group incentive compatible simultaneously: by misreporting preferences, a group of agents can obtain lotteries that strictly first-order stochastically dominate the lotteries they obtain in the truth-telling case. Hence, fairness concerns may force policy maker to give up group incentive compatibility. My results hold as long as there are at least three agents and at least three objects, no matter outside option is available or not. Possibility results exist when there are only two objects and outside option is not available.

In some object allocation problems, some players have private endowments and are willing to bring them to the market in exchange for better ones. In Chapter 3, "A New Solution to the Random Assignment Problem with Private Endowment", I propose a new mechanism to solve the problems. Intuitively, in my mechanism the popularity of a private endowment plays the role of "price" in determining his owner's advantage in the market. Formally, the mechanism is a simultaneous eating algorithm, which generalizes Probabilistic Serial, by letting agents obtain additional eating speeds if their private endowments are consumed by others, and letting multiple agents trade their private endowments if they form cycles. This feature can be summarized by the idea of "you request my house - I get your speed". Indifferent preferences often cause difficulty in efficient random assignment mechanisms. Interestingly, I show that the same idea can also be used to deal with indifferent preferences in a straightforward way. It is in contrast to the mainstream method of iteratively solving maximum network flow problems in the literature.

Thesis Files