Title: Essays on real-life allocation problems
Description: In recent years, economists have been called upon not only to understand markets, but also to design them. This dissertation studies the theoretical issues involved in the design of allocation mechanisms used for matching students to schools in choice plans. Concerns for fairness can often influence the choice of allocation mechanisms. Probabilistic allocation mechanisms, in particular, may be perceived as unfair ex-post despite treating agents symmetrically ex-ante. The first chapter examines fairness concerns in an assignment problem involving public resources where over 8,000 students per year are allocated a high school seat in New York City. The main result is that perceived fairness issues are irrelevant: a mechanism based on a single lottery, random serial dictatorship, produces a distribution of matchings which is equivalent to a mechanism based on multiple lotteries, top trading cycles with random priority. The next chapter, written jointly with Fuhito Kojima, analyzes the scope for manipulation in many-to-one matching markets (college admission problems) under the student-optimal stable mechanism when the number of participants is large and the length of the preference list is bounded. Under a mild independence assumption on the distribution of preferences for students, the fraction of colleges that have incentives to misrepresent their preferences approaches zero as the market becomes large. We show that truthful reporting is an approximate equilibrium under the student-optimal stable mechanism in large markets that are sufficiently thick, a condition that allows for certain types of heterogeneity in the distribution of student preferences.

Empirical and experimental evidence suggests different levels of sophistication among families in the Boston Public School (BPS) student assignment plan. In this chapter, written jointly with Tayfun Sönmez, we analyze the Nash equilibria of the preference revelation game induced by the Boston mechanism when there are two types of players. Sincere players are restricted to report their true preferences, while sophisticated players play a best response. We characterize the set of Nash equilibrium outcomes as the set of stable matchings of an economy with a modified priority structure, where sincere students lose their priority to sophisticated students. While there are multiple equilibrium outcomes, a sincere student receives the same assignment in all equilibria. Moreover any sophisticated student weakly prefers her assignment under the Pareto-dominant Nash equilibrium of the Boston mechanism to her assignment under the student-optimal stable mechanism, which was recently adopted by BPS for use starting with 2005-2006 school year.

The design of the New York City (NYC) High School match involved tradeoffs between incentives and efficiency, because some schools are strategic players that rank students in order of preference, while others order students based on large priority classes. Therefore it is desirable for a mechanism to produce stable matchings (to avoid giving the strategic players incentives to circumvent the match), but is also necessary to use tie-breaking for schools whose capacity is sufficient to accommodate some but not all students of a given priority class. In the last chapter, written jointly with Atila Abdulkadiroglu and Alvin Roth, we analyze a model that encompasses one-sided and two-sided matching models. We first observe that breaking indifferences the same way at every school is sufficient to produce the set of student optimal matchings. Our main theoretical result is that a student-proposing deferred acceptance mechanism that breaks indifferences the same way at every school is not dominated by any other mechanism that is strategy-proof for students. Finally, using data from the recent redesign of the NYC High School match, we document that the extent of potential efficiency loss is substantial, about 10% of assigned students could have improved their assignment in a (non strategy-proof) student optimal mechanism, if the same student preferences would have been revealed.