Stable Matching with Proportionality Constraints

More on Rakesh Vohra

Abstract: School choice programs seek to give students the option to choose their school but also close an opportunity gap. To be fair in the assignment of students it is usually argued that the assignment of students to schools should be stable. This second  concerns is usually expressed in terms of proportions. For example, in 1989, the city of White Plains, New York required each school to have the same proportions of Blacks, Hispanics, and ``others", a term that includes Whites and Asians. Satisfying both these concerns at the same time is difficult. Prior work modifies school’s priorities over students but gives no ex-post on guarantee on the final distribution of students. Or, it replaces the proportions by numbers related to the capacity of school, but this assumes each school will at capacity which need not be true. In this paper we treat such proportionality constraints as soft but provide ex-post guarantees on how well the constraints are satisfied while preserving stability. Based on joint work with Thanh Ngyuen.