Stable and Strategy-proof Matching and Value Representation of Choice Functions

We develop a college admissions mechanism in which the number of seats allocated to each major at a college can adjust in response to students’ demand and each major may have its own priority order over students. The mechanism we develop is a modified deferred acceptance (DA) mechanism and we show that the mechanism always results in the student-optimal matching among those that satisfy feasibility, individual rationality, non-wastefulness, and no justified envy. Besides, the mechanism is group strategy-proof for students, respects unambiguous improvement in student standing in the priority orders, and is unanimously preferred by students to a standard deferred acceptance mechanism where each major has a fixed number of seats. Different from matching-with-contract models, our approach does not take choice functions of colleges as primitives. Instead, we develop the notion of oversize functions, with which there is no need to specify choices of colleges that are irrelevant to the modified DA mechanism.