Expandable Preference Lists : A Mechanism for College Admissions in a Large Market

Although Gale-Shapley’s student optimal stable matching mechanism (SOSM) has desirable properties, it is infeasible for college admissions in a large market because it is impossible to ask every student to provide a complete ranking of thousands of colleges. Regarding college admissions problems in large-scale contexts, this paper introduces a new matching mechanism that allows students to provide incomplete but expandable preference lists (EPLs). In contrast to the standard one-shot (direct-revelation) or multirun (sequential-like) designs, the EPL mechanism matches students and colleges in a continuous period. Before the matching period begins, every college provides an algorithm to give a complete strict preference list over all students to the clearinghouse, whereas every student only needs to provide an incomplete initial preference list. During the matching period, (1) every student can expand her own preference list but cannot withdraw or change the order of colleges in her already submitted preference list; (2) the clearinghouse produces and updates the virtual (not final) matching results according to SOSM; and (3) a student can confirm (finalize) her own “best match” without the need to wait until the matching period ends. Theoretical analysis suggests that the EPL mechanism not only inherits much of the desirable stability and incentive properties of the SOSM but is also partially obviously strategy-proof. This paper proposes that by allowing interaction among participants, we can design matching mechanisms with more desirable properties