I completed my PhD
Today I defended my PhD thesis, titled “Tradeoffs between Information, Tractability, and Fairness in Large Matching Markets”. I have reproduced the abstract below. You can find the complete thesis here.
Tradeoffs between Information, Tractability, and Fairness in Large Matching Markets
Matching theory is one of the cornerstones of modern algorithmic market design, and is therefore heavily studied by communities in operations research, economics, and theoretical computer science. Such models arise whenever a central planner is tasked with pairing together agents of two distinct types but cannot use money to clear the market; and where each agent has idiosyncratic preferences over the agents of the other type. Natural applications of matching markets are found in the allocation of indivisible goods such as school assignment, medical residency matching, and the allocation of government subsidized housing.
Matching theory and in particular stable matching has seen significant research effort since seminal work by Gale and Shapley algorithmically established the existence of a condition called stability, which guarantees that a matching can be found with the property that no participant is incentivized to deviate from it. Many centralized mechanisms for two-sided matching markets have since been shown to enjoy strong theoretical properties, which ipso facto, justifies their use in the real world.
However, due to practical constraints—commonly due to the size and complexity of the market at hand—real world applications often resort to simplified models that do not faithfully capture reality. These simplifications lead to the central planner operating without perfect information about the participants or their preferences.
In this thesis, we present three interconnected branches of research exploring tradeoffs between information, tractability, and fairness in large matching markets. We investigate how various limitations on information acquisition and exchange affect the mechanisms, outcomes, and fairness of matching markets.
We are motivated by the matching mechanism that assigns students to public schools in New York City. The unified school district—which encompasses all five boroughs—has since 2003 employed the theory of stable matching to perform this assignment, with students as one side of the market and schools as the other. Consisting of over 1.1 million students, the size and diversity of the market presents a massively interesting real-world object of study.
In the first chapter, we investigate a model where students are restricted in the length of preference lists that they may submit to the market operator. In particular, we study such random instances of the Serial Dictatorship mechanism where students choose $d$ schools uniformly at random from $n$ schools as their preference list, and each school has exactly one seat. Our main result is that if the students primarily care about being matched to any school of their list (as opposed to ending up unmatched), then all students in position $i\leq n$ will prefer markets with longer lists when $n$ is large enough, whereas students after some cutoff $c>n$ (that quickly approaches $n$ as the list length grows) prefer markets with shorter lists. This suggests that markets that are well-approximated by our hypothesis and where the demand of schools does not exceed supply, should be designed with preference lists as long as reasonable.
In the second chapter, we study the impact of systemic bias in school matching by investigating the admissions process to the eight elite public schools (called the Specialized High Schools) in New York City. These schools admit students solely based on their score on a standardized test, but we observe a clear distributional shift in the test scores of disadvantaged students (as defined by the city). To study this shift, we present a stylized model where all students have a true potential (representing their innate ability) sampled independently from the same distribution. While non-disadvantaged students always perform at their true potential, disadvantaged students appear at a perceived potential strictly below their innate ability due to some systemic bias. We investigate both theoretically and empirically the impact of such bias on the admissions process, then turn to studying interventions to counter it. These interventions are in the form of vouchers targeted at certain disadvantaged students, which we assume give that student the resources they need to perform at their true potential. We measure aggregate mistreatment under various metrics, first investigating optimal deterministic voucher distribution, and then turning to randomized voucher distribution. We additionally present extensive numerical experiments both on a real dataset from New York, as well as on simulated data. We then confirm that our results hold under various relaxations to our stylized model, including moderate levels of model misspecification. Our key takeaway is that resources should be targeted at slightly above average performers instead of the absolute top performers.
In the third chapter, we take the schools’ side. Currently the city allows schools to only specify their preferences using a strict preference list over students. While this leads to a simple algorithm, stable matching models may be extended to allow schools to communicate much more rich preference via choice functions. We discuss the impact of using general choice functions in the offline model of stable matching, establishing that general path-independent and quota-filling choice functions are too large a class to be used in this setting. We propose the class of Kuhn choice functions, that arise as maximum-weight matchings in an auxiliary bipartite graph, as a tractable yet rich subclass. We show that such choice functions are amenable to use in the offline model and possess many desirable properties. We further discuss the hierarchy of choice and approximability of various classes of choice functions. Theoretical proofs are complemented by computational results and a discussion on various practical aspects of using choice functions in stable matching.