Essays on matching and preference aggregation

This thesis is a collection of two papers on matching and one paper on preference aggregation. The first two chapters are concerned with the problem of assigning students to schools. For this problem, the student proposing version of Gale and Shapley’s deferred acceptance mechanism and a mechanism known as Boston mechanism are widely used in many school districts in U.S and around the world. The Boston mechanism is prone to manipulation. The deferred acceptance mechanism is not manipulable ; however, it is not Pareto efficient. The first two chapters of this thesis deal with the problem of either improving the welfare of students over deferred acceptance or reducing the degree of manipulation under Boston. In Chapter 1, we study a decentralized matching game inspired from the early decision system in the U.S : It is a college admission system in which students can receive admission decisions before the general application period. But there are two requirements. First, each student is required to apply to one college. Second, each student commits to attend the college upon admitted. We propose a game in which students sequentially make one application each and colleges ultimately make admission decisions to which students commit to accept. We show that up to a relevant refinement of subgame perfect equilibrium notion, the expected outcomes of this mechanism are more efficient than that of deferred acceptance mechanism. In Chapter 2, we study a centralized university admission mechanism that the French government has implemented in 2009 to better match students to viii university schools. To deal with oversubscribed schools, the system defined priorities that partition students into very coarse equivalence classes but relies on student reported preferences to further resolve ties.We show that applying student-proposing deferred acceptance mechanism after breaking ties is a reasonable procedure. We refer to this mechanism as French mechanism. We show that this mechanism is less manipulable than the Boston mechanism and more efficient than the standard deferred acceptance in which ties are broken randomly. In Chapter 3, we introduce a class of rules called augmented serial rules for combining individual preferences into a collective ordering. The aggregation problem appears when faculty members want to devise a strategy for offering an open position without knowing whether any given applicant will ultimately accept an offer. It is a commonplace to order the applicants and make offers accordingly. Each of these augmented serial rules is parametrized by a list of agents (with possible repetition) and a committee voting rule. For a given preference profile, the collective ordering is determined as follows : The first agent’s most preferred alternative becomes the top-ranked alternative in the collective ordering, the second agent’s most preferred alternative (among those remaining) becomes the second-ranked alternative and so on until two alternatives remain, which are ranked by the committee voting rule. The main result establishes that these rules are succinctly characterized by neutrality and strategy-proofness under the lexicographic extension. Additional results show that these rules are strategy-proof under a variety of other reasonable preference extensions.

Keyphrases: Matching, Deferred acceptance, Boston mechanism, French mechanism, Preference aggregation, Strategy-proofness, Augmented serial rule