UC Berkeley

Within economic theory, the study of matching generally focuses on the problem of allocating heterogeneous, indivisible resources to agents, often without the use of prices. In this dissertation I focus on one-sided matching problems, in which a set of agents have preferences over a set of objects which are to be potentially allocated.In Chapter 1, coauthored with Andrew Tai, we study the classic house swapping problem of Shapley and Scarf (1974) but relax the usual assumption that agents have strict preferences over the objects. Top trading cycles with fixed tie-breaking (TTC) has been suggested to deal with indifferences in these kinds of object allocation problems. Unfortunately, under general indifferences, TTC is neither Pareto efficient nor group strategy proof. Furthermore, it may not select an allocation in the core of the market, even when the core is nonempty. However, when indifferences are agreed upon by all agents (“objective indifferences”), TTC maintains Pareto efficiency, group strategyproofness, and core selection. Further, we characterize objective indifferences as the most general setting where TTC maintains these properties.In Chapter 2, coauthored with Andrew Tai, we investigate object assignment problems in which objects may have minimum and maximum requirements. We describe a new random assignment mechanism, the minimums probabilistic serial (MPS) mechanism, which generalizes the probabilistic serial mechanism of Bogomolnaia and Moulin (2001) to this more general setting. The random allocation produced by MPS is guaranteed to be Pareto efficient; that is, there is no other implementable allocation that all agents prefer via first order stochastic dominance. We also show that MPS is i) envy free, in that no agent will strictly prefer another agent's assignment, and ii) weak strategy proof, in that agents cannot achieve a better assignment by misreporting their preferences.In Chapter 3, coauthored with Andrew Tai, we note that the proof of Bird (1984), the first to show group strategyproofness of top trading cycles (TTC), requires a correction. We provide a counterexample to a critical claim, and a corrected proof in the spirit of the original.