Journal Article

Stable Matching with Proportionality Constraints

Nguyen, Thành, Vohra, Rakesh

2019

Overview

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. As an 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 replaces the proportions by numbers related to the capacity of school, but this assumes each school is operating at full capacity, which is often not the case. 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. The problem of finding stable matches that meet distributional concerns is usually formulated by imposing side constraints whose “right-hand sides” are absolute numbers specified before the preferences or number of agents on the “proposing” side are known. In many cases, it is more natural to express the relevant constraints as proportions. We treat such constraints as soft but provide ex post guarantees on how well the constraints are satisfied while preserving stability. Our technique requires an extension of Scarf’s lemma, which is of independent interest.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Crosscutting Areas / diversity / Games, Information, and Networks / games/group decisions: cooperative / Matching theory / Methods / Operations research / Optimization / Problem solving / Proportionality (Mathematics) / Scarf’s lemma / Simulation / stable matching / Tests, problems and exercises / Theory of constraints / Theory of distributions