Essays in Matching Theory

Citation

Doe, Peter Nathanael (2025) Essays in Matching Theory. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/r209-2787. https://resolver.caltech.edu/CaltechTHESIS:05072025-232052009

Abstract

This dissertation consists of three essays on matching theory. The first two essays examine provide new cooperative solutions for two problems arising within matching markets in practice. The third contributes a theoretical analysis of the causes and effects of a market failure within the medical residency match.

Chapter 1 analyzes a matching market in which some agents have made prior commitments to each other. Typically, matching market models ignore prior commitments. I analyze two-sided matching markets with pre-existing binding agreements between market participants. In this model, a pair of participants bound to each other by a pre-existing agreement must agree to any action they take. To analyze their behavior, I propose a new solution concept, the agreeable core, consisting of the matches which cannot be renegotiated without violating the binding agreements. My main contribution is an algorithm that constructs such a match by a novel combination of the Deferred Acceptance and Top Trading Cycles algorithms. The algorithm is robust to various manipulations and has applications to numerous markets including the resident-to-hospital match, college admissions, school choice, and labor markets.

In Chapter 2, I turn to the problem of increasing the efficiency of student assignments in school choice subject to constraints imposed by policymakers. In school choice, policymakers consolidate a district’s objectives for a school into a priority ordering over students. They then face a trade-off between respecting these priorities and assigning students to more-preferred schools. However, because priorities are the amalgamation of multiple policy goals, some may be more flexible than others. This paper introduces a model that distinguishes between two types of priority: a between-group priority that ranks groups of students and must be respected, and a within-group priority for efficiently allocating seats within each group. The solution I introduce, the unified core, integrates both types. I provide a two-stage algorithm, the DA-TTC, that implements the unified core and generalizes both the Deferred Acceptance and Top Trading Cycles algorithms. This approach provides a method for improving efficiency in school choice while honoring policymakers’ objectives.

Chapter 3 introduces a a behavioral model of early matching within the context of the National Resident Matching Program, the system by which graduating medical students are matched to hospital residency programs. In my model, two hospitals compete to match to a continuum of doctors. Each hospital can make early offers or wait until the match is produced through the matching program. Some doctors have a behavioral preference to match early while others do not. I show that the less-desirable hospital benefits from the option to make early offers. My results provide a theoretical foundation for behavior widely documented within the medical ethics and graduate medical education literature and confirm beliefs commonly held by residency program directors.

Thesis Files