Stable Matching with Proportionality Constraints

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 concern 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 schools' priorities over students but gives no ex-post 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 be at capacity, which need not be true. In this talk, 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 Thành Nguyen.