Implementation of the Deferred Acceptance Algorithm in School Choice Application

Economists have extensively been studying and designing well-functioning algorithmic allocation (or matching) mechanisms where rank ordered lists are used in place of price (or willingness to pay). For example, public schools are “free” for students to attend, so many of the public school systems (Barcelona, Beijing, Boston, Denver, Ghana, New York City, and etc.) around the world adopted these mechanisms to allocate students to their public schools. In both theoretical and empirical literature, efforts to evaluate various implementations have been growing. This paper contributes to this literature and study the implementation of one of the most popular matching algorithm–the Deferred Acceptance algorithm.The first chapter investigates the New York City high school matching market. As requested by the New York City Department of Education, Abdulkadiroglu et al. (2005) havechosen the Deferred Acceptance (DA, henceforth) algorithm to be the allocation mechanism for its promising theoretical properties. The allocation, when all the assumptions are satisfied, is stable, which means that there exist no student-school pair (or any coalition of students and schools) that can exchange their match outcome and end up with better allocation. Adding to this positive result, DA produces an allocation with optimal student welfare among all otherstable allocations. Moreover, the mechanism induces strategy-proofness, where it is weakly dominant strategy for students to report their true preference when submitting their rank order list. Unfortunately, many of the assumptions required for such properties are not met in practice. Departures from the theoretic assumptions are: (1) schools do not strictly rank all of its applicants2, (2) students do not rank all of their choices in the main round3, and(3) DA is run twice4. Due to these violations, theoretical results mentioned above are no longer guaranteed, creating both instability and incentive to make strategic choices in the first round. I investigate the market data (including student choices and matching result) to build accurate picture. In particular, I find that there is a systematic relationship between student rank order choices (specifically, rank order list lengths) and matching outcomes (i.e. acceptance probabilities).The second and the third chapter modifies the Deferred Acceptance algorithm to accommodate some of the market features introduced in the first chapter. In the second chapter, I develop a version of the Deferred Acceptance algorithm to allow schools to address multidimensionaldiversity concern (such as affirmative action based on race, test scores, and etc.) while respecting their preference rankings. I show that, in general, diversity considerationsmakes students non-substitutes, which makes the matching non-stable. If a school considers the diversity goals lexicographically, then I prove that such choice rule yields the best student-optimal matching and preserves strategy proofness.In the third chapter, I develop another version of the Deferred Acceptance algorithm to combine two rounds. Inexplicably, most (including the New York City high school matchingmarket) of such implementations feature an additional matching round (often called supplementary or scramble round) where students can re-participate in another matching round for leftover seats. This chapter first shows, using a simple example, that the current two-roundimplementation does not preserve any of the desirable characterizations of Deferred Acceptancealgorithm. Then, the paper quantifies that 17-44% of the allocations have incentive to deviate (more precisely, justified envy) under the current two-round implementation in theNYC high school matching market. Finally, the paper designs a two (or multi)-round DA algorithm which preserves stability, strategy-proofness, and student optimality across two rounds.In the fourth chapter, I recover student valuations for each school when it is assumed that parents game the system. To handle rank order list data with extremely large choice set, a computationally efficient, nonparametric estimation strategy is used for acceptance probabilities and valuations. The model produce closed form representation of student preferences where low acceptance probabilities increases valuations. Given that students with low socioeconomicstatus, on average, have lower acceptance probabilities to their top choice(s), those students have higher valuations for their top choice(s) compared the students with highsocioeconomic status.