Abstract

This thesis consists of three studies in matching theory and market design. Its main focus is to compare matching rules according to normative criteria, primarily fairness, when objects have priorities over agents.


In the first study we analyze one-to-one matching and prove that in general we cannot find a strategy-proof and Pareto-efficient mechanism which stands out uniquely in terms of fairness when using fundamental criteria for profile-by-profile comparison. In particular, despite suggestions to the contrary in the literature, the Top Trading Cycles (TTC) mechanism is not more fair than all other mechanisms in this class. We also show that while the TTC is not dominated, if the priority profile is strongly cyclic then there is not much scope for TTC to dominate other matching rules in this class.

In the second study, which focuses on many-to-on matching, I provide a direct proof that Ergin's cycle (Ergin, 2002) is stronger than Kesten's cycle (Kesten, 2006), due to different scarcity conditions for the quotas on objects. I also prove that when there is a Kesten cycle there is no strategy-proof and Pareto-efficient mechanism which uniquely stands out in terms of the fairness criteria. Moreover, I use simulations to show that as the number of Kesten cycles increases, there are more fairness violations and fewer preference profiles at which the TTC mechanism is fair.


The third study compares three competing many-to-one matching mechanisms that are strategy-proof and Pareto-efficient but not fair, namely the TTC, Equitable Top Trading Cycles (ETTC) and Clinch and Trade (CT) mechanisms. Although one would expect that ETTC and CT are more fair than the TTC, I demonstrate the opposite for specific preference profiles and compare the aggregate number of fairness violations using simulations. I find that ETTC tends to have fewer priority violations in the aggregate than the other two mechanisms across both different quota distributions and varying correlations of preferences. Finally, I show that all three mechanisms become more efficient when the commonly most preferred object has the highest quota, and demonstrate that the more unequal the quota distribution, the more fair and efficient the three mechanisms become.