Designing and Optimizing Matching Markets

Matching market design studies the fundamental problem of how to allocate scarce resources to individuals with varied needs. In recent years, the theoretical study of matching markets such as medical residency, public housing and school choice has greatly informed and improved the design of such markets in practice. Impactful work in matching market design frequently makes use of techniques from computer science, economics and operations research to provide end–to-end solutions that address design questions holistically. In this dissertation, I develop tools for optimization in market design by studying matching mechanisms for school choice, an important societal problem that exemplifies many of the challenges in effective marketplace design. In the first part of this work I develop frameworks for optimization in school choice that allow us to address operational problems in the assignment process. In the school choice market, where scarce public school seats are assigned to students, a key operational issue is how to reassign seats that are vacated after an initial round of centralized assignment. We propose a class of reassignment mechanisms, the Permuted Lottery Deferred Acceptance (PLDA) mechanisms, which generalize the commonly used Deferred Acceptance school choice mechanism and retain its desirable incentive and efficiency properties. We find that under natural conditions on demand all PLDA mechanisms achieve equivalent allocative welfare, and the PLDA based on reversing the tie-breaking lottery during the reassignment round minimizes reassignment. Empirical investigations on data from NYC high school admissions support our theoretical findings. In this part, we also provide a framework for optimization when using the prominent Top Trading Cycles (TTC) mechanism. We show that the TTC assignment can be described by admission cutoffs, which explain the role of priorities in determining the TTC assignment and can be used to tractably analyze TTC. In a large-scale continuum model we show how to compute these cutoffs directly from the distribution of preferences and priorities, providing a framework for evaluating policy choices. As an application of the model we solve for optimal investment in school quality under choice and find that an egalitarian distribution can be more efficient as it allows students to choose schools based on idiosyncracies in their preferences. In the second part of this work, I consider the role of a marketplace as an information provider and explore how mechanisms affect information acquisition by agents in matching markets. I provide a tractable “Pandora's box” model where students hold a prior over their value for each school and can pay an inspection cost to learn their realized value. The model captures how students’ decisions to acquire information depend on priors and market information, and can rationalize a student’s choice to remain partially uninformed. In such a model students need market information in order to optimally acquire their personal preferences, and students benefit from waiting for the market to resolve before acquiring information. We extend the definition of stability to this partial information setting and define regret-free stable outcomes, where the matching is stable and each student has acquired the same information as if they had waited for the market to resolve. We show that regret-free stable outcomes have a cutoff characterization, and the set of regret-free stable outcomes is a non-empty lattice. However, there is no mechanism that always produces a regret-free stable matching, as there can be information deadlocks where every student finds it suboptimal to be the first to acquire information. In settings with sufficient information about the distribution of preferences, we provide mechanisms that exploit the cutoff structure to break the deadlock and approximately implement a regret-free stable matching